Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages
blockallocator.h
Go to the documentation of this file.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 00026 #include "csextern.h" 00027 #include "array.h" 00028 00029 // hack: work around problems caused by #defining 'new' 00030 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 00031 # undef new 00032 #endif 00033 #include <new> 00034 00035 #ifdef CS_MEMORY_TRACKER 00036 #include "csutil/memdebug.h" 00037 #include <typeinfo> 00038 #endif 00039 00056 template <class T> 00057 class csBlockAllocator 00058 { 00059 private: 00060 // A dummy structure for a linked list of free items. 00061 struct csFreeList 00062 { 00063 csFreeList* next; 00064 size_t numfree; // Free elements in this block. 00065 }; 00066 00067 // A memory block (a series of 'size' objects). 00068 struct csBlock 00069 { 00070 void* memory; 00071 csFreeList* firstfree; // Linked list of free items in this block. 00072 csBlock () : memory (0), firstfree (0) {} 00073 ~csBlock () 00074 { 00075 if (memory) 00076 { 00077 # ifdef CS_MEMORY_TRACKER 00078 int32* ptr = ((int32*)memory)-2; 00079 mtiRegisterFree ((MemTrackerInfo*)*ptr, (size_t)ptr[1]); 00080 free (ptr); 00081 # else 00082 free (memory); 00083 # endif 00084 } 00085 } 00086 }; 00087 00088 csArray<csBlock> blocks; 00089 size_t size; // Number of elements per block. 00090 size_t elsize; // Element size (bigger than 8). 00091 size_t blocksize; // Size in bytes per block. 00092 00093 // First block that contains a free element. 00094 size_t firstfreeblock; 00095 00099 size_t FindBlock (void* m) 00100 { 00101 size_t i; 00102 for (i = 0 ; i < blocks.Length () ; i++) 00103 { 00104 csBlock* b = &blocks[i]; 00105 if (b->memory <= m) 00106 { 00107 char* eb = ((char*)b->memory) + blocksize; 00108 if (((char*)m) < eb) 00109 return i; 00110 } 00111 } 00112 return (size_t)-1; 00113 } 00114 00119 void FindAndUpdateFreeBlock () 00120 { 00121 CS_ASSERT (blocks.Length() != 0); 00122 ++firstfreeblock; 00123 while (firstfreeblock < blocks.Length () 00124 && blocks[firstfreeblock].firstfree == 0) 00125 ++firstfreeblock; 00126 00127 if (firstfreeblock == blocks.Length ()) 00128 { 00129 firstfreeblock = blocks.Push (csBlock ()); 00130 csBlock& bl = blocks[firstfreeblock]; 00131 # ifdef CS_MEMORY_TRACKER 00132 char buf[255]; 00133 sprintf (buf, "csBlockAllocator<%s>", typeid (T).name()); 00134 int32* ptr = (int32*)malloc (blocksize + sizeof (int32)*2); 00135 *ptr++ = (int32)mtiRegisterAlloc (blocksize, buf); 00136 *ptr++ = blocksize; 00137 bl.memory = (void*)ptr; 00138 # else 00139 bl.memory = (void*)malloc (blocksize); 00140 # endif 00141 bl.firstfree = (csFreeList*)bl.memory; 00142 bl.firstfree->next = 0; 00143 bl.firstfree->numfree = size; 00144 } 00145 } 00146 00147 public: 00153 csBlockAllocator (size_t s) 00154 { 00155 size = s; 00156 elsize = sizeof (T); 00157 if (elsize < sizeof (csFreeList)) elsize = sizeof (csFreeList); 00158 blocksize = elsize * size; 00159 00160 size_t idx = blocks.Push (csBlock ()); 00161 csBlock& bl = blocks[idx]; 00162 # ifdef CS_MEMORY_TRACKER 00163 char buf[255]; 00164 sprintf (buf, "csBlockAllocator<%s>", typeid (T).name()); 00165 int32* ptr = (int32*)malloc (blocksize + sizeof (int32)*2); 00166 *ptr++ = (int32)mtiRegisterAlloc (blocksize, buf); 00167 *ptr++ = blocksize; 00168 bl.memory = (void*)ptr; 00169 # else 00170 bl.memory = (void*)malloc (blocksize); 00171 #endif 00172 bl.firstfree = (csFreeList*)bl.memory; 00173 bl.firstfree->next = 0; 00174 bl.firstfree->numfree = size; 00175 00176 firstfreeblock = 0; 00177 } 00178 00185 ~csBlockAllocator () 00186 { 00187 #ifdef CS_DEBUG 00188 CS_ASSERT (firstfreeblock == 0); 00189 size_t i; 00190 for (i = 0 ; i < blocks.Length () ; i++) 00191 { 00192 CS_ASSERT (blocks[i].firstfree == (csFreeList*)blocks[i].memory); 00193 CS_ASSERT (blocks[i].firstfree->next == 0); 00194 CS_ASSERT (blocks[i].firstfree->numfree == size); 00195 } 00196 #endif 00197 } 00198 00203 void Compact () 00204 { 00205 CS_ASSERT (blocks.Length() != 0); 00206 size_t i = blocks.Length () - 1; 00207 while (i > firstfreeblock) 00208 { 00209 if (blocks[i].firstfree == (csFreeList*)blocks[i].memory 00210 && blocks[i].firstfree->numfree == size) 00211 { 00212 CS_ASSERT (blocks[i].firstfree->next == 0); 00213 blocks.DeleteIndex (i); 00214 } 00215 i--; 00216 } 00217 } 00218 00222 T* Alloc () 00223 { 00224 CS_ASSERT (blocks.Length() != 0); 00225 00226 // This routine makes sure there is ALWAYS free space available. 00227 csBlock& freebl = blocks[firstfreeblock]; 00228 void* ptr = (void*)(freebl.firstfree); 00229 00230 if (freebl.firstfree->numfree >= 2) 00231 { 00232 // Still room in this block after allocation. 00233 csFreeList* nf = (csFreeList*)(((char*)ptr)+elsize); 00234 nf->next = freebl.firstfree->next; 00235 nf->numfree = freebl.firstfree->numfree-1; 00236 freebl.firstfree = nf; 00237 } 00238 else 00239 { 00240 // We need a new block later. 00241 freebl.firstfree = freebl.firstfree->next; 00242 if (!freebl.firstfree) 00243 { 00244 // This block has no more free space. We need a new one. 00245 FindAndUpdateFreeBlock (); 00246 } 00247 } 00248 00249 return new (ptr) T; 00250 } 00251 00255 void Free (T* el) 00256 { 00257 if (!el) return; 00258 00259 size_t idx = FindBlock ((void*)el); 00260 CS_ASSERT_MSG ( 00261 "csBlockAllocator<>::Free() called with invalid element address", 00262 idx != (size_t)-1); 00263 00264 el->~T(); 00265 00266 #ifdef CS_BLOCKALLOC_DEBUG 00267 memset (el, 0xfb, elsize); 00268 #endif 00269 00270 // If the index is lower than the index of the first free block 00271 // then we update the firstfreeblock index. 00272 if (idx < firstfreeblock) 00273 firstfreeblock = idx; 00274 00275 csBlock& bl = blocks[idx]; 00276 if (bl.firstfree == 0) 00277 { 00278 // Block has no free items so we create the first free item 00279 // here. 00280 bl.firstfree = (csFreeList*)el; 00281 bl.firstfree->next = 0; 00282 bl.firstfree->numfree = 1; 00283 } 00284 else 00285 { 00286 csFreeList* p_el = (csFreeList*)el; 00287 00288 if (p_el < bl.firstfree) 00289 { 00290 // New free element is before the current free element. 00291 if (((char*)bl.firstfree) - ((char*)p_el) == (int)elsize) 00292 { 00293 // New free element is directly before the current free 00294 // element. 00295 p_el->next = bl.firstfree->next; 00296 p_el->numfree = bl.firstfree->numfree+1; 00297 } 00298 else 00299 { 00300 // There is a gap. 00301 p_el->next = bl.firstfree; 00302 p_el->numfree = 1; 00303 } 00304 00305 bl.firstfree = p_el; 00306 } 00307 else 00308 { 00309 // New free element is after the current free element. 00310 // First we find the two free blocks that enclose the new 00311 // free element. 00312 csFreeList* fl_before = bl.firstfree; 00313 csFreeList* fl_after = bl.firstfree->next; 00314 while (fl_after != 0 && fl_after < p_el) 00315 { 00316 fl_before = fl_after; 00317 fl_after = fl_after->next; 00318 } 00319 00320 // 'fl_before_end' points to the memory right after the free block 00321 // that is directly before the new free element. We use 00322 // 'fl_before_end' later. 00323 char* fl_before_end = ((char*)fl_before) + fl_before->numfree * elsize; 00324 00325 if (!fl_after) 00326 { 00327 // The new free element is after the last free block. First check 00328 // if the new free element directly follows that free block. 00329 // If so we can extend that. 00330 if (fl_before_end == (char*)p_el) 00331 { 00332 // Yes, extend. 00333 ++(fl_before->numfree); 00334 } 00335 else 00336 { 00337 // No, we have to create a new free block. 00338 p_el->next = 0; 00339 p_el->numfree = 1; 00340 fl_before->next = p_el; 00341 } 00342 } 00343 else 00344 { 00345 // We have a block before and after the new free block. 00346 // First we check if the new free item exactly between 00347 // fl_before and fl_after. 00348 if (fl_before_end == (char*)p_el 00349 && ((char*)p_el) + elsize == (char*)fl_after) 00350 { 00351 // Perfect fit, merge fl_before and fl_after. 00352 fl_before->next = fl_after->next; 00353 fl_before->numfree = fl_before->numfree + 1 + fl_after->numfree; 00354 } 00355 else if (fl_before_end == (char*)p_el) 00356 { 00357 // New free item fits directly after fl_before. 00358 ++(fl_before->numfree); 00359 } 00360 else if (((char*)p_el) + elsize == (char*)fl_after) 00361 { 00362 // New free item fits directly before fl_after. 00363 fl_before->next = p_el; 00364 p_el->next = fl_after->next; 00365 p_el->numfree = fl_after->numfree+1; 00366 } 00367 else 00368 { 00369 // We need a new free block. 00370 fl_before->next = p_el; 00371 p_el->next = fl_after; 00372 p_el->numfree = 1; 00373 } 00374 } 00375 } 00376 } 00377 } 00378 00382 void Dump () 00383 { 00384 int i; 00385 printf ("=============================\nelsize = %d\n", elsize); 00386 for (i = 0 ; i < blocks.Length () ; i++) 00387 { 00388 printf ("Block %d\n", i); 00389 csFreeList* fl = blocks[i].firstfree; 00390 char* m = (char*)blocks[i].memory; 00391 while (fl) 00392 { 00393 printf (" free %d %d\n", (((char*)fl) - m) / elsize, fl->numfree); 00394 fl = fl->next; 00395 } 00396 } 00397 printf ("=============================\n"); 00398 fflush (stdout); 00399 } 00400 }; 00401 00402 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 00403 # define new CS_EXTENSIVE_MEMDEBUG_NEW 00404 #endif 00405 00406 #endif
Generated for Crystal Space by doxygen 1.3.9.1