csutil/fixedsizeallocator.h
Go to the documentation of this file.00001 /* 00002 Crystal Space Fixed Size Block Allocator 00003 Copyright (C) 2005 by Eric Sunshine <sunshine@sunshineco.com> 00004 (C) 2006 by Frank Richter 00005 00006 This library is free software; you can redistribute it and/or 00007 modify it under the terms of the GNU Library General Public 00008 License as published by the Free Software Foundation; either 00009 version 2 of the License, or (at your option) any later version. 00010 00011 This library is distributed in the hope that it will be useful, 00012 but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 Library General Public License for more details. 00015 00016 You should have received a copy of the GNU Library General Public 00017 License along with this library; if not, write to the Free 00018 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00019 */ 00020 #ifndef __CSUTIL_FIXEDSIZEALLOCATOR_H__ 00021 #define __CSUTIL_FIXEDSIZEALLOCATOR_H__ 00022 00027 #include "csextern.h" 00028 #include "csutil/array.h" 00029 #include "csutil/bitarray.h" 00030 #include "csutil/sysfunc.h" 00031 00032 #ifdef CS_DEBUG 00033 #include <typeinfo> 00034 #endif 00035 00036 #if defined(CS_DEBUG) && !defined(CS_FIXEDSIZEALLOC_DEBUG) 00037 #define _CS_FIXEDSIZEALLOC_DEBUG_DEFAULTED 00038 #define CS_FIXEDSIZEALLOC_DEBUG 00039 #endif 00040 00059 template <size_t Size, class Allocator = CS::Memory::AllocatorMalloc> 00060 class csFixedSizeAllocator 00061 { 00062 public: 00063 typedef csFixedSizeAllocator<Size, Allocator> ThisType; 00064 typedef Allocator AllocatorType; 00065 00066 protected: // 'protected' allows access by test-suite. 00067 struct FreeNode 00068 { 00069 FreeNode* next; 00070 }; 00071 00072 struct BlockKey 00073 { 00074 uint8 const* addr; 00075 size_t blocksize; 00076 BlockKey(uint8 const* p, size_t n) : addr(p), blocksize(n) {} 00077 }; 00078 00079 struct BlocksWrapper : public Allocator 00080 { 00081 csArray<uint8*> b; 00082 00083 BlocksWrapper () {} 00084 BlocksWrapper (const Allocator& alloc) : Allocator (alloc) {} 00085 }; 00087 BlocksWrapper blocks; 00089 size_t elcount; 00091 size_t elsize; 00093 size_t blocksize; 00095 FreeNode* freenode; 00101 bool insideDisposeAll; 00102 00109 static int FuzzyCmp(uint8* const& block, BlockKey const& k) 00110 { 00111 return (block + k.blocksize <= k.addr ? -1 : (block > k.addr ? 1 : 0)); 00112 } 00113 00117 size_t FindBlock(void const* m) const 00118 { 00119 return blocks.b.FindSortedKey( 00120 csArrayCmp<uint8*,BlockKey>(BlockKey((uint8*)m, blocksize), FuzzyCmp)); 00121 } 00122 00128 uint8* AllocBlock() 00129 { 00130 uint8* block = (uint8*)blocks.Alloc (blocksize); 00131 00132 // Build the free-node chain (all nodes are free in the new block). 00133 FreeNode* nextfree = 0; 00134 uint8* node = block + (elcount - 1) * elsize; 00135 for ( ; node >= block; node -= elsize) 00136 { 00137 FreeNode* slot = (FreeNode*)node; 00138 slot->next = nextfree; 00139 nextfree = slot; 00140 } 00141 CS_ASSERT((uint8*)nextfree == block); 00142 return block; 00143 } 00144 00148 void FreeBlock(uint8* p) 00149 { 00150 blocks.Free (p); 00151 } 00152 00156 template<typename Disposer> 00157 void DestroyObject (Disposer& disposer, void* p) const 00158 { 00159 disposer.Dispose (p); 00160 #ifdef CS_FIXEDSIZEALLOC_DEBUG 00161 memset (p, 0xfb, elsize); 00162 #endif 00163 } 00164 00169 csBitArray GetAllocationMap() const 00170 { 00171 csBitArray mask(elcount * blocks.b.GetSize()); 00172 mask.FlipAllBits(); 00173 for (FreeNode* p = freenode; p != 0; p = p->next) 00174 { 00175 size_t const n = FindBlock(p); 00176 CS_ASSERT(n != csArrayItemNotFound); 00177 size_t const slot = ((uint8*)p - blocks.b[n]) / elsize; // Slot in block. 00178 mask.ClearBit(n * elcount + slot); 00179 } 00180 return mask; 00181 } 00182 00184 class DefaultDisposer 00185 { 00186 #ifdef CS_DEBUG 00187 bool doWarn; 00188 const char* parentClass; 00189 const void* parent; 00190 size_t count; 00191 #endif 00192 public: 00193 #ifdef CS_DEBUG 00194 template<typename BA> 00195 DefaultDisposer (const BA& ba, bool legit) : 00196 doWarn (!legit), parentClass (typeid(BA).name()), parent (&ba), 00197 count (0) 00198 { 00199 } 00200 #else 00201 template<typename BA> 00202 DefaultDisposer (const BA&, bool legit) 00203 { (void)legit; } 00204 #endif 00205 ~DefaultDisposer() 00206 { 00207 #ifdef CS_DEBUG 00208 if ((count > 0) && doWarn) 00209 { 00210 csPrintfErr("%s %p leaked %zu objects.\n", parentClass, (void*)this, 00211 count); 00212 } 00213 #endif 00214 } 00215 void Dispose (void* /*p*/) 00216 { 00217 #ifdef CS_DEBUG 00218 count++; 00219 #endif 00220 } 00221 }; 00227 template<typename Disposer> 00228 void DisposeAll(Disposer& disposer) 00229 { 00230 insideDisposeAll = true; 00231 csBitArray const mask(GetAllocationMap()); 00232 size_t node = 0; 00233 for (size_t b = 0, bN = blocks.b.GetSize(); b < bN; b++) 00234 { 00235 for (uint8 *p = blocks.b[b], *pN = p + blocksize; p < pN; p += elsize) 00236 if (mask.IsBitSet(node++)) 00237 DestroyObject (disposer, p); 00238 FreeBlock(blocks.b[b]); 00239 } 00240 blocks.b.DeleteAll(); 00241 freenode = 0; 00242 insideDisposeAll = false; 00243 } 00244 00250 template<typename Disposer> 00251 void Free (Disposer& disposer, void* p) 00252 { 00253 if (p != 0 && !insideDisposeAll) 00254 { 00255 CS_ASSERT(FindBlock(p) != csArrayItemNotFound); 00256 DestroyObject (disposer, p); 00257 FreeNode* f = (FreeNode*)p; 00258 f->next = freenode; 00259 freenode = f; 00260 } 00261 } 00268 template<typename Disposer> 00269 bool TryFree (Disposer& disposer, void* p) 00270 { 00271 if (p != 0 && !insideDisposeAll) 00272 { 00273 if (FindBlock(p) == csArrayItemNotFound) return false; 00274 DestroyObject (disposer, p); 00275 FreeNode* f = (FreeNode*)p; 00276 f->next = freenode; 00277 freenode = f; 00278 } 00279 return true; 00280 } 00281 00283 void* AllocCommon () 00284 { 00285 if (insideDisposeAll) 00286 { 00287 csPrintfErr("ERROR: csFixedSizeAllocator(%p) tried to allocate memory " 00288 "while inside DisposeAll()", (void*)this); 00289 CS_ASSERT(false); 00290 } 00291 00292 if (freenode == 0) 00293 { 00294 uint8* p = AllocBlock(); 00295 blocks.b.InsertSorted(p); 00296 freenode = (FreeNode*)p; 00297 } 00298 void* const node = freenode; 00299 freenode = freenode->next; 00300 #ifdef CS_FIXEDSIZEALLOC_DEBUG 00301 memset (node, 0xfa, elsize); 00302 #endif 00303 return node; 00304 } 00305 private: 00306 void operator= (csFixedSizeAllocator const&); // Illegal; unimplemented. 00307 public: 00309 00319 csFixedSizeAllocator (size_t nelem = 32) : 00320 elcount (nelem), elsize(Size), freenode(0), insideDisposeAll(false) 00321 { 00322 #ifdef CS_MEMORY_TRACKER 00323 blocks.SetMemTrackerInfo (typeid(*this).name()); 00324 #endif 00325 if (elsize < sizeof (FreeNode)) 00326 elsize = sizeof (FreeNode); 00327 blocksize = elsize * elcount; 00328 } 00329 csFixedSizeAllocator (size_t nelem, const Allocator& alloc) : blocks (alloc), 00330 elcount (nelem), elsize(Size), freenode(0), insideDisposeAll(false) 00331 { 00332 #ifdef CS_MEMORY_TRACKER 00333 blocks.SetMemTrackerInfo (typeid(*this).name()); 00334 #endif 00335 if (elsize < sizeof (FreeNode)) 00336 elsize = sizeof (FreeNode); 00337 blocksize = elsize * elcount; 00338 } 00340 00348 csFixedSizeAllocator (csFixedSizeAllocator const& other) : 00349 elcount (other.elcount), elsize (other.elsize), 00350 blocksize (other.blocksize), freenode (0), insideDisposeAll (false) 00351 { 00352 /* Technically, an allocator can be empty even with freenode != 0 */ 00353 CS_ASSERT(other.freenode == 0); 00354 } 00355 00359 ~csFixedSizeAllocator() 00360 { 00361 DefaultDisposer disposer (*this, false); 00362 DisposeAll (disposer); 00363 } 00364 00370 void Empty() 00371 { 00372 DefaultDisposer disposer (*this, true); 00373 DisposeAll (disposer); 00374 } 00375 00380 void Compact() 00381 { 00382 if (insideDisposeAll) return; 00383 00384 bool compacted = false; 00385 csBitArray mask(GetAllocationMap()); 00386 for (size_t b = blocks.b.GetSize(); b-- > 0; ) 00387 { 00388 size_t const node = b * elcount; 00389 if (!mask.AreSomeBitsSet(node, elcount)) 00390 { 00391 FreeBlock(blocks.b[b]); 00392 blocks.b.DeleteIndex(b); 00393 mask.Delete(node, elcount); 00394 compacted = true; 00395 } 00396 } 00397 00398 // If blocks were deleted, then free-node chain broke, so rebuild it. 00399 if (compacted) 00400 { 00401 FreeNode* nextfree = 0; 00402 size_t const bN = blocks.b.GetSize(); 00403 size_t node = bN * elcount; 00404 for (size_t b = bN; b-- > 0; ) 00405 { 00406 uint8* const p0 = blocks.b[b]; 00407 for (uint8* p = p0 + (elcount - 1) * elsize; p >= p0; p -= elsize) 00408 { 00409 if (!mask.IsBitSet(--node)) 00410 { 00411 FreeNode* slot = (FreeNode*)p; 00412 slot->next = nextfree; 00413 nextfree = slot; 00414 } 00415 } 00416 } 00417 freenode = nextfree; 00418 } 00419 } 00420 00424 void* Alloc () 00425 { 00426 return AllocCommon(); 00427 } 00428 00433 void Free (void* p) 00434 { 00435 DefaultDisposer disposer (*this, true); 00436 Free (disposer, p); 00437 } 00444 bool TryFree (void* p) 00445 { 00446 DefaultDisposer disposer (*this, true); 00447 return TryFree (disposer, p); 00448 } 00450 size_t GetBlockElements() const { return elcount; } 00451 00454 void* Alloc (size_t n) 00455 { 00456 CS_ASSERT (n == Size); 00457 return Alloc(); 00458 } 00459 void* Alloc (void* p, size_t newSize) 00460 { 00461 CS_ASSERT (newSize == Size); 00462 return p; 00463 } 00464 void SetMemTrackerInfo (const char* /*info*/) { } 00466 }; 00467 00470 #ifdef _CS_FIXEDSIZEALLOC_DEBUG_DEFAULTED 00471 #undef CS_FIXEDSIZEALLOC_DEBUG 00472 #undef _CS_FIXEDSIZEALLOC_DEBUG_DEFAULTED 00473 #endif 00474 00475 #endif // __CSUTIL_FIXEDSIZEALLOCATOR_H__
Generated for Crystal Space 1.2.1 by doxygen 1.5.3