//StaticBuffer.h

//This file provides a class which allocates memory from a preallocated heap, in as quick a manner as possible.
//Essentially, it provides a second stack for the program, one which never gets deallocated.
//Usage: StaticMemoryAllocator::allocate(size_t bytes) returns a safely aligned void*

#ifndef PlaneGC_StaticBuffer_h
#define PlaneGC_StaticBuffer_h

#include "Allocators.h"

namespace PlaneGC {

class StaticBuffer {
public:
    static const size_t blocksize= 0x10000; //How many bytes it will allocate at a time. It is also the max bytes it can allocate per request

    template<typename T> class stl_wrapper {
    public:
        typedef T value_type;
        typedef size_t size_type;
        typedef ptrdiff_t difference_type;
        typedef T* pointer;
        typedef const T* const_pointer;
        typedef T& reference;
        typedef const T& const_reference;

        stl_wrapper() { };
        stl_wrapper(const stl_wrapper&) { };
        template <class U> stl_wrapper(const stl_wrapper<U>&) { };

        size_t max_size() const { return max((size_t)1, blocksize / sizeof(T)); };

        template<class U> struct rebind { typedef stl_wrapper<U> other; };
        pointer address(reference r) { return &r; }
        const_pointer address(const_reference r) { return &r; }

        pointer allocate(size_type n, const void* hint= 0) { return (T*)StaticBuffer::allocate(n*sizeof(T)); };
        void deallocate(pointer p, size_type n) { StaticBuffer::deallocate(p, n*sizeof(T)); };

        void construct(pointer p, const T& val) { new(p) T(val); };
        void destroy(pointer p) { p->~T(); };
    };

private:
    class Block {
    private:
        Block(Block* previous_, uint bytes) {
            previous= 0;
            next= 0;
            InsertAfter(previous_);
            remaining= bytes;
            head= (byte*)this + GetPaddedTotal(sizeof(*this));
        };
        ~Block() { RemoveLinks(); };
    public:
        static Block* CreateBlock(size_t minimum= StaticBuffer::blocksize) {
            size_t size= max(minimum, StaticBuffer::blocksize);
            return new(new byte[GetPaddedTotal(sizeof(Block)) + size]) Block(StaticBuffer::head(), size);
        };
        static void DestroyBlock(Block* block) {
            if(!block) return;
            block->~Block();
            delete[] (byte*) block;
        };;
    private:
        void InsertAfter(Block* previous_) {
            if(previous_ == this) return;
            RemoveLinks();
            if(previous= previous_) {
                if(next= previous->next) next->previous= this;
                previous->next= this;
            }
        };
        void RemoveLinks() {
            if(StaticBuffer::head() == this) StaticBuffer::head()= next ? next : previous;
            if(StaticBuffer::root() == this) StaticBuffer::root()= previous ? previous : next;
            if(previous) previous->next= next;
            if(next) next->previous= previous;
        };
        void SortIntoList() {
            if(!previous) return;
            //Moving this block to a position in the linked list where it will be sorted by bytesremaining
            Block* current= previous;
            while((current->remaining > remaining) && (current->previous)) {
                current= current->previous;
            }
            InsertAfter(current);
        };

    public:
        void* allocate(size_t bytes) {
            assert(this == StaticBuffer::head());
            if(remaining >= bytes) {
                void* result= head;
                head += bytes;
                remaining -= bytes;
                return result;
            }else{
                Block* current= previous;
                while(current->previous && (current->remaining >= bytes)) {
                    current= current->previous;
                }
                if(current->next && (current->next->remaining >= bytes)) {
                    //found the block with the least free space which can take this request
                    current= current->next;
                    current->InsertAfter(this);
                }else{
                    //no existing block had enough bytes
                    current= CreateBlock(bytes);
                }
                StaticBuffer::head()= current;
                SortIntoList();
                return next->allocate(bytes);
            }
        };

    private:
        Block* previous;
        Block* next;
        byte* head;
        size_t remaining;
    };

public:
    StaticBuffer() {
        inc();
    };

    ~StaticBuffer() {
        dec();
    };

    static void inc() { ++reference_count(); };
    static void dec() {
        if(!(--reference_count())) {
            lock();
            while(root()) Block::DestroyBlock(root());
            unlock();
        }
    };

    static void* allocate(size_t bytes) {
        lock();
        void* v= head()->allocate(bytes);
        if(v) {
            ++allocated_count();
            allocated_bytes() += bytes;
        }
        unlock();

        return v;
    };

    static void deallocate(void* memory, size_t bytes) {
        deallocated_count() += bytes;
    };

    static size_t& reference_count() { static size_t v= 0; return v; };
    static size_t& allocated_count() { static size_t v= 0; return v; };
    static size_t& deallocated_count() { static size_t v= 0; return v; };
    static size_t& allocated_bytes() { static size_t v= 0; return v; };

private:
    static Block*& root() { static Block* v= Block::CreateBlock(); return v; };
    static Block*& head() { static Block* v= root(); return v; };

    #ifdef PlaneThread_h
    static PlaneThread::SpinLock& GetLock() { static PlaneThread::SpinLock v; return v; };
    static void lock() { GetLock().lock(); };
    static void unlock() { GetLock().release(); };
    #else
    static void lock() { };
    static void unlock() { };
    #endif

    friend class Block;
};

const StaticBuffer StaticBuffer_handle;

}; //end namespace

#endif //#ifndef PlaneGC_StaticBuffer_h