heap_memory.cpp

Go to the documentation of this 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

Generated on Tue Mar 16 06:26:07 2004 for NeL by doxygen 1.3.6