csutil/blockallocator.h
00001 /* 00002 Crystal Space Generic Memory Block Allocator 00003 Copyright (C) 2003 by Jorrit Tyberghein 00004 00005 This library is free software; you can redistribute it and/or 00006 modify it under the terms of the GNU Library General Public 00007 License as published by the Free Software Foundation; either 00008 version 2 of the License, or (at your option) any later version. 00009 00010 This library is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 Library General Public License for more details. 00014 00015 You should have received a copy of the GNU Library General Public 00016 License along with this library; if not, write to the Free 00017 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00018 */ 00019 #ifndef __CSUTIL_BLKALLOC_H__ 00020 #define __CSUTIL_BLKALLOC_H__ 00021 00022 #include "csextern.h" 00023 #include "array.h" 00024 00025 // hack: work around problems caused by #defining 'new' 00026 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 00027 # undef new 00028 #endif 00029 #include <new> 00030 00031 #ifdef CS_MEMORY_TRACKER 00032 #include "csutil/memdebug.h" 00033 #include <typeinfo> 00034 #endif 00035 00052 template <class T> 00053 class csBlockAllocator 00054 { 00055 private: 00056 // A dummy structure for a linked list of free items. 00057 struct csFreeList 00058 { 00059 csFreeList* next; 00060 uint32 numfree; // Free elements in this block. 00061 }; 00062 00063 // A memory block (a series of 'size' objects). 00064 struct csBlock 00065 { 00066 void* memory; 00067 csFreeList* firstfree; // Linked list of free items in this block. 00068 csBlock () : memory (0) { } 00069 ~csBlock () 00070 { 00071 if (memory) 00072 { 00073 # ifdef CS_MEMORY_TRACKER 00074 int32* ptr = ((int32*)memory)-2; 00075 mtiRegisterFree ((MemTrackerInfo*)*ptr, (size_t)ptr[1]); 00076 free (ptr); 00077 # else 00078 free (memory); 00079 # endif 00080 } 00081 } 00082 }; 00083 00084 csArray<csBlock> blocks; 00085 unsigned int size; // Number of elements per block. 00086 unsigned int elsize; // Element size (bigger than 8). 00087 unsigned int blocksize; // Size in bytes per block. 00088 00089 // First block that contains a free element. 00090 int firstfreeblock; 00091 00095 int FindBlock (void* m) 00096 { 00097 int i; 00098 for (i = 0 ; i < blocks.Length () ; i++) 00099 { 00100 csBlock* b = &blocks[i]; 00101 if (b->memory <= m) 00102 { 00103 char* eb = ((char*)b->memory) + blocksize; 00104 if (((char*)m) < eb) 00105 return i; 00106 } 00107 } 00108 return -1; 00109 } 00110 00115 void FindAndUpdateFreeBlock () 00116 { 00117 ++firstfreeblock; 00118 while (firstfreeblock < blocks.Length () 00119 && blocks[firstfreeblock].firstfree == 0) 00120 ++firstfreeblock; 00121 00122 if (firstfreeblock == blocks.Length ()) 00123 { 00124 firstfreeblock = blocks.Push (csBlock ()); 00125 csBlock& bl = blocks[firstfreeblock]; 00126 # ifdef CS_MEMORY_TRACKER 00127 char buf[255]; 00128 sprintf (buf, "csBlockAllocator<%s>", typeid (T).name()); 00129 int32* ptr = (int32*)malloc (blocksize + sizeof (int32)*2); 00130 *ptr++ = (int32)mtiRegisterAlloc (blocksize, buf); 00131 *ptr++ = blocksize; 00132 bl.memory = (void*)ptr; 00133 # else 00134 bl.memory = (void*)malloc (blocksize); 00135 # endif 00136 bl.firstfree = (csFreeList*)bl.memory; 00137 bl.firstfree->next = 0; 00138 bl.firstfree->numfree = size; 00139 } 00140 } 00141 00142 public: 00148 csBlockAllocator (int s) 00149 { 00150 size = s; 00151 elsize = sizeof (T); 00152 if (elsize < sizeof (csFreeList)) elsize = sizeof (csFreeList); 00153 blocksize = elsize * size; 00154 00155 int idx = blocks.Push (csBlock ()); 00156 csBlock& bl = blocks[idx]; 00157 # ifdef CS_MEMORY_TRACKER 00158 char buf[255]; 00159 sprintf (buf, "csBlockAllocator<%s>", typeid (T).name()); 00160 int32* ptr = (int32*)malloc (blocksize + sizeof (int32)*2); 00161 *ptr++ = (int32)mtiRegisterAlloc (blocksize, buf); 00162 *ptr++ = blocksize; 00163 bl.memory = (void*)ptr; 00164 # else 00165 bl.memory = (void*)malloc (blocksize); 00166 #endif 00167 bl.firstfree = (csFreeList*)bl.memory; 00168 bl.firstfree->next = 0; 00169 bl.firstfree->numfree = size; 00170 00171 firstfreeblock = 0; 00172 } 00173 00180 ~csBlockAllocator () 00181 { 00182 #ifdef CS_DEBUG 00183 CS_ASSERT (firstfreeblock == 0); 00184 int i; 00185 for (i = 0 ; i < blocks.Length () ; i++) 00186 { 00187 CS_ASSERT (blocks[i].firstfree == (csFreeList*)blocks[i].memory); 00188 CS_ASSERT (blocks[i].firstfree->next == 0); 00189 CS_ASSERT (blocks[i].firstfree->numfree == size); 00190 } 00191 #endif 00192 } 00193 00198 void Compact () 00199 { 00200 int i = blocks.Length ()-1; 00201 while (i > firstfreeblock) 00202 { 00203 if (blocks[i].firstfree == (csFreeList*)blocks[i].memory && 00204 blocks[i].firstfree->next == 0) 00205 blocks.DeleteIndex (i); 00206 i--; 00207 } 00208 } 00209 00213 T* Alloc () 00214 { 00215 // This routine makes sure there is ALWAYS free space available. 00216 csBlock& freebl = blocks[firstfreeblock]; 00217 void* ptr = (void*)(freebl.firstfree); 00218 00219 if (freebl.firstfree->numfree >= 2) 00220 { 00221 // Still room in this block after allocation. 00222 csFreeList* nf = (csFreeList*)(((char*)ptr)+elsize); 00223 nf->next = freebl.firstfree->next; 00224 nf->numfree = freebl.firstfree->numfree-1; 00225 freebl.firstfree = nf; 00226 } 00227 else 00228 { 00229 // We need a new block later. 00230 freebl.firstfree = freebl.firstfree->next; 00231 if (!freebl.firstfree) 00232 { 00233 // This block has no more free space. We need a new one. 00234 FindAndUpdateFreeBlock (); 00235 } 00236 } 00237 00238 return new (ptr) T; 00239 } 00240 00244 void Free (T* el) 00245 { 00246 if (!el) return; 00247 00248 int idx = FindBlock ((void*)el); 00249 CS_ASSERT (idx != -1); 00250 00251 el->~T(); 00252 00253 #ifdef CS_BLOCKALLOC_DEBUG 00254 memset (el, 0xfb, elsize); 00255 #endif 00256 00257 // If the index is lower than the index of the first free block 00258 // then we update the firstfreeblock index. 00259 if (idx < firstfreeblock) 00260 firstfreeblock = idx; 00261 00262 csBlock& bl = blocks[idx]; 00263 if (bl.firstfree == 0) 00264 { 00265 // Block has no free items so we create the first free item 00266 // here. 00267 bl.firstfree = (csFreeList*)el; 00268 bl.firstfree->next = 0; 00269 bl.firstfree->numfree = 1; 00270 } 00271 else 00272 { 00273 csFreeList* p_el = (csFreeList*)el; 00274 00275 if (p_el < bl.firstfree) 00276 { 00277 // New free element is before the current free element. 00278 if (((char*)bl.firstfree) - ((char*)p_el) == (int)elsize) 00279 { 00280 // New free element is directly before the current free 00281 // element. 00282 p_el->next = bl.firstfree->next; 00283 p_el->numfree = bl.firstfree->numfree+1; 00284 } 00285 else 00286 { 00287 // There is a gap. 00288 p_el->next = bl.firstfree; 00289 p_el->numfree = 1; 00290 } 00291 00292 bl.firstfree = p_el; 00293 } 00294 else 00295 { 00296 // New free element is after the current free element. 00297 // First we find the two free blocks that enclose the new 00298 // free element. 00299 csFreeList* fl_before = bl.firstfree; 00300 csFreeList* fl_after = bl.firstfree->next; 00301 while (fl_after != 0 && fl_after < p_el) 00302 { 00303 fl_before = fl_after; 00304 fl_after = fl_after->next; 00305 } 00306 00307 // 'fl_before_end' points to the memory right after the free block 00308 // that is directly before the new free element. We use 00309 // 'fl_before_end' later. 00310 char* fl_before_end = ((char*)fl_before) + fl_before->numfree * elsize; 00311 00312 if (!fl_after) 00313 { 00314 // The new free element is after the last free block. First check 00315 // if the new free element directly follows that free block. 00316 // If so we can extend that. 00317 if (fl_before_end == (char*)p_el) 00318 { 00319 // Yes, extend. 00320 ++(fl_before->numfree); 00321 } 00322 else 00323 { 00324 // No, we have to create a new free block. 00325 p_el->next = 0; 00326 p_el->numfree = 1; 00327 fl_before->next = p_el; 00328 } 00329 } 00330 else 00331 { 00332 // We have a block before and after the new free block. 00333 // First we check if the new free item exactly between 00334 // fl_before and fl_after. 00335 if (fl_before_end == (char*)p_el 00336 && ((char*)p_el) + elsize == (char*)fl_after) 00337 { 00338 // Perfect fit, merge fl_before and fl_after. 00339 fl_before->next = fl_after->next; 00340 fl_before->numfree = fl_before->numfree + 1 + fl_after->numfree; 00341 } 00342 else if (fl_before_end == (char*)p_el) 00343 { 00344 // New free item fits directly after fl_before. 00345 ++(fl_before->numfree); 00346 } 00347 else if (((char*)p_el) + elsize == (char*)fl_after) 00348 { 00349 // New free item fits directly before fl_after. 00350 fl_before->next = p_el; 00351 p_el->next = fl_after->next; 00352 p_el->numfree = fl_after->numfree+1; 00353 } 00354 else 00355 { 00356 // We need a new free block. 00357 fl_before->next = p_el; 00358 p_el->next = fl_after; 00359 p_el->numfree = 1; 00360 } 00361 } 00362 } 00363 } 00364 } 00365 00369 void Dump () 00370 { 00371 int i; 00372 printf ("=============================\nelsize = %d\n", elsize); 00373 for (i = 0 ; i < blocks.Length () ; i++) 00374 { 00375 printf ("Block %d\n", i); 00376 csFreeList* fl = blocks[i].firstfree; 00377 char* m = (char*)blocks[i].memory; 00378 while (fl) 00379 { 00380 printf (" free %d %d\n", (((char*)fl) - m) / elsize, fl->numfree); 00381 fl = fl->next; 00382 } 00383 } 00384 printf ("=============================\n"); 00385 fflush (stdout); 00386 } 00387 }; 00388 00389 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 00390 # define new CS_EXTENSIVE_MEMDEBUG_NEW 00391 #endif 00392 00393 #endif 00394
Generated for Crystal Space by doxygen 1.2.18