nel/src/misc/heap_memory.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "stdmisc.h"
  18
  19 #include "nel/misc/heap_memory.h"
  20 #include "nel/misc/debug.h"
  21
  22 using namespace std;
  23
  24 #ifdef DEBUG_NEW
  25         #define new DEBUG_NEW
  26 #endif
  27
  28 namespace NLMISC
  29 {
  30
  31
  32 // ***************************************************************************
  33 CHeapMemory::CHeapMemory()
  34 {
  35         reset();
  36         // For allocate to work even if the heap is not initialized.
  37         _Alignment= 4;
  38 }
  39 // ***************************************************************************
  40 CHeapMemory::~CHeapMemory()
  41 {
  42         reset();
  43 }
  44
  45
  46 // ***************************************************************************
  47 void                    CHeapMemory::reset()
  48 {
  49         _EmptySpaces.clear();
  50         _EmptySpaceMap.clear();
  51         _AllocatedSpaceMap.clear();
  52         _HeapPtr= NULL;
  53         _HeapSize= 0;
  54         _HeapSizeUsed= 0;
  55 }
  56
  57
  58 // ***************************************************************************
  59 void                    CHeapMemory::initHeap(void *heap, uint size, uint align)
  60 {
  61         // setup alignement.
  62         if(align!=4 && align!=8 && align!=16 && align!=32)
  63         {
  64                 nlstop;
  65                 align= 4;
  66         }
  67         _Alignment= align;
  68
  69         // Manage alignement.
  70         size= (size) & (~(_Alignment-1));
  71
  72         // clear container.
  73         reset();
  74         if(heap==0 || size==0)
  75                 return;
  76
  77         _HeapPtr= (uint8*)heap;
  78         _HeapSize= size;
  79         _HeapSizeUsed= 0;
  80
  81         // Add the only one empty space.
  82         CEmptySpace             space;
  83         space.Ptr= _HeapPtr;
  84         space.Size= _HeapSize;
  85
  86         addEmptySpace(space);
  87 }
  88
  89
  90 // ***************************************************************************
  91 void            CHeapMemory::removeEmptySpace(CEmptySpace &space)
  92 {
  93         // remove the iterator on the spaceMap.
  94         _EmptySpaceMap.erase( space.SizeIt );
  95
  96         // remove from the list of EmptySpaces. NB: must fo it after all, because "space" may be deleted.
  97         _EmptySpaces.erase( space.Ptr );
  98 }
  99
 100
 101 // ***************************************************************************
 102 void            CHeapMemory::addEmptySpace(CEmptySpace &space)
 103 {
 104         // insert and get the iterator on the spaceMap.
 105         space.SizeIt= _EmptySpaceMap.insert( make_pair(space.Size, space.Ptr));
 106
 107         // insert into the list of EmptySpaces.
 108         _EmptySpaces.insert( make_pair(space.Ptr, space) );
 109 }
 110
 111
 112 // ***************************************************************************
 113 void                    *CHeapMemory::allocate(uint size)
 114 {
 115         if(size==0)
 116                 return NULL;
 117
 118         // Manage alignement.
 119         size= (size + (_Alignment-1)) & (~(_Alignment-1));
 120
 121
 122         // retrieve the best block.
 123         //=========================
 124         CEmptySpace             bestSpace;
 125         // NB: do a copy, because of removeEmptySpace() which delete the space.
 126
 127         // Find the smaller space which is >= than size.
 128         ItEmptySpaceSizeMap             it;
 129         it= _EmptySpaceMap.lower_bound(size);
 130
 131         // if not found, alloc fails.
 132         if(it == _EmptySpaceMap.end())
 133                 return NULL;
 134         else
 135         {
 136                 // NB: this space must exist in the "array".
 137                 bestSpace= _EmptySpaces[it->second];
 138         }
 139
 140
 141         // remove this empty space from list.
 142         //=========================
 143         removeEmptySpace(bestSpace);
 144
 145
 146         // if any, add the space unused to the list.
 147         //=========================
 148         if(bestSpace.Size > size)
 149         {
 150                 CEmptySpace             space;
 151                 space.Ptr= bestSpace.Ptr + size;
 152                 space.Size= bestSpace.Size - size;
 153
 154                 addEmptySpace(space);
 155         }
 156
 157
 158         // return / insert the allocated space.
 159         //=========================
 160         _AllocatedSpaceMap.insert(make_pair(bestSpace.Ptr, size));
 161         _HeapSizeUsed+= size;
 162
 163         // return the ptr of start of this empty space.
 164         return bestSpace.Ptr;
 165 }
 166
 167 // ***************************************************************************
 168 void                    CHeapMemory::freeBlock(void *ptr)
 169 {
 170         if(ptr==NULL)
 171                 return;
 172
 173         // Must find the array in allocated spaces.
 174         //==========================
 175         ItAllocatedSpaceMap             itAlloc= _AllocatedSpaceMap.find((uint8*)ptr);
 176         if(itAlloc == _AllocatedSpaceMap.end())
 177         {
 178                 nlstop;
 179                 return;
 180         }
 181         uint    size= itAlloc->second;
 182
 183         // free this space from allocated Spaces.
 184         _AllocatedSpaceMap.erase(itAlloc);
 185         _HeapSizeUsed-= size;
 186
 187
 188         // Must find previous or/and next empty space, if any.
 189         //==========================
 190         ItEmptySpacePtrMap              itPrevious, itNext;
 191
 192         // find the empty space which is immediately >= than ptr.
 193         itNext= _EmptySpaces.lower_bound((uint8*)ptr);
 194         // NB: it may be end(), if it is the last block (very rare).
 195
 196         // some check. next empty space ptr must be after ptr.
 197         if(itNext!=_EmptySpaces.end())
 198         {
 199                 nlassert(itNext->second.Ptr >= (uint8*)ptr + size);
 200         }
 201
 202         // if itNext is not the first empty space, there is an empty space before us.
 203         if( itNext!= _EmptySpaces.begin() )
 204         {
 205                 // NB: work even if itNext==end().
 206                 itPrevious= itNext;
 207                 itPrevious--;
 208                 // some check. previous empty space ptr must be before ptr.
 209                 nlassert(itPrevious!=_EmptySpaces.end());
 210                 nlassert(itPrevious->second.Ptr + itPrevious->second.Size <= (uint8*)ptr );
 211         }
 212         else
 213                 itPrevious= _EmptySpaces.end();
 214
 215
 216         // if next exist.
 217         if(itNext!=_EmptySpaces.end())
 218         {
 219                 // If Previous is not just after allocated ptr, it means that there is some allocated blocks beetween,
 220                 // so it is not a valid empty space to concat.
 221                 if(itNext->second.Ptr != (uint8*)ptr + size)
 222                         itNext= _EmptySpaces.end();
 223         }
 224         // if previous exist.
 225         if(itPrevious!=_EmptySpaces.end())
 226         {
 227                 // If Previous is not just before allocated ptr, it means that there is some allocated blocks beetween,
 228                 // so it is not a valid empty space to concat.
 229                 if(itPrevious->second.Ptr + itPrevious->second.Size != (uint8*)ptr )
 230                         itPrevious=_EmptySpaces.end();
 231         }
 232
 233
 234
 235         // According to configuration, build the new empty space, mreging previous and next, and remove old ones.
 236         //==========================
 237         CEmptySpace             newSpace;
 238
 239         // if no previous empty space, then newSpace start at ptr.
 240         if(itPrevious == _EmptySpaces.end())
 241         {
 242                 // Start with old allocated block.
 243                 newSpace.Ptr= (uint8*)ptr;
 244                 newSpace.Size= size;
 245         }
 246         // else, start at previous Ptr.
 247         else
 248         {
 249                 // Start with previous block. size is previous size + allocated block size.
 250                 newSpace.Ptr= itPrevious->second.Ptr;
 251                 newSpace.Size= itPrevious->second.Size + size;
 252         }
 253
 254         // if next empty space, must inc size.
 255         if(itNext != _EmptySpaces.end())
 256         {
 257                 newSpace.Size+= itNext->second.Size;
 258         }
 259
 260
 261         // remove old empty space, and add new one.
 262         //==========================
 263
 264         // remove old empty spaces.
 265         if(itPrevious != _EmptySpaces.end())
 266                 removeEmptySpace(itPrevious->second);
 267         if(itNext != _EmptySpaces.end())
 268                 removeEmptySpace(itNext->second);
 269
 270
 271         // Add the new concatenated empty space.
 272         addEmptySpace(newSpace);
 273 }
 274
 275
 276
 277 } // NLMISC