NeL: heap_memory.cpp Source File

00001 
+00007 /* Copyright, 2001 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #include "stdmisc.h"
+00027 
+00028 #include "nel/misc/heap_memory.h"
+00029 
+00030 using namespace std;
+00031 
+00032 
+00033 namespace NLMISC 
+00034 {
+00035 
+00036 
+00037 // ***************************************************************************
+00038 CHeapMemory::CHeapMemory()
+00039 {
+00040         reset();
+00041         // For allocate to work even if the heap is not initialized.
+00042         _Alignment= 4;
+00043 }
+00044 // ***************************************************************************
+00045 CHeapMemory::~CHeapMemory()
+00046 {
+00047         reset();
+00048 }
+00049 
+00050 
+00051 // ***************************************************************************
+00052 void                    CHeapMemory::reset()
+00053 {
+00054         _EmptySpaces.clear();
+00055         _EmptySpaceMap.clear();
+00056         _AllocatedSpaceMap.clear();
+00057         _HeapPtr= NULL;
+00058         _HeapSize= 0;
+00059         _HeapSizeUsed= 0;
+00060 }
+00061 
+00062 
+00063 // ***************************************************************************
+00064 void                    CHeapMemory::initHeap(void *heap, uint size, uint align)
+00065 {
+00066         // setup alignement.
+00067         if(align!=4 && align!=8 && align!=16 && align!=32)
+00068         {
+00069                 nlstop;
+00070                 align= 4;
+00071         }
+00072         _Alignment= align;
+00073 
+00074         // Manage alignement.
+00075         size= (size) & (~(_Alignment-1));
+00076 
+00077         // clear container.
+00078         reset();
+00079         if(heap==0 || size==0)
+00080                 return;
+00081 
+00082         _HeapPtr= (uint8*)heap;
+00083         _HeapSize= size;
+00084         _HeapSizeUsed= 0;
+00085 
+00086         // Add the only one empty space.
+00087         CEmptySpace             space;
+00088         space.Ptr= _HeapPtr;
+00089         space.Size= _HeapSize;
+00090 
+00091         addEmptySpace(space);
+00092 }
+00093 
+00094 
+00095 // ***************************************************************************
+00096 void            CHeapMemory::removeEmptySpace(CEmptySpace &space)
+00097 {
+00098         // remove the iterator on the spaceMap.
+00099         _EmptySpaceMap.erase( space.SizeIt );
+00100 
+00101         // remove from the list of EmptySpaces. NB: must fo it after all, because "space" may be deleted.
+00102         _EmptySpaces.erase( space.Ptr );
+00103 }
+00104 
+00105 
+00106 // ***************************************************************************
+00107 void            CHeapMemory::addEmptySpace(CEmptySpace &space)
+00108 {
+00109         // insert and get the iterator on the spaceMap.
+00110         space.SizeIt= _EmptySpaceMap.insert( make_pair(space.Size, space.Ptr));
+00111 
+00112         // insert into the list of EmptySpaces.
+00113         _EmptySpaces.insert( make_pair(space.Ptr, space) );
+00114 }
+00115 
+00116 
+00117 // ***************************************************************************
+00118 void                    *CHeapMemory::allocate(uint size)
+00119 {
+00120         if(size==0)
+00121                 return NULL;
+00122 
+00123         // Manage alignement.
+00124         size= (size + (_Alignment-1)) & (~(_Alignment-1));
+00125 
+00126 
+00127         // retrieve the best block.
+00128         //=========================
+00129         CEmptySpace             bestSpace;
+00130         // NB: do a copy, because of removeEmptySpace() which delete the space.
+00131 
+00132         // Find the smaller space which is >= than size.
+00133         ItEmptySpaceSizeMap             it;
+00134         it= _EmptySpaceMap.lower_bound(size);
+00135 
+00136         // if not found, alloc fails.
+00137         if(it == _EmptySpaceMap.end())
+00138                 return NULL;
+00139         else
+00140         {
+00141                 // NB: this space must exist in the "array".
+00142                 bestSpace= _EmptySpaces[it->second];
+00143         }
+00144 
+00145 
+00146         // remove this empty space from list.
+00147         //=========================
+00148         removeEmptySpace(bestSpace);
+00149 
+00150 
+00151         // if any, add the space unused to the list.
+00152         //=========================
+00153         if(bestSpace.Size > size)
+00154         {
+00155                 CEmptySpace             space;
+00156                 space.Ptr= bestSpace.Ptr + size;
+00157                 space.Size= bestSpace.Size - size;
+00158 
+00159                 addEmptySpace(space);
+00160         }
+00161 
+00162 
+00163         // return / insert the allocated space.
+00164         //=========================
+00165         _AllocatedSpaceMap.insert(make_pair(bestSpace.Ptr, size));
+00166         _HeapSizeUsed+= size;
+00167 
+00168         // return the ptr of start of this empty space.
+00169         return bestSpace.Ptr;
+00170 }
+00171 
+00172 // ***************************************************************************
+00173 void                    CHeapMemory::free(void *ptr)
+00174 {
+00175         if(ptr==NULL)
+00176                 return;
+00177 
+00178         // Must find the array in allocated spaces.
+00179         //==========================
+00180         ItAllocatedSpaceMap             itAlloc= _AllocatedSpaceMap.find((uint8*)ptr);
+00181         if(itAlloc == _AllocatedSpaceMap.end())
+00182         {
+00183                 nlstop;
+00184                 return;
+00185         }
+00186         uint    size= itAlloc->second;
+00187 
+00188         // free this space from allocated Spaces.
+00189         _AllocatedSpaceMap.erase(itAlloc);
+00190         _HeapSizeUsed-= size;
+00191 
+00192 
+00193         // Must find previous or/and next empty space, if any.
+00194         //==========================
+00195         ItEmptySpacePtrMap              itPrevious, itNext;
+00196 
+00197         // find the empty space which is immediately >= than ptr.
+00198         itNext= _EmptySpaces.lower_bound((uint8*)ptr);
+00199         // NB: it may be end(), if it is the last block (very rare).
+00200 
+00201         // some check. next empty space ptr must be after ptr.
+00202         if(itNext!=_EmptySpaces.end())
+00203         {
+00204                 nlassert(itNext->second.Ptr >= (uint8*)ptr + size);
+00205         }
+00206 
+00207         // if itNext is not the first empty space, there is an empty space before us.
+00208         if( itNext!= _EmptySpaces.begin() )
+00209         {
+00210                 // NB: work even if itNext==end().
+00211                 itPrevious= itNext;
+00212                 itPrevious--;
+00213                 // some check. previous empty space ptr must be before ptr.
+00214                 nlassert(itPrevious!=_EmptySpaces.end());
+00215                 nlassert(itPrevious->second.Ptr + itPrevious->second.Size <= (uint8*)ptr );
+00216         }
+00217         else
+00218                 itPrevious= _EmptySpaces.end();
+00219 
+00220 
+00221         // if next exist.
+00222         if(itNext!=_EmptySpaces.end())
+00223         {
+00224                 // If Previous is not just after allocated ptr, it means that there is some allocated blocks beetween,
+00225                 // so it is not a valid empty space to concat.
+00226                 if(itNext->second.Ptr != (uint8*)ptr + size)
+00227                         itNext= _EmptySpaces.end();
+00228         }
+00229         // if previous exist.
+00230         if(itPrevious!=_EmptySpaces.end())
+00231         {
+00232                 // If Previous is not just before allocated ptr, it means that there is some allocated blocks beetween,
+00233                 // so it is not a valid empty space to concat.
+00234                 if(itPrevious->second.Ptr + itPrevious->second.Size != (uint8*)ptr )
+00235                         itPrevious=_EmptySpaces.end();
+00236         }
+00237 
+00238 
+00239 
+00240         // According to configuration, build the new empty space, mreging previous and next, and remove old ones.
+00241         //==========================
+00242         CEmptySpace             newSpace;
+00243 
+00244         // if no previous empty space, then newSpace start at ptr.
+00245         if(itPrevious == _EmptySpaces.end())
+00246         {
+00247                 // Start with old allocated block.
+00248                 newSpace.Ptr= (uint8*)ptr;
+00249                 newSpace.Size= size;
+00250         }
+00251         // else, start at previous Ptr.
+00252         else
+00253         {
+00254                 // Start with previous block. size is previous size + allocated block size.
+00255                 newSpace.Ptr= itPrevious->second.Ptr;
+00256                 newSpace.Size= itPrevious->second.Size + size;
+00257         }
+00258 
+00259         // if next empty space, must inc size.
+00260         if(itNext != _EmptySpaces.end())
+00261         {
+00262                 newSpace.Size+= itNext->second.Size;
+00263         }
+00264 
+00265 
+00266         // remove old empty space, and add new one.
+00267         //==========================
+00268 
+00269         // remove old empty spaces.
+00270         if(itPrevious != _EmptySpaces.end())
+00271                 removeEmptySpace(itPrevious->second);
+00272         if(itNext != _EmptySpaces.end())
+00273                 removeEmptySpace(itNext->second);
+00274 
+00275 
+00276         // Add the new concatenated empty space.
+00277         addEmptySpace(newSpace);
+00278 }
+00279 
+00280 
+00281 
+00282 } // NLMISC
+