Home > Code Samples > Static Allocator

Static Allocator

This is a simple static allocator I wrote to do block allocations of a fixed size. The fixed size allowed for very quick allocations and deallocations and enabled cache coherency (when objects of the same type were used, especially with components).

I did not modify this in any way before posting, except to remove commented out code blocks. Anything you see here directly corresponds to my own personal coding style and standards.

/******************************************************************************
  Author: Trevor Sundberg
    Date: 03/12/2008

 Purpose:
          An allocator that allocates objects in fixed size blocks.
          All content © 2009 DigiPen (USA) Corporation, all rights reserved.
******************************************************************************/


// Includes
#include "stdafx.h"
#include "static_allocator.h"

// Creates the ObjectManager per the specified values
StaticAllocator::StaticAllocator(unsigned object_size, unsigned objects_per_page)
{
  // Store the object size and objects per page
  mObjectSize     = object_size;
  mObjectsPerPage = objects_per_page;

  // Pre-calculate the size of a single page (+ 4 bytes at the end for the page list next pointer)
  mPageSize = objects_per_page * mObjectSize + sizeof(void*);

  // Set up the initial stats that don't change
  mStats.mPageSize   = mPageSize;
  mStats.mObjectSize = mObjectSize;

  // Build a new page (there was no previous page, so pass it null)
  char* new_page = BuildPage(NULL);

  // Setup the page list pointer to point at the start of the page
  mPageList = new_page;

  // Setup the free list pointer to point at the next free block
  mFreeList = &new_page[mPageSize - object_size];
}

// Allocates and builds a page
char* StaticAllocator::BuildPage(char* last_page)
{
  // Allocate the memory for a single page
  char *allocated_memory = new char[mPageSize];

  // Initialize the first 4 bytes to null, since it's a new page
  // it should point at the previous page
  *reinterpret_cast<char**>(allocated_memory) = last_page;

  // Store two pointers that will point at the previous free list ptr and the current
  char* last;
  char* current = NULL;

  // Initialize the "free list pointers" on the object
  // Loop through the number of objects that's supposed to be on a page
  for (unsigned i = 0; i < mObjectsPerPage; ++i)
  {
    // Update the last and current
    last = current;
    //                          Offset objects     +   sizeof(void*) (for next page ptr)
    current = &allocated_memory[mObjectSize * i   +   sizeof(void*)];

    // Set the free list pointer to point at the previous node
    *reinterpret_cast<char**>(current) = last;
  }

  // Update the stats to reflect the allocated page
  mStats.mFreeObjects += mObjectsPerPage;
  ++mStats.mPagesInUse;

  // Return the allocated memory as a void pointer
  return allocated_memory;
}

// Destroys the ObjectManager
StaticAllocator::~StaticAllocator()
{
  // Walk the page list and free all the pages
  void* iter = mPageList;

  // Iterate through the page list
  while (iter != NULL)
  {
    // Make a temporary copy of the iterator
    void* temp = iter;

    // Iterate to the next position in the page list
    iter = *reinterpret_cast<void**>(iter);

    // Free the memory through the temporary copy
    delete[] reinterpret_cast<char*>(temp);
  }
}



// Take an object from the free list and give it to the client (simulates new)
void* StaticAllocator::Allocate()
{
  // Update the stats to reflect the allocation
  --mStats.mFreeObjects;
  ++mStats.mObjectsInUse;
  ++mStats.mAllocations;

  // Check to see if we have more objects then the current "max/most", if so set the new "most"
  if (mStats.mObjectsInUse > mStats.mMostObjects)
    mStats.mMostObjects = mStats.mObjectsInUse;

  // Check if the free list is empty, if so add a new page
  if (mFreeList == NULL)
  {
    // Build a new page (give it the last page)
    char* new_page = BuildPage(reinterpret_cast<char*>(mPageList));

    // Iterate through the page list until we reach the end
    mPageList = new_page;

    // Setup the free list pointer to point at the next free block
    mFreeList = &new_page[mPageSize - mObjectSize];
  }

  // Create a temporary pointer that points at the current node in the free list
  void* temp = mFreeList;

  // Remove the node from the free list
  mFreeList = *reinterpret_cast<void**>(mFreeList);

  // Return the temporary pointer
  return temp;
}


// Returns an object to the free list for the client (simulates delete)
// Throws an exception if the the object can't be freed. (Invalid object)
void StaticAllocator::Free(void* object)
{
  // Check for a null pointer first
  if (object == NULL)
    return;

  // Update the stats to reflect the free
  ++mStats.mDeallocations;

  // Set the free list ptr in the freed object to point at the free list
  *reinterpret_cast<void**>(object) = mFreeList;

  // Update the stats to reflect the free
  ++mStats.mFreeObjects;
  --mStats.mObjectsInUse;

  // Add the object to the free list
  mFreeList = object;
}

// returns the statistics for the allocator
SAStats StaticAllocator::GetStats(void) const
{
  // Return the current stats
  return mStats;
}
Categories: Code Samples Tags:
  1. No comments yet.
  1. No trackbacks yet.