chunk_heap.h

/*****************************************************/
/* lean Memory                  (c) Tobias Zirr 2011 */
/*****************************************************/

#ifndef LEAN_MEMORY_CHUNK_HEAP
#define LEAN_MEMORY_CHUNK_HEAP

#include "../lean.h"
#include "../tags/noncopyable.h"
#include "alignment.h"
#include "default_heap.h"

namespace lean
{
namespace memory
{

template <size_t Size>
struct optional_mem_block
{
    char memory[Size];

    LEAN_INLINE char* get() { return memory; }
    LEAN_INLINE const char* get() const { return memory; }

    LEAN_INLINE operator char*() { return memory; }
    LEAN_INLINE operator const char*() const { return memory; }
};
template <>
struct optional_mem_block<0>
{
    LEAN_INLINE char* get() { return nullptr; }
    LEAN_INLINE const char* get() const { return nullptr; }

    LEAN_INLINE operator char*() { return nullptr; }
    LEAN_INLINE operator const char*() const { return nullptr; }
};

template <size_t ChunkSize, class Heap = default_heap, size_t StaticChunkSize = ChunkSize, size_t DefaultAlignment = sizeof(void*)>
class chunk_heap : public lean::noncopyable
{
public:
    typedef Heap heap_type;
    typedef typename heap_type::size_type size_type;
    static const size_type chunk_size = ChunkSize;
    static const size_type default_alignment = DefaultAlignment;

private:
    // Optional first static chunk
    optional_mem_block<StaticChunkSize> m_firstChunk;
    
    // Current chunk
    char *m_chunk;
    char *m_chunkOffset;
    char *m_chunkEnd;

    // Next chunk size
    size_type m_nextChunkSize;

    struct chunk_header
    {
        char *prev_chunk;

        chunk_header(char *prev_chunk)
            : prev_chunk(prev_chunk) { }
    };
    // Chunk alignment
    static const size_t chunk_alignment = alignof(chunk_header);

    LEAN_INLINE static chunk_header* to_chunk_header(char *chunk)
    {
        return reinterpret_cast<chunk_header*>(chunk) - 1;
    }

    template <size_t Alignment>
    char* allocate_aligned(size_type size)
    {
        // Get next free memory location
        char *aligned = align<Alignment>(m_chunkOffset);

        // Allocate new chunk, if old chunk too small
        if (size + static_cast<size_type>(aligned - m_chunkOffset) > static_cast<size_type>(m_chunkEnd - m_chunkOffset))
        {
            // Make sure new chunk is large enough for requested amount of memory + alignment
            size_type alignedSize = size + (Alignment - 1);

            size_type nextChunkSize = m_nextChunkSize;
            if (nextChunkSize < alignedSize)
                nextChunkSize = alignedSize;

            nextChunkSize += sizeof(chunk_header);

            char *nextChunkBase = static_cast<char*>( Heap::allocate<chunk_alignment>(nextChunkSize) );
            new( static_cast<void*>(nextChunkBase) ) chunk_header(m_chunk);

            m_chunk = nextChunkBase + sizeof(chunk_header);
            m_chunkOffset = m_chunk;
            m_chunkEnd = nextChunkBase + nextChunkSize;

            // Reset chunk size
            if (chunk_size != 0)
                m_nextChunkSize = chunk_size;

            // Get next free memory location
            aligned = align<Alignment>(m_chunkOffset);
        }

        // Memory now occupied
        m_chunkOffset = aligned + size;

        return aligned;
    }

public:
    LEAN_INLINE chunk_heap(size_type chunkSize = ChunkSize)
        : m_chunk(m_firstChunk),
        m_chunkOffset(m_firstChunk),
        m_chunkEnd(m_firstChunk.get() + StaticChunkSize),
        m_nextChunkSize(chunkSize) { }
    LEAN_INLINE ~chunk_heap()
    {
        clear();
    }

    LEAN_INLINE void nextChunkSize(size_type nextSize) { m_nextChunkSize = nextSize; }
    LEAN_INLINE size_type nextChunkSize() const { return m_nextChunkSize; }

    LEAN_INLINE size_type capacity() const { return m_chunkEnd - m_chunkOffset; }

    LEAN_INLINE void reserve(size_type newCapacity, size_type minChunkSize = chunk_size)
    {
        size_type currentCapacity = capacity();

        if (newCapacity > currentCapacity) 
            nextChunkSize( max(newCapacity - currentCapacity, minChunkSize) );
    }

    void clear()
    {
        // Free as many chunks as possible
        while (m_chunk != m_firstChunk)
        {
            chunk_header *freeChunkBase = to_chunk_header(m_chunk);

            // Immediately store previous chunk in case clear is re-called after exception
            m_chunk = freeChunkBase->prev_chunk;
            m_chunkOffset = m_chunk;
            m_chunkEnd = m_chunk;

            Heap::free<chunk_alignment>(freeChunkBase);
        }

        // Re-initialize with first chunk
        m_chunkEnd = m_chunk + StaticChunkSize;
    }

    void clearButFirst()
    {
        if (m_chunk != m_firstChunk && to_chunk_header(m_chunk)->prev_chunk == m_firstChunk)
            // Re-initialize first dynamic chunk
            m_chunkOffset = m_chunk;
        else
            clear();
    }

    bool currentStatic()
    {
        return (m_chunk == m_firstChunk);
    }
    char* currentOffset()
    {
        return m_chunkOffset;
    }
    char* clearCurrent()
    {
        // Re-initialize with current chunk
        m_chunkOffset = m_chunk;
        return m_chunk;
    }
    char* clearFreeNext()
    {
        if (m_chunk != m_firstChunk)
        {
            chunk_header *freeChunkBase = to_chunk_header(m_chunk);

            // Immediately store previous chunk (exception-safe)
            m_chunk = freeChunkBase->prev_chunk;
            m_chunkOffset = m_chunk;
            m_chunkEnd = (m_chunk == m_firstChunk) ? m_chunk + StaticChunkSize : m_chunk;

            Heap::free<chunk_alignment>(freeChunkBase);
        }

        return m_chunk;
    }

    LEAN_INLINE void* allocate(size_type size) { return allocate<default_alignment>(size); }
    LEAN_INLINE void free(void *memory) { free<default_alignment>(memory); }

    template <size_t Alignment>
    LEAN_INLINE void* allocate(size_type size)
    {
        return allocate_aligned<Alignment>(size);
    }
    template <size_t Alignment>
    LEAN_INLINE void free(void *memory)
    {
        // Freeing of individual memory blocks unsupported
    }
};

} // namespace

using memory::chunk_heap;

} // namespace

#endif