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