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
00046 template <class T>
00047 class csBlockAllocator
00048 {
00049 private:
00050
00051 struct csFreeList
00052 {
00053 csFreeList* next;
00054 uint32 numfree;
00055 };
00056
00057
00058 struct csBlock
00059 {
00060 void* memory;
00061 csFreeList* firstfree;
00062 csBlock () : memory (0) { }
00063 ~csBlock () { if (memory) free (memory); }
00064 };
00065
00066 csArray<csBlock> blocks;
00067 unsigned int size;
00068 unsigned int elsize;
00069 unsigned int blocksize;
00070
00071
00072 int firstfreeblock;
00073
00077 int FindBlock (void* m)
00078 {
00079 int i;
00080 for (i = 0 ; i < blocks.Length () ; i++)
00081 {
00082 csBlock* b = &blocks[i];
00083 if (b->memory <= m)
00084 {
00085 char* eb = ((char*)b->memory) + blocksize;
00086 if (((char*)m) < eb)
00087 return i;
00088 }
00089 }
00090 return -1;
00091 }
00092
00097 void FindAndUpdateFreeBlock ()
00098 {
00099 ++firstfreeblock;
00100 while (firstfreeblock < blocks.Length ()
00101 && blocks[firstfreeblock].firstfree == 0)
00102 ++firstfreeblock;
00103
00104 if (firstfreeblock == blocks.Length ())
00105 {
00106 firstfreeblock = blocks.Push (csBlock ());
00107 csBlock& bl = blocks[firstfreeblock];
00108 bl.memory = (void*)malloc (blocksize);
00109 bl.firstfree = (csFreeList*)bl.memory;
00110 bl.firstfree->next = 0;
00111 bl.firstfree->numfree = size;
00112 }
00113 }
00114
00115 public:
00121 csBlockAllocator (int s)
00122 {
00123 size = s;
00124 elsize = sizeof (T);
00125 if (elsize < sizeof (csFreeList)) elsize = sizeof (csFreeList);
00126 blocksize = elsize * size;
00127
00128 int idx = blocks.Push (csBlock ());
00129 csBlock& bl = blocks[idx];
00130 bl.memory = (void*)malloc (blocksize);
00131 bl.firstfree = (csFreeList*)bl.memory;
00132 bl.firstfree->next = 0;
00133 bl.firstfree->numfree = size;
00134
00135 firstfreeblock = 0;
00136 }
00137
00144 ~csBlockAllocator ()
00145 {
00146 #ifdef CS_DEBUG
00147 CS_ASSERT (firstfreeblock == 0);
00148 int i;
00149 for (i = 0 ; i < blocks.Length () ; i++)
00150 {
00151 CS_ASSERT (blocks[i].firstfree == (csFreeList*)blocks[i].memory);
00152 CS_ASSERT (blocks[i].firstfree->next == 0);
00153 CS_ASSERT (blocks[i].firstfree->numfree == size);
00154 }
00155 #endif
00156 }
00157
00161 T* Alloc ()
00162 {
00163
00164 csBlock& freebl = blocks[firstfreeblock];
00165 void* ptr = (void*)(freebl.firstfree);
00166
00167 if (freebl.firstfree->numfree >= 2)
00168 {
00169
00170 csFreeList* nf = (csFreeList*)(((char*)ptr)+elsize);
00171 nf->next = freebl.firstfree->next;
00172 nf->numfree = freebl.firstfree->numfree-1;
00173 freebl.firstfree = nf;
00174 }
00175 else
00176 {
00177
00178 freebl.firstfree = freebl.firstfree->next;
00179 if (!freebl.firstfree)
00180 {
00181
00182 FindAndUpdateFreeBlock ();
00183 }
00184 }
00185
00186 return new (ptr) T ();
00187 }
00188
00192 void Free (T* el)
00193 {
00194 if (!el) return;
00195
00196 int idx = FindBlock ((void*)el);
00197 CS_ASSERT (idx != -1);
00198
00199 el->T::~T();
00200
00201 #ifdef CS_BLOCKALLOC_DEBUG
00202 memset (el, 0xfb, elsize);
00203 #endif
00204
00205
00206
00207 if (idx < firstfreeblock)
00208 firstfreeblock = idx;
00209
00210 csBlock& bl = blocks[idx];
00211 if (bl.firstfree == 0)
00212 {
00213
00214
00215 bl.firstfree = (csFreeList*)el;
00216 bl.firstfree->next = 0;
00217 bl.firstfree->numfree = 1;
00218 }
00219 else
00220 {
00221 csFreeList* p_el = (csFreeList*)el;
00222
00223 if (p_el < bl.firstfree)
00224 {
00225
00226 if (((char*)bl.firstfree) - ((char*)p_el) == (int)elsize)
00227 {
00228
00229
00230 p_el->next = bl.firstfree->next;
00231 p_el->numfree = bl.firstfree->numfree+1;
00232 }
00233 else
00234 {
00235
00236 p_el->next = bl.firstfree;
00237 p_el->numfree = 1;
00238 }
00239
00240 bl.firstfree = p_el;
00241 }
00242 else
00243 {
00244
00245
00246
00247 csFreeList* fl_before = bl.firstfree;
00248 csFreeList* fl_after = bl.firstfree->next;
00249 while (fl_after != 0 && fl_after < p_el)
00250 {
00251 fl_before = fl_after;
00252 fl_after = fl_after->next;
00253 }
00254
00255
00256
00257
00258 char* fl_before_end = ((char*)fl_before) + fl_before->numfree * elsize;
00259
00260 if (!fl_after)
00261 {
00262
00263
00264
00265 if (fl_before_end == (char*)p_el)
00266 {
00267
00268 ++(fl_before->numfree);
00269 }
00270 else
00271 {
00272
00273 p_el->next = 0;
00274 p_el->numfree = 1;
00275 fl_before->next = p_el;
00276 }
00277 }
00278 else
00279 {
00280
00281
00282
00283 if (fl_before_end == (char*)p_el
00284 && ((char*)p_el) + elsize == (char*)fl_after)
00285 {
00286
00287 fl_before->next = fl_after->next;
00288 fl_before->numfree = fl_before->numfree + 1 + fl_after->numfree;
00289 }
00290 else if (fl_before_end == (char*)p_el)
00291 {
00292
00293 ++(fl_before->numfree);
00294 }
00295 else if (((char*)p_el) + elsize == (char*)fl_after)
00296 {
00297
00298 fl_before->next = p_el;
00299 p_el->next = fl_after->next;
00300 p_el->numfree = fl_after->numfree+1;
00301 }
00302 else
00303 {
00304
00305 fl_before->next = p_el;
00306 p_el->next = fl_after;
00307 p_el->numfree = 1;
00308 }
00309 }
00310 }
00311 }
00312 }
00313
00317 void Dump ()
00318 {
00319 int i;
00320 printf ("=============================\nelsize = %d\n", elsize);
00321 for (i = 0 ; i < blocks.Length () ; i++)
00322 {
00323 printf ("Block %d\n", i);
00324 csFreeList* fl = blocks[i].firstfree;
00325 char* m = (char*)blocks[i].memory;
00326 while (fl)
00327 {
00328 printf (" free %d %d\n", (((char*)fl) - m) / elsize, fl->numfree);
00329 fl = fl->next;
00330 }
00331 }
00332 printf ("=============================\n");
00333 fflush (stdout);
00334 }
00335 };
00336
00337 #ifdef CS_EXTENSIVE_MEMDEBUG
00338 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00339 #endif
00340
00341 #endif
00342