src/NCollection/NCollection_AccAllocator.cxx

   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 #include <NCollection_AccAllocator.hxx>
  17 #include <Standard_OutOfMemory.hxx>
  18 #include <Standard_Assert.hxx>
  19
  20
  21 IMPLEMENT_STANDARD_RTTIEXT(NCollection_AccAllocator,NCollection_BaseAllocator)
  22
  23 //=======================================================================
  24 //function : NCollection_AccAllocator
  25 //purpose  : Constructor
  26 //=======================================================================
  27 NCollection_AccAllocator::NCollection_AccAllocator(const size_t theBlockSize)
  28 : myBlockSize(theBlockSize), mypLastBlock(0L)
  29 {
  30   allocateNewBlock(myBlockSize);
  31 }
  32
  33 //=======================================================================
  34 //function : ~NCollection_AccAllocator
  35 //purpose  : Destructor
  36 //=======================================================================
  37 NCollection_AccAllocator::~NCollection_AccAllocator()
  38 {
  39   for (Block* aBlock = mypLastBlock; aBlock; aBlock = aBlock->prevBlock)
  40   {
  41     Standard::Free(aBlock->address);
  42   }
  43 }
  44
  45 //=======================================================================
  46 //function : Allocate
  47 //purpose  : Allocate a memory
  48 //=======================================================================
  49 void* NCollection_AccAllocator::Allocate(const size_t theSize)
  50 {
  51   const AlignedSize aSize(theSize);
  52   Block* aBlock;
  53
  54   if (aSize <= mypLastBlock->FreeSize())
  55   {
  56     aBlock = mypLastBlock;
  57   }
  58   else if (aSize > myBlockSize)
  59   {
  60     // If the requested size exceeds normal allocation size,
  61     // allocate a separate block
  62     aBlock = allocateNewBlock(aSize);
  63   }
  64   else
  65   {
  66     // Search for a block in the list with enough free space
  67     Standard_Integer aBlocksRest = MaxLookupBlocks;
  68     for (aBlock = mypLastBlock->prevBlock;
  69          aBlock != 0L && --aBlocksRest;
  70          aBlock = aBlock->prevBlock)
  71     {
  72       if (aSize <= aBlock->FreeSize())
  73         break;
  74     }
  75     if (aBlock == 0L || !aBlocksRest)
  76       // There is no available block with enough free space, create a new one
  77       aBlock = allocateNewBlock(myBlockSize);
  78   }
  79
  80   void* anAddress = aBlock->Allocate(aSize);
  81 #ifdef OCCT_DEBUG_FINDBLOCK
  82   Key aKey;
  83   Standard_ASSERT_VOID(aBlock == findBlock(anAddress, aKey),
  84                        "improper work of NCollection_AccAllocator::findBlock");
  85 #endif
  86   return anAddress;
  87 }
  88
  89 //=======================================================================
  90 //function : Free
  91 //purpose  : Free a previously allocated memory
  92 //=======================================================================
  93 void NCollection_AccAllocator::Free(void* theAddress)
  94 {
  95   Key aKey;
  96   Block* aBlock = findBlock(theAddress, aKey);
  97
  98 #if !defined No_Exception && !defined No_Standard_ProgramError
  99   if (aBlock == 0L || aBlock->IsEmpty())
 100   {
 101     throw Standard_ProgramError("NCollection_AccAllocator::Free: \
 102                                 Trying to free an invalid address");
 103   }
 104 #endif
 105
 106   aBlock->Free();
 107   if (aBlock->IsEmpty())
 108   {
 109     Standard_Address anAddress = aBlock->address;
 110
 111     // Deallocate and remove the free block if there are more blocks
 112     if (myBlocks.Size() > 1)
 113     {
 114       Standard::Free(anAddress);
 115       Block** appBlock;
 116       for (appBlock = &mypLastBlock;
 117           *appBlock != 0L;
 118            appBlock = &(*appBlock)->prevBlock)
 119       {
 120         if (*appBlock == aBlock)
 121         {
 122           *appBlock = aBlock->prevBlock;
 123           break;
 124         }
 125       }
 126       myBlocks.UnBind(aKey);
 127     }
 128     // If there are no more blocks, reallocate the block to the default size
 129     else
 130     {
 131       Standard_Address aNewAddress = Standard::Reallocate(anAddress,
 132                                                           myBlockSize);
 133       if (aNewAddress == anAddress)
 134       {
 135         // Normally, the reallocation keeps the block at the same address
 136         // (since no block can be smaller than the default size, and thus
 137         // the allocated memory is just shrunk or untouched).
 138         // In this case, just update the block's free size.
 139         aBlock->SetFreeSize(myBlockSize);
 140       }
 141       else
 142       {
 143         // Reallocation still may return a different address even if the new
 144         // size is equal to or smaller than the old one (this can happen in
 145         // debug mode).
 146         Key aNewKey = getKey(aNewAddress);
 147         if (aNewKey.Value == aKey.Value)
 148         {
 149           // If the new address have the same key,
 150           // just update the block's address and free size
 151           aBlock->address = aNewAddress;
 152           aBlock->SetFreeSize(myBlockSize);
 153         }
 154         else
 155         {
 156           // If the new address have different key,
 157           // rebind the block to the map of blocks with the new key.
 158           myBlocks.Clear(Standard_False);
 159           mypLastBlock = myBlocks.Bound(aNewKey,
 160                                         Block(aNewAddress, myBlockSize));
 161         }
 162       }
 163     }
 164   }
 165 }
 166
 167 //=======================================================================
 168 //function : findBlock
 169 //purpose  : Find a block that the given allocation unit belongs to
 170 //=======================================================================
 171 NCollection_AccAllocator::Block*
 172 NCollection_AccAllocator::findBlock(const Standard_Address theAddress, Key& theKey)
 173 {
 174   theKey = getKey(theAddress);
 175
 176   Block* aBlock = myBlocks.ChangeSeek(theKey);
 177   if (aBlock && aBlock->address <= theAddress)
 178   {
 179     return aBlock;
 180   }
 181
 182   theKey.Value--;
 183   aBlock = myBlocks.ChangeSeek(theKey);
 184   if (aBlock &&
 185     (Standard_Byte*)aBlock->address + (Standard_Size)myBlockSize > theAddress)
 186   {
 187     return aBlock;
 188   }
 189
 190   return 0L;
 191 }
 192
 193 //=======================================================================
 194 //function : allocateNewBlock
 195 //purpose  : Allocate a new block and return a pointer to it
 196 //=======================================================================
 197 NCollection_AccAllocator::Block*
 198 NCollection_AccAllocator::allocateNewBlock(const Standard_Size theSize)
 199 {
 200   Standard_Address anAddress = Standard::Allocate(theSize);
 201   // we depend on the fact that Standard::Allocate always returns
 202   // a pointer aligned to a 4 byte boundary
 203   mypLastBlock = myBlocks.Bound(getKey(anAddress),
 204                                 Block(anAddress, theSize, mypLastBlock));
 205 #ifdef OCCT_DEBUG_FINDBLOCK
 206   Key aKey;
 207   Standard_ASSERT_VOID(
 208     mypLastBlock == findBlock((Standard_Byte*)mypLastBlock->allocStart-1, aKey),
 209     "improper work of NCollection_AccAllocator::findBlock");
 210 #endif
 211   return mypLastBlock;
 212 }