CrystalSpace

Public API Reference

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 
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: // 'protected' allows access by test-suite.
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     // Build the free-node chain (all nodes are free in the new block).
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; // Slot in block.
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* /*p*/) 
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&);         // Illegal; unimplemented.
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     /* Technically, an allocator can be empty even with freenode != 0 */
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     // If blocks were deleted, then free-node chain broke, so rebuild it.
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* /*info*/) { }
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   } // namespace Memory
00580 } // namespace CS
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__

Generated for Crystal Space 2.0 by doxygen 1.7.6.1