Home

nevrax.com

Nevrax.org News Mailing-list Documentation CVS Bugs License

Documentation                       Search   heap_memory.cpp Go to the documentation of this file. /* Copyright, 2001 Nevrax Ltd. * * This file is part of NEVRAX NEL. * NEVRAX NEL is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2, or (at your option) * any later version. * NEVRAX NEL is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * You should have received a copy of the GNU General Public License * along with NEVRAX NEL; see the file COPYING. If not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ #include "stdmisc.h" #include "nel/misc/heap_memory.h" using namespace std; namespace NLMISC { // *************************************************************************** CHeapMemory::CHeapMemory() { reset(); // For allocate to work even if the heap is not initialized. _Alignment= 4; } // *************************************************************************** CHeapMemory::~CHeapMemory() { reset(); } // *************************************************************************** void CHeapMemory::reset() { _EmptySpaces.clear(); _EmptySpaceMap.clear(); _AllocatedSpaceMap.clear(); _HeapPtr= NULL; _HeapSize= 0; _HeapSizeUsed= 0; } // *************************************************************************** void CHeapMemory::initHeap(void *heap, uint size, uint align) { // setup alignement. if(align!=4 && align!=8 && align!=16 && align!=32) { nlstop; align= 4; } _Alignment= align; // Manage alignement. size= (size) & (~(_Alignment-1)); // clear container. reset(); if(heap==0 || size==0) return; _HeapPtr= (uint8*)heap; _HeapSize= size; _HeapSizeUsed= 0; // Add the only one empty space. CEmptySpace space; space.Ptr= _HeapPtr; space.Size= _HeapSize; addEmptySpace(space); } // *************************************************************************** void CHeapMemory::removeEmptySpace(CEmptySpace &space) { // remove the iterator on the spaceMap. _EmptySpaceMap.erase( space.SizeIt ); // remove from the list of EmptySpaces. NB: must fo it after all, because "space" may be deleted. _EmptySpaces.erase( space.Ptr ); } // *************************************************************************** void CHeapMemory::addEmptySpace(CEmptySpace &space) { // insert and get the iterator on the spaceMap. space.SizeIt= _EmptySpaceMap.insert( make_pair(space.Size, space.Ptr)); // insert into the list of EmptySpaces. _EmptySpaces.insert( make_pair(space.Ptr, space) ); } // *************************************************************************** void *CHeapMemory::allocate(uint size) { if(size==0) return NULL; // Manage alignement. size= (size + (_Alignment-1)) & (~(_Alignment-1)); // retrieve the best block. //========================= CEmptySpace bestSpace; // NB: do a copy, because of removeEmptySpace() which delete the space. // Find the smaller space which is >= than size. ItEmptySpaceSizeMap it; it= _EmptySpaceMap.lower_bound(size); // if not found, alloc fails. if(it == _EmptySpaceMap.end()) return NULL; else { // NB: this space must exist in the "array". bestSpace= _EmptySpaces[it->second]; } // remove this empty space from list. //========================= removeEmptySpace(bestSpace); // if any, add the space unused to the list. //========================= if(bestSpace.Size > size) { CEmptySpace space; space.Ptr= bestSpace.Ptr + size; space.Size= bestSpace.Size - size; addEmptySpace(space); } // return / insert the allocated space. //========================= _AllocatedSpaceMap.insert(make_pair(bestSpace.Ptr, size)); _HeapSizeUsed+= size; // return the ptr of start of this empty space. return bestSpace.Ptr; } // *************************************************************************** void CHeapMemory::free(void *ptr) { if(ptr==NULL) return; // Must find the array in allocated spaces. //========================== ItAllocatedSpaceMap itAlloc= _AllocatedSpaceMap.find((uint8*)ptr); if(itAlloc == _AllocatedSpaceMap.end()) { nlstop; return; } uint size= itAlloc->second; // free this space from allocated Spaces. _AllocatedSpaceMap.erase(itAlloc); _HeapSizeUsed-= size; // Must find previous or/and next empty space, if any. //========================== ItEmptySpacePtrMap itPrevious, itNext; // find the empty space which is immediately >= than ptr. itNext= _EmptySpaces.lower_bound((uint8*)ptr); // NB: it may be end(), if it is the last block (very rare). // some check. next empty space ptr must be after ptr. if(itNext!=_EmptySpaces.end()) { nlassert(itNext->second.Ptr >= (uint8*)ptr + size); } // if itNext is not the first empty space, there is an empty space before us. if( itNext!= _EmptySpaces.begin() ) { // NB: work even if itNext==end(). itPrevious= itNext; itPrevious--; // some check. previous empty space ptr must be before ptr. nlassert(itPrevious!=_EmptySpaces.end()); nlassert(itPrevious->second.Ptr + itPrevious->second.Size <= (uint8*)ptr ); } else itPrevious= _EmptySpaces.end(); // if next exist. if(itNext!=_EmptySpaces.end()) { // If Previous is not just after allocated ptr, it means that there is some allocated blocks beetween, // so it is not a valid empty space to concat. if(itNext->second.Ptr != (uint8*)ptr + size) itNext= _EmptySpaces.end(); } // if previous exist. if(itPrevious!=_EmptySpaces.end()) { // If Previous is not just before allocated ptr, it means that there is some allocated blocks beetween, // so it is not a valid empty space to concat. if(itPrevious->second.Ptr + itPrevious->second.Size != (uint8*)ptr ) itPrevious=_EmptySpaces.end(); } // According to configuration, build the new empty space, mreging previous and next, and remove old ones. //========================== CEmptySpace newSpace; // if no previous empty space, then newSpace start at ptr. if(itPrevious == _EmptySpaces.end()) { // Start with old allocated block. newSpace.Ptr= (uint8*)ptr; newSpace.Size= size; } // else, start at previous Ptr. else { // Start with previous block. size is previous size + allocated block size. newSpace.Ptr= itPrevious->second.Ptr; newSpace.Size= itPrevious->second.Size + size; } // if next empty space, must inc size. if(itNext != _EmptySpaces.end()) { newSpace.Size+= itNext->second.Size; } // remove old empty space, and add new one. //========================== // remove old empty spaces. if(itPrevious != _EmptySpaces.end()) removeEmptySpace(itPrevious->second); if(itNext != _EmptySpaces.end()) removeEmptySpace(itNext->second); // Add the new concatenated empty space. addEmptySpace(newSpace); } } // NLMISC