fsa.h

00001 /* 
00002 
00003 A* Algorithm Implementation using STL is
00004 Copyright (C)2001-2005 Justin Heyes-Jones
00005 
00006 Permission is given by the author to freely redistribute and 
00007 include this code in any program as long as this credit is 
00008 given where due.
00009  
00010   COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, 
00011   WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, 
00012   INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE 
00013   IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
00014   OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND 
00015   PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED 
00016   CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL 
00017   DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY 
00018   NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF 
00019   WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE 
00020   OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
00021   THIS DISCLAIMER.
00022  
00023   Use at your own risk!
00024 
00025 
00026 
00027   FixedSizeAllocator class
00028   Copyright 2001 Justin Heyes-Jones
00029 
00030   This class is a constant time O(1) memory manager for objects of 
00031   a specified type. The type is specified using a template class.
00032 
00033   Memory is allocated from a fixed size buffer which you can specify in the
00034   class constructor or use the default.
00035 
00036   Using GetFirst and GetNext it is possible to iterate through the elements
00037   one by one, and this would be the most common use for the class. 
00038 
00039   I would suggest using this class when you want O(1) add and delete
00040   and you don't do much searching, which would be O(n). Structures such as binary 
00041   trees can be used instead to get O(logn) access time.
00042 
00043 */
00044 
00045 #ifndef FSA_H
00046 #define FSA_H
00047 
00048 #include <string.h>
00049 #include <stdio.h>
00050 
00051 template <class USER_TYPE> class FixedSizeAllocator
00052 {
00053 
00054 public: 
00055         // Constants
00056         enum
00057         {
00058                 FSA_DEFAULT_SIZE = 100
00059         };
00060 
00061         // This class enables us to transparently manage the extra data 
00062         // needed to enable the user class to form part of the double-linked
00063         // list class
00064         struct FSA_ELEMENT
00065         {
00066                 USER_TYPE UserType;
00067                 
00068                 FSA_ELEMENT *pPrev;
00069                 FSA_ELEMENT *pNext;
00070         };
00071 
00072 public: // methods
00073         FixedSizeAllocator( unsigned int MaxElements = FSA_DEFAULT_SIZE ) :
00074         m_MaxElements( MaxElements ),
00075         m_pFirstUsed( NULL )
00076         {
00077                 // Allocate enough memory for the maximum number of elements
00078 
00079                 char *pMem = new char[ m_MaxElements * sizeof(FSA_ELEMENT) ];
00080 
00081                 m_pMemory = (FSA_ELEMENT *) pMem; 
00082 
00083                 // Set the free list first pointer
00084                 m_pFirstFree = m_pMemory;
00085 
00086                 // Clear the memory
00087                 memset( m_pMemory, 0, sizeof( FSA_ELEMENT ) * m_MaxElements );
00088 
00089                 // Point at first element
00090                 FSA_ELEMENT *pElement = m_pFirstFree;
00091 
00092                 // Set the double linked free list
00093                 for( unsigned int i=0; i<m_MaxElements; i++ )
00094                 {
00095                         pElement->pPrev = pElement-1;
00096                         pElement->pNext = pElement+1;
00097 
00098                         pElement++;
00099                 }
00100 
00101                 // first element should have a null prev
00102                 m_pFirstFree->pPrev = NULL;
00103                 // last element should have a null next
00104                 (pElement-1)->pNext = NULL;
00105 
00106         }
00107 
00108 
00109         ~FixedSizeAllocator()
00110         {
00111                 // Free up the memory
00112                 delete [] (char *) m_pMemory;
00113         }
00114 
00115         // Allocate a new USER_TYPE and return a pointer to it 
00116         USER_TYPE *alloc()
00117         {
00118 
00119                 FSA_ELEMENT *pNewNode = NULL;
00120 
00121                 if( !m_pFirstFree )
00122                 {
00123                         return NULL;
00124                 }
00125                 else
00126                 {
00127                         pNewNode = m_pFirstFree;
00128                         m_pFirstFree = pNewNode->pNext;
00129 
00130                         // if the new node points to another free node then
00131                         // change that nodes prev free pointer...
00132                         if( pNewNode->pNext )
00133                         {
00134                                 pNewNode->pNext->pPrev = NULL;
00135                         }
00136 
00137                         // node is now on the used list
00138 
00139                         pNewNode->pPrev = NULL; // the allocated node is always first in the list
00140 
00141                         if( m_pFirstUsed == NULL )
00142                         {
00143                                 pNewNode->pNext = NULL; // no other nodes
00144                         }
00145                         else
00146                         {
00147                                 m_pFirstUsed->pPrev = pNewNode; // insert this at the head of the used list
00148                                 pNewNode->pNext = m_pFirstUsed;
00149                         }
00150 
00151                         m_pFirstUsed = pNewNode;
00152                 }       
00153                 
00154                 return reinterpret_cast<USER_TYPE*>(pNewNode);
00155         }
00156 
00157         // Free the given user type
00158         // For efficiency I don't check whether the user_data is a valid
00159         // pointer that was allocated. I may add some debug only checking
00160         // (To add the debug check you'd need to make sure the pointer is in 
00161         // the m_pMemory area and is pointing at the start of a node)
00162         void free( USER_TYPE *user_data )
00163         {
00164                 FSA_ELEMENT *pNode = reinterpret_cast<FSA_ELEMENT*>(user_data);
00165 
00166                 // manage used list, remove this node from it
00167                 if( pNode->pPrev )
00168                 {
00169                         pNode->pPrev->pNext = pNode->pNext;
00170                 }
00171                 else
00172                 {
00173                         // this handles the case that we delete the first node in the used list
00174                         m_pFirstUsed = pNode->pNext;
00175                 }
00176 
00177                 if( pNode->pNext )
00178                 {
00179                         pNode->pNext->pPrev = pNode->pPrev;
00180                 }
00181 
00182                 // add to free list
00183                 if( m_pFirstFree == NULL ) 
00184                 {
00185                         // free list was empty
00186                         m_pFirstFree = pNode;
00187                         pNode->pPrev = NULL;
00188                         pNode->pNext = NULL;
00189                 }
00190                 else
00191                 {
00192                         // Add this node at the start of the free list
00193                         m_pFirstFree->pPrev = pNode;
00194                         pNode->pNext = m_pFirstFree;
00195                         m_pFirstFree = pNode;
00196                 }
00197 
00198         }
00199 
00200         // For debugging this displays both lists (using the prev/next list pointers)
00201         void Debug()
00202         {
00203                 printf( "free list " );
00204 
00205                 FSA_ELEMENT *p = m_pFirstFree;
00206                 while( p )
00207                 {
00208                         printf( "%x!%x ", p->pPrev, p->pNext );
00209                         p = p->pNext;
00210                 }
00211                 printf( "\n" );
00212 
00213                 printf( "used list " );
00214 
00215                 p = m_pFirstUsed;
00216                 while( p )
00217                 {
00218                         printf( "%x!%x ", p->pPrev, p->pNext );
00219                         p = p->pNext;
00220                 }
00221                 printf( "\n" );
00222         }
00223 
00224         // Iterators
00225 
00226         USER_TYPE *GetFirst()
00227         {
00228                 return reinterpret_cast<USER_TYPE *>(m_pFirstUsed);
00229         }
00230 
00231         USER_TYPE *GetNext( USER_TYPE *node )
00232         {
00233                 return reinterpret_cast<USER_TYPE *>
00234                         (
00235                                 (reinterpret_cast<FSA_ELEMENT *>(node))->pNext
00236                         );
00237         }
00238 
00239 public: // data
00240 
00241 private: // methods
00242 
00243 private: // data
00244 
00245         FSA_ELEMENT *m_pFirstFree;
00246         FSA_ELEMENT *m_pFirstUsed;
00247         unsigned int m_MaxElements;
00248         FSA_ELEMENT *m_pMemory;
00249 
00250 };
00251 
00252 #endif // defined FSA_H

Generated on Tue Jun 19 11:15:43 2007 for mainplansys.kdevelop by  doxygen 1.4.7