PoolBase.cpp

#include "PoolBase.h"
 
#include <OsoMemoryProfiler/OsoMemoryProfiler.h>
 
#include <limits>
 
// Uncomment to put pool elements onto the heap instead of in the pool,
// which allows memory debugging tools to identify problems.
//
//#define COGS_HEAP_DEBUG 1
 
namespace
{
  struct PoolHeader
  {
    void * next;
  };
}
 
Cogs::Collections::PoolBase::PoolBase(size_t elementSize, size_t initialCapacity, size_t pageSize, Memory::Allocator * allocator, MemBlockType memType) :
  elementSize(elementSize),
  pageSize(pageSize),
  allocator(allocator),
  memType(memType)
{
  assert(elementSize >= sizeof(PoolHeader) && "Element size must be at least enough to store a pointer.");
  assert(pageSize <= std::numeric_limits<ElementOffset>::max() && "Page size must be smaller or equal to max element offset.");
 
  resize(initialCapacity);
}
 
void Cogs::Collections::PoolBase::resize(size_t desiredCapacity)
{
  assert(desiredCapacity >= capacity && "Pool does not support shrinkage.");
 
  const size_t numPages = (desiredCapacity / pageSize) + ((desiredCapacity % pageSize) ? 1 : 0);
 
  assert(numPages <= std::numeric_limits<ElementOffset>::max() && "Page count must be smaller or equal to max element offset.");
 
  while (numPages > pages.size()) {
    addPage(pageSize);
  }
 
  capacity = pages.size() * pageSize;
}
 
void Cogs::Collections::PoolBase::addPage(size_t pageSize)
{
  // Add a single page to the list of pages.
  pages.emplace_back(pageSize * elementSize, allocator, memType);
 
  // Retrieve the new page.
  auto data = static_cast<uint8_t *>(pages.back().data());
 
  // Initialize the linked list of elements chaining all elements in the page together.
  for (size_t i = 0; i < pageSize; ++i) {
    PoolHeader * block = reinterpret_cast<PoolHeader *>(data + i * elementSize);
 
    block->next = reinterpret_cast<PoolHeader *>(data + (i + 1) * elementSize);
  }
 
  // Terminate the linked list at the last element.
  reinterpret_cast<PoolHeader *>(data + (pageSize - 1) * elementSize)->next = nullptr;
 
  if (!freeHead) {
    // If there are currently no free elements in the pool, we simply insert our new page of free elements
    // as the first available.
    freeHead = data;
  } else {
    // Walk to the last free element in the pool and insert our new linked list of free elements from the
    // page there.
    PoolHeader * last = static_cast<PoolHeader *>(freeHead);
 
    while (last->next) {
      last = static_cast<PoolHeader *>(last->next);
    }
 
    last->next = data;
  }
}
 
void * Cogs::Collections::PoolBase::allocate()
{
  // If there are no elements in our free list, we need to grow by one page.
  if (!freeHead) resize(capacity + pageSize);
 
  // Pick the first available element in the free list.
  auto element = static_cast<PoolHeader *>(freeHead);
 
  // Set the first free element to the next element in the free list. This element might be nullptr, and
  // in that case the pool will need to grow if further allocations are made.
  freeHead = element->next;
 
  ++numAllocated;
 
#ifdef COGS_HEAP_DEBUG
  uint8_t* mem = static_cast<uint8_t*>(std::malloc(sizeof(void*) + elementSize));
  *reinterpret_cast<PoolHeader**>(mem) = element;
  element->next = mem + sizeof(void*);
  return element->next;
#else
  return element;
#endif
}
 
void Cogs::Collections::PoolBase::deallocate(void * element)
{
#ifdef COGS_HEAP_DEBUG
  void * foo = static_cast<char*>(element) - sizeof(void*);
  element = *static_cast<PoolHeader**>(foo);
  std::free(foo);
#endif
 
  assert(numAllocated && "No available elements to free.");
 
  --numAllocated;
 
  static_cast<PoolHeader *>(element)->next = freeHead;
  freeHead = element;
}
 
Cogs::Collections::ElementHandle Cogs::Collections::PoolBase::getHandle(void * element) const
{
#ifdef COGS_HEAP_DEBUG
  element = *reinterpret_cast<PoolHeader**>(static_cast<char*>(element) - sizeof(void*));
#endif
 
  for (size_t i = 0; i < pages.size(); ++i) {
    auto & page = pages[i];
    auto data = static_cast<const uint8_t *>(page.data());
 
    const auto pageBegin = data;
    const auto pageEnd = data + pageSize * elementSize;
 
    if (element >= pageBegin && element < pageEnd) {
      const size_t offsetInBytes = static_cast<uint8_t *>(element) - pageBegin;
      const ElementOffset offset = static_cast<ElementOffset>(offsetInBytes / elementSize);
      const size_t pageIndex = (i << (sizeof(ElementOffset) * 8));
      const ElementHandle handle = static_cast<ElementHandle>(pageIndex) + offset;
 
      return handle;
    }
  }
 
  assert(false && "Element not part of any allocated pages.");
 
  return 0;
}
 
void * Cogs::Collections::PoolBase::getElement(ElementHandle handle)
{
  const auto pageIndex = getPageIndex(handle);
 
  assert(pageIndex < pages.size() && "Page index out of range.");
 
  const auto elementIndex = getElementOffset(handle);
 
  assert(elementIndex < pageSize && "Element index out of range.");
 
  auto elementPtr = reinterpret_cast<uint8_t *>(pages[pageIndex].data()) + elementIndex * elementSize;
 
#ifdef COGS_HEAP_DEBUG
  return reinterpret_cast<PoolHeader *>(elementPtr)->next;
#else
  return elementPtr;
#endif
}
 
bool Cogs::Collections::PoolBase::isAllocated(ElementHandle handle) const
{
  if (!isValid(handle)) return false;
  const auto pageIndex = getPageIndex(handle);
  const auto elementIndex = getElementOffset(handle);
  const void* elementPtr = static_cast<const void*>(reinterpret_cast<const uint8_t*>(pages[pageIndex].data()) + elementIndex * elementSize);
 
  PoolHeader* last = static_cast<PoolHeader*>(freeHead);
 
  while (last->next) {
    if (last == elementPtr)
      return false;
    last = static_cast<PoolHeader*>(last->next);
  }
 
  return true;
}