fsa.h

Go to the documentation of this file.

/*

A* Algorithm Implementation using STL is
Copyright (C)2001-2005 Justin Heyes-Jones

Permission is given by the author to freely redistribute and
include this code in any program as long as this credit is
given where due.

  COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS,
  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED,
  INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE
  IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
  OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND
  PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED
  CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL
  DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY
  NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF
  WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE
  OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
  THIS DISCLAIMER.

  Use at your own risk!



  FixedSizeAllocator class
  Copyright 2001 Justin Heyes-Jones

  This class is a constant time O(1) memory manager for objects of
  a specified type. The type is specified using a template class.

  Memory is allocated from a fixed size buffer which you can specify in the
  class constructor or use the default.

  Using GetFirst and GetNext it is possible to iterate through the elements
  one by one, and this would be the most common use for the class.

  I would suggest using this class when you want O(1) add and delete
  and you don't do much searching, which would be O(n). Structures such as binary
  trees can be used instead to get O(logn) access time.

*/

#ifndef FSA_H
#define FSA_H

#include <string.h>
#include <stdio.h>

template <class USER_TYPE> class FixedSizeAllocator {
public:
  // Constants
  enum { FSA_DEFAULT_SIZE = 100 };

  // This class enables us to transparently manage the extra data
  // needed to enable the user class to form part of the double-linked
  // list class
  struct FSA_ELEMENT {
    USER_TYPE UserType;

    FSA_ELEMENT *pPrev;
    FSA_ELEMENT *pNext;
  };

private:
  FixedSizeAllocator(const FixedSizeAllocator &) {}
public: // methods
  explicit FixedSizeAllocator(unsigned int MaxElements = FSA_DEFAULT_SIZE)
      : m_MaxElements(MaxElements), m_pFirstUsed(NULL)
  {
    // Allocate enough memory for the maximum number of elements

    m_pMemory = new char[m_MaxElements];

    // Set the free list first pointer
    m_pFirstFree = m_pMemory;

    // Clear the memory
    memset(m_pMemory, 0, sizeof(FSA_ELEMENT) * m_MaxElements);

    // Point at first element
    FSA_ELEMENT *pElement = m_pFirstFree;

    // Set the double linked free list
    for (unsigned int i = 0; i < m_MaxElements; i++) {
      pElement->pPrev = pElement - 1;
      pElement->pNext = pElement + 1;

      pElement++;
    }

    // first element should have a null prev
    m_pFirstFree->pPrev = NULL;
    // last element should have a null next
    (pElement - 1)->pNext = NULL;
  }

  ~FixedSizeAllocator()
  {
    // Free up the memory
    delete[] m_pMemory;
  }

  // Allocate a new USER_TYPE and return a pointer to it
  USER_TYPE *alloc()
  {
    FSA_ELEMENT *pNewNode = NULL;

    if (!m_pFirstFree) {
      return NULL;
    } else {
      pNewNode = m_pFirstFree;
      m_pFirstFree = pNewNode->pNext;

      // if the new node points to another free node then
      // change that nodes prev free pointer...
      if (pNewNode->pNext) {
        pNewNode->pNext->pPrev = NULL;
      }

      // node is now on the used list

      pNewNode->pPrev = NULL; // the allocated node is always first in the list

      if (m_pFirstUsed == NULL) {
        pNewNode->pNext = NULL; // no other nodes
      } else {
        m_pFirstUsed->pPrev = pNewNode; // insert this at the head of the used list
        pNewNode->pNext = m_pFirstUsed;
      }

      m_pFirstUsed = pNewNode;
    }

    return reinterpret_cast<USER_TYPE *>(pNewNode);
  }

  // Free the given user type
  // For efficiency I don't check whether the user_data is a valid
  // pointer that was allocated. I may add some debug only checking
  // (To add the debug check you'd need to make sure the pointer is in
  // the m_pMemory area and is pointing at the start of a node)
  void free(USER_TYPE *user_data)
  {
    FSA_ELEMENT *pNode = reinterpret_cast<FSA_ELEMENT *>(user_data);

    // manage used list, remove this node from it
    if (pNode->pPrev) {
      pNode->pPrev->pNext = pNode->pNext;
    } else {
      // this handles the case that we delete the first node in the used list
      m_pFirstUsed = pNode->pNext;
    }

    if (pNode->pNext) {
      pNode->pNext->pPrev = pNode->pPrev;
    }

    // add to free list
    if (m_pFirstFree == NULL) {
      // free list was empty
      m_pFirstFree = pNode;
      pNode->pPrev = NULL;
      pNode->pNext = NULL;
    } else {
      // Add this node at the start of the free list
      m_pFirstFree->pPrev = pNode;
      pNode->pNext = m_pFirstFree;
      m_pFirstFree = pNode;
    }
  }

  // For debugging this displays both lists (using the prev/next list pointers)
  void Debug()
  {
    printf("free list ");

    FSA_ELEMENT *p = m_pFirstFree;
    while (p) {
      printf("%p!%p ", p->pPrev, p->pNext);
      p = p->pNext;
    }
    printf("\n");

    printf("used list ");

    p = m_pFirstUsed;
    while (p) {
      printf("%p!%p ", p->pPrev, p->pNext);
      p = p->pNext;
    }
    printf("\n");
  }

  // Iterators

  USER_TYPE *GetFirst() { return reinterpret_cast<USER_TYPE *>(m_pFirstUsed); }
  USER_TYPE *GetNext(USER_TYPE *node)
  {
    return reinterpret_cast<USER_TYPE *>((reinterpret_cast<FSA_ELEMENT *>(node))->pNext);
  }

public: // data
private: // methods
private: // data
  FSA_ELEMENT *m_pFirstFree;
  FSA_ELEMENT *m_pFirstUsed;
  unsigned int m_MaxElements;
  FSA_ELEMENT *m_pMemory;
};

#endif // defined FSA_H