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 
00054 template <size_t Size, class Allocator = CS::Memory::AllocatorMalloc>
00055 class csFixedSizeAllocator
00056 {
00057 public:
00058   typedef csFixedSizeAllocator<Size, Allocator> ThisType;
00059   typedef Allocator AllocatorType;
00060 
00061 protected: // 'protected' allows access by test-suite.
00062   struct FreeNode
00063   {
00064     FreeNode* next;
00065   };
00066 
00067   struct BlockKey
00068   {
00069     uint8 const* addr;
00070     size_t blocksize;
00071     BlockKey(uint8 const* p, size_t n) : addr(p), blocksize(n) {}
00072   };
00073 
00074   struct BlocksWrapper : public Allocator
00075   {
00076     csArray<uint8*> b;
00077   };
00079   BlocksWrapper blocks;
00081   size_t elcount;
00083   size_t elsize;
00085   size_t blocksize;
00087   FreeNode* freenode;
00093   bool insideDisposeAll;
00094 
00101   static int FuzzyCmp(uint8* const& block, BlockKey const& k)
00102   {
00103     return (block + k.blocksize <= k.addr ? -1 : (block > k.addr ? 1 : 0));
00104   }
00105 
00109   size_t FindBlock(void const* m) const
00110   {
00111     return blocks.b.FindSortedKey(
00112       csArrayCmp<uint8*,BlockKey>(BlockKey((uint8*)m, blocksize), FuzzyCmp));
00113   }
00114 
00120   uint8* AllocBlock()
00121   {
00122     uint8* block = (uint8*)blocks.Alloc (blocksize);
00123 
00124     // Build the free-node chain (all nodes are free in the new block).
00125     FreeNode* nextfree = 0;
00126     uint8* node = block + (elcount - 1) * elsize;
00127     for ( ; node >= block; node -= elsize)
00128     {
00129       FreeNode* slot = (FreeNode*)node;
00130       slot->next = nextfree;
00131       nextfree = slot;
00132     }
00133     CS_ASSERT((uint8*)nextfree == block);
00134     return block;
00135   }
00136 
00140   void FreeBlock(uint8* p)
00141   {
00142     blocks.Free (p);
00143   }
00144 
00148   template<typename Disposer>
00149   void DestroyObject (Disposer& disposer, void* p) const
00150   {
00151     disposer.Dispose (p);
00152 #ifdef CS_FIXEDSIZEALLOC_DEBUG
00153     memset (p, 0xfb, elsize);
00154 #endif
00155   }
00156 
00161   csBitArray GetAllocationMap() const
00162   {
00163     csBitArray mask(elcount * blocks.b.GetSize());
00164     mask.FlipAllBits();
00165     for (FreeNode* p = freenode; p != 0; p = p->next)
00166     {
00167       size_t const n = FindBlock(p);
00168       CS_ASSERT(n != csArrayItemNotFound);
00169       size_t const slot = ((uint8*)p - blocks.b[n]) / elsize; // Slot in block.
00170       mask.ClearBit(n * elcount + slot);
00171     }
00172     return mask;
00173   }
00174 
00176   class DefaultDisposer
00177   {
00178   #ifdef CS_DEBUG
00179     bool doWarn;
00180     const char* parentClass;
00181     const void* parent;
00182     size_t count;
00183   #endif
00184   public:
00185   #ifdef CS_DEBUG
00186     template<typename BA>
00187     DefaultDisposer (const BA& ba, bool legit) :
00188       doWarn (!legit), parentClass (typeid(BA).name()), parent (&ba),
00189       count (0)
00190     { 
00191     }
00192   #else
00193     template<typename BA>
00194     DefaultDisposer (const BA&, bool legit)
00195     { (void)legit; }
00196   #endif
00197     ~DefaultDisposer()
00198     {
00199   #ifdef CS_DEBUG
00200       if ((count > 0) && doWarn)
00201       {
00202         csPrintfErr("%s %p leaked %zu objects.\n", parentClass, (void*)this, 
00203           count);
00204       }
00205   #endif
00206     }
00207     void Dispose (void* /*p*/) 
00208     {
00209   #ifdef CS_DEBUG
00210       count++;
00211   #endif
00212     }
00213   };
00219   template<typename Disposer>
00220   void DisposeAll(Disposer& disposer)
00221   {
00222     insideDisposeAll = true;
00223     csBitArray const mask(GetAllocationMap());
00224     size_t node = 0;
00225     for (size_t b = 0, bN = blocks.b.GetSize(); b < bN; b++)
00226     {
00227       for (uint8 *p = blocks.b[b], *pN = p + blocksize; p < pN; p += elsize)
00228         if (mask.IsBitSet(node++))
00229           DestroyObject (disposer, p);
00230       FreeBlock(blocks.b[b]);
00231     }
00232     blocks.b.DeleteAll();
00233     freenode = 0;
00234     insideDisposeAll = false;
00235   }
00236 
00242   template<typename Disposer>
00243   void Free (Disposer& disposer, void* p)
00244   {
00245     if (p != 0 && !insideDisposeAll)
00246     {
00247       CS_ASSERT(FindBlock(p) != csArrayItemNotFound);
00248       DestroyObject (disposer, p);
00249       FreeNode* f = (FreeNode*)p;
00250       f->next = freenode;
00251       freenode = f;
00252     }
00253   }
00260   template<typename Disposer>
00261   bool TryFree (Disposer& disposer, void* p)
00262   {
00263     if (p != 0 && !insideDisposeAll)
00264     {
00265       if (FindBlock(p) == csArrayItemNotFound) return false;
00266       DestroyObject (disposer, p);
00267       FreeNode* f = (FreeNode*)p;
00268       f->next = freenode;
00269       freenode = f;
00270     }
00271     return true;
00272   }
00273 
00275   void* AllocCommon ()
00276   {
00277     if (insideDisposeAll)
00278     {
00279       csPrintfErr("ERROR: csFixedSizeAllocator(%p) tried to allocate memory "
00280         "while inside DisposeAll()", (void*)this);
00281       CS_ASSERT(false);
00282     }
00283 
00284     if (freenode == 0)
00285     {
00286       uint8* p = AllocBlock();
00287       blocks.b.InsertSorted(p);
00288       freenode = (FreeNode*)p;
00289     }
00290     void* const node = freenode;
00291     freenode = freenode->next;
00292     return node;
00293   }
00294 private:
00295   csFixedSizeAllocator (csFixedSizeAllocator const&);  // Illegal; unimplemented.
00296   void operator= (csFixedSizeAllocator const&);         // Illegal; unimplemented.
00297 public:
00308   csFixedSizeAllocator (size_t nelem = 32) :
00309     elcount (nelem), elsize(Size), freenode(0), insideDisposeAll(false)
00310   {
00311 #ifdef CS_MEMORY_TRACKER
00312     blocks.SetMemTrackerInfo (typeid(*this).name());
00313 #endif
00314     if (elsize < sizeof (FreeNode))
00315       elsize = sizeof (FreeNode);
00316     blocksize = elsize * elcount;
00317   }
00318 
00322   ~csFixedSizeAllocator()
00323   {
00324     DefaultDisposer disposer (*this, false);
00325     DisposeAll (disposer);
00326   }
00327 
00333   void Empty()
00334   {
00335     DefaultDisposer disposer (*this, true);
00336     DisposeAll (disposer);
00337   }
00338 
00343   void Compact()
00344   {
00345     if (insideDisposeAll) return;
00346 
00347     bool compacted = false;
00348     csBitArray mask(GetAllocationMap());
00349     for (size_t b = blocks.b.GetSize(); b-- > 0; )
00350     {
00351       size_t const node = b * elcount;
00352       if (!mask.AreSomeBitsSet(node, elcount))
00353       {
00354         FreeBlock(blocks.b[b]);
00355         blocks.b.DeleteIndex(b);
00356         mask.Delete(node, elcount);
00357         compacted = true;
00358       }
00359     }
00360 
00361     // If blocks were deleted, then free-node chain broke, so rebuild it.
00362     if (compacted)
00363     {
00364       FreeNode* nextfree = 0;
00365       size_t const bN = blocks.b.GetSize();
00366       size_t node = bN * elcount;
00367       for (size_t b = bN; b-- > 0; )
00368       {
00369         uint8* const p0 = blocks.b[b];
00370         for (uint8* p = p0 + (elcount - 1) * elsize; p >= p0; p -= elsize)
00371         {
00372           if (!mask.IsBitSet(--node))
00373           {
00374             FreeNode* slot = (FreeNode*)p;
00375             slot->next = nextfree;
00376             nextfree = slot;
00377           }
00378         }
00379       }
00380       freenode = nextfree;
00381     }
00382   }
00383 
00387   void* Alloc ()
00388   {
00389     return AllocCommon();
00390   }
00391 
00396   void Free (void* p)
00397   {
00398     DefaultDisposer disposer (*this, true);
00399     Free (disposer, p);
00400   }
00407   bool TryFree (void* p)
00408   {
00409     DefaultDisposer disposer (*this, true);
00410     return TryFree (disposer, p);
00411   }
00413   size_t GetBlockElements() const { return elcount; }
00414   
00417   void* Alloc (size_t n)
00418   {
00419     CS_ASSERT (n == Size);
00420     return Alloc();
00421   }
00422   void* Alloc (void* p, size_t newSize)
00423   {
00424     CS_ASSERT (newSize == Size);
00425     return p;
00426   }
00427   void SetMemTrackerInfo (const char* /*info*/) { }
00429 };
00430 
00433 #endif // __CSUTIL_FIXEDSIZEALLOCATOR_H__

Generated for Crystal Space 1.0.2 by doxygen 1.4.7