module tango.util.container.mgmt.ChunkAllocator;

public import tango.util.container.mgmt.Allocator;

/*******************************************************************************

        Can save approximately 30% memory for small elements (tested with
        integer elements and a chunk size of 8192), and is at least twice
        as fast at adding elements when compared to the default allocator
        (nine or ten times faster when reusing prior allocations)

*******************************************************************************/

class ChunkAllocator(T) : Allocator!(T)
{
        private T[]     list;
        private T[][]   lists;
        private int     index;
        private int     chunks;
        private int     freelists;

        /***********************************************************************

                set the chunk size

        ***********************************************************************/

        this (int chunks = 1024)
        {
                this.chunks = chunks;
        }

        /***********************************************************************

                allocate a fixed-size (T) chunk of memory

        ***********************************************************************/

        final override void[] allocate ()
        {
                if (index >= list.length)
                    newlist;

                return (&list[index++]) [0..1];
        }

        /***********************************************************************

                allocate an arbitrary chunk of memory

        ***********************************************************************/

        final override void[] allocate (uint size)
        {
                    return new void [size];
        }

        /***********************************************************************

                Invoked when clear/reset is called on the host. Parameter
                all indicates whether all memory usage should be collected
                or just the fixed-size blocks. We can safely ingore it

        ***********************************************************************/

        final override void collect (bool all)
        {
                freelists = 0;
                newlist;
        }

        /***********************************************************************

                Invoked during a client .dup to clone an attached allocator

        ***********************************************************************/

        final override ChunkAllocator factory ()
        {
                return new ChunkAllocator (chunks);
        }

        /***********************************************************************

                list manager

        ***********************************************************************/

        private void newlist ()
        {
                index = 0;
                if (freelists >= lists.length)
                   {
                   lists.length = lists.length + 1;
                   lists[$-1] = new T[chunks];
                   }
                list = lists[freelists++];
        }
}