# Home    # nevrax.com   
Nevrax
Nevrax.org
#News
#Mailing-list
#Documentation
#CVS
#Bugs
#License
Docs
 
Documentation  
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages   Search  

heap_allocator.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 /*      This file can't use Visual precompilated headers because
00027         the precompilated header ("nel/misc/stdmisc.h") includes 
00028         "nel/misc/types_nl.h". Before including the file 
00029         "nel/misc/types_nl.h", we need to define NL_HEAP_ALLOCATOR_H
00030         for this file to avoid new overriding. */
00031 
00032 #include "stdmisc.h"
00033 
00034 #include "nel/misc/heap_allocator.h"
00035 #include "nel/misc/debug.h"
00036 
00037 #ifdef NL_OS_WINDOWS
00038 #       include <windows.h>
00039 #else
00040 #       include <sys/types.h>
00041 #       include <sys/stat.h>
00042 #       include <fcntl.h>
00043 #endif // NL_OS_WINDOWS
00044 
00045 #include <set>
00046 
00047 namespace NLMISC 
00048 {
00049 
00050 // Include inlines functions
00051 #include "nel/misc/heap_allocator_inline.h"
00052 
00053 #define NL_HEAP_SB_CATEGORY "_SmlBlk"
00054 #define NL_HEAP_CATEGORY_BLOCK_CATEGORY "_MemCat"
00055 #define NL_HEAP_MEM_DEBUG_CATEGORY "_MemDb"
00056 #define NL_HEAP_UNKNOWN_CATEGORY "Unknown"
00057 
00058 void CHeapAllocatorOutputError (const char *str)
00059 {
00060         fprintf (stderr, str);
00061 #ifdef NL_OS_WINDOWS
00062         OutputDebugString (str);
00063 #endif // NL_OS_WINDOWS
00064 }
00065 
00066 // *********************************************************
00067 // Constructors / desctrutors
00068 // *********************************************************
00069 
00070 CHeapAllocator::CHeapAllocator (uint mainBlockSize, uint blockCount, TBlockAllocationMode blockAllocationMode, 
00071                                   TOutOfMemoryMode outOfMemoryMode)
00072 {
00073         // Critical section
00074         enterCriticalSection ();
00075 
00076         // Allocator name
00077         _Name[0] = 0;
00078 
00079         // Check size of structures must be aligned
00080         internalAssert ((sizeof (CNodeBegin) & (Align-1)) == 0);
00081         internalAssert ((NL_HEAP_NODE_END_SIZE & (Align-1)) == 0);
00082         internalAssert ((sizeof (CFreeNode) & (Align-1)) == 0);
00083 
00084         // Check small block sizes
00085         internalAssert ((FirstSmallBlock&(SmallBlockGranularity-1)) == 0);
00086         internalAssert ((LastSmallBlock&(SmallBlockGranularity-1)) == 0);
00087 
00088         _MainBlockList = NULL;
00089         _MainBlockSize = mainBlockSize;
00090         _BlockCount = blockCount;
00091         _BlockAllocationMode = blockAllocationMode;
00092         _OutOfMemoryMode = outOfMemoryMode;
00093         _FreeTreeRoot = &_NullNode.FreeNode;
00094 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00095         _AlwaysCheck = false;
00096 #endif // NL_HEAP_ALLOCATION_NDEBUG
00097 
00098         _NullNode.FreeNode.Left = &_NullNode.FreeNode;
00099         _NullNode.FreeNode.Right = &_NullNode.FreeNode;
00100         _NullNode.FreeNode.Parent = NULL;
00101 
00102         setNodeBlack (&_NullNode.FreeNode);
00103 
00104 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00105         _AllocateCount = 0;
00106 #endif // NL_HEAP_ALLOCATION_NDEBUG
00107 
00108         // *********************************************************
00109         // Small Block
00110         // *********************************************************
00111 
00112         // The free smallblock array by size
00113         const uint smallBlockSizeCount = NL_SMALLBLOCK_COUNT;
00114         uint smallBlockSize;
00115         for (smallBlockSize=0; smallBlockSize<smallBlockSizeCount; smallBlockSize++)
00116         {
00117                 _FreeSmallBlocks[smallBlockSize] = NULL;
00118         }
00119 
00120         // No small block
00121         _SmallBlockPool = NULL;
00122 
00123         leaveCriticalSection ();
00124 }
00125 
00126 // *********************************************************
00127 
00128 CHeapAllocator::~CHeapAllocator ()
00129 {
00130         // Release all memory used
00131         releaseMemory ();
00132 }
00133 
00134 // *********************************************************
00135 
00136 void CHeapAllocator::insert (CHeapAllocator::CFreeNode *x)
00137 {
00138     CHeapAllocator::CFreeNode *current, *parent;
00139 
00140     // Find future parent
00141         current = _FreeTreeRoot;
00142         parent = NULL;
00143         while (current != &_NullNode.FreeNode)
00144         {
00145                 parent = current;
00146                 current = (getNodeSize (getNode (x)) <= getNodeSize (getNode (current)) ) ? current->Left : current->Right;
00147         }
00148 
00149         // Setup new node
00150         x->Parent = parent;
00151         x->Left = &_NullNode.FreeNode;
00152         x->Right = &_NullNode.FreeNode;
00153         setNodeRed (x);
00154 
00155         // Insert node in tree
00156         if (parent)
00157         {
00158                 if(getNodeSize (getNode (x)) <= getNodeSize (getNode (parent)))
00159                         parent->Left = x;
00160                 else
00161                         parent->Right = x;
00162                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (parent);
00163         }
00164         else
00165         {
00166                 _FreeTreeRoot = x;
00167         }
00168 
00169         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x);
00170 
00171     // Maintain Red-Black tree balance
00172     // After inserting node x
00173         // Check Red-Black properties
00174 
00175         while (x != _FreeTreeRoot && isNodeRed (x->Parent))
00176         {
00177                 // We have a violation
00178                 if (x->Parent == x->Parent->Parent->Left)
00179                 {
00180                         CHeapAllocator::CFreeNode *y = x->Parent->Parent->Right;
00181                         if (isNodeRed (y))
00182                         {
00183                                 // Uncle is RED
00184                 setNodeBlack (x->Parent);
00185                                 setNodeBlack (y);
00186                                 setNodeRed (x->Parent->Parent);
00187 
00188                                 // Crc node
00189                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y);
00190                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00191                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent->Parent);
00192 
00193                                 x = x->Parent->Parent;
00194                         }
00195                         else
00196                         {
00197                 // Uncle is Black
00198                                 if (x == x->Parent->Right)
00199                                 {
00200                     // Make x a left child
00201                                         x = x->Parent;
00202                     rotateLeft(x);
00203                                 }
00204 
00205                                 // Recolor and rotate
00206                                 setNodeBlack (x->Parent);
00207                                 setNodeRed (x->Parent->Parent);
00208 
00209                                 rotateRight (x->Parent->Parent);
00210 
00211                                 // Crc node
00212                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00213                         }
00214                 }
00215                 else
00216                 {
00217                         // Mirror image of above code
00218                         CHeapAllocator::CFreeNode *y = x->Parent->Parent->Left;
00219                         if (isNodeRed (y))
00220                         {                
00221                                 // Uncle is Red
00222                                 setNodeBlack (x->Parent);
00223                                 setNodeBlack (y);
00224                                 setNodeRed (x->Parent->Parent);
00225 
00226                                 // Crc node
00227                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y);
00228                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00229                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent->Parent);
00230 
00231                                 x = x->Parent->Parent;
00232                         }
00233                         else
00234                         {
00235                 // Uncle is Black
00236                 if (x == x->Parent->Left) 
00237                                 {
00238                     x = x->Parent;                    
00239                                         rotateRight(x);
00240                 }
00241                                 setNodeBlack (x->Parent);
00242                 setNodeRed (x->Parent->Parent);
00243 
00244                 rotateLeft (x->Parent->Parent);
00245 
00246                                 // Crc node
00247                                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00248                         }        
00249                 }    
00250         }
00251     setNodeBlack (_FreeTreeRoot);
00252 
00253         // Crc node
00254         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (_FreeTreeRoot);
00255 }
00256 
00257 // *********************************************************
00258 
00259 void CHeapAllocator::erase (CHeapAllocator::CFreeNode *z)
00260 {
00261         CFreeNode *x, *y;
00262         if (z->Left == &_NullNode.FreeNode || z->Right == &_NullNode.FreeNode)
00263         {
00264                 // y has a NULL node as a child
00265                 y = z;
00266         }
00267         else
00268         {
00269                 // Find tree successor with a &_NullNode.FreeNode node as a child
00270                 y = z->Right;
00271                 while (y->Left != &_NullNode.FreeNode)
00272                         y = y->Left;
00273         }
00274         
00275         // x is y's only child
00276         if (y->Left != &_NullNode.FreeNode)
00277                 x = y->Left;
00278         else
00279                 x = y->Right;
00280 
00281         // Remove y from the parent chain
00282         x->Parent = y->Parent;
00283 
00284         if (y->Parent)
00285         {
00286                 if (y == y->Parent->Left)
00287                         y->Parent->Left = x;
00288                 else
00289                 {
00290                         internalAssert (y == y->Parent->Right);
00291                         y->Parent->Right = x;
00292                 }
00293                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Parent);
00294         }
00295         else
00296                 _FreeTreeRoot = x;
00297 
00298         bool yRed = isNodeRed (y);
00299 
00300         if (y != z)
00301         {
00302                 // Replace y by z
00303                 *y = *z;
00304                 setNodeColor (y, isNodeRed (z));
00305                 if (y->Parent)
00306                 {
00307                         if (y->Parent->Left == z)
00308                         {
00309                                 y->Parent->Left = y;
00310                         }
00311                         else
00312                         {
00313                                 internalAssert (y->Parent->Right == z);
00314                                 y->Parent->Right = y;
00315                         }
00316                 }
00317                 else
00318                 {
00319                         internalAssert (_FreeTreeRoot == z);
00320                         _FreeTreeRoot = y;
00321                 }
00322 
00323                 if (y->Left)
00324                 {
00325                         internalAssert (y->Left->Parent == z);
00326                         y->Left->Parent = y;
00327                         
00328                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Left);
00329                 }
00330                 if (y->Right)
00331                 {
00332                         internalAssert (y->Right->Parent == z);
00333                         y->Right->Parent = y;
00334         
00335                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Right);
00336                 }
00337         }
00338 
00339         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x);
00340         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y);
00341         if (y->Parent)
00342                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Parent);
00343 
00344         if (!yRed)
00345         {
00346                 // Maintain Red-Black tree balance
00347                 // After deleting node x
00348                 while (x != _FreeTreeRoot && isNodeBlack (x))
00349                 {
00350                         if (x == x->Parent->Left)
00351                         {
00352                                 CFreeNode *w = x->Parent->Right;
00353                                 if (isNodeRed (w))
00354                                 {
00355                                         setNodeBlack (w);
00356                                         setNodeRed (x->Parent);
00357                                         rotateLeft (x->Parent);
00358 
00359                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00360 
00361                                         w = x->Parent->Right;
00362                                 }
00363                                 if (isNodeBlack (w->Left) && isNodeBlack (w->Right))
00364                                 {
00365                                         setNodeRed (w);
00366                                         x = x->Parent;
00367 
00368                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00369                                 }
00370                                 else
00371                                 {
00372                                         if (isNodeBlack (w->Right))
00373                                         {
00374                                                 setNodeBlack (w->Left);
00375                                                 setNodeRed (w);
00376                                                 rotateRight (w);
00377                                                 w = x->Parent->Right;
00378                                         }
00379                                         setNodeColor (w, isNodeRed (x->Parent));
00380                                         setNodeBlack (x->Parent);
00381                                         setNodeBlack (w->Right);
00382                                         rotateLeft (x->Parent);
00383 
00384                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00385                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w->Right);
00386 
00387                                         x = _FreeTreeRoot;
00388                                 }
00389                         }
00390                         else
00391                         {
00392                                 CFreeNode *w = x->Parent->Left;
00393                                 if (isNodeRed (w))
00394                                 {
00395                                         setNodeBlack (w);
00396                                         setNodeRed (x->Parent);
00397                                         rotateRight (x->Parent);
00398 
00399                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00400 
00401                                         w = x->Parent->Left;
00402                                 }
00403                                 if ( isNodeBlack (w->Right) && isNodeBlack (w->Left) )
00404                                 {
00405                                         setNodeRed (w);
00406                                         x = x->Parent;
00407 
00408                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00409                                 }
00410                                 else
00411                                 {
00412                                         if ( isNodeBlack (w->Left) )
00413                                         {
00414                                                 setNodeBlack (w->Right);
00415                                                 setNodeRed (w);
00416                                                 rotateLeft (w);
00417                                                 w = x->Parent->Left;
00418                                         }
00419                                         setNodeColor (w, isNodeRed (x->Parent) );
00420                                         setNodeBlack (x->Parent);
00421                                         setNodeBlack (w->Left);
00422 
00423                                         rotateRight (x->Parent);
00424 
00425                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00426                                         NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w->Left);
00427 
00428                                         x = _FreeTreeRoot;
00429                                 }
00430                         }
00431                 }
00432                 setNodeBlack (x);
00433                 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x);
00434         }
00435 }
00436 
00437 // *********************************************************
00438 // Node methods
00439 // *********************************************************
00440 
00441 CHeapAllocator::CNodeBegin *CHeapAllocator::splitNode (CNodeBegin *node, uint newSize)
00442 {
00443         // Should be smaller than node size
00444         internalAssert (newSize <= getNodeSize (node));
00445 
00446         // Align size
00447         uint allignedSize = (newSize&~(Align-1)) + (( (newSize&(Align-1))==0 ) ? 0 : Align);
00448         if (allignedSize <= UserDataBlockSizeMin)
00449                 allignedSize = UserDataBlockSizeMin;
00450 
00451 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00452         // End magic number aligned on new size
00453         node->EndMagicNumber = (uint32*)((uint8*)node + newSize + sizeof (CNodeBegin));
00454 #endif // NL_HEAP_ALLOCATION_NDEBUG
00455 
00456         // Rest is empty ?
00457         if ( getNodeSize (node) - allignedSize < UserDataBlockSizeMin + sizeof (CNodeBegin) + NL_HEAP_NODE_END_SIZE )
00458                 // No split
00459                 return NULL;
00460 
00461         // New node begin structure
00462         CNodeBegin *newNode = (CNodeBegin*)((uint8*)node + sizeof (CNodeBegin) + allignedSize + NL_HEAP_NODE_END_SIZE );
00463 
00464         // Fill the new node header
00465 
00466         // Size
00467         setNodeSize (newNode, getNodeSize (node) - allignedSize - sizeof (CNodeBegin) - NL_HEAP_NODE_END_SIZE);
00468 
00469         // Set the node free
00470         setNodeFree (newNode);
00471 
00472         // Set the previous node pointer
00473         newNode->Previous = node;
00474 
00475         // Last flag
00476         setNodeLast (newNode, isNodeLast (node));
00477 
00478 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00479         // Begin markers
00480         memset (newNode->BeginMarkers, BeginNodeMarkers, CNodeBegin::MarkerSize-1);
00481         newNode->BeginMarkers[CNodeBegin::MarkerSize-1] = 0;
00482 
00483         // End pointer
00484         newNode->EndMagicNumber = (uint32*)((uint8*)newNode + getNodeSize (newNode) + sizeof (CNodeBegin));
00485 
00486         // End markers
00487         CNodeEnd *endNode = (CNodeEnd*)((uint8*)newNode + getNodeSize (newNode) + sizeof (CNodeBegin));
00488         memset (endNode->EndMarkers, EndNodeMarkers, CNodeEnd::MarkerSize-1);
00489         endNode->EndMarkers[CNodeEnd::MarkerSize-1] = 0;
00490 
00491         // No source informations
00492         newNode->File = NULL;
00493         newNode->Line = 0xffff;
00494         node->AllocateNumber = 0xffffffff;
00495         memset (newNode->Category, 0, CategoryStringLength);
00496 
00497         // Heap pointer
00498         newNode->Heap = this;
00499 #endif // NL_HEAP_ALLOCATION_NDEBUG
00500 
00501         // Get next node
00502         CNodeBegin *next = getNextNode (node);
00503         if (next)
00504         {
00505                 // Set previous
00506                 next->Previous = newNode;
00507 
00508                 NL_UPDATE_MAGIC_NUMBER (next);
00509         }
00510 
00511         // Should be big enough
00512         internalAssert (getNodeSize (newNode) >= UserDataBlockSizeMin);
00513 
00514         // New size of the first node
00515         setNodeSize (node, allignedSize);
00516 
00517         // No more the last
00518         setNodeLast (node, false);
00519 
00520         // Return new node
00521         return newNode;
00522 }
00523 
00524 // *********************************************************
00525 
00526 void CHeapAllocator::mergeNode (CNodeBegin *node)
00527 {
00528         // Get the previous node to merge with
00529         CNodeBegin *previous = node->Previous;
00530         internalAssert (getNextNode (previous) == node);
00531         internalAssert (previous);
00532         internalAssert (isNodeFree (previous));
00533 
00534         // New size
00535         setNodeSize (previous, getNodeSize (previous) + getNodeSize (node) + sizeof (CNodeBegin) + NL_HEAP_NODE_END_SIZE);
00536 
00537 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00538         // Set end pointers
00539         previous->EndMagicNumber = (uint32*)((uint8*)previous + getNodeSize (previous) + sizeof (CNodeBegin));
00540 #endif // NL_HEAP_ALLOCATION_NDEBUG
00541 
00542         // Get the next node to relink
00543         CNodeBegin *next = getNextNode (node);
00544         if (next)
00545         {
00546                 // Relink
00547                 next->Previous = previous;
00548 
00549                 NL_UPDATE_MAGIC_NUMBER (next);
00550         }
00551 
00552         // Get the last flag
00553         setNodeLast (previous, isNodeLast (node));
00554 
00555 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00556 
00557         // todo align
00558 
00559         // Clear the node informations
00560         memset (((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin)), DeletedMemory, NL_HEAP_NODE_END_SIZE);
00561         memset (node, DeletedMemory, sizeof (CNodeBegin));
00562 #endif // NL_HEAP_ALLOCATION_NDEBUG
00563 }
00564 
00565 
00566 // *********************************************************
00567 // *********************************************************
00568 
00569 // Synchronized methods
00570 
00571 // *********************************************************
00572 // *********************************************************
00573 
00574 
00575 void CHeapAllocator::initEmptyBlock (CMainBlock& mainBlock)
00576 {
00577         // Get the node pointer
00578         CNodeBegin *node = getFirstNode (&mainBlock);
00579 
00580         // Allocated size remaining after alignment
00581         internalAssert ((uint32)node - (uint32)mainBlock.Ptr >= 0);
00582         uint allocSize = mainBlock.Size - ((uint32)node - (uint32)mainBlock.Ptr);
00583 
00584         // *** Fill the new node header
00585 
00586         // User data size
00587         setNodeSize (node, allocSize-sizeof (CNodeBegin)-NL_HEAP_NODE_END_SIZE);
00588 
00589         // Node is free
00590         setNodeFree (node);
00591 
00592         // Node is last
00593         setNodeLast (node, true);
00594 
00595         // No previous node
00596         node->Previous = NULL;
00597 
00598         // Debug info
00599 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00600         // End magic number
00601         node->EndMagicNumber = (uint32*)((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin));
00602 
00603         // Begin markers
00604         memset (node->BeginMarkers, BeginNodeMarkers, CNodeBegin::MarkerSize-1);
00605         node->BeginMarkers[CNodeBegin::MarkerSize-1] = 0;
00606 
00607         // End markers
00608         CNodeEnd *endNode = (CNodeEnd*)node->EndMagicNumber;
00609         memset (endNode->EndMarkers, EndNodeMarkers, CNodeEnd::MarkerSize-1);
00610         endNode->EndMarkers[CNodeEnd::MarkerSize-1] = 0;
00611 
00612         // Unallocated memory
00613         memset ((uint8*)node + sizeof(CNodeBegin), UnallocatedMemory, getNodeSize (node) );
00614 
00615         // No source file
00616         memset (node->Category, 0, CategoryStringLength);
00617         node->File = NULL;
00618         node->Line = 0xffff;
00619         node->AllocateNumber = 0xffffffff;
00620 
00621         // Heap pointer
00622         node->Heap = this;
00623 
00624         NL_UPDATE_MAGIC_NUMBER (node);
00625 #endif // NL_HEAP_ALLOCATION_NDEBUG
00626 }
00627 
00628 // *********************************************************
00629 
00630 uint CHeapAllocator::getBlockSize (void *block)
00631 {
00632         // Get the node pointer
00633         CNodeBegin *node = (CNodeBegin*) ((uint)block - sizeof (CNodeBegin));
00634 
00635         return getNodeSize (((CNodeBegin*) ((uint)block - sizeof (CNodeBegin))));
00636 }
00637 
00638 // *********************************************************
00639 
00640 #ifdef NL_HEAP_ALLOCATION_NDEBUG
00641 void *CHeapAllocator::allocate (uint size)
00642 #else // NL_HEAP_ALLOCATION_NDEBUG
00643 void *CHeapAllocator::allocate (uint size, const char *sourceFile, uint line, const char *category)
00644 #endif // NL_HEAP_ALLOCATION_NDEBUG
00645 {
00646         // Check size is valid
00647         if (size != 0)
00648         {
00649 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00650                 // If category is NULL
00651                 if (category == NULL)
00652                 {
00653                         // Get the current category
00654                         CCategory *cat = (CCategory*)_CategoryStack.getPointer ();
00655                         if (cat)
00656                         {
00657                                 category = cat->Name;
00658                         }
00659                         else
00660                         {
00661                                 // Not yet initialised
00662                                 category = NL_HEAP_UNKNOWN_CATEGORY;
00663                         }
00664                 }
00665 
00666                 // Checks ?
00667                 if (_AlwaysCheck)
00668                 {
00669                         // Check heap integrity
00670                         internalCheckHeap (true);
00671                 }
00672 
00673                 // Check breakpoints
00674                 /*if (_Breakpoints.find (_AllocateCount) != _Breakpoints.end())
00675                 {
00676                         // ********
00677                         // * STOP *
00678                         // ********
00679                         // * Breakpoints allocation
00680                         // ********
00681                         NL_ALLOC_STOP;
00682                 }*/
00683 #endif // NL_HEAP_ALLOCATION_NDEBUG
00684 
00685                 // Small or largs block ?
00686 #ifdef NL_HEAP_NO_SMALL_BLOCK_OPTIMIZATION
00687                 if (0)
00688 #else // NL_HEAP_NO_SMALL_BLOCK_OPTIMIZATION
00689                 if (size <= LastSmallBlock)
00690 #endif// NL_HEAP_NO_SMALL_BLOCK_OPTIMIZATION
00691                 {
00692                         // *******************
00693                         // Small block
00694                         // *******************
00695                         
00696                         enterCriticalSectionSB ();
00697 
00698                         // Get pointer on the free block list
00699                         CNodeBegin **freeNode = (CNodeBegin **)_FreeSmallBlocks+NL_SIZE_TO_SMALLBLOCK_INDEX (size);
00700 
00701                         // Not found ?
00702                         if (*freeNode == NULL)
00703                         {
00704                                 leaveCriticalSectionSB ();
00705 
00706                                 // Size must be aligned
00707                                 uint alignedSize = NL_ALIGN_SIZE_FOR_SMALLBLOCK (size);
00708 
00709                                 // Use internal allocator
00710                                 CSmallBlockPool *smallBlock = (CSmallBlockPool *)NelAlloc (*this, sizeof(CSmallBlockPool) + SmallBlockPoolSize * (sizeof(CNodeBegin) + alignedSize + 
00711                                         NL_HEAP_NODE_END_SIZE), NL_HEAP_SB_CATEGORY);
00712 
00713                                 enterCriticalSectionSB ();
00714 
00715                                 // Link this new block
00716                                 smallBlock->Size = alignedSize;
00717                                 smallBlock->Next = (CSmallBlockPool*)_SmallBlockPool;
00718                                 _SmallBlockPool = smallBlock;
00719 
00720                                 // Initialize the block
00721                                 uint pool;
00722                                 CNodeBegin *nextNode = *freeNode;
00723                                 for (pool=0; pool<SmallBlockPoolSize; pool++)
00724                                 {
00725                                         // Get the pool
00726                                         CNodeBegin *node = getSmallBlock (smallBlock, pool);
00727 
00728                                         // Set as free
00729                                         node->SizeAndFlags = alignedSize;
00730 
00731                                         // Insert in the list
00732                                         setNextSmallBlock (node, nextNode);
00733                                         nextNode = node;
00734 
00735                                         // Set debug informations
00736 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00737                                         // Set node free
00738                                         setNodeFree (node);
00739                                         
00740                                         // End magic number
00741                                         node->EndMagicNumber = (uint32*)(CNodeEnd*)((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin));
00742 
00743                                         // Begin markers
00744                                         memset (node->BeginMarkers, BeginNodeMarkers, CNodeBegin::MarkerSize-1);
00745                                         node->BeginMarkers[CNodeBegin::MarkerSize-1] = 0;
00746 
00747                                         // End markers
00748                                         CNodeEnd *endNode = (CNodeEnd*)((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin));
00749                                         memset (endNode->EndMarkers, EndNodeMarkers, CNodeEnd::MarkerSize-1);
00750                                         endNode->EndMarkers[CNodeEnd::MarkerSize-1] = 0;
00751 
00752                                         // Unallocated memory
00753                                         memset ((uint8*)node + sizeof(CNodeBegin), UnallocatedMemory, getNodeSize (node) );
00754 
00755                                         // No source file
00756                                         memset (node->Category, 0, CategoryStringLength);
00757                                         node->File = NULL;
00758                                         node->Line = 0xffff;
00759                                         node->AllocateNumber = 0xffffffff;
00760 
00761                                         // Heap pointer
00762                                         node->Heap = this;
00763 
00764                                         NL_UPDATE_MAGIC_NUMBER (node);
00765 
00766 #endif // NL_HEAP_ALLOCATION_NDEBUG
00767                                 }
00768 
00769                                 // Link the new blocks
00770                                 *freeNode = nextNode;
00771                         }
00772 
00773                         // Check allocation as been done
00774                         internalAssert (*freeNode);
00775 
00776                         // Get a node
00777                         CNodeBegin *node = *freeNode;
00778 
00779                         // Checks
00780                         internalAssert (size <= getNodeSize (node));
00781                         internalAssert ((NL_SIZE_TO_SMALLBLOCK_INDEX (size)) < (NL_SMALLBLOCK_COUNT));
00782 
00783                         // Relink
00784                         *freeNode = getNextSmallBlock (node);
00785 
00786 #ifndef NL_HEAP_ALLOCATION_NDEBUG               
00787                         // Check the node CRC
00788                         checkNode (node, evalMagicNumber (node));
00789 
00790                         // Set node free for checks
00791                         setNodeUsed (node);
00792 
00793                         // Fill category
00794                         strncpy (node->Category, category, CategoryStringLength-1);
00795 
00796                         // Source filename
00797                         node->File = sourceFile;
00798 
00799                         // Source line
00800                         node->Line = line;
00801 
00802                         // Allocate count
00803                         node->AllocateNumber = _AllocateCount++;
00804 
00805                         // End magic number aligned on new size
00806                         node->EndMagicNumber = (uint32*)((uint8*)node + size + sizeof (CNodeBegin));
00807 
00808                         // Uninitialised memory
00809                         memset ((uint8*)node + sizeof(CNodeBegin), UninitializedMemory, (uint32)(node->EndMagicNumber) - ( (uint32)node + sizeof(CNodeBegin) ) );
00810 
00811                         // Crc node
00812                         NL_UPDATE_MAGIC_NUMBER (node);
00813 #endif // NL_HEAP_ALLOCATION_NDEBUG
00814 
00815                         leaveCriticalSectionSB ();
00816 
00817                         // Return the user pointer
00818                         return (void*)((uint)node + sizeof (CNodeBegin));
00819                 }
00820                 else
00821                 {
00822                         // *******************
00823                         // Large block
00824                         // *******************
00825 
00826                         // Check size
00827                         if ( (size & ~CNodeBegin::SizeMask) != 0)
00828                         {
00829                                 // ********
00830                                 // * STOP *
00831                                 // ********
00832                                 // * Attempt to allocate more than 1 Go
00833                                 // ********
00834                                 NL_ALLOC_STOP;
00835 
00836                                 // Select outofmemory mode
00837                                 if (_OutOfMemoryMode == ReturnNull)
00838                                         return NULL;
00839                                 else
00840                                         throw std::bad_alloc();
00841                         }
00842 
00843                         enterCriticalSectionLB ();
00844 
00845                         // Find a free node
00846                         CHeapAllocator::CFreeNode *freeNode = CHeapAllocator::find (size);
00847 
00848                         // The node
00849                         CNodeBegin *node;
00850 
00851                         // Node not found ?
00852                         if (freeNode == NULL)
00853                         {
00854                                 // Block allocation mode
00855                                 if ((_BlockAllocationMode == DontGrow) && (_MainBlockList != NULL))
00856                                 {
00857                                         // Select outofmemory mode
00858                                         if (_OutOfMemoryMode == ReturnNull)
00859                                                 return NULL;
00860                                         else
00861                                                 throw std::bad_alloc();
00862                                 }
00863 
00864                                 // The node
00865                                 uint8 *buffer;
00866 
00867                                 // Alloc size
00868                                 uint allocSize;
00869 
00870                                 // Aligned size
00871                                 uint allignedSize = (size&~(Align-1)) + (( (size&(Align-1))==0 ) ? 0 : Align);
00872                                 if (allignedSize < BlockDataSizeMin)
00873                                         allignedSize = BlockDataSizeMin;
00874 
00875                                 // Does the node bigger than mainNodeSize ?
00876                                 if (allignedSize > (_MainBlockSize-sizeof (CNodeBegin)-NL_HEAP_NODE_END_SIZE))
00877                                         // Allocate a specific block
00878                                         allocSize = allignedSize + sizeof (CNodeBegin) + NL_HEAP_NODE_END_SIZE;
00879                                 else
00880                                         // Allocate a new block
00881                                         allocSize = _MainBlockSize;
00882 
00883                                 // Allocate the buffer
00884                                 buffer = allocateBlock (allocSize+Align);
00885 
00886                                 // Add the buffer
00887                                 CMainBlock *mainBlock = (CMainBlock*)allocateBlock (sizeof(CMainBlock)); 
00888                                 mainBlock->Size = allocSize+Align;
00889                                 mainBlock->Ptr = buffer;
00890                                 mainBlock->Next = _MainBlockList;
00891                                 _MainBlockList = mainBlock;
00892 
00893                                 // Init the new block
00894                                 initEmptyBlock (*mainBlock);
00895 
00896                                 // Get the first node
00897                                 node = getFirstNode (mainBlock);
00898                         }
00899                         else
00900                         {
00901                                 // Get the node
00902                                 node = getNode (freeNode);
00903 
00904                                 // Remove the node from free blocks and get the removed block
00905                                 erase (freeNode);
00906                         }
00907 
00908 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00909                         // Check the node CRC
00910                         checkNode (node, evalMagicNumber (node));
00911 #endif // NL_HEAP_ALLOCATION_NDEBUG
00912 
00913                         // Split the node
00914                         CNodeBegin *rest = splitNode (node, size);
00915 
00916                         // Fill informations for the first part of the node
00917 
00918                         // Clear free flag
00919                         setNodeUsed (node);
00920 
00921 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00922                         // Fill category
00923                         strncpy (node->Category, category, CategoryStringLength-1);
00924 
00925                         // Source filename
00926                         node->File = sourceFile;
00927 
00928                         // Source line
00929                         node->Line = line;
00930 
00931                         // Allocate count
00932                         node->AllocateNumber = _AllocateCount++;
00933 
00934                         // Crc node
00935                         NL_UPDATE_MAGIC_NUMBER (node);
00936 
00937                         // Uninitialised memory
00938                         memset ((uint8*)node + sizeof(CNodeBegin), UninitializedMemory, (uint32)(node->EndMagicNumber) - ( (uint32)node + sizeof(CNodeBegin) ) );
00939 #endif // NL_HEAP_ALLOCATION_NDEBUG
00940 
00941                         // Node has been splited ?
00942                         if (rest)
00943                         {
00944                                 // Fill informations for the second part of the node
00945 
00946                                 // Get the freeNode
00947                                 freeNode = getFreeNode (rest);
00948 
00949                                 // Insert the free node
00950                                 insert (freeNode);
00951 
00952                                 // Crc node
00953                                 NL_UPDATE_MAGIC_NUMBER (rest);
00954                         }
00955 
00956                         // Check the node size
00957                         internalAssert ( size <= getNodeSize (node) );
00958                         internalAssert ( std::max ((uint)BlockDataSizeMin, size + (uint)Align) + sizeof (CNodeBegin) + sizeof (CNodeEnd) + sizeof (CNodeBegin) + sizeof (CNodeEnd) + BlockDataSizeMin >= getNodeSize (node) );
00959 
00960                         // Check pointer alignment
00961                         internalAssert (((uint32)node&(Align-1)) == 0);
00962                         internalAssert (((uint32)((char*)node + sizeof(CNodeBegin))&(Align-1)) == 0);
00963 
00964                         // Check size
00965                         internalAssert ((uint32)node->EndMagicNumber <= (uint32)((uint8*)node+sizeof(CNodeBegin)+getNodeSize (node) ));
00966                         internalAssert ((uint32)node->EndMagicNumber > (uint32)(((uint8*)node+sizeof(CNodeBegin)+getNodeSize (node) ) - BlockDataSizeMin - BlockDataSizeMin - sizeof(CNodeBegin) - sizeof(CNodeEnd)));
00967 
00968                         leaveCriticalSectionLB ();
00969 
00970                         // Return the user pointer
00971                         return (void*)((uint)node + sizeof (CNodeBegin));
00972                 }
00973         }
00974         else
00975         {
00976                 // ********
00977                 // * STOP *
00978                 // ********
00979                 // * Attempt to allocate 0 bytes
00980                 // ********
00981                 NL_ALLOC_STOP;
00982                 return NULL;
00983         }
00984 }
00985 
00986 // *********************************************************
00987 
00988 void CHeapAllocator::free (void *ptr)
00989 {
00990         // Delete a null pointer ?
00991         if (ptr == NULL)
00992         {
00993                 // ********
00994                 // * STOP *
00995                 // ********
00996                 // * Attempt to delete a NULL pointer
00997                 // ********
00998 #ifdef NL_HEAP_STOP_NULL_FREE
00999                 NL_ALLOC_STOP;
01000 #endif // NL_HEAP_STOP_NULL_FREE
01001         }
01002         else
01003         {
01004 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01005                 // Checks ?
01006                 if (_AlwaysCheck)
01007                 {
01008                         // Check heap integrity
01009                         internalCheckHeap (true);
01010                 }
01011 
01012                 // Get the node pointer
01013                 CNodeBegin *node = (CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin));
01014 
01015                 // Check the node CRC
01016                 enterCriticalSectionSB ();
01017                 enterCriticalSectionLB ();
01018                 checkNode (node, evalMagicNumber (node));
01019                 leaveCriticalSectionLB ();
01020                 leaveCriticalSectionSB ();
01021 #endif // NL_HEAP_ALLOCATION_NDEBUG
01022 
01023                 // Large or small block ?
01024 #ifdef NL_HEAP_ALLOCATION_NDEBUG
01025                 uint size = (((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin))))->SizeAndFlags;
01026 #else // NL_HEAP_ALLOCATION_NDEBUG
01027                 uint size = getNodeSize (((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin))));
01028 #endif // NL_HEAP_ALLOCATION_NDEBUG
01029                 if (size <= LastSmallBlock)
01030                 {
01031                         // *******************
01032                         // Small block
01033                         // *******************
01034 
01035                         // Check the node has not been deleted
01036                         if (isNodeFree (node))
01037                         {
01038                                 // ********
01039                                 // * STOP *
01040                                 // ********
01041                                 // * Attempt to delete a pointer already deleted
01042                                 // ********
01043                                 // * (*node):   the already deleted node
01044                                 // ********
01045                                 NL_ALLOC_STOP;
01046                         }
01047                         else
01048                         {
01049                                 enterCriticalSectionSB ();
01050 
01051 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01052                                 // Uninitialised memory
01053                                 memset ((uint8*)node + sizeof(CNodeBegin), DeletedMemory, size );
01054 
01055                                 // Set end pointers
01056                                 node->EndMagicNumber = (uint32*)((uint8*)node + size + sizeof (CNodeBegin));
01057 
01058                                 // Mark has free
01059                                 setNodeFree (node);
01060 #endif // NL_HEAP_ALLOCATION_NDEBUG
01061 
01062                                 // Add in the free list
01063                                 CNodeBegin **freeNode = (CNodeBegin **)_FreeSmallBlocks+NL_SIZE_TO_SMALLBLOCK_INDEX (size);
01064                                 ((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin)))->Previous = *freeNode;
01065                                 *freeNode = ((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin)));
01066 
01067                                 // Update smallblock crc
01068                                 NL_UPDATE_MAGIC_NUMBER (node);
01069 
01070                                 leaveCriticalSectionSB ();
01071                         }
01072                 }
01073                 else
01074                 {
01075 #ifdef NL_HEAP_ALLOCATION_NDEBUG
01076                         // Get the real size
01077                         size = getNodeSize (((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin))));
01078 #endif // NL_HEAP_ALLOCATION_NDEBUG
01079 
01080                         // Get the node pointer
01081                         CNodeBegin *node = (CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin));
01082 
01083                         // Check the node has not been deleted
01084                         if (isNodeFree (node))
01085                         {
01086                                 // ********
01087                                 // * STOP *
01088                                 // ********
01089                                 // * Attempt to delete a pointer already deleted
01090                                 // ********
01091                                 // * (*node):   the already deleted node
01092                                 // ********
01093                                 NL_ALLOC_STOP;
01094                         }
01095                         else
01096                         {
01097                                 enterCriticalSectionLB ();
01098 
01099 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01100                                 // Uninitialised memory
01101                                 memset ((uint8*)node + sizeof(CNodeBegin), DeletedMemory, size );
01102 
01103                                 // Set end pointers
01104                                 node->EndMagicNumber = (uint32*)((uint8*)node + size + sizeof (CNodeBegin));
01105 #endif // NL_HEAP_ALLOCATION_NDEBUG
01106 
01107                                 // Mark has free
01108                                 setNodeFree (node);
01109 
01110                                 // *******************
01111                                 // Large block
01112                                 // *******************
01113 
01114                                 // A free node
01115                                 CHeapAllocator::CFreeNode *freeNode = NULL;
01116 
01117                                 // Previous node
01118                                 CNodeBegin *previous = node->Previous;
01119                                 if (previous)
01120                                 {
01121 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01122                                         // Check the previous node
01123                                         checkNode (previous, evalMagicNumber (previous));
01124 #endif // NL_HEAP_ALLOCATION_NDEBUG
01125 
01126                                         // Is it free ?
01127                                         if (isNodeFree (previous))
01128                                         {
01129                                                 // Merge the two nodes
01130                                                 mergeNode (node);
01131 
01132                                                 // Get its free node
01133                                                 erase (getFreeNode (previous));
01134 
01135                                                 // Curent node
01136                                                 node = previous;
01137                                         }
01138                                 }
01139 
01140                                 // Mark has free
01141                                 setNodeFree (node);
01142 
01143                                 // Next node
01144                                 CNodeBegin *next = getNextNode (node);
01145                                 if (next)
01146                                 {
01147 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01148                                         // Check the next node
01149                                         checkNode (next, evalMagicNumber (next));
01150 #endif // NL_HEAP_ALLOCATION_NDEBUG
01151 
01152                                         // Is it free ?
01153                                         if (isNodeFree (next))
01154                                         {
01155                                                 // Free the new one
01156                                                 erase (getFreeNode (next));
01157 
01158                                                 // Merge the two nodes
01159                                                 mergeNode (next);
01160                                         }
01161                                 }
01162 
01163                                 // Insert it into the tree
01164                                 insert (getFreeNode (node));
01165 
01166                                 NL_UPDATE_MAGIC_NUMBER (node);
01167                                 
01168                                 leaveCriticalSectionLB ();
01169                         }
01170                 }
01171         }
01172 }
01173 
01174 // *********************************************************
01175 // Statistics
01176 // *********************************************************
01177 
01178 uint CHeapAllocator::getAllocatedMemory () const
01179 {
01180         enterCriticalSection ();
01181 
01182         // Sum allocated memory
01183         uint memory = 0;
01184 
01185         // For each small block
01186         CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01187         while (currentSB)
01188         {
01189                 // For each node in this small block pool
01190                 uint block;
01191                 for (block=0; block<SmallBlockPoolSize; block++)
01192                 {
01193                         // Get the node
01194                         const CNodeBegin *current = getSmallBlock (currentSB, block);
01195 
01196                         // Node allocated ?
01197                         if (isNodeUsed (current))
01198                                 memory += getNodeSize (current) + ReleaseHeaderSize;
01199                 }
01200 
01201                 // Next block
01202                 currentSB = currentSB->Next;
01203         }
01204 
01205         // For each main block
01206         CMainBlock *currentBlock = _MainBlockList;
01207         while (currentBlock)
01208         {
01209                 // Get the first node
01210                 const CNodeBegin *current = getFirstNode (currentBlock);
01211                 while (current)
01212                 {
01213 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01214                         // Check node
01215                         checkNode (current, evalMagicNumber (current));
01216 #endif // NL_HEAP_ALLOCATION_NDEBUG
01217 
01218                         // Node allocated ? Don't sum small blocks..
01219                         if (isNodeUsed (current) && (strcmp (current->Category, NL_HEAP_SB_CATEGORY) != 0))
01220                                 memory += getNodeSize (current) + ReleaseHeaderSize;
01221 
01222                         // Next node
01223                         current = getNextNode (current);
01224                 }
01225 
01226                 // Next block
01227                 currentBlock = currentBlock->Next;
01228         }
01229 
01230         leaveCriticalSection ();
01231 
01232         // Return memory used
01233         return memory;
01234 }
01235 
01236 // *********************************************************
01237 
01238 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01239 uint CHeapAllocator::debugGetAllocatedMemoryByCategory (const char* category) const
01240 {
01241         enterCriticalSection ();
01242 
01243         // Sum allocated memory
01244         uint memory = 0;
01245 
01246         // For each small block
01247         CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01248         while (currentSB)
01249         {
01250                 // For each node in this small block pool
01251                 uint block;
01252                 for (block=0; block<SmallBlockPoolSize; block++)
01253                 {
01254                         // Get the node
01255                         const CNodeBegin *current = getSmallBlock (currentSB, block);
01256 
01257                         // Node allocated ?
01258                         if ((isNodeUsed (current)) && (strcmp (current->Category, category)==0))
01259                                 memory += getNodeSize (current);
01260 
01261                         memory += getNodeSize (current);
01262                 }
01263 
01264                 // Next block
01265                 currentSB = currentSB->Next;
01266         }
01267 
01268         // For each main block
01269         CMainBlock *currentBlock = _MainBlockList;
01270         while (currentBlock)
01271         {
01272                 // Get the first node
01273                 const CNodeBegin *current = getFirstNode (currentBlock);
01274                 while (current)
01275                 {
01276                         // Node allocated ?
01277                         if ((isNodeUsed (current)) && (strcmp (current->Category, category)==0))
01278                                 memory += getNodeSize (current);
01279 
01280                         // Next node
01281                         current = getNextNode (current);
01282                 }
01283 
01284                 // Next block
01285                 currentBlock = currentBlock->Next;
01286         }
01287 
01288         leaveCriticalSection ();
01289 
01290         // Return memory used
01291         return memory;
01292 }
01293 #endif // NL_HEAP_ALLOCATION_NDEBUG
01294 
01295 // *********************************************************
01296 
01297 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01298 uint CHeapAllocator::debugGetDebugInfoSize () const
01299 {
01300         // Return memory used
01301         return debugGetSBDebugInfoSize () + debugGetLBDebugInfoSize ();
01302 }
01303 
01304 uint CHeapAllocator::debugGetLBDebugInfoSize () const
01305 {
01306         enterCriticalSection ();
01307 
01308         // Sum memory used by debug header
01309         uint memory = 0;
01310 
01311         // For each main block
01312         CMainBlock *currentBlock = _MainBlockList;
01313         while (currentBlock)
01314         {
01315                 // Get the first node
01316                 const CNodeBegin *current = getFirstNode (currentBlock);
01317                 while (current)
01318                 {
01319                         // Node allocated ?
01320                         memory  += sizeof(CNodeBegin) - ReleaseHeaderSize + sizeof(CNodeEnd);
01321 
01322                         // Next node
01323                         current = getNextNode (current);
01324                 }
01325 
01326                 // Next block
01327                 currentBlock = currentBlock->Next;
01328         }
01329 
01330         leaveCriticalSection ();
01331 
01332         // Return memory used
01333         return memory;
01334 }
01335 
01336 uint CHeapAllocator::debugGetSBDebugInfoSize () const
01337 {
01338         enterCriticalSection ();
01339 
01340         // Sum memory used by debug header
01341         uint memory = 0;
01342 
01343         // For each small blocks
01344         CSmallBlockPool *pool = (CSmallBlockPool*)_SmallBlockPool;
01345         while (pool)
01346         {
01347                 memory  += SmallBlockPoolSize * (sizeof(CNodeBegin) - ReleaseHeaderSize + sizeof(CNodeEnd));
01348 
01349                 // Next pool
01350                 pool = pool->Next;
01351         }
01352 
01353         leaveCriticalSection ();
01354 
01355         // Return memory used
01356         return memory;
01357 }
01358 #endif // NL_HEAP_ALLOCATION_NDEBUG
01359 
01360 // *********************************************************
01361 
01362 void fprintf_int (uint value)
01363 {
01364         
01365 }
01366 
01367 // *********************************************************
01368 
01369 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01370 
01371 class CCategoryMap
01372 {
01373 public:
01374         CCategoryMap ()
01375         {
01376                 BlockCount = 0;
01377                 Size = 0;
01378                 Min = 0xffffffff;
01379                 Max = 0;
01380         }
01381         uint    BlockCount;
01382         uint    Size;
01383         uint    Min;
01384         uint    Max;
01385 };
01386 
01387 bool CHeapAllocator::debugStatisticsReport (const char* stateFile, bool memoryMap)
01388 {
01389         // Status
01390         bool status = false;
01391 
01392         debugPushCategoryString (NL_HEAP_MEM_DEBUG_CATEGORY);
01393 
01394         // Open files
01395         FILE *file = fopen (stateFile, "wt");
01396 
01397         // Block map
01398         typedef std::map<std::string, CCategoryMap> TBlockMap;
01399         TBlockMap blockMap;
01400 
01401         // Both OK
01402         if (file)
01403         {
01404                 // **************************
01405 
01406                 // For each small block
01407                 uint smallBlockCount = 0;
01408                 uint largeBlockCount = 0;
01409                 CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01410                 while (currentSB)
01411                 {
01412                         // For each node in this small block pool
01413                         uint block;
01414                         for (block=0; block<SmallBlockPoolSize; block++)
01415                         {
01416                                 // Get the node
01417                                 const CNodeBegin *current = getSmallBlock (currentSB, block);
01418 
01419                                 // Node allocated ?
01420                                 if (isNodeUsed (current))
01421                                 {
01422                                         // Find the node
01423                                         TBlockMap::iterator ite = blockMap.find ((const char*)current->Category);
01424 
01425                                         // Found ?
01426                                         if (ite == blockMap.end ())
01427                                         {
01428                                                 ite = blockMap.insert (TBlockMap::value_type (current->Category, CCategoryMap ())).first;
01429                                         }
01430                                         uint size = getNodeSize (current) + ReleaseHeaderSize;
01431                                         ite->second.BlockCount++;
01432                                         ite->second.Size += size;
01433                                         if (size < ite->second.Min)
01434                                                 ite->second.Min = size;
01435                                         if (size > ite->second.Max)
01436                                                 ite->second.Max = size;
01437                                 }
01438 
01439                                 // Next node
01440                                 smallBlockCount++;
01441                         }
01442 
01443                         // Next block
01444                         currentSB = currentSB->Next;
01445                 }
01446 
01447                 // For each main block
01448                 CMainBlock *currentBlock = _MainBlockList;
01449                 while (currentBlock)
01450                 {
01451                         // Get the first node
01452                         const CNodeBegin *current = getFirstNode (currentBlock);
01453                         while (current)
01454                         {
01455                                 // Node is used ?
01456                                 if (isNodeUsed (current))
01457                                 {
01458                                         // Find the node
01459                                         TBlockMap::iterator ite = blockMap.find ((const char*)current->Category);
01460 
01461                                         // Found ?
01462                                         if (ite == blockMap.end ())
01463                                         {
01464                                                 ite = blockMap.insert (TBlockMap::value_type (current->Category, CCategoryMap ())).first;
01465                                         }
01466                                         uint size = getNodeSize (current) + ReleaseHeaderSize;
01467                                         ite->second.BlockCount++;
01468                                         ite->second.Size += size;
01469                                         if (size < ite->second.Min)
01470                                                 ite->second.Min = size;
01471                                         if (size > ite->second.Max)
01472                                                 ite->second.Max = size;
01473                                 }
01474 
01475                                 // Next node
01476                                 current = getNextNode (current);
01477                                 largeBlockCount++;
01478                         }
01479 
01480                         // Next block
01481                         currentBlock = currentBlock->Next;
01482                 }
01483 
01484                 // Write the heap info file
01485                 fprintf (file, "HEAP STATISTICS\n");
01486                 fprintf (file, "HEAP, TOTAL MEMORY USED, ALLOCATED MEMORY, FREE MEMORY, FRAGMENTATION RATIO, MAIN BLOCK SIZE, MAIN BLOCK COUNT\n");
01487 
01488                 fprintf (file, "%s, %d, %d, %d, %f%%, %d, %d\n", _Name, getTotalMemoryUsed (),
01489                         getAllocatedMemory (), getFreeMemory (), 100.f*getFragmentationRatio (), getMainBlockSize (), getMainBlockCount ());
01490 
01491                 fprintf (file, "\n\nHEAP BLOCKS\n");
01492                 fprintf (file, "SMALL BLOCK MEMORY, SMALL BLOCK COUNT, LARGE BLOCK COUNT\n");
01493 
01494                 fprintf (file, "%d, %d, %d\n", getSmallBlockMemory (), smallBlockCount, largeBlockCount);
01495 
01496                 fprintf (file, "\n\nHEAP DEBUG INFOS\n");
01497                 fprintf (file, "SB DEBUG INFO, LB DEBUG INFO, TOTAL DEBUG INFO\n");
01498 
01499                 fprintf (file, "%d, %d, %d\n", debugGetSBDebugInfoSize (), debugGetLBDebugInfoSize (), debugGetDebugInfoSize ());
01500 
01501                 // **************************
01502 
01503                 // Write the system heap info file
01504                 uint systemMemory = getAllocatedSystemMemory ();
01505                 uint nelSystemMemory = getAllocatedSystemMemoryByAllocator ();
01506 
01507                 fprintf (file, "\n\nSYSTEM HEAP STATISTICS\n");
01508                 fprintf (file, "TOTAL ALLOCATED MEMORY, NEL ALLOCATED MEMORY, OTHER ALLOCATED MEMORY\n");
01509                 fprintf (file, "%d, %d, %d\n", systemMemory, nelSystemMemory, systemMemory-nelSystemMemory);
01510 
01511                 // Write the category map file
01512                 fprintf (file, "\n\n\nCATEGORY STATISTICS\n");
01513                 fprintf (file, "CATEGORY, BLOCK COUNT, MEMORY ALLOCATED, MIN BLOCK SIZE, MAX BLOCK SIZE, AVERAGE BLOCK SIZE, SB COUNT 8, SB COUNT 16, SB COUNT 24, SB COUNT 32, SB COUNT 40, SB COUNT 48, SB COUNT 56, SB COUNT 64, SB COUNT 72, SB COUNT 80, SB COUNT 88, SB COUNT 96, SB COUNT 104, SB COUNT 112, SB COUNT 120, SB COUNT 128\n");
01514 
01515                 TBlockMap::iterator ite = blockMap.begin();
01516                 while (ite != blockMap.end())
01517                 {
01518                         // Number of small blocks
01519                         uint smallB[NL_SMALLBLOCK_COUNT];
01520 
01521                         // Clean
01522                         uint smallBlock;
01523                         for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01524                         {
01525                                 smallB[smallBlock] = 0;
01526                         }
01527                         
01528                         // Scan small block for this category
01529                         currentSB = (CSmallBlockPool *)_SmallBlockPool;
01530                         while (currentSB)
01531                         {
01532                                 // For each node in this small block pool
01533                                 uint block;
01534                                 for (block=0; block<SmallBlockPoolSize; block++)
01535                                 {
01536                                         // Get the node
01537                                         const CNodeBegin *current = getSmallBlock (currentSB, block);
01538 
01539                                         // Node allocated ?
01540                                         if (isNodeUsed (current))
01541                                         {
01542                                                 // Good node ?
01543                                                 if (current->Category == ite->first)
01544                                                 {
01545                                                         // Get the small block index
01546                                                         uint index = NL_SIZE_TO_SMALLBLOCK_INDEX (getNodeSize (current));
01547 
01548                                                         // One more node
01549                                                         smallB[index]++;
01550                                                 }
01551                                         }
01552                                 }
01553 
01554                                 // Next block
01555                                 currentSB = currentSB->Next;
01556                         }
01557 
01558                         // Average
01559                         uint average = ite->second.Size / ite->second.BlockCount;
01560 
01561                         // Print the line
01562                         fprintf (file, "%s, %d, %d, %d, %d, %d", ite->first.c_str(), ite->second.BlockCount, ite->second.Size, 
01563                                 ite->second.Min, ite->second.Max, average);
01564 
01565                         // Print small blocks
01566                         for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01567                         {
01568                                 fprintf (file, ", %d", smallB[smallBlock]);
01569                         }
01570 
01571                         fprintf (file, "\n");
01572 
01573                         ite++;
01574                 }
01575 
01576                 // **************************
01577 
01578                 // Write the small block statistics
01579                 fprintf (file, "\n\n\nSMALL BLOCK STATISTICS\n");
01580                 fprintf (file, "SIZE, BLOCK COUNT, BLOCK FREE, BLOCK USED, TOTAL MEMORY USED\n");
01581 
01582                 // Number of small blocks
01583                 uint count[NL_SMALLBLOCK_COUNT];
01584                 uint free[NL_SMALLBLOCK_COUNT];
01585 
01586                 uint smallBlock;
01587                 for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01588                 {
01589                         count[smallBlock] = 0;
01590                         free[smallBlock] = 0;
01591                 }
01592 
01593                 // For each small block
01594                 currentSB = (CSmallBlockPool *)_SmallBlockPool;
01595                 while (currentSB)
01596                 {
01597                         // For each node in this small block pool
01598                         uint block;
01599                         for (block=0; block<SmallBlockPoolSize; block++)
01600                         {
01601                                 // Get the node
01602                                 const CNodeBegin *current = getSmallBlock (currentSB, block);
01603 
01604                                 // Get the small block index
01605                                 uint index = NL_SIZE_TO_SMALLBLOCK_INDEX (getNodeSize (current));
01606 
01607                                 // Add a block
01608                                 count[index]++;
01609 
01610                                 // Node allocated ?
01611                                 if (isNodeFree (current))
01612                                 {
01613                                         // Add a free block
01614                                         free[index]++;
01615                                 }
01616 
01617                                 // Next node
01618                                 current = getNextNode (current);
01619                         }
01620 
01621                         // Next block
01622                         currentSB = currentSB->Next;
01623                 }
01624 
01625                 // Print stats
01626                 for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01627                 {
01628                         uint size = (smallBlock+1)*SmallBlockGranularity;
01629                         fprintf (file,"%d, %d, %d, %d, %d\n",size, count[smallBlock], free[smallBlock], 
01630                                 count[smallBlock]-free[smallBlock], count[smallBlock]*(sizeof (CNodeBegin) + size + NL_HEAP_NODE_END_SIZE));
01631                 }
01632                 
01633                 // **************************
01634 
01635                 // Write the memory map file
01636                 if (memoryMap)
01637                 {
01638                         fprintf (file, "\n\n\nHEAP LARGE BLOCK DUMP\n");
01639                         fprintf (file, "ADDRESS, SIZE, CATEGORY, HEAP, STATE, SOURCE, LINE\n");
01640 
01641                         // For each main block
01642                         currentBlock = _MainBlockList;
01643                         while (currentBlock)
01644                         {
01645                                 // Get the first node
01646                                 const CNodeBegin *current = getFirstNode (currentBlock);
01647                                 while (current)
01648                                 {
01649                                         // Write the entry
01650                                         fprintf (file, "0x%08x, %d, %s, %s, %s, %s, %d\n", (uint)current + sizeof(CNodeBegin),
01651                                                 getNodeSize (current), current->Category, _Name, 
01652                                                 isNodeFree (current)?"free":"used", current->File, current->Line);
01653 
01654                                         // Next node
01655                                         current = getNextNode (current);
01656                                 }
01657 
01658                                 // Next block
01659                                 currentBlock = currentBlock->Next;
01660                         }
01661                 }
01662 
01663                 // File created successfuly
01664                 status = true;
01665         }
01666 
01667         // Close
01668         if (file)
01669                 fclose (file);
01670 
01671         debugPopCategoryString ();
01672 
01673         return status;
01674 }
01675 #endif // NL_HEAP_ALLOCATION_NDEBUG
01676 
01677 // *********************************************************
01678 
01679 uint CHeapAllocator::getFreeMemory () const
01680 {
01681         enterCriticalSection ();
01682 
01683         // Sum free memory
01684         uint memory = 0;
01685 
01686         // For each small block
01687         CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01688         while (currentSB)
01689         {
01690                 // For each node in this small block pool
01691                 uint block;
01692                 for (block=0; block<SmallBlockPoolSize; block++)
01693                 {
01694                         // Get the node
01695                         const CNodeBegin *current = getSmallBlock (currentSB, block);
01696 
01697                         // Node allocated ?
01698                         if (isNodeFree (current))
01699                                 memory  += getNodeSize (current) + ReleaseHeaderSize;
01700 
01701                         // Next node
01702                         current = getNextNode (current);
01703                 }
01704 
01705                 // Next block
01706                 currentSB = currentSB->Next;
01707         }
01708 
01709         // For each main block
01710         CMainBlock *currentBlock = _MainBlockList;
01711         while (currentBlock)
01712         {
01713                 // Get the first node
01714                 const CNodeBegin *current = getFirstNode (currentBlock);
01715                 while (current)
01716                 {
01717 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01718                         // Check node
01719                         checkNode (current, evalMagicNumber (current));
01720 #endif // NL_HEAP_ALLOCATION_NDEBUG
01721 
01722                         // Node allocated ?
01723                         if (isNodeFree (current))
01724                                 memory  += getNodeSize (current) + ReleaseHeaderSize;
01725 
01726                         // Next node
01727                         current = getNextNode (current);
01728                 }
01729 
01730                 // Next block
01731                 currentBlock = currentBlock->Next;
01732         }
01733 
01734         leaveCriticalSection ();
01735 
01736         // Return memory used
01737         return memory;
01738 }
01739 
01740 // *********************************************************
01741 
01742 uint CHeapAllocator::getTotalMemoryUsed () const
01743 {
01744         enterCriticalSection ();
01745 
01746         // Sum total memory
01747         uint memory = 0;
01748 
01749         // For each main block
01750         CMainBlock *currentBlock = _MainBlockList;
01751         while (currentBlock)
01752         {
01753                 // Get block size
01754                 memory += currentBlock->Size;
01755 
01756                 // Sum the arrays
01757                 memory += sizeof (CMainBlock);
01758 
01759                 // Next block
01760                 currentBlock = currentBlock->Next;
01761         }
01762 
01763         leaveCriticalSection ();
01764 
01765         // Return the memory
01766         return memory;
01767 }
01768 
01769 // *********************************************************
01770 
01771 uint CHeapAllocator::getSmallBlockMemory () const
01772 {
01773         enterCriticalSection ();
01774 
01775         // Sum total memory
01776         uint memory = 0;
01777 
01778         // For each small block
01779         CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01780         while (currentSB)
01781         {
01782                 // Get block size
01783                 memory += sizeof(CSmallBlockPool) + SmallBlockPoolSize * (sizeof(CNodeBegin) + currentSB->Size + 
01784                                         NL_HEAP_NODE_END_SIZE);
01785 
01786                 // Next block
01787                 currentSB = currentSB->Next;
01788         }
01789 
01790         leaveCriticalSection ();
01791 
01792         // Return the memory
01793         return memory;
01794 }
01795 
01796 // *********************************************************
01797 
01798 float CHeapAllocator::getFragmentationRatio () const
01799 {
01800         enterCriticalSection ();
01801 
01802         // Sum free and used node
01803         float free = 0;
01804         float used = 0;
01805 
01806         // For each main block
01807         CMainBlock *currentBlock = _MainBlockList;
01808         while (currentBlock)
01809         {
01810                 // Get the first node
01811                 const CNodeBegin *current = getFirstNode (currentBlock);
01812                 while (current)
01813                 {
01814                         // Node allocated ?
01815                         if (isNodeUsed (current))
01816                                 used++;
01817                         else
01818                                 free++;
01819 
01820                         // Next node
01821                         current = getNextNode (current);
01822                 }
01823 
01824                 // Next block
01825                 currentBlock = currentBlock->Next;
01826         }
01827 
01828         leaveCriticalSection ();
01829 
01830         // Return the memory
01831         if (used != 0)
01832                 return free / used;
01833         else
01834                 return 0;
01835 }
01836 
01837 // *********************************************************
01838 
01839 void    CHeapAllocator::freeAll ()
01840 {
01841         enterCriticalSection ();
01842 
01843         // Sum free memory
01844         uint memory = 0;
01845 
01846         // Clear the free tree
01847         _FreeTreeRoot = &_NullNode.FreeNode;
01848 
01849         // For each main block
01850         CMainBlock *currentBlock = _MainBlockList;
01851         while (currentBlock)
01852         {
01853                 // Reinit this block
01854                 initEmptyBlock (*currentBlock);
01855 
01856                 // Get first block
01857                 CNodeBegin *node = getFirstNode (currentBlock);
01858 
01859                 // Insert the free node
01860                 insert (getFreeNode (node));
01861 
01862                 NL_UPDATE_MAGIC_NUMBER (node);
01863 
01864                 // Next block
01865                 currentBlock = currentBlock->Next;
01866         }
01867 
01868         leaveCriticalSection ();
01869 }
01870 
01871 // *********************************************************
01872 
01873 void    CHeapAllocator::releaseMemory ()
01874 {
01875         enterCriticalSection ();
01876 
01877         // Clear the free tree
01878         _FreeTreeRoot = &_NullNode.FreeNode;
01879 
01880         // For each main block
01881         CMainBlock *currentBlock = _MainBlockList;
01882         while (currentBlock)
01883         {
01884                 freeBlock (currentBlock->Ptr);
01885 
01886                 // Next block
01887                 CMainBlock *toDelete = currentBlock;
01888                 currentBlock = toDelete->Next;
01889                 ::free (toDelete);
01890         }
01891 
01892         // Erase block node
01893         _MainBlockList = NULL;
01894 
01895         leaveCriticalSection ();
01896 }
01897 
01898 // *********************************************************
01899 
01900 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01901 
01902 struct CLeak
01903 {
01904         uint    Count;
01905         uint    Memory;
01906 };
01907 
01908 typedef std::map<std::string, CLeak> TLinkMap;
01909 
01910 void CHeapAllocator::debugReportMemoryLeak ()
01911 {
01912         // enterCriticalSection ();
01913 
01914         debugPushCategoryString (NL_HEAP_MEM_DEBUG_CATEGORY);
01915 
01916         // Sum allocated memory
01917         uint memory = 0;
01918 
01919         // Leak map
01920         TLinkMap leakMap;
01921 
01922         // Header
01923         char report[2048];
01924         smprintf (report, 2048, "Report Memory leak for allocator \"%s\"\n", _Name);
01925         CHeapAllocatorOutputError (report);
01926 
01927         // For each small block
01928         CMainBlock *currentBlock = _MainBlockList;
01929         while (currentBlock)
01930         {
01931                 // Get the first node
01932                 const CNodeBegin *current = getFirstNode (currentBlock);
01933                 while (current)
01934                 {
01935                         // Check node
01936                         checkNode (current, evalMagicNumber (current));
01937 
01938                         // Node allocated ?
01939                         if (isNodeUsed (current) && ( (current->Category == NULL) || (current->Category[0] != '_')) )
01940                         {
01941                                 // Make a report
01942                                 smprintf (report, 2048, "%s(%d)\t: \"%s\"", current->File, current->Line, current->Category);
01943 
01944                                 // Look for this leak
01945                                 TLinkMap::iterator ite = leakMap.find (report);
01946 
01947                                 // Not found ?
01948                                 if (ite == leakMap.end ())
01949                                 {
01950                                         ite = leakMap.insert (TLinkMap::value_type (report, CLeak ())).first;
01951                                         ite->second.Count = 0;
01952                                         ite->second.Memory = 0;
01953                                 }
01954 
01955                                 // One more leak
01956                                 ite->second.Count++;
01957                                 ite->second.Memory += getNodeSize (current);
01958 
01959                                 memory += getNodeSize (current);
01960                         }
01961 
01962                         // Next node
01963                         current = getNextNode (current);
01964                 }
01965 
01966                 // Next block
01967                 currentBlock = currentBlock->Next;
01968         }
01969 
01970         // For each small block
01971         CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01972         while (currentSB)
01973         {
01974                 // For each node in this small block pool
01975                 uint block;
01976                 for (block=0; block<SmallBlockPoolSize; block++)
01977                 {
01978                         // Get the node
01979                         const CNodeBegin *current = getSmallBlock (currentSB, block);
01980                         // Check node
01981                         checkNode (current, evalMagicNumber (current));
01982 
01983                         // Node allocated ?
01984                         if (isNodeUsed (current) && ( (current->Category == NULL) || (current->Category[0] != '_')) )
01985                         {
01986                                 // Make a report
01987                                 smprintf (report, 2048, "%s(%d)\t: \"%s\"",     current->File, current->Line, current->Category);
01988 
01989                                 // Look for this leak
01990                                 TLinkMap::iterator ite = leakMap.find (report);
01991 
01992                                 // Not found ?
01993                                 if (ite == leakMap.end ())
01994                                 {
01995                                         ite = leakMap.insert (TLinkMap::value_type (report, CLeak ())).first;
01996                                         ite->second.Count = 0;
01997                                         ite->second.Memory = 0;
01998                                 }
01999 
02000                                 // One more leak
02001                                 ite->second.Count++;
02002                                 ite->second.Memory += getNodeSize (current);
02003 
02004                                 memory += getNodeSize (current);
02005                         }
02006                 }
02007 
02008                 // Next block
02009                 currentSB = currentSB->Next;
02010         }
02011 
02012         // Look for this leak
02013         TLinkMap::iterator ite = leakMap.begin ();
02014         while (ite != leakMap.end ())
02015         {
02016                 // Make a report
02017                 smprintf (report, 2048, "%s,\tLeak count : %d,\tMemory allocated : %d\n", ite->first.c_str (), ite->second.Count, ite->second.Memory);
02018 
02019                 // Report on stderr
02020                 CHeapAllocatorOutputError (report);
02021 
02022                 ite++;
02023         }
02024 
02025         // Make a report
02026         if (memory)
02027         {
02028                 smprintf (report, 2048, "%d byte(s) found\n", memory);
02029         }
02030         else
02031         {
02032                 smprintf (report, 2048, "No memory leak\n");
02033         }
02034         CHeapAllocatorOutputError (report);
02035 
02036         debugPopCategoryString ();
02037 
02038         // leaveCriticalSection ();
02039 }
02040 #endif // NL_HEAP_ALLOCATION_NDEBUG
02041 
02042 // *********************************************************
02043 
02044 bool CHeapAllocator::checkHeap (bool stopOnError) const
02045 {
02046         bool res = internalCheckHeap (stopOnError);
02047 
02048         return res;
02049 }
02050 
02051 // *********************************************************
02052 
02053 uint8 *CHeapAllocator::allocateBlock (uint size)
02054 {
02055 #undef malloc
02056         return (uint8*)::malloc (size);
02057 }
02058 
02059 // *********************************************************
02060 
02061 void CHeapAllocator::freeBlock (uint8 *block)
02062 {
02063         ::free (block);
02064 }
02065 
02066 // *********************************************************
02067 
02068 bool CHeapAllocator::internalCheckHeap (bool stopOnError) const
02069 {
02070         enterCriticalSection ();
02071 
02072         // For each small blocks
02073         CSmallBlockPool *pool = (CSmallBlockPool*)_SmallBlockPool;
02074         while (pool)
02075         {
02076                 // For each small block
02077                 uint smallBlock;
02078                 CNodeBegin      *previous = NULL;
02079                 for (smallBlock=0; smallBlock<SmallBlockPoolSize; smallBlock++)
02080                 {
02081                         // Get the small block
02082                         CNodeBegin      *node = getSmallBlock (pool, smallBlock);
02083                         CNodeBegin      *next = (smallBlock+1<SmallBlockPoolSize) ? getSmallBlock (pool, smallBlock+1) : NULL;
02084 
02085                         // Check node
02086                         checkNodeSB (pool, previous, node, next, stopOnError);
02087 
02088                         previous = node;
02089                 }
02090 
02091                 // Next pool
02092                 pool = pool->Next;
02093         }
02094         
02095         // For each main block
02096         CMainBlock *currentBlock = _MainBlockList;
02097         while (currentBlock)
02098         {
02099                 // Get the nodes
02100                 const CNodeBegin *previous = NULL;
02101                 const CNodeBegin *current = getFirstNode (currentBlock);
02102                 internalAssert (current);       // Should have at least one block in the main block
02103                 const CNodeBegin *next;
02104                 
02105                 // For each node
02106                 while (current)
02107                 {
02108                         // Get next
02109                         next = getNextNode (current);
02110 
02111                         // Return Error ?
02112                         if (!checkNodeLB (currentBlock, previous, current, next, stopOnError))
02113                                 return false;
02114 
02115                         // Next
02116                         previous = current;
02117                         current = next;
02118                 }
02119 
02120                 // Next block
02121                 currentBlock = currentBlock->Next;
02122         }
02123 
02124         // Check free tree
02125         if (!checkFreeNode (_FreeTreeRoot, stopOnError, true))
02126                 return false;
02127 
02128         leaveCriticalSection ();
02129 
02130         // Ok, no problem
02131         return true;
02132 }
02133 
02134 // *********************************************************
02135 
02136 #ifndef NL_HEAP_ALLOCATION_NDEBUG
02137 void CHeapAllocator::debugAlwaysCheckMemory (bool alwaysCheck)
02138 {
02139         _AlwaysCheck = alwaysCheck;
02140 }
02141 #endif // NL_HEAP_ALLOCATION_NDEBUG
02142 
02143 // *********************************************************
02144 
02145 #ifndef NL_HEAP_ALLOCATION_NDEBUG
02146 bool CHeapAllocator::debugIsAlwaysCheckMemory (bool alwaysCheck) const
02147 {
02148         return _AlwaysCheck;
02149 }
02150 #endif // NL_HEAP_ALLOCATION_NDEBUG
02151 
02152 // *********************************************************
02153 
02154 void    CHeapAllocator::setName (const char* name)
02155 {
02156         enterCriticalSection ();
02157 
02158         strncpy (_Name, name, NameLength-1);
02159 
02160         leaveCriticalSection ();
02161 }
02162 
02163 // *********************************************************
02164 // Category control
02165 // *********************************************************
02166 
02167 void CHeapAllocator::debugPushCategoryString (const char *str)
02168 {
02169         // Get the category stack pointer
02170         CCategory *last = (CCategory*)_CategoryStack.getPointer ();
02171 
02172         // New category node
02173         CCategory *_new = (CCategory *)NelAlloc (*this, sizeof(CCategory), NL_HEAP_CATEGORY_BLOCK_CATEGORY);
02174         _new->Name = str;
02175         _new->Next = last;
02176 
02177         /* Push it, no need to be thread safe here, because we use thread specifc storage */
02178         _CategoryStack.setPointer (_new);
02179 }
02180 
02181 // *********************************************************
02182 
02183 void CHeapAllocator::debugPopCategoryString ()
02184 {
02185         // Get the category stack pointer
02186         CCategory *last = (CCategory*)_CategoryStack.getPointer ();
02187         // nlassertex (last, ("(CHeapAllocator::debugPopCategoryString ()) Pop category wihtout Push"));
02188         if (last)
02189         {
02190                 CCategory *next = last->Next;
02191 
02192                 // Free last node, no need to be thread safe here, because we use thread specifc storage
02193                 free (last);
02194 
02195                 /* Push it, no need to be thread safe here, because we use thread specifc storage */
02196                 _CategoryStack.setPointer (next);
02197         }
02198 }
02199 
02200 // *********************************************************
02201 
02202 #ifndef NL_HEAP_ALLOCATION_NDEBUG
02203 
02204 #ifdef NL_OS_WINDOWS
02205 #pragma optimize( "", off )
02206 #endif // NL_OS_WINDOWS
02207 
02208 void CHeapAllocator::checkNode (const CNodeBegin *node, uint32 crc) const
02209 {
02210         // Check the bottom CRC of the node 
02211         if (crc != *(node->EndMagicNumber))
02212         {
02213                 // ********
02214                 // * STOP *
02215                 // ********
02216                 // * The bottom CRC32 of the current node is wrong. Use checkMemory() to debug the heap.
02217                 // ********
02218                 // * (*node) Check for more informations
02219                 // ********
02220                 NL_ALLOC_STOP;
02221         }
02222 
02223         // Check the node is hold by this heap
02224         if (node->Heap != this)
02225         {
02226                 // ********
02227                 // * STOP *
02228                 // ********
02229                 // * This node is not hold by this heap. It has been allocated with another heap.
02230                 // ********
02231                 // * (*node) Check for more informations
02232                 // ********
02233                 NL_ALLOC_STOP;
02234         }
02235 }
02236 
02237 #ifdef NL_OS_WINDOWS
02238 #pragma optimize( "", on )
02239 #endif // NL_OS_WINDOWS
02240 
02241 #endif // NL_HEAP_ALLOCATION_NDEBUG
02242 
02243 
02244 
02245 
02246 #ifndef NL_OS_WINDOWS
02247 static inline char *skipWS(const char *p)
02248 {
02249     while (isspace(*p)) p++;
02250     return (char *)p;
02251 }
02252 
02253 static inline char *skipToken(const char *p)
02254 {
02255     while (isspace(*p)) p++;
02256     while (*p && !isspace(*p)) p++;
02257     return (char *)p;
02258 }
02259 #endif
02260 
02261 // *********************************************************
02262 
02263 uint CHeapAllocator::getAllocatedSystemMemory ()
02264 {
02265         uint systemMemory = 0;
02266 #ifdef NL_OS_WINDOWS
02267         // Get system memory informations
02268         HANDLE hHeap[100];
02269         DWORD heapCount = GetProcessHeaps (100, hHeap);
02270 
02271         uint heap;
02272         for (heap = 0; heap < heapCount; heap++)
02273         {
02274                 PROCESS_HEAP_ENTRY entry;
02275                 entry.lpData = NULL;
02276                 while (HeapWalk (hHeap[heap], &entry))
02277                 {
02278                         if (entry.wFlags & PROCESS_HEAP_ENTRY_BUSY)
02279                         {
02280                                 systemMemory += entry.cbData + entry.cbOverhead;
02281                         }
02282                 }
02283         }
02284 
02285 #elif defined NL_OS_UNIX
02286         
02287         char buffer[4096], *p;
02288         int fd, len;
02289         
02290         fd = open("/proc/self/stat", O_RDONLY);
02291         len = read(fd, buffer, sizeof(buffer)-1);
02292         close(fd);
02293         
02294         buffer[len] = '\0';
02295         
02296         p = buffer;
02297         p = strchr(p, ')')+1;                   /* skip pid */
02298         p = skipWS(p);
02299         p++;
02300         
02301         p = skipToken(p);                               /* skip ppid */
02302         p = skipToken(p);                               /* skip pgrp */
02303         p = skipToken(p);                               /* skip session */
02304         p = skipToken(p);                               /* skip tty */
02305         p = skipToken(p);                               /* skip tty pgrp */
02306         p = skipToken(p);                               /* skip flags */
02307         p = skipToken(p);                               /* skip min flt */
02308         p = skipToken(p);                               /* skip cmin flt */
02309         p = skipToken(p);                               /* skip maj flt */
02310         p = skipToken(p);                               /* skip cmaj flt */
02311         p = skipToken(p);                               /* utime */
02312         p = skipToken(p);                               /* stime */
02313         p = skipToken(p);                               /* skip cutime */
02314         p = skipToken(p);                               /* skip cstime */
02315         p = skipToken(p);                               /* priority */
02316         p = skipToken(p);                               /* nice */
02317         p = skipToken(p);                               /* skip timeout */
02318         p = skipToken(p);                               /* skip it_real_val */
02319         p = skipToken(p);                               /* skip start_time */
02320         
02321         systemMemory = strtoul(p, &p, 10);      /* vsize in bytes */
02322 
02323 #endif // NL_OS_WINDOWS
02324         return systemMemory;
02325 }
02326 
02327 // *********************************************************
02328 
02329 uint CHeapAllocator::getAllocatedSystemMemoryByAllocator ()
02330 {
02331         uint nelSystemMemory = 0;
02332 
02333         // Build a set of allocated system memory pointers
02334         std::set<void*> ptrInUse;
02335 
02336         // For each main block
02337         CMainBlock *currentBlock = _MainBlockList;
02338         while (currentBlock)
02339         {
02340                 // Save pointers
02341                 ptrInUse.insert ((void*)currentBlock);
02342                 ptrInUse.insert ((void*)(currentBlock->Ptr));
02343 
02344                 // Next block
02345                 currentBlock = currentBlock->Next;
02346         }
02347 
02348 #ifdef NL_OS_WINDOWS
02349         // Get system memory informations
02350         HANDLE hHeap[100];
02351         DWORD heapCount = GetProcessHeaps (100, hHeap);
02352 
02353         uint heap;
02354         for (heap = 0; heap < heapCount; heap++)
02355         {
02356                 PROCESS_HEAP_ENTRY entry;
02357                 entry.lpData = NULL;
02358                 while (HeapWalk (hHeap[heap], &entry))
02359                 {
02360                         if (entry.wFlags & PROCESS_HEAP_ENTRY_BUSY)
02361                         {
02362                                 // This pointer is already used ?
02363                                 if ( (ptrInUse.find ((void*)((char*)entry.lpData)) != ptrInUse.end ()) || 
02364                                         (ptrInUse.find ((void*)((char*)entry.lpData+32)) != ptrInUse.end ()) )
02365                                         nelSystemMemory += entry.cbData + entry.cbOverhead;
02366                         }
02367                 }
02368         }
02369 #endif // NL_OS_WINDOWS
02370         return nelSystemMemory;
02371 }
02372 
02373 // *********************************************************
02374 
02375 } // NLMISC