/*********************************************************
Copyright: (C) 2008-2010 by Steven Schveighoffer.
All rights reserved

License: Boost Software License version 1.0

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer, must
be included in all copies of the Software, in whole or in part, and all
derivative works of the Software, unless such copies or derivative works are
solely in the form of machine-executable object code generated by a source
language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

**********************************************************/
module Engine.Allocator;

version(DDoc)
{
}
else
{
    private import core.memory;
    private import std.c..string;
}

/**
* Allocate a chunk of elements at once, then use the chunk to return
* elements.  This makes allocating individual elements more efficient
* because the GC isn't used for allocating every element, only every
* chunk of elements.
*
* The only requirement is that the size of V is >= size of a pointer.
* This is because the data V contains is used as a pointer when freeing
* the element.
*
* If an entire chunk of elements is freed, that chunk is then returned to
* the GC.
*/
struct ChunkAllocator(V, uint elemsPerChunk)
{
    /**
	* Free is needed to recycle nodes for another allocation.
	*/
    enum bool freeNeeded = true;
    static if(V.sizeof < (void*).sizeof)
    {
        static assert(false, "Error, allocator for " ~ V.stringof ~ " failed to instantiate");
    }

    /**
	* This is the form used to link recyclable elements together.
	*/
    struct element
    {
        element *next;
    }

    /**
	* A chunk of elements
	*/
    struct chunk
    {
        /**
		* The next chunk in the chain
		*/
        chunk *next;

        /**
		* The previous chunk in the chain.  Required for O(1) removal
		* from the chain.
		*/
        chunk *prev;

        /**
		* The linked list of free elements in the chunk.  This list is
		* amended each time an element in this chunk is freed.
		*/
        element *freeList;

        /**
		* The number of free elements in the freeList.  Used to determine
		* whether this chunk can be given back to the GC
		*/
        uint numFree;

        /**
		* The elements in the chunk.
		*/
        V[elemsPerChunk] elems;

        /**
		* Allocate a V* from the free list.
		*/
        V *allocateFromFree()
        {
            element *x = freeList;
            freeList = x.next;
            //
            // initialize the element.  We do it this way to avoid triggering
            // any copy hooks such as postblits
            //
            auto init = cast(ubyte[])typeid(V).init();
            if(init.ptr is null) // null ptr means initialize to 0
                x.next = null; // we already know the other bytes are 0
            else
            {
                auto buf = (cast(ubyte *)x)[0..(V).sizeof];
                buf[] = init[];
            }
            numFree--;
            return cast(V*)x;
        }

        /**
		* deallocate a V*, send it to the free list
		*
		* returns true if this chunk no longer has any used elements.
		*/
        bool deallocate(V *v)
        {
            //
            // clear the element so the GC does not interpret the element
            // as pointing to anything else.
            //
            memset(v, 0, (V).sizeof);
            element *x = cast(element *)v;
            x.next = freeList;
            freeList = x;
            return (++numFree == elemsPerChunk);
        }
    }

    /**
	* The chain of used chunks.  Used chunks have had all their elements
	* allocated at least once.
	*/
    chunk *used;

    /**
	* The fresh chunk.  This is only used if no elements are available in
	* the used chain.
	*/
    chunk *fresh;

    /**
	* The next element in the fresh chunk.  Because we don't worry about
	* the free list in the fresh chunk, we need to keep track of the next
	* fresh element to use.
	*/
    uint nextFresh;

    /**
	* Allocate a V*
	*/
    V* allocate()
    {
        if(used !is null && used.numFree > 0)
        {
            //
            // allocate one element of the used list
            //
            V* result = used.allocateFromFree();
            if(used.numFree == 0)
                //
                // move used to the end of the list
                //
                used = used.next;
            return result;
        }

        //
        // no used elements are available, allocate out of the fresh
        // elements
        //
        if(fresh is null)
        {
            fresh = new chunk;
            nextFresh = 0;
        }

        V* result = &fresh.elems[nextFresh];
        if(++nextFresh == elemsPerChunk)
        {
            if(used is null)
            {
                used = fresh;
                fresh.next = fresh;
                fresh.prev = fresh;
            }
            else
            {
                //
                // insert fresh into the used chain
                //
                fresh.prev = used.prev;
                fresh.next = used;
                fresh.prev.next = fresh;
                fresh.next.prev = fresh;
                if(fresh.numFree != 0)
                {
                    //
                    // can recycle elements from fresh
                    //
                    used = fresh;
                }
            }
            fresh = null;
        }
        return result;
    }

    /**
	* free a V*
	*/
    void free(V* v)
    {
        //
        // need to figure out which chunk v is in
        //
        chunk *cur = cast(chunk *)GC.addrOf(v);

        if(cur !is fresh && cur.numFree == 0)
        {
            //
            // move cur to the front of the used list, it has free nodes
            // to be used.
            //
            if(cur !is used)
            {
                if(used !is null)
                {
                    //
                    // first, unlink cur from its current location
                    //
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;

                    //
                    // now, insert cur before used.
                    //
                    cur.prev = used.prev;
                    cur.next = used;
                    used.prev = cur;
                    cur.prev.next = cur;
                }
                else
                {
                    cur.next = cur.prev = cur;
                }
                used = cur;
            }
        }

        if(cur.deallocate(v))
        {
            //
            // cur no longer has any elements in use, it can be deleted.
            //
            if(cur is fresh || cur.next is cur)
            {
                //
                // cur is either fresh or is the only element in the
                // used chain
                //
            }
            else
            {
                //
                // remove cur from list
                //
                if(used is cur)
                {
                    //
                    // update used pointer
                    //
                    used = used.next;
                }
                cur.next.prev = cur.prev;
                cur.prev.next = cur.next;
                delete cur;
            }
        }
    }

    /**
	* Deallocate all chunks used by this allocator.
	*/
    void freeAll()
    {
        if(fresh is null)
        {
            fresh = used;
        }
        used = null;

        //
        // keep fresh around
        //
        if(fresh !is null)
        {
            nextFresh = 0;
            // need to re-initialize the data elements
            auto chunkinit = cast(ubyte[])typeid(chunk).init();
            if(chunkinit.ptr is null)
                // all the data is zero, just write 0s to the chunk
                memset(fresh, 0, chunk.sizeof);
            else
            {
                // copy the entire init array
                auto buf = (cast(ubyte *)fresh)[0..chunk.sizeof];
                buf[] = chunkinit[];
            }
        }
    }
}