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