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 "array.h" 00023 00024 // hack: work around problems caused by #defining 'new' 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 // A dummy structure for a linked list of free items. 00051 struct csFreeList 00052 { 00053 csFreeList* next; 00054 uint32 numfree; // Free elements in this block. 00055 }; 00056 00057 // A memory block (a series of 'size' objects). 00058 struct csBlock 00059 { 00060 void* memory; 00061 csFreeList* firstfree; // Linked list of free items in this block. 00062 csBlock () : memory (0) { } 00063 ~csBlock () { if (memory) free (memory); } 00064 }; 00065 00066 csArray<csBlock> blocks; 00067 unsigned int size; // Number of elements per block. 00068 unsigned int elsize; // Element size (bigger than 8). 00069 unsigned int blocksize; // Size in bytes per block. 00070 00071 // First block that contains a free element. 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 // This routine makes sure there is ALWAYS free space available. 00164 csBlock& freebl = blocks[firstfreeblock]; 00165 void* ptr = (void*)(freebl.firstfree); 00166 00167 if (freebl.firstfree->numfree >= 2) 00168 { 00169 // Still room in this block after allocation. 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 // We need a new block later. 00178 freebl.firstfree = freebl.firstfree->next; 00179 if (!freebl.firstfree) 00180 { 00181 // This block has no more free space. We need a new one. 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(); 00200 00201 #ifdef CS_BLOCKALLOC_DEBUG 00202 memset (el, 0xfb, elsize); 00203 #endif 00204 00205 // If the index is lower than the index of the first free block 00206 // then we update the firstfreeblock index. 00207 if (idx < firstfreeblock) 00208 firstfreeblock = idx; 00209 00210 csBlock& bl = blocks[idx]; 00211 if (bl.firstfree == 0) 00212 { 00213 // Block has no free items so we create the first free item 00214 // here. 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 // New free element is before the current free element. 00226 if (((char*)bl.firstfree) - ((char*)p_el) == (int)elsize) 00227 { 00228 // New free element is directly before the current free 00229 // element. 00230 p_el->next = bl.firstfree->next; 00231 p_el->numfree = bl.firstfree->numfree+1; 00232 } 00233 else 00234 { 00235 // There is a gap. 00236 p_el->next = bl.firstfree; 00237 p_el->numfree = 1; 00238 } 00239 00240 bl.firstfree = p_el; 00241 } 00242 else 00243 { 00244 // New free element is after the current free element. 00245 // First we find the two free blocks that enclose the new 00246 // free element. 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 // 'fl_before_end' points to the memory right after the free block 00256 // that is directly before the new free element. We use 00257 // 'fl_before_end' later. 00258 char* fl_before_end = ((char*)fl_before) + fl_before->numfree * elsize; 00259 00260 if (!fl_after) 00261 { 00262 // The new free element is after the last free block. First check 00263 // if the new free element directly follows that free block. 00264 // If so we can extend that. 00265 if (fl_before_end == (char*)p_el) 00266 { 00267 // Yes, extend. 00268 ++(fl_before->numfree); 00269 } 00270 else 00271 { 00272 // No, we have to create a new free block. 00273 p_el->next = 0; 00274 p_el->numfree = 1; 00275 fl_before->next = p_el; 00276 } 00277 } 00278 else 00279 { 00280 // We have a block before and after the new free block. 00281 // First we check if the new free item exactly between 00282 // fl_before and fl_after. 00283 if (fl_before_end == (char*)p_el 00284 && ((char*)p_el) + elsize == (char*)fl_after) 00285 { 00286 // Perfect fit, merge fl_before and fl_after. 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 // New free item fits directly after fl_before. 00293 ++(fl_before->numfree); 00294 } 00295 else if (((char*)p_el) + elsize == (char*)fl_after) 00296 { 00297 // New free item fits directly before fl_after. 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 // We need a new free block. 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
Generated for Crystal Space by doxygen 1.2.18