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 
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