00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
00060 template <size_t Size, class Allocator = CS::Memory::AllocatorMalloc>
00061 class csFixedSizeAllocator
00062 {
00063 public:
00064 typedef csFixedSizeAllocator<Size, Allocator> ThisType;
00065 typedef Allocator AllocatorType;
00066
00067 protected:
00068 struct FreeNode
00069 {
00070 FreeNode* next;
00071 };
00072
00073 struct BlockKey
00074 {
00075 uint8 const* addr;
00076 size_t blocksize;
00077 BlockKey(uint8 const* p, size_t n) : addr(p), blocksize(n) {}
00078 };
00079
00080 struct BlocksWrapper : public Allocator
00081 {
00082 csArray<uint8*> b;
00083
00084 BlocksWrapper () {}
00085 BlocksWrapper (const Allocator& alloc) : Allocator (alloc) {}
00086 };
00088 BlocksWrapper blocks;
00090 size_t elcount;
00092 size_t elsize;
00094 size_t blocksize;
00096 FreeNode* freenode;
00102 bool insideDisposeAll;
00103
00110 static int FuzzyCmp(uint8* const& block, BlockKey const& k)
00111 {
00112 return (block + k.blocksize <= k.addr ? -1 : (block > k.addr ? 1 : 0));
00113 }
00114
00118 size_t FindBlock(void const* m) const
00119 {
00120 return blocks.b.FindSortedKey(
00121 csArrayCmp<uint8*,BlockKey>(BlockKey((uint8*)m, blocksize), FuzzyCmp));
00122 }
00123
00129 uint8* AllocBlock()
00130 {
00131 uint8* block = (uint8*)blocks.Alloc (blocksize);
00132
00133
00134 FreeNode* nextfree = 0;
00135 uint8* node = block + (elcount - 1) * elsize;
00136 for ( ; node >= block; node -= elsize)
00137 {
00138 FreeNode* slot = (FreeNode*)node;
00139 slot->next = nextfree;
00140 nextfree = slot;
00141 }
00142 CS_ASSERT((uint8*)nextfree == block);
00143 return block;
00144 }
00145
00149 void FreeBlock(uint8* p)
00150 {
00151 blocks.Free (p);
00152 }
00153
00157 template<typename Disposer>
00158 void DestroyObject (Disposer& disposer, void* p) const
00159 {
00160 disposer.Dispose (p);
00161 #ifdef CS_FIXEDSIZEALLOC_DEBUG
00162 memset (p, 0xfb, elsize);
00163 #endif
00164 }
00165
00170 csBitArray GetAllocationMap() const
00171 {
00172 csBitArray mask(elcount * blocks.b.GetSize());
00173 mask.FlipAllBits();
00174 for (FreeNode* p = freenode; p != 0; p = p->next)
00175 {
00176 size_t const n = FindBlock(p);
00177 CS_ASSERT(n != csArrayItemNotFound);
00178 size_t const slot = ((uint8*)p - blocks.b[n]) / elsize;
00179 mask.ClearBit(n * elcount + slot);
00180 }
00181 return mask;
00182 }
00183
00185 class DefaultDisposer
00186 {
00187 #ifdef CS_DEBUG
00188 bool doWarn;
00189 const char* parentClass;
00190 const void* parent;
00191 size_t count;
00192 #endif
00193 public:
00194 #ifdef CS_DEBUG
00195 template<typename BA>
00196 DefaultDisposer (const BA& ba, bool legit) :
00197 doWarn (!legit), parentClass (typeid(BA).name()), parent (&ba),
00198 count (0)
00199 {
00200 }
00201 #else
00202 template<typename BA>
00203 DefaultDisposer (const BA&, bool legit)
00204 { (void)legit; }
00205 #endif
00206 ~DefaultDisposer()
00207 {
00208 #ifdef CS_DEBUG
00209 if ((count > 0) && doWarn)
00210 {
00211 csPrintfErr("%s %p leaked %zu objects.\n", parentClass, (void*)this,
00212 count);
00213 }
00214 #endif
00215 }
00216 void Dispose (void* )
00217 {
00218 #ifdef CS_DEBUG
00219 count++;
00220 #endif
00221 }
00222 };
00228 template<typename Disposer>
00229 void DisposeAll(Disposer& disposer)
00230 {
00231 insideDisposeAll = true;
00232 csBitArray const mask(GetAllocationMap());
00233 size_t node = 0;
00234 for (size_t b = 0, bN = blocks.b.GetSize(); b < bN; b++)
00235 {
00236 for (uint8 *p = blocks.b[b], *pN = p + blocksize; p < pN; p += elsize)
00237 if (mask.IsBitSet(node++))
00238 DestroyObject (disposer, p);
00239 FreeBlock(blocks.b[b]);
00240 }
00241 blocks.b.DeleteAll();
00242 freenode = 0;
00243 insideDisposeAll = false;
00244 }
00245
00251 template<typename Disposer>
00252 void Free (Disposer& disposer, void* p)
00253 {
00254 if (p != 0 && !insideDisposeAll)
00255 {
00256 CS_ASSERT(FindBlock(p) != csArrayItemNotFound);
00257 DestroyObject (disposer, p);
00258 FreeNode* f = (FreeNode*)p;
00259 f->next = freenode;
00260 freenode = f;
00261 }
00262 }
00269 template<typename Disposer>
00270 bool TryFree (Disposer& disposer, void* p)
00271 {
00272 if (p != 0 && !insideDisposeAll)
00273 {
00274 if (FindBlock(p) == csArrayItemNotFound) return false;
00275 DestroyObject (disposer, p);
00276 FreeNode* f = (FreeNode*)p;
00277 f->next = freenode;
00278 freenode = f;
00279 }
00280 return true;
00281 }
00287 template<typename Disposer>
00288 void FreeAll (Disposer& disposer)
00289 {
00290 insideDisposeAll = true;
00291 csBitArray const mask(GetAllocationMap());
00292 size_t node = 0;
00293 for (size_t b = 0, bN = blocks.b.GetSize(); b < bN; b++)
00294 {
00295 for (uint8 *p = blocks.b[b], *pN = p + blocksize; p < pN; p += elsize)
00296 {
00297 if (mask.IsBitSet(node++))
00298 {
00299 DestroyObject (disposer, p);
00300 FreeNode* f = (FreeNode*)p;
00301 f->next = freenode;
00302 freenode = f;
00303 }
00304 }
00305 }
00306 insideDisposeAll = false;
00307 }
00308
00310 void* AllocCommon ()
00311 {
00312 if (insideDisposeAll)
00313 {
00314 csPrintfErr("ERROR: csFixedSizeAllocator(%p) tried to allocate memory "
00315 "while inside DisposeAll()", (void*)this);
00316 CS_ASSERT(false);
00317 }
00318
00319 if (freenode == 0)
00320 {
00321 uint8* p = AllocBlock();
00322 blocks.b.InsertSorted(p);
00323 freenode = (FreeNode*)p;
00324 }
00325 union
00326 {
00327 FreeNode* a;
00328 void* b;
00329 } pun;
00330 pun.a = freenode;
00331 freenode = freenode->next;
00332 #ifdef CS_FIXEDSIZEALLOC_DEBUG
00333 memset (pun.b, 0xfa, elsize);
00334 #endif
00335 return pun.b;
00336 }
00337 private:
00338 void operator= (csFixedSizeAllocator const&);
00339 public:
00341
00351 csFixedSizeAllocator (size_t nelem = 32) :
00352 elcount (nelem), elsize(Size), freenode(0), insideDisposeAll(false)
00353 {
00354 #ifdef CS_MEMORY_TRACKER
00355 blocks.SetMemTrackerInfo (typeid(*this).name());
00356 #endif
00357 if (elsize < sizeof (FreeNode))
00358 elsize = sizeof (FreeNode);
00359 blocksize = elsize * elcount;
00360 }
00361 csFixedSizeAllocator (size_t nelem, const Allocator& alloc) : blocks (alloc),
00362 elcount (nelem), elsize(Size), freenode(0), insideDisposeAll(false)
00363 {
00364 #ifdef CS_MEMORY_TRACKER
00365 blocks.SetMemTrackerInfo (typeid(*this).name());
00366 #endif
00367 if (elsize < sizeof (FreeNode))
00368 elsize = sizeof (FreeNode);
00369 blocksize = elsize * elcount;
00370 }
00372
00380 csFixedSizeAllocator (csFixedSizeAllocator const& other) :
00381 elcount (other.elcount), elsize (other.elsize),
00382 blocksize (other.blocksize), freenode (0), insideDisposeAll (false)
00383 {
00384 #ifdef CS_MEMORY_TRACKER
00385 blocks.SetMemTrackerInfo (typeid(*this).name());
00386 #endif
00387
00388 CS_ASSERT(other.freenode == 0);
00389 }
00390
00394 ~csFixedSizeAllocator()
00395 {
00396 DefaultDisposer disposer (*this, false);
00397 DisposeAll (disposer);
00398 }
00399
00405 void Empty()
00406 {
00407 DefaultDisposer disposer (*this, true);
00408 DisposeAll (disposer);
00409 }
00410
00415 void Compact()
00416 {
00417 if (insideDisposeAll) return;
00418
00419 bool compacted = false;
00420 csBitArray mask(GetAllocationMap());
00421 for (size_t b = blocks.b.GetSize(); b-- > 0; )
00422 {
00423 size_t const node = b * elcount;
00424 if (!mask.AreSomeBitsSet(node, elcount))
00425 {
00426 FreeBlock(blocks.b[b]);
00427 blocks.b.DeleteIndex(b);
00428 mask.Delete(node, elcount);
00429 compacted = true;
00430 }
00431 }
00432
00433
00434 if (compacted)
00435 {
00436 FreeNode* nextfree = 0;
00437 size_t const bN = blocks.b.GetSize();
00438 size_t node = bN * elcount;
00439 for (size_t b = bN; b-- > 0; )
00440 {
00441 uint8* const p0 = blocks.b[b];
00442 for (uint8* p = p0 + (elcount - 1) * elsize; p >= p0; p -= elsize)
00443 {
00444 if (!mask.IsBitSet(--node))
00445 {
00446 FreeNode* slot = (FreeNode*)p;
00447 slot->next = nextfree;
00448 nextfree = slot;
00449 }
00450 }
00451 }
00452 freenode = nextfree;
00453 }
00454 }
00455
00459 size_t GetAllocatedElems() const
00460 {
00461 csBitArray mask(GetAllocationMap());
00462 return mask.NumBitsSet();
00463 }
00464
00468 void* Alloc ()
00469 {
00470 return AllocCommon();
00471 }
00472
00477 void Free (void* p)
00478 {
00479 DefaultDisposer disposer (*this, true);
00480 Free (disposer, p);
00481 }
00488 bool TryFree (void* p)
00489 {
00490 DefaultDisposer disposer (*this, true);
00491 return TryFree (disposer, p);
00492 }
00494 size_t GetBlockElements() const { return elcount; }
00495
00498 void* Alloc (size_t n)
00499 {
00500 CS_ASSERT (n == Size);
00501 return Alloc();
00502 }
00503 void* Alloc (void* p, size_t newSize)
00504 {
00505 CS_ASSERT (newSize == Size);
00506 return p;
00507 }
00508 void SetMemTrackerInfo (const char* ) { }
00510 };
00511
00512 namespace CS
00513 {
00514 namespace Memory
00515 {
00521 template <size_t Size, class Allocator = CS::Memory::AllocatorMalloc>
00522 class FixedSizeAllocatorSafe :
00523 public CS::Memory::AllocatorSafe<csFixedSizeAllocator<Size, Allocator> >
00524 {
00525 protected:
00526 typedef csFixedSizeAllocator<Size, Allocator> WrappedAllocatorType;
00527 typedef CS::Memory::AllocatorSafe<csFixedSizeAllocator<Size, Allocator> >
00528 AllocatorSafeType;
00529 public:
00530 FixedSizeAllocatorSafe (size_t nelem = 32) : AllocatorSafeType (nelem)
00531 {
00532 }
00533 FixedSizeAllocatorSafe (size_t nelem, const Allocator& alloc) :
00534 AllocatorSafeType (nelem, alloc)
00535 {
00536 }
00537
00538 FixedSizeAllocatorSafe (FixedSizeAllocatorSafe const& other) :
00539 AllocatorSafeType (other)
00540 {
00541 }
00542
00543 void Empty()
00544 {
00545 CS::Threading::RecursiveMutexScopedLock lock (AllocatorSafeType::mutex);
00546 WrappedAllocatorType::Empty();
00547 }
00548
00549 void Compact()
00550 {
00551 CS::Threading::RecursiveMutexScopedLock lock (AllocatorSafeType::mutex);
00552 WrappedAllocatorType::Compact();
00553 }
00554
00555 size_t GetAllocatedElems() const
00556 {
00557 CS::Threading::RecursiveMutexScopedLock lock (AllocatorSafeType::mutex);
00558 return WrappedAllocatorType::GetAllocatedElems();
00559 }
00560
00561 void* Alloc ()
00562 {
00563 CS::Threading::RecursiveMutexScopedLock lock (AllocatorSafeType::mutex);
00564 return WrappedAllocatorType::Alloc();
00565 }
00566 using AllocatorSafeType::Alloc;
00567
00568 bool TryFree (void* p)
00569 {
00570 CS::Threading::RecursiveMutexScopedLock lock (AllocatorSafeType::mutex);
00571 return WrappedAllocatorType::TryFree (p);
00572 }
00573 size_t GetBlockElements() const
00574 {
00575 CS::Threading::RecursiveMutexScopedLock lock (AllocatorSafeType::mutex);
00576 return WrappedAllocatorType::GetBlockElements();
00577 }
00578 };
00579 }
00580 }
00581
00584 #ifdef _CS_FIXEDSIZEALLOC_DEBUG_DEFAULTED
00585 #undef CS_FIXEDSIZEALLOC_DEBUG
00586 #undef _CS_FIXEDSIZEALLOC_DEBUG_DEFAULTED
00587 #endif
00588
00589 #endif // __CSUTIL_FIXEDSIZEALLOCATOR_H__