src/NCollection/NCollection_AccAllocator.hxx

   1 // Created on: 2013-11-12
   2 // Created by: Maxim YAKUNIN (myn)
   3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16
  17 #ifndef NCollection_AccAllocator_HeaderFile
  18 #define NCollection_AccAllocator_HeaderFile
  19
  20 #include <NCollection_BaseAllocator.hxx>
  21 #include <NCollection_DataMap.hxx>
  22
  23 //!
  24 //! Class  NCollection_AccAllocator  -  accumulating  memory  allocator.  This
  25 //! class  allocates  memory on request returning the pointer to the allocated
  26 //! space.  The  allocation  units  are  grouped  in blocks requested from the
  27 //! system  as  required.  This  memory  is  returned  to  the system when all
  28 //! allocations in a block are freed.
  29 //!
  30 //! By comparison with  the standard new() and malloc()  calls, this method is
  31 //! faster and consumes very small additional memory to maintain the heap.
  32 //!
  33 //! By comparison with NCollection_IncAllocator,  this class requires some more
  34 //! additional memory  and a little more time for allocation and deallocation.
  35 //! Memory overhead for NCollection_IncAllocator is 12 bytes per block;
  36 //! average memory overhead for NCollection_AccAllocator is 28 bytes per block.
  37 //!
  38 //! All pointers  returned by Allocate() are aligned to 4 byte boundaries.
  39 //! To  define  the size  of  memory  blocks  requested  from the OS,  use the
  40 //! parameter of the constructor (measured in bytes).
  41
  42 class NCollection_AccAllocator : public NCollection_BaseAllocator
  43 {
  44 // --------- PUBLIC CONSTANTS ---------
  45 public:
  46   //! Alignment of all allocated objects: 4 bytes
  47   static const Standard_Size    Align            = 4;
  48
  49   //! Default block size
  50   static const Standard_Size    DefaultBlockSize = 24600;
  51
  52   //! Number of last blocks to check for free space
  53   static const Standard_Integer MaxLookupBlocks  = 16;
  54
  55 // ---------- PUBLIC METHODS ----------
  56 public:
  57   //! Constructor
  58   Standard_EXPORT NCollection_AccAllocator(const size_t
  59                                            theBlockSize = DefaultBlockSize);
  60
  61   //! Destructor
  62   Standard_EXPORT ~NCollection_AccAllocator();
  63
  64   //! Allocate memory with given size
  65   Standard_EXPORT virtual void* Allocate  (const size_t theSize);
  66
  67   //! Free a previously allocated memory;
  68   //! memory is returned to the OS when all allocations in some block are freed
  69   Standard_EXPORT virtual void  Free      (void* theAddress);
  70
  71 // --------- PROTECTED TYPES ---------
  72 protected:
  73   //! Size value aligned to a 4 byte boundary
  74   class AlignedSize
  75   {
  76     Standard_Size myValue;
  77   public:
  78     AlignedSize(){}
  79     AlignedSize(const Standard_Size theValue)
  80       : myValue((theValue + Align - 1) & ~(Align - 1)) {}
  81     operator       Standard_Size()       {return myValue;}
  82     operator const Standard_Size() const {return myValue;}
  83   };
  84
  85   //! A pointer aligned to a 4 byte boundary
  86   class AlignedPtr
  87   {
  88     Standard_Byte* myValue;
  89   public:
  90     AlignedPtr(){}
  91     AlignedPtr(const Standard_Address theValue)
  92       : myValue((Standard_Byte*)((Standard_Size)theValue & ~(Align - 1))) {}
  93     operator Standard_Address       ()       {return myValue;}
  94     operator Standard_Address const () const {return myValue;}
  95     operator Standard_Byte*         ()       {return myValue;}
  96     operator Standard_Byte*   const () const {return myValue;}
  97     AlignedPtr operator -(const AlignedSize theValue) const
  98       {return myValue - theValue;}
  99     AlignedPtr operator +(const AlignedSize theValue) const
 100       {return myValue + theValue;}
 101     AlignedPtr operator -=(const AlignedSize theValue)
 102       {return myValue -= theValue;}
 103     AlignedPtr operator +=(const AlignedSize theValue)
 104       {return myValue += theValue;}
 105   };
 106
 107   //! A key for the map of blocks
 108   struct Key {Standard_Size Value;};
 109
 110   //! Key hasher
 111   class Hasher
 112   {
 113   public:
 114     static Standard_Integer HashCode(const Key theKey, const Standard_Integer theUpper)
 115     { return theKey.Value % theUpper + 1; }
 116
 117     static Standard_Boolean IsEqual(const Key theOne, const Key theTwo)
 118     { return theOne.Value == theTwo.Value; }
 119   };
 120
 121   //! Descriptor of a block
 122   struct Block
 123   {
 124     Standard_Address address;
 125     AlignedPtr       allocStart;
 126     Block*           prevBlock;
 127     Standard_Integer allocCount;
 128
 129     Block(const Standard_Address theAddress,
 130           const Standard_Size    theSize,
 131           Block*                 thePrevBlock = 0L)
 132       : address(theAddress), prevBlock(thePrevBlock), allocCount(0)
 133       {SetFreeSize (theSize);}
 134
 135     void SetFreeSize(const Standard_Size theSize)
 136       {allocStart = (Standard_Byte*)address + theSize;}
 137
 138     Standard_Size FreeSize() const
 139       {return (Standard_Byte*)allocStart - (Standard_Byte*)address;}
 140
 141     AlignedPtr Allocate(const AlignedSize theSize)
 142       {allocCount++; return allocStart -= theSize;}
 143
 144     void Free()
 145       {allocCount--;}
 146
 147     Standard_Boolean IsEmpty() const
 148       {return allocCount == 0;}
 149   };
 150
 151 // --------- PROTECTED METHODS ---------
 152 protected:
 153   //! Calculate a key for the data map basing on the given address
 154   inline Key getKey(const Standard_Address theAddress) const
 155   {
 156     Key aKey = {(Standard_Size)theAddress / myBlockSize};
 157     return aKey;
 158   }
 159
 160   //! Find a block that the given allocation unit belongs to
 161   Standard_EXPORT Block* findBlock(const Standard_Address theAddress, Key& theKey);
 162
 163   //! Allocate a new block and return a pointer to it
 164   Standard_EXPORT Block* allocateNewBlock(const Standard_Size theSize);
 165
 166 // --------- PROHIBITED METHODS ---------
 167 private:
 168   NCollection_AccAllocator (const NCollection_AccAllocator&);
 169   NCollection_AccAllocator& operator = (const NCollection_AccAllocator&);
 170
 171 // --------- PROTECTED DATA ---------
 172 protected:
 173   AlignedSize myBlockSize;
 174   Block*      mypLastBlock;
 175   NCollection_DataMap<Key, Block, Hasher> myBlocks;
 176
 177 // Declaration of CASCADE RTTI
 178 public:
 179   DEFINE_STANDARD_RTTI (NCollection_AccAllocator, NCollection_BaseAllocator)
 180 };
 181
 182 // Definition of HANDLE object using Standard_DefineHandle.hxx
 183 DEFINE_STANDARD_HANDLE (NCollection_AccAllocator, NCollection_BaseAllocator)
 184
 185
 186 #endif