Public API Reference

csutil/fixedsizeallocator.h

Go to the documentation of this file.

/*
  Crystal Space Fixed Size Block Allocator
  Copyright (C) 2005 by Eric Sunshine <[email protected]>
            (C) 2006 by Frank Richter

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Library General Public
  License as published by the Free Software Foundation; either
  version 2 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Library General Public License for more details.

  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free
  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef __CSUTIL_FIXEDSIZEALLOCATOR_H__
#define __CSUTIL_FIXEDSIZEALLOCATOR_H__

#include "csextern.h"
#include "csutil/array.h"
#include "csutil/bitarray.h"
#include "csutil/sysfunc.h"

#ifdef CS_DEBUG
#include <typeinfo>
#endif

template <size_t Size, class Allocator = CS::Memory::AllocatorMalloc>
class csFixedSizeAllocator
{
public:
  typedef csFixedSizeAllocator<Size, Allocator> ThisType;
  typedef Allocator AllocatorType;

protected: // 'protected' allows access by test-suite.
  struct FreeNode
  {
    FreeNode* next;
  };

  struct BlockKey
  {
    uint8 const* addr;
    size_t blocksize;
    BlockKey(uint8 const* p, size_t n) : addr(p), blocksize(n) {}
  };

  struct BlocksWrapper : public Allocator
  {
    csArray<uint8*> b;
  };
  BlocksWrapper blocks;
  size_t elcount;
  size_t elsize;
  size_t blocksize;
  FreeNode* freenode;
  bool insideDisposeAll;

  static int FuzzyCmp(uint8* const& block, BlockKey const& k)
  {
    return (block + k.blocksize <= k.addr ? -1 : (block > k.addr ? 1 : 0));
  }

  size_t FindBlock(void const* m) const
  {
    return blocks.b.FindSortedKey(
      csArrayCmp<uint8*,BlockKey>(BlockKey((uint8*)m, blocksize), FuzzyCmp));
  }

  uint8* AllocBlock()
  {
    uint8* block = (uint8*)blocks.Alloc (blocksize);

    // Build the free-node chain (all nodes are free in the new block).
    FreeNode* nextfree = 0;
    uint8* node = block + (elcount - 1) * elsize;
    for ( ; node >= block; node -= elsize)
    {
      FreeNode* slot = (FreeNode*)node;
      slot->next = nextfree;
      nextfree = slot;
    }
    CS_ASSERT((uint8*)nextfree == block);
    return block;
  }

  void FreeBlock(uint8* p)
  {
    blocks.Free (p);
  }

  template<typename Disposer>
  void DestroyObject (Disposer& disposer, void* p) const
  {
    disposer.Dispose (p);
#ifdef CS_FIXEDSIZEALLOC_DEBUG
    memset (p, 0xfb, elsize);
#endif
  }

  csBitArray GetAllocationMap() const
  {
    csBitArray mask(elcount * blocks.b.GetSize());
    mask.FlipAllBits();
    for (FreeNode* p = freenode; p != 0; p = p->next)
    {
      size_t const n = FindBlock(p);
      CS_ASSERT(n != csArrayItemNotFound);
      size_t const slot = ((uint8*)p - blocks.b[n]) / elsize; // Slot in block.
      mask.ClearBit(n * elcount + slot);
    }
    return mask;
  }

  class DefaultDisposer
  {
  #ifdef CS_DEBUG
    bool doWarn;
    const char* parentClass;
    const void* parent;
    size_t count;
  #endif
  public:
  #ifdef CS_DEBUG
    template<typename BA>
    DefaultDisposer (const BA& ba, bool legit) :
      doWarn (!legit), parentClass (typeid(BA).name()), parent (&ba),
      count (0)
    { 
    }
  #else
    template<typename BA>
    DefaultDisposer (const BA&, bool legit)
    { (void)legit; }
  #endif
    ~DefaultDisposer()
    {
  #ifdef CS_DEBUG
      if ((count > 0) && doWarn)
      {
        csPrintfErr("%s %p leaked %zu objects.\n", parentClass, (void*)this, 
          count);
      }
  #endif
    }
    void Dispose (void* /*p*/) 
    {
  #ifdef CS_DEBUG
      count++;
  #endif
    }
  };
  template<typename Disposer>
  void DisposeAll(Disposer& disposer)
  {
    insideDisposeAll = true;
    csBitArray const mask(GetAllocationMap());
    size_t node = 0;
    for (size_t b = 0, bN = blocks.b.GetSize(); b < bN; b++)
    {
      for (uint8 *p = blocks.b[b], *pN = p + blocksize; p < pN; p += elsize)
        if (mask.IsBitSet(node++))
          DestroyObject (disposer, p);
      FreeBlock(blocks.b[b]);
    }
    blocks.b.DeleteAll();
    freenode = 0;
    insideDisposeAll = false;
  }

  template<typename Disposer>
  void Free (Disposer& disposer, void* p)
  {
    if (p != 0 && !insideDisposeAll)
    {
      CS_ASSERT(FindBlock(p) != csArrayItemNotFound);
      DestroyObject (disposer, p);
      FreeNode* f = (FreeNode*)p;
      f->next = freenode;
      freenode = f;
    }
  }
  template<typename Disposer>
  bool TryFree (Disposer& disposer, void* p)
  {
    if (p != 0 && !insideDisposeAll)
    {
      if (FindBlock(p) == csArrayItemNotFound) return false;
      DestroyObject (disposer, p);
      FreeNode* f = (FreeNode*)p;
      f->next = freenode;
      freenode = f;
    }
    return true;
  }

  void* AllocCommon ()
  {
    if (insideDisposeAll)
    {
      csPrintfErr("ERROR: csFixedSizeAllocator(%p) tried to allocate memory "
        "while inside DisposeAll()", (void*)this);
      CS_ASSERT(false);
    }

    if (freenode == 0)
    {
      uint8* p = AllocBlock();
      blocks.b.InsertSorted(p);
      freenode = (FreeNode*)p;
    }
    void* const node = freenode;
    freenode = freenode->next;
    return node;
  }
private:
  csFixedSizeAllocator (csFixedSizeAllocator const&);  // Illegal; unimplemented.
  void operator= (csFixedSizeAllocator const&);         // Illegal; unimplemented.
public:
  csFixedSizeAllocator (size_t nelem = 32) :
    elcount (nelem), elsize(Size), freenode(0), insideDisposeAll(false)
  {
#ifdef CS_MEMORY_TRACKER
    blocks.SetMemTrackerInfo (typeid(*this).name());
#endif
    if (elsize < sizeof (FreeNode))
      elsize = sizeof (FreeNode);
    blocksize = elsize * elcount;
  }

  ~csFixedSizeAllocator()
  {
    DefaultDisposer disposer (*this, false);
    DisposeAll (disposer);
  }

  void Empty()
  {
    DefaultDisposer disposer (*this, true);
    DisposeAll (disposer);
  }

  void Compact()
  {
    if (insideDisposeAll) return;

    bool compacted = false;
    csBitArray mask(GetAllocationMap());
    for (size_t b = blocks.b.GetSize(); b-- > 0; )
    {
      size_t const node = b * elcount;
      if (!mask.AreSomeBitsSet(node, elcount))
      {
        FreeBlock(blocks.b[b]);
        blocks.b.DeleteIndex(b);
        mask.Delete(node, elcount);
        compacted = true;
      }
    }

    // If blocks were deleted, then free-node chain broke, so rebuild it.
    if (compacted)
    {
      FreeNode* nextfree = 0;
      size_t const bN = blocks.b.GetSize();
      size_t node = bN * elcount;
      for (size_t b = bN; b-- > 0; )
      {
        uint8* const p0 = blocks.b[b];
        for (uint8* p = p0 + (elcount - 1) * elsize; p >= p0; p -= elsize)
        {
          if (!mask.IsBitSet(--node))
          {
            FreeNode* slot = (FreeNode*)p;
            slot->next = nextfree;
            nextfree = slot;
          }
        }
      }
      freenode = nextfree;
    }
  }

  void* Alloc ()
  {
    return AllocCommon();
  }

  void Free (void* p)
  {
    DefaultDisposer disposer (*this, true);
    Free (disposer, p);
  }
  bool TryFree (void* p)
  {
    DefaultDisposer disposer (*this, true);
    return TryFree (disposer, p);
  }
  size_t GetBlockElements() const { return elcount; }
  
  void* Alloc (size_t n)
  {
    CS_ASSERT (n == Size);
    return Alloc();
  }
  void* Alloc (void* p, size_t newSize)
  {
    CS_ASSERT (newSize == Size);
    return p;
  }
  void SetMemTrackerInfo (const char* /*info*/) { }
};

#endif // __CSUTIL_FIXEDSIZEALLOCATOR_H__

---