NeL: NLMISC::CHeapMemory class Reference

00039 {
+00040         reset();
+00041         // For allocate to work even if the heap is not initialized.
+00042         _Alignment= 4;
+00043 }
+

00046 {
+00047         reset();
+00048 }
+

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 }
+

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 }
+

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 }
+

00067 {return _HeapSize;}
+

00069 {return _HeapSizeUsed;}
+

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 }
+

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 }
+

00053 {
+00054         _EmptySpaces.clear();
+00055         _EmptySpaceMap.clear();
+00056         _AllocatedSpaceMap.clear();
+00057         _HeapPtr= NULL;
+00058         _HeapSize= 0;
+00059         _HeapSizeUsed= 0;
+00060 }
+


Public Member Functions
void *	allocate (uint size)
	CHeapMemory ()
	Constructor.
void	free (void *ptr)
	free a block allocated with alloate(). no-op if NULL. nlstop() if don't find this block.
uint	getHeapSize () const
	return the size passed in setHeap().
uint	getHeapSizeUsed () const
	return the heap size allocated.
void	initHeap (void *heap, uint size, uint align=4)
void	reset ()
	reset the entire container. NB: no free() is made on the heap.
	~CHeapMemory ()
Private Types
typedef TAllocatedSpaceMap::iterator	ItAllocatedSpaceMap
typedef TEmptySpacePtrMap::iterator	ItEmptySpacePtrMap
typedef TEmptySpaceSizeMap::iterator	ItEmptySpaceSizeMap
typedef std::map< uint8 *, + uint >	TAllocatedSpaceMap
typedef std::map< uint8 *, + CEmptySpace >	TEmptySpacePtrMap
typedef std::multimap< uint, + uint8 * >	TEmptySpaceSizeMap
Private Member Functions
void	addEmptySpace (CEmptySpace &space)
void	removeEmptySpace (CEmptySpace &space)
Private Attributes
uint	_Alignment
TAllocatedSpaceMap	_AllocatedSpaceMap
TEmptySpaceSizeMap	_EmptySpaceMap
	for allocate method, the size -> empty space map.
TEmptySpacePtrMap	_EmptySpaces
	The array of empty spaces.
uint8 *	_HeapPtr
uint	_HeapSize
uint	_HeapSizeUsed

NLMISC::CHeapMemory Class Reference

Detailed Description

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation