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 }; 00084 BlocksWrapper blocks; 00086 size_t elcount; 00088 size_t elsize; 00090 size_t blocksize; 00092 FreeNode* freenode; 00098 bool insideDisposeAll; 00099 00106 static int FuzzyCmp(uint8* const& block, BlockKey const& k) 00107 { 00108 return (block + k.blocksize <= k.addr ? -1 : (block > k.addr ? 1 : 0)); 00109 } 00110 00114 size_t FindBlock(void const* m) const 00115 { 00116 return blocks.b.FindSortedKey( 00117 csArrayCmp<uint8*,BlockKey>(BlockKey((uint8*)m, blocksize), FuzzyCmp)); 00118 } 00119 00125 uint8* AllocBlock() 00126 { 00127 uint8* block = (uint8*)blocks.Alloc (blocksize); 00128 00129 // Build the free-node chain (all nodes are free in the new block). 00130 FreeNode* nextfree = 0; 00131 uint8* node = block + (elcount - 1) * elsize; 00132 for ( ; node >= block; node -= elsize) 00133 { 00134 FreeNode* slot = (FreeNode*)node; 00135 slot->next = nextfree; 00136 nextfree = slot; 00137 } 00138 CS_ASSERT((uint8*)nextfree == block); 00139 return block; 00140 } 00141 00145 void FreeBlock(uint8* p) 00146 { 00147 blocks.Free (p); 00148 } 00149 00153 template<typename Disposer> 00154 void DestroyObject (Disposer& disposer, void* p) const 00155 { 00156 disposer.Dispose (p); 00157 #ifdef CS_FIXEDSIZEALLOC_DEBUG 00158 memset (p, 0xfb, elsize); 00159 #endif 00160 } 00161 00166 csBitArray GetAllocationMap() const 00167 { 00168 csBitArray mask(elcount * blocks.b.GetSize()); 00169 mask.FlipAllBits(); 00170 for (FreeNode* p = freenode; p != 0; p = p->next) 00171 { 00172 size_t const n = FindBlock(p); 00173 CS_ASSERT(n != csArrayItemNotFound); 00174 size_t const slot = ((uint8*)p - blocks.b[n]) / elsize; // Slot in block. 00175 mask.ClearBit(n * elcount + slot); 00176 } 00177 return mask; 00178 } 00179 00181 class DefaultDisposer 00182 { 00183 #ifdef CS_DEBUG 00184 bool doWarn; 00185 const char* parentClass; 00186 const void* parent; 00187 size_t count; 00188 #endif 00189 public: 00190 #ifdef CS_DEBUG 00191 template<typename BA> 00192 DefaultDisposer (const BA& ba, bool legit) : 00193 doWarn (!legit), parentClass (typeid(BA).name()), parent (&ba), 00194 count (0) 00195 { 00196 } 00197 #else 00198 template<typename BA> 00199 DefaultDisposer (const BA&, bool legit) 00200 { (void)legit; } 00201 #endif 00202 ~DefaultDisposer() 00203 { 00204 #ifdef CS_DEBUG 00205 if ((count > 0) && doWarn) 00206 { 00207 csPrintfErr("%s %p leaked %zu objects.\n", parentClass, (void*)this, 00208 count); 00209 } 00210 #endif 00211 } 00212 void Dispose (void* /*p*/) 00213 { 00214 #ifdef CS_DEBUG 00215 count++; 00216 #endif 00217 } 00218 }; 00224 template<typename Disposer> 00225 void DisposeAll(Disposer& disposer) 00226 { 00227 insideDisposeAll = true; 00228 csBitArray const mask(GetAllocationMap()); 00229 size_t node = 0; 00230 for (size_t b = 0, bN = blocks.b.GetSize(); b < bN; b++) 00231 { 00232 for (uint8 *p = blocks.b[b], *pN = p + blocksize; p < pN; p += elsize) 00233 if (mask.IsBitSet(node++)) 00234 DestroyObject (disposer, p); 00235 FreeBlock(blocks.b[b]); 00236 } 00237 blocks.b.DeleteAll(); 00238 freenode = 0; 00239 insideDisposeAll = false; 00240 } 00241 00247 template<typename Disposer> 00248 void Free (Disposer& disposer, void* p) 00249 { 00250 if (p != 0 && !insideDisposeAll) 00251 { 00252 CS_ASSERT(FindBlock(p) != csArrayItemNotFound); 00253 DestroyObject (disposer, p); 00254 FreeNode* f = (FreeNode*)p; 00255 f->next = freenode; 00256 freenode = f; 00257 } 00258 } 00265 template<typename Disposer> 00266 bool TryFree (Disposer& disposer, void* p) 00267 { 00268 if (p != 0 && !insideDisposeAll) 00269 { 00270 if (FindBlock(p) == csArrayItemNotFound) return false; 00271 DestroyObject (disposer, p); 00272 FreeNode* f = (FreeNode*)p; 00273 f->next = freenode; 00274 freenode = f; 00275 } 00276 return true; 00277 } 00278 00280 void* AllocCommon () 00281 { 00282 if (insideDisposeAll) 00283 { 00284 csPrintfErr("ERROR: csFixedSizeAllocator(%p) tried to allocate memory " 00285 "while inside DisposeAll()", (void*)this); 00286 CS_ASSERT(false); 00287 } 00288 00289 if (freenode == 0) 00290 { 00291 uint8* p = AllocBlock(); 00292 blocks.b.InsertSorted(p); 00293 freenode = (FreeNode*)p; 00294 } 00295 void* const node = freenode; 00296 freenode = freenode->next; 00297 #ifdef CS_FIXEDSIZEALLOC_DEBUG 00298 memset (node, 0xfa, elsize); 00299 #endif 00300 return node; 00301 } 00302 private: 00303 csFixedSizeAllocator (csFixedSizeAllocator const&); // Illegal; unimplemented. 00304 void operator= (csFixedSizeAllocator const&); // Illegal; unimplemented. 00305 public: 00316 csFixedSizeAllocator (size_t nelem = 32) : 00317 elcount (nelem), elsize(Size), freenode(0), insideDisposeAll(false) 00318 { 00319 #ifdef CS_MEMORY_TRACKER 00320 blocks.SetMemTrackerInfo (typeid(*this).name()); 00321 #endif 00322 if (elsize < sizeof (FreeNode)) 00323 elsize = sizeof (FreeNode); 00324 blocksize = elsize * elcount; 00325 } 00326 00330 ~csFixedSizeAllocator() 00331 { 00332 DefaultDisposer disposer (*this, false); 00333 DisposeAll (disposer); 00334 } 00335 00341 void Empty() 00342 { 00343 DefaultDisposer disposer (*this, true); 00344 DisposeAll (disposer); 00345 } 00346 00351 void Compact() 00352 { 00353 if (insideDisposeAll) return; 00354 00355 bool compacted = false; 00356 csBitArray mask(GetAllocationMap()); 00357 for (size_t b = blocks.b.GetSize(); b-- > 0; ) 00358 { 00359 size_t const node = b * elcount; 00360 if (!mask.AreSomeBitsSet(node, elcount)) 00361 { 00362 FreeBlock(blocks.b[b]); 00363 blocks.b.DeleteIndex(b); 00364 mask.Delete(node, elcount); 00365 compacted = true; 00366 } 00367 } 00368 00369 // If blocks were deleted, then free-node chain broke, so rebuild it. 00370 if (compacted) 00371 { 00372 FreeNode* nextfree = 0; 00373 size_t const bN = blocks.b.GetSize(); 00374 size_t node = bN * elcount; 00375 for (size_t b = bN; b-- > 0; ) 00376 { 00377 uint8* const p0 = blocks.b[b]; 00378 for (uint8* p = p0 + (elcount - 1) * elsize; p >= p0; p -= elsize) 00379 { 00380 if (!mask.IsBitSet(--node)) 00381 { 00382 FreeNode* slot = (FreeNode*)p; 00383 slot->next = nextfree; 00384 nextfree = slot; 00385 } 00386 } 00387 } 00388 freenode = nextfree; 00389 } 00390 } 00391 00395 void* Alloc () 00396 { 00397 return AllocCommon(); 00398 } 00399 00404 void Free (void* p) 00405 { 00406 DefaultDisposer disposer (*this, true); 00407 Free (disposer, p); 00408 } 00415 bool TryFree (void* p) 00416 { 00417 DefaultDisposer disposer (*this, true); 00418 return TryFree (disposer, p); 00419 } 00421 size_t GetBlockElements() const { return elcount; } 00422 00425 void* Alloc (size_t n) 00426 { 00427 CS_ASSERT (n == Size); 00428 return Alloc(); 00429 } 00430 void* Alloc (void* p, size_t newSize) 00431 { 00432 CS_ASSERT (newSize == Size); 00433 return p; 00434 } 00435 void SetMemTrackerInfo (const char* /*info*/) { } 00437 }; 00438 00441 #ifdef _CS_FIXEDSIZEALLOC_DEBUG_DEFAULTED 00442 #undef CS_FIXEDSIZEALLOC_DEBUG 00443 #undef _CS_FIXEDSIZEALLOC_DEBUG_DEFAULTED 00444 #endif 00445 00446 #endif // __CSUTIL_FIXEDSIZEALLOCATOR_H__
Generated for Crystal Space 1.2 by doxygen 1.4.7