00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
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
00056 enum
00057 {
00058 FSA_DEFAULT_SIZE = 100
00059 };
00060
00061
00062
00063
00064 struct FSA_ELEMENT
00065 {
00066 USER_TYPE UserType;
00067
00068 FSA_ELEMENT *pPrev;
00069 FSA_ELEMENT *pNext;
00070 };
00071
00072 public:
00073 FixedSizeAllocator( unsigned int MaxElements = FSA_DEFAULT_SIZE ) :
00074 m_MaxElements( MaxElements ),
00075 m_pFirstUsed( NULL )
00076 {
00077
00078
00079 char *pMem = new char[ m_MaxElements * sizeof(FSA_ELEMENT) ];
00080
00081 m_pMemory = (FSA_ELEMENT *) pMem;
00082
00083
00084 m_pFirstFree = m_pMemory;
00085
00086
00087 memset( m_pMemory, 0, sizeof( FSA_ELEMENT ) * m_MaxElements );
00088
00089
00090 FSA_ELEMENT *pElement = m_pFirstFree;
00091
00092
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
00102 m_pFirstFree->pPrev = NULL;
00103
00104 (pElement-1)->pNext = NULL;
00105
00106 }
00107
00108
00109 ~FixedSizeAllocator()
00110 {
00111
00112 delete [] (char *) m_pMemory;
00113 }
00114
00115
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
00131
00132 if( pNewNode->pNext )
00133 {
00134 pNewNode->pNext->pPrev = NULL;
00135 }
00136
00137
00138
00139 pNewNode->pPrev = NULL;
00140
00141 if( m_pFirstUsed == NULL )
00142 {
00143 pNewNode->pNext = NULL;
00144 }
00145 else
00146 {
00147 m_pFirstUsed->pPrev = pNewNode;
00148 pNewNode->pNext = m_pFirstUsed;
00149 }
00150
00151 m_pFirstUsed = pNewNode;
00152 }
00153
00154 return reinterpret_cast<USER_TYPE*>(pNewNode);
00155 }
00156
00157
00158
00159
00160
00161
00162 void free( USER_TYPE *user_data )
00163 {
00164 FSA_ELEMENT *pNode = reinterpret_cast<FSA_ELEMENT*>(user_data);
00165
00166
00167 if( pNode->pPrev )
00168 {
00169 pNode->pPrev->pNext = pNode->pNext;
00170 }
00171 else
00172 {
00173
00174 m_pFirstUsed = pNode->pNext;
00175 }
00176
00177 if( pNode->pNext )
00178 {
00179 pNode->pNext->pPrev = pNode->pPrev;
00180 }
00181
00182
00183 if( m_pFirstFree == NULL )
00184 {
00185
00186 m_pFirstFree = pNode;
00187 pNode->pPrev = NULL;
00188 pNode->pNext = NULL;
00189 }
00190 else
00191 {
00192
00193 m_pFirstFree->pPrev = pNode;
00194 pNode->pNext = m_pFirstFree;
00195 m_pFirstFree = pNode;
00196 }
00197
00198 }
00199
00200
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
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:
00240
00241 private:
00242
00243 private:
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