#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <new>

/********************************************
 * IMPORTANT: You do not have to understand *
 * this to pass this course. This example   *
 * uses classes and linked lists, which     *
 * will be taught later in the course.      *
 ********************************************/

/********************************************************
 * First-fit dynamic memory allocation
 *
 * We begin with one large block of available memory.
 *
 * When memory is requested, we search a linked list
 * of free blocks and select the first sufficiently
 * large block.
 *
 * If the selected block is large enough, we split it
 * into an allocated block and a smaller free block.
 *
 * Otherwise, we allocate the entire block.
 *
 * When memory is freed, its block is inserted at the
 * beginning of the free list.
 *
 * This is a teaching example, not a replacement for
 * malloc, free, new, or delete.
 *
 * In particular, adjacent free blocks are not merged.
 ********************************************************/

// Class declaration

class First_fit {
  public:
    explicit First_fit( std::size_t const blocks_available );
    ~First_fit();

    // The memory pool must not be copied.
    First_fit( First_fit const & ) = delete;
    First_fit &operator=( First_fit const & ) = delete;

    void *alloc( std::size_t const memory_request );
    void free( void *p_freed_memory );
    void map() const;

  private:
    // Every block begins with a header containing
    // its total size, including the header itself.
    //
    // The next pointer is used only while the
    // block is free.

    struct alignas(std::max_align_t) Memory_block {
        std::size_t block_size_;
        Memory_block *p_next_block_;
    };

    static constexpr std::size_t ALIGNMENT{
        alignof(std::max_align_t)
    };

    std::size_t bytes_available_;
    Memory_block *p_first_block_;
    void *p_memory_pool_;

    static std::size_t required_size(
        std::size_t const memory_request
    );
};

// Function declaration
int main();

// Function definitions

int main() {
    // Create a pool of 20 blocks of 64 bytes:
    // 1280 bytes in total.

    First_fit memory{ 20 };

    std::size_t const N{ 5 };
    void *a_alloc[N]{};

    memory.map();
    std::cout << std::endl;

    unsigned int successful_requests_made{ 0 };

    // Randomly choose one of the five pointers.
    //
    // If it is nullptr, request some memory.
    // Otherwise, free its allocated memory.
    //
    // Stop when a request cannot be satisfied.

    while ( true ) {
        std::size_t const k{
            static_cast<std::size_t>( std::rand() )%N
        };

        if ( a_alloc[k] == nullptr ) {
            std::size_t const request{
                static_cast<std::size_t>(
                    std::rand()%100 + 1
                )
            };

            std::cout << "Memory request: "
                      << request << " bytes"
                      << std::endl;

            a_alloc[k] = memory.alloc( request );

            std::cout << "  Memory allocated at "
                      << a_alloc[k] << std::endl;

            if ( a_alloc[k] == nullptr ) {
                std::cout
                    << "Memory not allocated; ending program."
                    << std::endl;

                std::cout
                    << "Successful requests: "
                    << successful_requests_made
                    << std::endl;

                break;
            }

            ++successful_requests_made;
        } else {
            std::cout << "Memory freed at "
                      << a_alloc[k] << std::endl;

            memory.free( a_alloc[k] );
            a_alloc[k] = nullptr;
        }

        memory.map();
        std::cout << std::endl;
    }

    return 0;
}

// Constructor:
//
// Allocate one contiguous pool of memory and
// create one free block covering the entire pool.

First_fit::First_fit(
    std::size_t const blocks_available
):
    bytes_available_{ 0 },
    p_first_block_{ nullptr },
    p_memory_pool_{ nullptr }
{
    assert( blocks_available > 0 );

    if (
        blocks_available
        > std::numeric_limits<std::size_t>::max()/64
    ) {
        throw std::bad_alloc{};
    }

    std::size_t const pool_size{
        64*blocks_available
    };

    if ( pool_size < sizeof(Memory_block) ) {
        throw std::bad_alloc{};
    }

    p_memory_pool_ = std::malloc( pool_size );

    if ( p_memory_pool_ == nullptr ) {
        throw std::bad_alloc{};
    }

    bytes_available_ = pool_size;

    p_first_block_ =
        static_cast<Memory_block *>( p_memory_pool_ );

    p_first_block_->block_size_ = pool_size;
    p_first_block_->p_next_block_ = nullptr;
}

// Destructor:
//
// Release the original memory pool, not one of
// the individual blocks managed by this class.

First_fit::~First_fit() {
    std::free( p_memory_pool_ );
}

// Calculate the total space required for a
// request, including the block header.
//
// Round up to a multiple of ALIGNMENT so that
// every block begins at a suitably aligned
// address.
//
// Return zero if the calculation would overflow.

std::size_t First_fit::required_size(
    std::size_t const memory_request
) {
    std::size_t const requested_bytes{
        (memory_request == 0) ? 1 : memory_request
    };

    std::size_t const overhead{
        sizeof(Memory_block)
    };

    std::size_t const maximum{
        std::numeric_limits<std::size_t>::max()
    };

    if ( requested_bytes > maximum - overhead ) {
        return 0;
    }

    std::size_t const total{
        requested_bytes + overhead
    };

    std::size_t const remainder{
        total%ALIGNMENT
    };

    if ( remainder == 0 ) {
        return total;
    }

    std::size_t const padding{
        ALIGNMENT - remainder
    };

    if ( total > maximum - padding ) {
        return 0;
    }

    return total + padding;
}

// Allocate memory using first fit.
//
// The free list is searched from beginning
// to end. The first sufficiently large block
// is selected.
//
// If splitting would leave enough space for
// another usable block, split it. Otherwise,
// allocate the entire selected block.

void *First_fit::alloc(
    std::size_t const memory_request
) {
    std::size_t const needed{
        required_size( memory_request )
    };

    if ( needed == 0 ) {
        return nullptr;
    }

    Memory_block *p_previous{ nullptr };
    Memory_block *p_current{ p_first_block_ };

    while ( p_current != nullptr ) {
        if ( p_current->block_size_ >= needed ) {
            break;
        }

        p_previous = p_current;
        p_current = p_current->p_next_block_;
    }

    if ( p_current == nullptr ) {
        return nullptr;
    }

    std::size_t const remaining{
        p_current->block_size_ - needed
    };

    // The remainder must have enough space for
    // its own header and at least one aligned
    // unit of usable memory.

    if (
        remaining >= sizeof(Memory_block) + ALIGNMENT
    ) {
        // Split the selected block.

        auto *p_remainder{
            reinterpret_cast<Memory_block *>(
                reinterpret_cast<char *>( p_current )
                + needed
            )
        };

        p_remainder->block_size_ = remaining;
        p_remainder->p_next_block_ =
            p_current->p_next_block_;

        if ( p_previous == nullptr ) {
            p_first_block_ = p_remainder;
        } else {
            p_previous->p_next_block_ = p_remainder;
        }

        p_current->block_size_ = needed;
        bytes_available_ -= needed;
    } else {
        // Allocate the entire block.

        if ( p_previous == nullptr ) {
            p_first_block_ =
                p_current->p_next_block_;
        } else {
            p_previous->p_next_block_ =
                p_current->p_next_block_;
        }

        bytes_available_ -= p_current->block_size_;
    }

    // The caller receives the address immediately
    // after the header, not the header itself.

    return static_cast<void *>( p_current + 1 );
}

// Free a previously allocated block.
//
// Preconditions:
//   - The pointer was returned by this allocator.
//   - The block has not already been freed.
//   - The allocator still owns the memory.
//
// A null pointer is permitted and does nothing.

void First_fit::free( void *p_freed_memory ) {
    if ( p_freed_memory == nullptr ) {
        return;
    }

    auto *p_block{
        static_cast<Memory_block *>( p_freed_memory ) - 1
    };

    bytes_available_ += p_block->block_size_;

    p_block->p_next_block_ = p_first_block_;
    p_first_block_ = p_block;
}

// Display the linked list of free blocks.

void First_fit::map() const {
    std::cout << "Available memory blocks:"
              << std::endl;

    std::cout << "* p_first_block_" << std::endl;

    for (
        Memory_block const *p_block{ p_first_block_ };
        p_block != nullptr;
        p_block = p_block->p_next_block_
    ) {
        if ( p_block->p_next_block_ == nullptr ) {
            std::cout << "`";
        } else {
            std::cout << "|";
        }

        std::cout << "---> " << p_block
                  << ": " << p_block->block_size_
                  << " bytes --> "
                  << p_block->p_next_block_
                  << std::endl;
    }

    std::cout << "Total free memory: "
              << bytes_available_
              << " bytes" << std::endl;
}