Just the implementation of some c style memory manager functions

MemoryManager.cpp

/*!
  Memory Manager
  Nathan Park

*/


#include "MemoryManager.h"

// #include <new.h> placement new

namespace MemoryManager
{
  // IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT 
  //
  // This is the only static memory that you may use, no other global variables may be
  // created, if you need to save data make it fit in MM_pool
  //
  // IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT

  enum ErrorType
  {
    Bad_Alloc,
    Invalid_Bounds,
    Multiple_Free
  };

  const int MM_POOL_SIZE = 65536;
  char MM_pool[MM_POOL_SIZE];

  struct Block
  {
    int m_size; // could be 2 bytes
    char m_free; // could  be a bit
    
    // intrusively linked lists
    Block * m_nextBlock; // these could be 2 bytes each if we used indicies
    Block * m_prevBlock; 
    Block * m_nextFree;  
    Block * m_prevFree;

    // I wish I didn't have to use a doubly-linked list, but how else can I 
    // remove a node from a list, given only that node?... 
    // I can't index backwards into the array because blocks are of
    // variable size.
    // 
    // Actually, I probably don't need the nextBlock pointer, because knowing
    // the size of my block, so I can index forward by that amount to reach
    // the next.
    
    // eventually, I'd like to use pad bytes to detect buffer under/overflow

    Block(int size, char free)
      : m_size(size)
      , m_free(free)
      , m_nextBlock(0)
      , m_prevBlock(0)
      , m_nextFree (0)
      , m_prevFree (0)
    {}
    
    char * GetData()
    {
      return reinterpret_cast<char*>(this) + sizeof(Block);
    }
    void InsertNodeAfterMe(Block * block)
    {
      // [this][block][this->next]
      
      // link block and this->next
      m_nextBlock->m_prevBlock = block;
      block->m_nextBlock = m_nextBlock;
      
      // link this and block
      block->m_prevBlock = this;
      m_nextBlock = block;
    }
    void RemoveFromFreeList()
    {
      // remove bestfit from the freelist
      m_nextFree->m_prevFree = m_prevFree;
      m_prevFree->m_nextFree = m_nextFree;
      m_nextFree = 0;
      m_prevFree = 0;

      m_free = false;
    }
  };
  
  // return new(location) Block(size,free); <-- ideally
  Block * blockPlacementNew(char * location, int size, char free)
  {
    Block * block = reinterpret_cast<Block*>(location);
    *block = Block(size, free);

    return block;
  }

  struct Manager 
  {
    // makes doubly linked lists easier
    Block * m_dummyHead;
    Block * m_dummyTail;

    static Manager * Instance()
    {
      return reinterpret_cast<Manager*>(MM_pool);
    }
    Block * BeginBlock()
    {
      return m_dummyHead->m_nextBlock;
    }
    Block * EndBlock()
    {
      return m_dummyTail;
    }
    Block * BeginFree()
    {
      return m_dummyHead->m_nextFree;
    }
    Block * EndFree()
    {
      return m_dummyTail;
    }

    void PushFrontOntoFreeList(Block * block)
    {
      // right 2 pointers
      block->m_nextFree = BeginFree();
      BeginFree()->m_prevFree = block;
      
      // left 2 pointers
      m_dummyHead->m_nextFree = block;
      block->m_prevFree = m_dummyHead;

      block->m_free = true;
    }
    void MergeAdjacentFreeBlocks(Block * lhs, Block * rhs)
    {
      rhs->RemoveFromFreeList();

      rhs->m_nextBlock->m_prevBlock = lhs;
      lhs->m_nextBlock = rhs->m_nextBlock;

      lhs->m_size += rhs->m_size;
      lhs->m_size += sizeof(Block);
    }
  };


  // Initialize set up any data needed to manage the memory pool
  void initializeMemoryManager(void)
  {
    // std::cout << "manager size: " << sizeof(Manager) << std::endl;
    // std::cout << "block   size: " << sizeof(Block)   << std::endl;

    Manager * memManager = Manager::Instance();
    
    // forever in-use ( will never be merged with)
    char * dummyHeaderPos = MM_pool + sizeof(Manager);
    memManager->m_dummyHead = blockPlacementNew(dummyHeaderPos, 0, false);
      
    char * dummyTailPos = MM_pool + MM_POOL_SIZE - sizeof(Block);
    memManager->m_dummyTail = blockPlacementNew(dummyTailPos, 0, false);

    char * freeBlockPos = dummyHeaderPos + sizeof(Block);
    int initialBlockSize 
      = MM_POOL_SIZE
      - sizeof (Manager)
      - sizeof(Block)  // head
      - sizeof(Block)  // tail
      - sizeof(Block); // own header
      
    Block * freeBlock = blockPlacementNew(freeBlockPos, initialBlockSize, true);
      
    // Link the initial 3 blocks
    memManager->m_dummyHead->m_prevBlock = 0;
    memManager->m_dummyHead->m_nextBlock = freeBlock;

    freeBlock->m_prevBlock = memManager->m_dummyHead;
    freeBlock->m_nextBlock = memManager->m_dummyTail;

    memManager->m_dummyTail->m_prevBlock = freeBlock;
    memManager->m_dummyTail->m_nextBlock = 0;

    // free list
    memManager->m_dummyHead->m_nextFree = freeBlock;
    freeBlock->m_prevFree = memManager->m_dummyHead;
    freeBlock->m_nextFree = memManager->m_dummyTail;
  }

  // return a pointer inside the memory pool
  // If no chunk can accommodate aSize call onOutOfMemory()
  void* allocate(int aSize)
  {
    int smallestData = 4; // probably better than 2

    if (aSize <= 0)
    {
      onIllegalOperation("Error # %i: Trying to allocate <= 0 bytes", Bad_Alloc);
    }
    
    if (aSize < smallestData)
    {
      aSize = smallestData;
    }

    Manager * memManager = Manager::Instance();
    Block * bestFit = 0;
    int smallestDifference;
    for (Block * block = memManager->BeginFree(); block != memManager->EndFree(); block = block->m_nextFree)
    {
      int sizeDifference = block->m_size - aSize;
      if (sizeDifference < 0) continue; // blocksize < aSize (block too small)
      if (sizeDifference == 0) // Perfect Fit
      {
        block->RemoveFromFreeList();
        return block->GetData();
      }
      if (!bestFit) // first run
      {
        bestFit = block;
        smallestDifference = sizeDifference;
      } // better fit
      else if (sizeDifference < smallestDifference)
      {
        bestFit = block;
        smallestDifference = sizeDifference;
      }
    }
    if (!bestFit) 
    {
      onOutOfMemory();
    }
    if (smallestDifference >= (int)sizeof(Block) + smallestData) // Can split
    {
      // BEFORE SPLIT:
      //         
      //         |<-- bestFit->m_size ------------------------------------->| 
      //         |                                                          |
      //         |                                  possible extra space |  |
      // [ header, data                                                  v  ]
      //         | <--aSize--> | <--sizeof(Block)-->|<--smallestData-->|    |
      //                       | <----------smallest difference-----------> |
      //                       |                                            |
      // AFTER SPLIT:          |                                            |
      // [ header, data       ]|[ header, data                              ]
      // ^                     ^
      // |                     |
      // bestFit               rHalf
      
      char * rHalfStart = reinterpret_cast<char*>(bestFit) + sizeof(Block) + aSize;
      int rHalfSize = smallestDifference - sizeof(Block);

      Block * rHalf = blockPlacementNew(rHalfStart, rHalfSize, true);

      bestFit->InsertNodeAfterMe(rHalf);

      bestFit->RemoveFromFreeList();
      memManager->PushFrontOntoFreeList(rHalf);
      
      bestFit->m_size = aSize;
      return bestFit->GetData();
    }
    else // cannot split, just return bestfit
    {
      bestFit->RemoveFromFreeList();
      return bestFit->GetData();
    }
  }

  // Free up a chunk previously allocated
  void deallocate(void* aPointer)
  {
    Manager * memManager = Manager::Instance();

    char * position = reinterpret_cast<char*>(aPointer);
    if (position < MM_pool || position >= MM_pool + MM_POOL_SIZE)
    {
      onIllegalOperation("Error # %i: Trying to deallocate data outside of the memory manager's pool", Invalid_Bounds);
    }
    Block * block = reinterpret_cast<Block*>(position - sizeof(Block));
    if (block->m_free)
    {
      onIllegalOperation("Error # %i: Trying to deallocate data that has already been freed", Multiple_Free);
    }
    
    memManager->PushFrontOntoFreeList(block);
    
    Block * prev = block->m_prevBlock;
    if (prev->m_free) // dummy blocks aren't free, so no problem
    {
      memManager->MergeAdjacentFreeBlocks(prev, block);
      block = prev; 
    }
    Block * next = block->m_nextBlock;
    if (next->m_free) // dummy blocks aren't free, so no problem
    {
      memManager->MergeAdjacentFreeBlocks(block, next);
    }
  }

  //---
  //--- support routines
  //--- 

  // Will scan the memory pool and return the total free space remaining
  int freeRemaining(void)
  {
    int totalFreeSpace = 0;
    Manager * memManager = Manager::Instance();
    for (Block * block = memManager->BeginFree(); block != memManager->EndFree(); block = block->m_nextFree)
    {
      totalFreeSpace += block->m_size;
    }
    return totalFreeSpace;
  }

  // Will scan the memory pool and return the largest free space remaining
  int largestFree(void)
  {
    int largestFree = 0;
    Manager * memManager = Manager::Instance();
    for (Block * block = memManager->BeginFree(); block != memManager->EndFree(); block = block->m_nextFree)
    {
      int blockSize = block->m_size;
      if (blockSize > largestFree) largestFree = blockSize;
    }
    return largestFree;
  }

  // will scan the memory pool and return the smallest free space remaining
  int smallestFree(void)
  {
    Manager * memManager = Manager::Instance();

    Block * head = memManager->BeginFree();
    if (head == memManager->EndFree()) return 0;

    int smallestFree = head->m_size;

    for (Block * block = head->m_nextFree; block != memManager->EndFree(); block = block->m_nextFree)
    {
      int blockSize = block->m_size;
      if (blockSize < smallestFree) smallestFree = blockSize;
    }
    return smallestFree;
  }
 }