00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CSUTIL_BLKALLOC_H__
00020 #define __CSUTIL_BLKALLOC_H__
00021
00022 #include "csutil/array.h"
00023
00024
00025 #ifdef CS_EXTENSIVE_MEMDEBUG
00026 # undef new
00027 #endif
00028 #include <new>
00029
00041 template <class T>
00042 class csBlockAllocator
00043 {
00044 private:
00045
00046 struct csFreeList
00047 {
00048 csFreeList* next;
00049 uint32 numfree;
00050 };
00051
00052
00053 struct csBlock
00054 {
00055 void* memory;
00056 csFreeList* firstfree;
00057 csBlock () : memory (NULL) { }
00058 ~csBlock () { if (memory) free (memory); }
00059 };
00060
00061 csArray<csBlock> blocks;
00062 unsigned int size;
00063 unsigned int elsize;
00064 unsigned int blocksize;
00065
00066
00067 int firstfreeblock;
00068
00072 int FindBlock (void* m)
00073 {
00074 int i;
00075 for (i = 0 ; i < blocks.Length () ; i++)
00076 {
00077 csBlock* b = &blocks[i];
00078 if (b->memory <= m)
00079 {
00080 char* eb = ((char*)b->memory) + blocksize;
00081 if (((char*)m) < eb)
00082 return i;
00083 }
00084 }
00085 return -1;
00086 }
00087
00092 void FindAndUpdateFreeBlock ()
00093 {
00094 ++firstfreeblock;
00095 while (firstfreeblock < blocks.Length ()
00096 && blocks[firstfreeblock].firstfree == NULL)
00097 ++firstfreeblock;
00098
00099 if (firstfreeblock == blocks.Length ())
00100 {
00101 firstfreeblock = blocks.Push (csBlock ());
00102 csBlock& bl = blocks[firstfreeblock];
00103 bl.memory = (void*)malloc (blocksize);
00104 bl.firstfree = (csFreeList*)bl.memory;
00105 bl.firstfree->next = NULL;
00106 bl.firstfree->numfree = size;
00107 }
00108 }
00109
00110 public:
00116 csBlockAllocator (int s)
00117 {
00118 size = s;
00119 elsize = sizeof (T);
00120 if (elsize < sizeof (csFreeList)) elsize = sizeof (csFreeList);
00121 blocksize = elsize * size;
00122
00123 int idx = blocks.Push (csBlock ());
00124 csBlock& bl = blocks[idx];
00125 bl.memory = (void*)malloc (blocksize);
00126 bl.firstfree = (csFreeList*)bl.memory;
00127 bl.firstfree->next = NULL;
00128 bl.firstfree->numfree = size;
00129
00130 firstfreeblock = 0;
00131 }
00132
00139 ~csBlockAllocator ()
00140 {
00141 #ifdef CS_DEBUG
00142 CS_ASSERT (firstfreeblock == 0);
00143 int i;
00144 for (i = 0 ; i < blocks.Length () ; i++)
00145 {
00146 CS_ASSERT (blocks[i].firstfree == (csFreeList*)blocks[i].memory);
00147 CS_ASSERT (blocks[i].firstfree->next == NULL);
00148 CS_ASSERT (blocks[i].firstfree->numfree == size);
00149 }
00150 #endif
00151 }
00152
00156 T* Alloc ()
00157 {
00158
00159 csBlock& freebl = blocks[firstfreeblock];
00160 void* ptr = (void*)(freebl.firstfree);
00161
00162 if (freebl.firstfree->numfree >= 2)
00163 {
00164
00165 csFreeList* nf = (csFreeList*)(((char*)ptr)+elsize);
00166 nf->next = freebl.firstfree->next;
00167 nf->numfree = freebl.firstfree->numfree-1;
00168 freebl.firstfree = nf;
00169 }
00170 else
00171 {
00172
00173 freebl.firstfree = freebl.firstfree->next;
00174 if (!freebl.firstfree)
00175 {
00176
00177 FindAndUpdateFreeBlock ();
00178 }
00179 }
00180
00181 return new (ptr) T ();
00182 }
00183
00187 void Free (T* el)
00188 {
00189 if (!el) return;
00190
00191 int idx = FindBlock ((void*)el);
00192 CS_ASSERT (idx != -1);
00193
00194 el->T::~T();
00195
00196
00197
00198 if (idx < firstfreeblock)
00199 firstfreeblock = idx;
00200
00201 csBlock& bl = blocks[idx];
00202 if (bl.firstfree == NULL)
00203 {
00204
00205
00206 bl.firstfree = (csFreeList*)el;
00207 bl.firstfree->next = NULL;
00208 bl.firstfree->numfree = 1;
00209 }
00210 else
00211 {
00212 csFreeList* p_el = (csFreeList*)el;
00213
00214 if (p_el < bl.firstfree)
00215 {
00216
00217 if (((char*)bl.firstfree) - ((char*)p_el) == (int)elsize)
00218 {
00219
00220
00221 p_el->next = bl.firstfree->next;
00222 p_el->numfree = bl.firstfree->numfree+1;
00223 }
00224 else
00225 {
00226
00227 p_el->next = bl.firstfree;
00228 p_el->numfree = 1;
00229 }
00230
00231 bl.firstfree = p_el;
00232 }
00233 else
00234 {
00235
00236
00237
00238 csFreeList* fl_before = bl.firstfree;
00239 csFreeList* fl_after = bl.firstfree->next;
00240 while (fl_after != NULL && fl_after < p_el)
00241 {
00242 fl_before = fl_after;
00243 fl_after = fl_after->next;
00244 }
00245
00246
00247
00248
00249 char* fl_before_end = ((char*)fl_before) + fl_before->numfree * elsize;
00250
00251 if (!fl_after)
00252 {
00253
00254
00255
00256 if (fl_before_end == (char*)p_el)
00257 {
00258
00259 ++(fl_before->numfree);
00260 }
00261 else
00262 {
00263
00264 p_el->next = NULL;
00265 p_el->numfree = 1;
00266 fl_before->next = p_el;
00267 }
00268 }
00269 else
00270 {
00271
00272
00273
00274 if (fl_before_end == (char*)p_el
00275 && ((char*)p_el) + elsize == (char*)fl_after)
00276 {
00277
00278 fl_before->next = fl_after->next;
00279 fl_before->numfree = fl_before->numfree + 1 + fl_after->numfree;
00280 }
00281 else if (fl_before_end == (char*)p_el)
00282 {
00283
00284 ++(fl_before->numfree);
00285 }
00286 else if (((char*)p_el) + elsize == (char*)fl_after)
00287 {
00288
00289 fl_before->next = p_el;
00290 p_el->next = fl_after->next;
00291 p_el->numfree = fl_after->numfree+1;
00292 }
00293 else
00294 {
00295
00296 fl_before->next = p_el;
00297 p_el->next = fl_after;
00298 p_el->numfree = 1;
00299 }
00300 }
00301 }
00302 }
00303 }
00304
00308 void Dump ()
00309 {
00310 int i;
00311 printf ("=============================\nelsize = %d\n", elsize);
00312 for (i = 0 ; i < blocks.Length () ; i++)
00313 {
00314 printf ("Block %d\n", i);
00315 csFreeList* fl = blocks[i].firstfree;
00316 char* m = (char*)blocks[i].memory;
00317 while (fl)
00318 {
00319 printf (" free %d %d\n", (((char*)fl) - m) / elsize, fl->numfree);
00320 fl = fl->next;
00321 }
00322 }
00323 printf ("=============================\n");
00324 fflush (stdout);
00325 }
00326 };
00327
00328 #ifdef CS_EXTENSIVE_MEMDEBUG
00329 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00330 #endif
00331
00332 #endif
00333