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