## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# csutil/blockallocator.h

Go to the documentation of this file.

    00001 /*
    00002   Crystal Space Generic Object Block Allocator
    00003   Copyright (C)2005 by Eric sunshine <sunshine@sunshineco.com>
    00004
    00005   This library is free software; you can redistribute it and/or
    00006   modify it under the terms of the GNU Library General Public
    00007   License as published by the Free Software Foundation; either
    00008   version 2 of the License, or (at your option) any later version.
    00009
    00010   This library is distributed in the hope that it will be useful,
    00011   but WITHOUT ANY WARRANTY; without even the implied warranty of
    00012   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00013   Library General Public License for more details.
    00014
    00015   You should have received a copy of the GNU Library General Public
    00016   License along with this library; if not, write to the Free
    00017   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
    00018 */
    00019 #ifndef __CSUTIL_BLOCK_ALLOCATOR_H__
    00020 #define __CSUTIL_BLOCK_ALLOCATOR_H__
    00021
    00026 #include "csextern.h"
    00027 #include "csutil/array.h"
    00028 #include "csutil/bitarray.h"
    00029 #include "csutil/sysfunc.h"
    00030
    00031 // hack: work around problems caused by #defining 'new'
    00032 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
    00033 # undef new
    00034 #endif
    00035 #include <new>
    00036
    00037 #ifdef CS_MEMORY_TRACKER
    00038 #include "csutil/memdebug.h"
    00039 #include <typeinfo>
    00040 #endif
    00041
    00046 class csBlockAllocatorNormalBlockPolicy
    00047 {
    00048 public:
    00052   static inline uint8* AllocBlock (size_t blocksize)
    00053   {
    00054     return (uint8*)malloc(blocksize);
    00055   }
    00056
    00061   static inline void FreeBlock(uint8* p)
    00062   {
    00063     free (p);
    00064   }
    00065 };
    00066
    00072 template <size_t A = 1>
    00073 class csBlockAllocatorAlignPolicy
    00074 {
    00075 public:
    00079   static inline uint8* AllocBlock(size_t blocksize)
    00080   {
    00081     return (uint8*)csAlignedMalloc (blocksize, A);
    00082   }
    00083
    00088   static inline void FreeBlock(uint8* p)
    00089   {
    00090     csAlignedFree (p);
    00091   }
    00092 };
    00093
    00094 #ifdef CS_MEMORY_TRACKER
    00095
    00100 template <class T>
    00101 class csBlockAllocatorMTBlockPolicy
    00102 {
    00103 public:
    00107   static inline uint8* AllocBlock (size_t blocksize)
    00108   {
    00109     char buf[255];
    00110     sprintf (buf, "csBlockAllocator<%s>", typeid (T).name());
    00111     uintptr_t* ptr = (uintptr_t*)malloc (blocksize + sizeof (uintptr_t)*2);
    00112     *ptr++ = (uintptr_t)mtiRegisterAlloc (blocksize, buf);
    00113     *ptr++ = blocksize;
    00114     return (uint8*)ptr;
    00115   }
    00116
    00121   static inline void FreeBlock(uint8* p)
    00122   {
    00123     uintptr_t* ptr = ((uintptr_t*)p)-2;
    00124     mtiRegisterFree ((csMemTrackerInfo*)*ptr, (size_t)ptr[1]);
    00125     free (ptr);
    00126   }
    00127 };
    00128 #endif
    00129
    00150 #ifdef CS_MEMORY_TRACKER
    00151 template <class T, class BlockPolicy = csBlockAllocatorMTBlockPolicy<T> >
    00152 #else
    00153 template <class T, class BlockPolicy = csBlockAllocatorNormalBlockPolicy>
    00154 #endif
    00155 class csBlockAllocator
    00156 {
    00157 protected: // 'protected' allows access by test-suite.
    00158   struct FreeNode
    00159   {
    00160     FreeNode* next;
    00161   };
    00162
    00163   struct BlockKey
    00164   {
    00165     uint8 const* addr;
    00166     size_t blocksize;
    00167     BlockKey(uint8 const* p, size_t n) : addr(p), blocksize(n) {}
    00168   };
    00169
    00170   csArray<uint8*> blocks;       // List of allocated blocks; sorted by address.
    00171   size_t size;                  // Number of elements per block.
    00172   size_t elsize;                // Element size; >= sizeof(void*).
    00173   size_t blocksize;             // Size in bytes per block.
    00174   FreeNode* freenode;           // Head of the chain of free nodes.
    00175   bool pedantic;                // Warn about nodes not explicitly freed.
    00176   bool insideDisposeAll;        // Flag to ignore calls to Compact() and
    00177                                 //  Free() if they're called recursively
    00178                                 //  while disposing the entire allocation set.
    00179                                 //  Recursive calls to Alloc() will signal an
    00180                                 //  assertion failure.
    00181
    00188   static int FuzzyCmp(uint8* const& block, BlockKey const& k)
    00189   {
    00190     return (block + k.blocksize <= k.addr ? -1 : (block > k.addr ? 1 : 0));
    00191   }
    00192
    00196   size_t FindBlock(void const* m) const
    00197   {
    00198     return blocks.FindSortedKey(
    00199       csArrayCmp<uint8*,BlockKey>(BlockKey((uint8*)m, blocksize), FuzzyCmp));
    00200   }
    00201
    00207   uint8* AllocBlock() const
    00208   {
    00209     uint8* block = BlockPolicy::AllocBlock(blocksize);
    00210
    00211     // Build the free-node chain (all nodes are free in the new block).
    00212     FreeNode* nextfree = 0;
    00213     uint8* node = block + (size - 1) * elsize;
    00214     for ( ; node >= block; node -= elsize)
    00215     {
    00216       FreeNode* slot = (FreeNode*)node;
    00217       slot->next = nextfree;
    00218       nextfree = slot;
    00219     }
    00220     CS_ASSERT((uint8*)nextfree == block);
    00221     return block;
    00222   }
    00223
    00227   void FreeBlock(uint8* p) const
    00228   {
    00229     BlockPolicy::FreeBlock(p);
    00230   }
    00231
    00235   void DestroyObject(T* p, bool warn = false) const
    00236   {
    00237     p->~T();
    00238     if (warn)
    00239     {
    00240 #ifdef CS_DEBUG
    00241       csPrintfErr("NOTIFY: csBlockAllocator(%p) destroying potentially leaked "
    00242                   "object at %p.\n", (void*)this, (void*)p);
    00243 #endif
    00244     }
    00245 #ifdef CS_BLOCKALLOC_DEBUG
    00246     memset (p, 0xfb, elsize);
    00247 #endif
    00248   }
    00249
    00254   csBitArray GetAllocationMap() const
    00255   {
    00256     csBitArray mask(size * blocks.GetSize());
    00257     mask.FlipAllBits();
    00258     for (FreeNode* p = freenode; p != 0; p = p->next)
    00259     {
    00260       size_t const n = FindBlock(p);
    00261       CS_ASSERT(n != csArrayItemNotFound);
    00262       size_t const slot = ((uint8*)p - blocks[n]) / elsize; // Slot in block.
    00263       mask.ClearBit(n * size + slot);
    00264     }
    00265     return mask;
    00266   }
    00267
    00273   void DisposeAll(bool warn_unfreed)
    00274   {
    00275     insideDisposeAll = true;
    00276     csBitArray const mask(GetAllocationMap());
    00277     size_t node = 0;
    00278     for (size_t b = 0, bN = blocks.GetSize(); b < bN; b++)
    00279     {
    00280       for (uint8 *p = blocks[b], *pN = p + blocksize; p < pN; p += elsize)
    00281           if (mask.IsBitSet(node++))
    00282             DestroyObject((T*)p, warn_unfreed);
    00283       FreeBlock(blocks[b]);
    00284     }
    00285     blocks.DeleteAll();
    00286     freenode = 0;
    00287     insideDisposeAll = false;
    00288   }
    00289
    00290 public:
    00312   csBlockAllocator(size_t nelem = 32, bool warn_unfreed = false) :
    00313     size(nelem), elsize(sizeof(T)), freenode(0), pedantic(warn_unfreed),
    00314     insideDisposeAll(false)
    00315   {
    00316     if (elsize < sizeof (FreeNode))
    00317       elsize = sizeof (FreeNode);
    00318     blocksize = elsize * size;
    00319   }
    00320
    00324   ~csBlockAllocator()
    00325   {
    00326     DisposeAll(pedantic);
    00327   }
    00328
    00334   void Empty()
    00335   {
    00336     DisposeAll(false);
    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.GetSize(); b-- > 0; )
    00350     {
    00351       size_t const node = b * size;
    00352       if (!mask.AreSomeBitsSet(node, size))
    00353       {
    00354         FreeBlock(blocks[b]);
    00355         blocks.DeleteIndex(b);
    00356         mask.Delete(node, size);
    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.GetSize();
    00366       size_t node = bN * size;
    00367       for (size_t b = bN; b-- > 0; )
    00368       {
    00369         uint8* const p0 = blocks[b];
    00370         for (uint8* p = p0 + (size - 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   T* Alloc()
    00388   {
    00389     if (insideDisposeAll)
    00390     {
    00391       csPrintfErr("ERROR: csBlockAllocator(%p) tried to allocate memory while inside DisposeAll()", (void*)this);
    00392       CS_ASSERT(false);
    00393     }
    00394
    00395     if (freenode == 0)
    00396     {
    00397       uint8* p = AllocBlock();
    00398       blocks.InsertSorted(p);
    00399       freenode = (FreeNode*)p;
    00400     }
    00401     void* const node = freenode;
    00402     freenode = freenode->next;
    00403     return new (node) T;
    00404   }
    00405
    00409   void Free(T* p)
    00410   {
    00411     if (p != 0 && !insideDisposeAll)
    00412     {
    00413       CS_ASSERT(FindBlock(p) != csArrayItemNotFound);
    00414       DestroyObject(p, false);
    00415       FreeNode* f = (FreeNode*)p;
    00416       f->next = freenode;
    00417       freenode = f;
    00418     }
    00419   }
    00421   size_t GetBlockElements() const { return size; }
    00422 };
    00423
    00424 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
    00425 # define new CS_EXTENSIVE_MEMDEBUG_NEW
    00426 #endif
    00427
    00428 #endif // __CSUTIL_BLOCK_ALLOCATOR_H__