ifndef SASS_MEMORY_POOL_H define SASS_MEMORY_POOL_H

include <stdlib.h> include <iostream> include <algorithm> include <climits> include <vector>

namespace Sass {

// SIMPLE MEMORY-POOL ALLOCATOR WITH FREE-LIST ON TOP

// This is a memory pool allocator with a free list on top.
// We only allocate memory arenas from the system in specific
// sizes (`SassAllocatorArenaSize`). Users claim memory slices
// of certain sizes from the pool. If the allocation is too big
// to fit into our buckets, we use regular malloc/free instead.

// When the systems starts, we allocate the first arena and then
// start to give out addresses to memory slices. During that
// we steadily increase `offset` until the current arena is full.
// Once that happens we allocate a new arena and continue.
// https://en.wikipedia.org/wiki/Memory_pool

// Fragments that get deallocated are not really freed, we put
// them on our free-list. For every bucket we have a pointer to
// the first item for reuse. That item itself holds a pointer to
// the previously free item (regular free-list implementation).
// https://en.wikipedia.org/wiki/Free_list

// On allocation calls we first check if there is any suitable
// item on the free-list. If there is we pop it from the stack
// and return it to the caller. Otherwise we have to take out
// a new slice from the current `arena` and increase `offset`.

// Note that this is not thread safe. This is on purpose as we
// want to use the memory pool in a thread local usage. In order
// to get this thread safe you need to only allocate one pool
// per thread. This can be achieved by using thread local PODs.
// Simply create a pool on the first allocation and dispose
// it once all allocations have been returned. E.g. by using:
// static thread_local size_t allocations;
// static thread_local MemoryPool* pool;

class MemoryPool {

  // Current arena we fill up
  char* arena;

  // Position into the arena
  size_t offset = std::string::npos;

  // A list of full arenas
  std::vector<void*> arenas;

  // One pointer for every bucket (zero init)
  #ifdef _MSC_VER
  #pragma warning (suppress:4351)
  #endif
  void* freeList[SassAllocatorBuckets]{};

  // Increase the address until it sits on a
  // memory aligned address (maybe use `aligned`).
  inline static size_t alignMemAddr(size_t addr) {
    return (addr + SASS_MEM_ALIGN - 1) & ~(SASS_MEM_ALIGN - 1);
  }

public:

  // Default ctor
  MemoryPool() :
    // Wait for first allocation
    arena(nullptr),
    // Set to maximum value in order to
    // make an allocation on the first run
    offset(std::string::npos)
  {
  }

  // Destructor
  ~MemoryPool() {
    // Delete full arenas
    for (auto area : arenas) {
      free(area);
    }
    // Delete current arena
    free(arena);

  }

  // Allocate a slice of the memory pool
  void* allocate(size_t size)
  {

    // Increase size so its memory is aligned
    size = alignMemAddr(
      // Make sure we have enough space for us to
      // create the pointer to the free list later
      std::max(sizeof(void*), size)
      // and the size needed for our book-keeping
      + SassAllocatorBookSize);

    // Size must be multiple of alignment
    // So we can derive bucket index from it
    size_t bucket = size / SASS_MEM_ALIGN;

    // Everything bigger is allocated via malloc
    // Malloc is optimized for exactly this case
    if (bucket >= SassAllocatorBuckets) {
      char* buffer = (char*)malloc(size);
      if (buffer == nullptr) {
        throw std::bad_alloc();
      }
      // Mark it for deallocation via free
      ((unsigned int*)buffer)[0] = UINT_MAX;
      // Return pointer after our book-keeping space
      return (void*)(buffer + SassAllocatorBookSize);
    }
    // Use custom allocator
    else {
      // Get item from free list
      void*& free = freeList[bucket];
      // Do we have a free item?
      if (free != nullptr) {
        // Copy pointer to return
        void* ptr = free;
        // Update free list pointer
        free = ((void**)ptr)[0];
        // Return popped item
        return ptr;
      }
    }

    // Make sure we have enough space in the arena
    if (!arena || offset > SassAllocatorArenaSize - size) {
      if (arena) arenas.emplace_back(arena);
      arena = (char*)malloc(SassAllocatorArenaSize);
      if (arena == nullptr) throw std::bad_alloc();
      offset = SassAllocatorArenaHeadSize;
    }

    // Get pointer into the arena
    char* buffer = arena + offset;
    // Consume object size
    offset += size;

    // Set the bucket index for this slice
    ((unsigned int*)buffer)[0] = (unsigned int)bucket;

    // Return pointer after our book-keeping space
    return (void*)(buffer + SassAllocatorBookSize);

  }
  // EO allocate

  void deallocate(void* ptr)
  {

    // Rewind buffer from pointer
    char* buffer = (char*)ptr -
      SassAllocatorBookSize;

    // Get the bucket index stored in the header
    unsigned int bucket = ((unsigned int*)buffer)[0];

    // Check allocation method
    if (bucket != UINT_MAX) {
      // Let memory point to previous item in free list
      ((void**)ptr)[0] = freeList[bucket];
      // Free list now points to our memory
      freeList[bucket] = (void*)ptr;
    }
    else {
      // Release memory
      free(buffer);
    }

  }
  // EO deallocate

};

}

endif