Pol  Revision:3cfda13
fsa.h
Go to the documentation of this file.
1 // History
2 // 2006/10/07 Shinigami: smaller Bug in Debug() (m_pFirst -> m_pFirstUsed)
3 
4 /*
5 
6  FixedSizeAllocator class
7  Copyright 2001 Justin Heyes-Jones
8 
9  This class is a constant time O(1) memory manager for objects of
10  a specified type. The type is specified using a template class.
11 
12  Memory is allocated from a fixed size buffer which you can specify in the
13  class constructor or use the default.
14 
15  Using GetFirst and GetNext it is possible to iterate through the elements
16  one by one, and this would be the most common use for the class.
17 
18  I would suggest using this class when you want O(1) add and delete
19  and you don't do much searching, which would be O(n). Structures such as binary
20  trees can be used instead to get O(logn) access time.
21 
22 */
23 
24 #ifndef FSA_H
25 #define FSA_H
26 
27 #include "../clib/logfacility.h"
28 #include <stdio.h>
29 #include <string>
30 namespace Pol
31 {
32 namespace Plib
33 {
34 template <class USER_TYPE>
36 {
37 public:
38  // Constants
39  enum
40  {
42  };
43 
44  // This class enables us to transparently manage the extra data
45  // needed to enable the user class to form part of the double-linked
46  // list class
47  struct FSA_ELEMENT
48  {
49  USER_TYPE UserType;
50 
53  };
54 
55 public: // methods
56  FixedSizeAllocator( size_t MaxElements = FSA_DEFAULT_SIZE )
57  : m_pFirstUsed( NULL ), m_MaxElements( MaxElements )
58  {
59  // Allocate enough memory for the maximum number of elements
60 
61  char* pMem = new char[m_MaxElements * sizeof( FSA_ELEMENT )];
62 
63  m_pMemory = (FSA_ELEMENT*)pMem;
64 
65  // Set the free list first pointer
67 
68  // Clear the memory
69  memset( m_pMemory, 0, sizeof( FSA_ELEMENT ) * m_MaxElements );
70 
71  // Point at first element
72  FSA_ELEMENT* pElement = m_pFirstFree;
73 
74  // Set the double linked free list
75  for ( unsigned int i = 0; i < m_MaxElements; i++ )
76  {
77  pElement->pPrev = pElement - 1;
78  pElement->pNext = pElement + 1;
79 
80  pElement++;
81  }
82 
83  // first element should have a null prev
84  m_pFirstFree->pPrev = NULL;
85  // last element should have a null next
86  ( pElement - 1 )->pNext = NULL;
87  }
88 
89 
91  {
92  // Free up the memory
93  delete[] m_pMemory;
94  }
95 
96  // Allocate a new USER_TYPE and return a pointer to it
97  USER_TYPE* alloc()
98  {
99  FSA_ELEMENT* pNewNode = NULL;
100 
101  if ( !m_pFirstFree )
102  {
103  return NULL;
104  }
105  else
106  {
107  pNewNode = m_pFirstFree;
108  m_pFirstFree = pNewNode->pNext;
109 
110  // if the new node points to another free node then
111  // change that nodes prev free pointer...
112  if ( pNewNode->pNext )
113  {
114  pNewNode->pNext->pPrev = NULL;
115  }
116 
117  // node is now on the used list
118 
119  pNewNode->pPrev = NULL; // the allocated node is always first in the list
120 
121  if ( m_pFirstUsed == NULL )
122  {
123  pNewNode->pNext = NULL; // no other nodes
124  }
125  else
126  {
127  m_pFirstUsed->pPrev = pNewNode; // insert this at the head of the used list
128  pNewNode->pNext = m_pFirstUsed;
129  }
130 
131  m_pFirstUsed = pNewNode;
132  }
133 
134  return reinterpret_cast<USER_TYPE*>( pNewNode );
135  }
136 
137  // Free the given user type
138  // For efficiency I don't check whether the user_data is a valid
139  // pointer that was allocated. I may add some debug only checking
140  // (To add the debug check you'd need to make sure the pointer is in
141  // the m_pMemory area and is pointing at the start of a node)
142  void free( USER_TYPE* user_data )
143  {
144  FSA_ELEMENT* pNode = reinterpret_cast<FSA_ELEMENT*>( user_data );
145 
146  // manage used list, remove this node from it
147  if ( pNode->pPrev )
148  {
149  pNode->pPrev->pNext = pNode->pNext;
150  }
151  else
152  {
153  // this handles the case that we delete the first node in the used list
154  m_pFirstUsed = pNode->pNext;
155  }
156 
157  if ( pNode->pNext )
158  {
159  pNode->pNext->pPrev = pNode->pPrev;
160  }
161 
162  // add to free list
163  if ( m_pFirstFree == NULL )
164  {
165  // free list was empty
166  m_pFirstFree = pNode;
167  pNode->pPrev = NULL;
168  pNode->pNext = NULL;
169  }
170  else
171  {
172  // Add this node at the start of the free list
173  m_pFirstFree->pPrev = pNode;
174  pNode->pNext = m_pFirstFree;
175  m_pFirstFree = pNode;
176  }
177  }
178 
179  // For debugging this displays both lists (using the prev/next list pointers)
180  void Debug()
181  {
182  INFO_PRINT << "free list";
183  FSA_ELEMENT* p = m_pFirstFree;
184  fmt::Writer _tmp;
185  while ( p )
186  {
187  _tmp << fmt::hex( p->pPrev ) << "!" << fmt::hex( p->pNext ) << " ";
188  p = p->pNext;
189  }
190  _tmp << "\n";
191  INFO_PRINT << _tmp.str();
192 
193  INFO_PRINT << "used list\n";
194  _tmp.Clear();
195 
196  p = m_pFirstUsed;
197  while ( p )
198  {
199  _tmp << fmt::hex( p->pPrev ) << "!" << fmt::hex( p->pNext ) << " ";
200  p = p->pNext;
201  }
202  _tmp << "\n";
203  INFO_PRINT << _tmp.str();
204  }
205 
206  // Iterators
207 
208  USER_TYPE* GetFirst() { return reinterpret_cast<USER_TYPE*>( m_pFirstUsed ); }
209  USER_TYPE* GetNext( USER_TYPE* node )
210  {
211  return reinterpret_cast<USER_TYPE*>( ( reinterpret_cast<FSA_ELEMENT*>( node ) )->pNext );
212  }
213 
214 public: // data
215 private: // methods
216 private: // data
217  FSA_ELEMENT* m_pFirstFree;
218  FSA_ELEMENT* m_pFirstUsed;
220  FSA_ELEMENT* m_pMemory;
221 };
222 }
223 }
224 #endif // defined FSA_H
USER_TYPE * GetFirst()
Definition: fsa.h:208
USER_TYPE * alloc()
Definition: fsa.h:97
FSA_ELEMENT * m_pFirstUsed
Definition: fsa.h:218
FixedSizeAllocator(size_t MaxElements=FSA_DEFAULT_SIZE)
Definition: fsa.h:56
FSA_ELEMENT * m_pMemory
Definition: fsa.h:220
USER_TYPE * GetNext(USER_TYPE *node)
Definition: fsa.h:209
FSA_ELEMENT * m_pFirstFree
Definition: fsa.h:217
void free(USER_TYPE *user_data)
Definition: fsa.h:142
#define INFO_PRINT
Definition: logfacility.h:223
Definition: berror.cpp:12