home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 October: Mac OS SDK / Dev.CD Oct 96 SDK / Dev.CD Oct 96 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Memory / BestFitH.cpp next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  38.4 KB  |  1,344 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        BestFitH.cpp
  3.  
  4.     Contains:    BestFitHeap class implementation
  5.  
  6.     Owned by:    Michael Burbidge
  7.  
  8.     Copyright:    © 1993 - 1996 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.     
  12.          <2>     1/15/96    TJ        Cleaned Up
  13.         <14>      8/4/95    DM        Leak checking [1267956]
  14.         <13>      5/4/95    jpa        Support for finding largest free block
  15.                                     [1235657] and validating memory ranges
  16.                                     [1246077]. Better calculation of dflt huge
  17.                                     block size [1233941]
  18.         <12>     2/14/95    jpa        Fixed DoIsValidBlock to do proper size
  19.                                     checking (was giving spurious warnings.)
  20.                                     [1215473]
  21.         <11>    12/20/94    jpa        Disallow case where fHugeBlockSize >
  22.                                     sizeIncrement. [1199188]
  23.         <10>     12/5/94    jpa        Nuked errant pragma lib_export's. [1195676]
  24.          <9>    10/24/94    jpa        Don't call CheckTree all over the place
  25.                                     unless gValidate>0.
  26.          <8>     9/29/94    RA        1189812: Mods for 68K build.
  27.          <7>     9/14/94    jpa        Eliminated dependencies on rest of OpenDoc.
  28.                                     Added support for getting the heap of a
  29.                                     block by stuffing heap ptr in busy block
  30.                                     header. [1186692]
  31.          <6>     8/17/94    jpa        Implemented huge-block support [1179565],
  32.                                     segment disposal [1181509] and the
  33.                                     SOM-block flag [1181510].
  34.          <5>      8/8/94    jpa        Added fHugeBlockSize -- not used yet
  35.                                     [1179565]
  36.          <4>      8/2/94    jpa        Install block cushion hooks. Allocate
  37.                                     blocks on 4byte boundaries. Fixed bug when
  38.                                     getting block size (didn't work right with
  39.                                     hooks installed.)
  40.          <3>     6/18/94    MB        Add #pragma lib_export lines
  41.          <2>     6/10/94    MB        Make it build
  42.          <1>      6/9/94    MB        first checked in
  43.          <5>     5/27/94    MB        #1165129: CreateNewSegment doesn't check
  44.                                     for NULL after allocating new segment.
  45.          <4>     5/27/94    MB        #1162181: Fixed MMM integration bug
  46.          <2>      5/9/94    MB        #1162181: Changes necessary to install MMM.
  47.          <1>     4/29/94    MB        first checked in
  48.          
  49.     To Do:
  50.     In Progress:
  51.         
  52. */
  53.  
  54. #ifndef _PLATFMEM_
  55. #include "PlatfMem.h"
  56. #endif
  57.  
  58. #ifndef _MEMMGRPV_
  59. #include "MemMgrPv.h"
  60. #endif
  61.  
  62. #ifndef _BESTFITH_
  63. #include "BestFitH.h"
  64. #endif
  65.  
  66. #if MM_DEBUG
  67. #ifndef _MEMHOOKS_
  68. #include "MemHooks.h"
  69. #endif
  70. #endif
  71.  
  72. #ifndef __MEMORY__
  73. #include <Memory.h>
  74. #endif
  75.  
  76. #ifndef __LIMITS__
  77. #include <limits.h>
  78. #endif
  79.  
  80. #ifndef __STRING__
  81. #include <string.h>
  82. #endif
  83.  
  84. #ifndef __STDIO__
  85. #include <stdio.h>
  86. #endif
  87.  
  88.  
  89. #define BLOCKS_ON_4BYTE 1        // Allocate blocks on 4-byte boundaries.
  90.  
  91.  
  92. #if MM_DEBUG
  93. //----------------------------------------------------------------------------------------
  94. // IsValidBlock
  95. //----------------------------------------------------------------------------------------
  96. #pragma segment HeapSeg
  97.  
  98. static const PrivBestFitBlock *ValidBlock(const void* ptr)
  99. {
  100.     if( ptr==kMMNULL )
  101.         return kMMNULL;
  102. #if BLOCKS_ON_4BYTE
  103.     if( (long)ptr & 0x00000003 )
  104.         return kMMNULL;                    // Not on a 4-byte boundary
  105. #endif
  106.         
  107.     const PrivBestFitBlock *blk 
  108.         = (const PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  109.  
  110.     ODBlockSize blkSize = blk->GetSize();
  111.     if( (blkSize >= PrivBestFitBlock::kMinBlockSize || blkSize <= BestFitBlock_kMaxBlockSize)
  112.             && blk->GetBusy()
  113.             && blk->GetMagicNumber() == (unsigned int)PrivBestFitBlock::kMagicNumber )
  114.         return blk;
  115.     else
  116.         return kMMNULL;
  117. }
  118. #endif
  119.  
  120. //========================================================================================
  121. // PrivBestFitBlock
  122. //========================================================================================
  123.  
  124. //----------------------------------------------------------------------------------------
  125. // PrivBestFitBlock::operator >
  126. //----------------------------------------------------------------------------------------
  127. #pragma segment HeapSeg
  128.  
  129. Boolean PrivBestFitBlock::operator>(const PrivBestFitBlock& blk) const
  130. {
  131.     if (GetSize() == blk.GetSize())
  132.         return this > &blk;
  133.     else
  134.         return GetSize() > blk.GetSize();
  135. }
  136.  
  137. //----------------------------------------------------------------------------------------
  138. // PrivBestFitBlock::operator <
  139. //----------------------------------------------------------------------------------------
  140. #pragma segment HeapSeg
  141.  
  142. Boolean PrivBestFitBlock::operator<(const PrivBestFitBlock& blk) const
  143. {
  144.     if (GetSize() == blk.GetSize())
  145.         return this < &blk;
  146.     else
  147.         return GetSize() < blk.GetSize();
  148. }
  149.  
  150. //----------------------------------------------------------------------------------------
  151. // PrivBestFitBlock::operator ==
  152. //----------------------------------------------------------------------------------------
  153. #pragma segment HeapSeg
  154.  
  155. Boolean PrivBestFitBlock::operator==(const PrivBestFitBlock& blk) const
  156. {
  157.     return GetSize() == blk.GetSize() && this == &blk;
  158. }
  159.  
  160. //----------------------------------------------------------------------------------------
  161. // PrivBestFitBlock::StuffAddressAtEnd
  162. //----------------------------------------------------------------------------------------
  163. #pragma segment HeapSeg
  164.  
  165. void PrivBestFitBlock::StuffAddressAtEnd()
  166. {
  167.     // coalescence possible in constant time.
  168.  
  169.     if (!this->GetBusy())
  170.     {
  171.         void** addr= (void**) ((ODBytePtr) this + this->GetSize() - sizeof(PrivBestFitBlock *));
  172.         *addr = this;
  173.     }
  174. #if MM_DEBUG
  175.     else
  176.         MM_WARN("PrivBestFitBlock::StuffAddressAtEnd: corrupt heap!");
  177. #endif
  178. }
  179.  
  180.  
  181. //========================================================================================
  182. // BestFitHeap
  183. //========================================================================================
  184.  
  185. //----------------------------------------------------------------------------------------
  186. // BestFitHeap::BestFitHeap
  187. //----------------------------------------------------------------------------------------
  188. #pragma segment HeapSeg
  189.  
  190. BestFitHeap::BestFitHeap(unsigned long sizeInitial,
  191.                                  unsigned long sizeIncrement,
  192.                                  unsigned long hugeBlockSize,        // "0" means sizeIncrement/2
  193.                                  MMHeapLocation memSrc) :
  194.     MemoryHeap(false, false, false, memSrc)
  195. {
  196. #if MM_DEBUG
  197.     CompilerCheck();
  198. #endif
  199.  
  200.     fSizeIncrement = sizeIncrement;
  201.     fSizeInitial = sizeInitial;
  202.     
  203.     if( hugeBlockSize!=0 )
  204.         fHugeBlockSize = hugeBlockSize;
  205.     else
  206.         fHugeBlockSize = sizeIncrement>>1;
  207.     
  208.     if( fHugeBlockSize > kMaxHugeBlockSize )
  209.         fHugeBlockSize = kMaxHugeBlockSize;
  210.         
  211.     if( fHugeBlockSize > sizeIncrement ) {
  212.         MM_WARN("hugeSize must be <= sizeIncrement");
  213.         fHugeBlockSize = sizeIncrement;        // Cannot allow range between huge size & sizeIncrement
  214.     }
  215.     
  216.     fSegments = NULL;
  217.     
  218. //    this->GrowHeap(fSizeInitial);    * MEB *
  219. }
  220.  
  221. //----------------------------------------------------------------------------------------
  222. // BestFitHeap::~BestFitHeap
  223. //----------------------------------------------------------------------------------------
  224. #pragma segment HeapSeg
  225.  
  226. BestFitHeap::~BestFitHeap()
  227. {
  228.     this->DeleteSegments();
  229. }
  230.  
  231. //----------------------------------------------------------------------------------------
  232. // BestFitHeap::IBestFitHeap    * MEB *
  233. //----------------------------------------------------------------------------------------
  234. #pragma segment HeapSeg
  235.  
  236. void BestFitHeap::IBestFitHeap()
  237. {
  238.     this->GrowHeap(fSizeInitial);
  239.  
  240. #if MM_DEBUG
  241.     ODMemoryHook *hook = new(this->GetLocation()) CBlockStackCrawlHook;
  242.     this->AdoptHook(hook);
  243.     // Block cushion hooks have to be installed before any blocks are allocated
  244.     // in the heap; so do so now if this is a debug build.
  245.     hook = new(this->GetLocation()) CBlockCushionHook;
  246.     this->AdoptHook(hook);
  247. #endif
  248. }
  249.  
  250. //----------------------------------------------------------------------------------------
  251. // BestFitHeap::ExpandHeap    * MEB *
  252. //----------------------------------------------------------------------------------------
  253. #pragma segment HeapSeg
  254.  
  255. void BestFitHeap::ExpandHeap(unsigned long sizeInitial, unsigned long sizeIncrement)
  256. {
  257.     if (sizeInitial > fSizeInitial)
  258.         fSizeInitial = sizeInitial;
  259.     if (sizeIncrement > fSizeIncrement)
  260.         fSizeIncrement = sizeIncrement;
  261.     
  262.     if (sizeInitial > this->HeapSize())
  263.         this->GrowHeap(sizeInitial);
  264.     else
  265.         this->GrowHeap(sizeIncrement);
  266. }
  267.  
  268. //----------------------------------------------------------------------------------------
  269. // BestFitHeap::BytesFree
  270. //----------------------------------------------------------------------------------------
  271. #pragma segment HeapSeg
  272.  
  273. unsigned long BestFitHeap::BytesFree() const
  274. {
  275.     unsigned long bytesFree, numberOfNodes;
  276.  
  277.     fFreeTree.TreeInfo(bytesFree, numberOfNodes);
  278.     bytesFree -= numberOfNodes * PrivBestFitBlock::kBusyOverhead;
  279.  
  280.     return bytesFree;
  281. }
  282.  
  283. #if MM_DEBUG
  284. //----------------------------------------------------------------------------------------
  285. // BestFitHeap::Check (MM_DEBUG only)
  286. //----------------------------------------------------------------------------------------
  287. #pragma segment HeapSeg
  288.  
  289. void BestFitHeap::Check( HeapWalkProc proc, void *refCon ) const
  290. {
  291.     ODBlockSize blockHeaderSize = this->CallGetHeaderSize();
  292.  
  293.     // ----- validate each segment
  294.     
  295.     PrivBestFitSegment * segment;
  296.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  297.         if( !segment->CheckSegment(proc,refCon,blockHeaderSize) )
  298.             return;
  299.  
  300.     // ----- check the free tree
  301.     
  302.     fFreeTree.CheckTree();
  303. }
  304. #endif
  305.  
  306. #if MM_DEBUG
  307. //----------------------------------------------------------------------------------------
  308. // BestFitHeap::DoFindBlockContaining (MM_DEBUG only)
  309. //----------------------------------------------------------------------------------------
  310. MMBoolean
  311. BestFitHeap::DoFindBlockContaining( const void *start, const void* end,
  312.                                     const void* &blockStart, const void* &blockEnd ) const
  313. {
  314.     PrivBestFitSegment * segment;
  315.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  316.         if( segment->FindBlockContaining(start,end, blockStart,blockEnd) )
  317.             return kMMTrue;
  318.     return kMMFalse;
  319. }
  320. #endif
  321.  
  322. //----------------------------------------------------------------------------------------
  323. // BestFitHeap::DoGetBlockHeap
  324. //----------------------------------------------------------------------------------------
  325. #pragma segment HeapSeg
  326.  
  327. MemoryHeap*
  328. BestFitHeap::DoGetBlockHeap( const void *block ) const
  329. {
  330. #if MM_DEBUG
  331.     if(!ValidBlock(block)) {
  332.         MM_WARN("GetBlockHeap(%p): bogus block",block);
  333.         return kMMNULL;
  334.     }
  335. #endif
  336.     
  337.     PrivBestFitBlock * blk
  338.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  339.  
  340.     BestFitHeap *heap = blk->GetHeap();
  341. #if MM_DEBUG
  342.     if( !heap->ValidateMagicNumber() )
  343.         return kMMNULL;
  344. #endif
  345.     return heap;
  346. }
  347.  
  348. //----------------------------------------------------------------------------------------
  349. // BestFitHeap::DoAllocate
  350. //----------------------------------------------------------------------------------------
  351. #pragma segment HeapSeg
  352.  
  353. void* BestFitHeap::DoAllocate(ODBlockSize size, ODBlockSize& allocatedSize)
  354. {
  355.     ODBlockSize blkSize = size + PrivBestFitBlock::kBusyOverhead;
  356.  
  357.     if (blkSize < PrivBestFitBlock::kMinBlockSize)
  358.         blkSize = PrivBestFitBlock::kMinBlockSize;
  359.  
  360. #if BLOCKS_ON_4BYTE
  361.     // Make sure blkSize is a multiple of 4 (to keep all blocks on 4byte boundaries)
  362.     // (Added this fix on 7/28/94 on Mike's advice. --jpa)
  363.     blkSize = (blkSize+3) & ~0x03L;
  364. #else
  365.     // Make sure blkSize is even
  366.     if (blkSize & 0x01)
  367.         blkSize++;
  368. #endif
  369.  
  370. #if MM_DEBUG
  371.     MM_ASSERT(blkSize <= BestFitBlock_kMaxBlockSize);
  372. #endif
  373.  
  374.     PrivBestFitBlock * blk;
  375.     
  376.     // A "Huge" block is always allocated its own segment, so the memory can be freed
  377.     // to the platform memory manager as soon as the huge block is deleted:
  378.     
  379.     if( size >= fHugeBlockSize ) {
  380.         blk = this->CreateNewSegment(blkSize + PrivBestFitSegment::kSegmentPrefixSize
  381.                                              + sizeof(PrivBestFitBlock) );
  382.         if( blk )
  383.             MM_ASSERT(blk->GetSize()==blkSize);
  384.             
  385.     } else {
  386.         blk = this->SearchFreeBlocks(blkSize);        // Not huge, so search free blocks
  387.         if (blk == NULL && fSizeIncrement > 0)
  388.         {
  389.             this->GrowHeap(fSizeIncrement);            // Make an attempt to expand the heap
  390.             blk = this->SearchFreeBlocks(blkSize);
  391.         }
  392.     }
  393.  
  394.     allocatedSize = 0;
  395.     void* newPtr = NULL;
  396.  
  397.     if (blk != NULL)
  398.     {
  399.         // We found a block, so mark it busy and remove it from the free list.
  400.  
  401.         blk->SetBusy(true);
  402.         this->RemoveFromFreeBlocks(blk);
  403.         blk->SetHeap(this);
  404.         blk->SetIsObject(false);
  405.  
  406.         if (blk->GetSize() - blkSize >= PrivBestFitBlock::kMinBlockSize)
  407.         {
  408.             // The block is big enough to split, so here we do the split.
  409.  
  410.             PrivBestFitBlock *newBlk
  411.                 = new((void *) ((ODBytePtr) blk + blkSize))
  412.                     PrivBestFitBlock(false, true, blk->GetSize() - blkSize);
  413.             this->AddToFreeBlocks(newBlk);
  414.             blk->SetSize(blkSize);
  415.         }
  416.  
  417.         PrivBestFitBlock * nextBlk
  418.             = (PrivBestFitBlock *) ((ODBytePtr) blk + blk->GetSize());
  419.         nextBlk->SetPrevBusy(true);
  420.  
  421.         newPtr = (void *) ((ODBytePtr) blk + PrivBestFitBlock::kBusyOverhead);
  422.         allocatedSize = blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  423.     }
  424.  
  425.     return newPtr;
  426. }
  427.  
  428. //----------------------------------------------------------------------------------------
  429. // BestFitHeap::DoBlockSize
  430. //----------------------------------------------------------------------------------------
  431. #pragma segment HeapSeg
  432.  
  433. ODBlockSize BestFitHeap::DoBlockSize(const void* block) const
  434. {
  435.     PrivBestFitBlock * blk
  436.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  437.  
  438. #if MM_DEBUG
  439.     MM_ASSERT(blk->GetBusy());
  440. #endif
  441.     
  442.     return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  443. }
  444.  
  445. //----------------------------------------------------------------------------------------
  446. // BestFitHeap::DoFree
  447. //----------------------------------------------------------------------------------------
  448. #pragma segment HeapSeg
  449.  
  450. void BestFitHeap::DoFree(void* ptr)
  451. {
  452.     PrivBestFitBlock *blk
  453.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  454.  
  455. #if MM_DEBUG
  456.     MM_ASSERT(blk->GetBusy());
  457. #endif
  458.     
  459.     blk->SetBusy(false);
  460.     blk->StuffAddressAtEnd();
  461.  
  462.     PrivBestFitBlock *nextBlk
  463.         = (PrivBestFitBlock *) ((ODBytePtr) blk + blk->GetSize());
  464.     nextBlk->SetPrevBusy(false);
  465.  
  466.     if (this->Coalesce(nextBlk))
  467.         this->RemoveFromFreeBlocks(nextBlk);
  468.  
  469.     PrivBestFitBlock * prevBlk = this->Coalesce(blk);
  470.     if (prevBlk)
  471.     {
  472.         this->RemoveFromFreeBlocks(prevBlk);
  473.         //this->AddToFreeBlocks(prevBlk);// Nope, now happens down below unless seg is freed --jpa
  474.         blk = prevBlk;
  475.     }
  476.     
  477.     if( blk->GetIsFirst() ) {
  478.         // If the first block of the segment is free, look just before it for the seg hdr:
  479.         PrivBestFitSegment *segment;
  480.         segment = (PrivBestFitSegment*)( (ODBytePtr)blk - PrivBestFitSegment::kSegmentPrefixSize );
  481. #if MM_DEBUG
  482.         MM_ASSERT(segment->fSegmentSpace==blk);
  483.         MM_ASSERT(blk->GetSize() + sizeof(PrivBestFitBlock) <= segment->fSegmentSize);
  484. #endif
  485.         if( blk->GetSize() + sizeof(PrivBestFitBlock) == segment->fSegmentSize ) {
  486.             this->DeleteSegment(segment);        // Entire seg is free, so delete it
  487.             return;
  488.         }
  489.     }
  490.     
  491.     // If the segment remains, add the free block to the tree:
  492.     this->AddToFreeBlocks(blk);
  493. }
  494.  
  495. //----------------------------------------------------------------------------------------
  496. // BestFitHeap::DoLargestFreeBlock
  497. //----------------------------------------------------------------------------------------
  498. #pragma segment HeapSeg
  499.  
  500. unsigned long BestFitHeap::DoLargestFreeBlock() const
  501. {
  502.     const PrivBestFitBlock *blk = fFreeTree.FindLargestBlock();
  503.     if( blk )
  504.         return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  505.     else
  506.         return 0;
  507. }
  508.  
  509. #if MM_DEBUG
  510. //----------------------------------------------------------------------------------------
  511. // BestFitHeap::DoIsValidBlock
  512. //----------------------------------------------------------------------------------------
  513. #pragma segment HeapSeg
  514.  
  515. Boolean BestFitHeap::DoIsValidBlock(const void* ptr) const
  516. {
  517.     const PrivBestFitBlock *blk = ValidBlock(ptr);
  518.     if( !blk )
  519.         return kMMFalse;
  520.     else
  521.         // Verify that a huge block must be the first block in its segment:
  522.         return blk->GetIsFirst() || blk->GetSize()<fHugeBlockSize;
  523. }
  524. #endif
  525.  
  526. //----------------------------------------------------------------------------------------
  527. // BestFitHeap::DoReset
  528. //----------------------------------------------------------------------------------------
  529. #pragma segment HeapSeg
  530.  
  531. void BestFitHeap::DoReset()
  532. {
  533.     this->DeleteSegments();
  534.     fSegments = NULL;
  535.     fFreeTree = PrivFreeBlockTree();
  536.  
  537.     this->GrowHeap(fSizeInitial);
  538. }
  539.  
  540. //----------------------------------------------------------------------------------------
  541. // BestFitHeap::HeapSize
  542. //----------------------------------------------------------------------------------------
  543. #pragma segment HeapSeg
  544.  
  545. unsigned long BestFitHeap::HeapSize() const
  546. {
  547.     PrivBestFitSegment * segment = fSegments;
  548.     unsigned long heapSize = 0;
  549.  
  550.     while (segment != NULL)
  551.     {
  552.         heapSize += segment->fSegmentSize;
  553.         segment = segment->fNextSegment;
  554.     }
  555.  
  556.     return heapSize;
  557. }
  558.  
  559.  
  560. //----------------------------------------------------------------------------------------
  561. // BestFitHeap::DoSetBlockIsObject
  562. //----------------------------------------------------------------------------------------
  563. void BestFitHeap::DoSetBlockIsObject( void* ptr, Boolean isObject )
  564. {
  565. #if MM_DEBUG
  566.     MM_ASSERT(this->DoIsValidBlock(ptr));
  567. #endif
  568.     PrivBestFitBlock *blk
  569.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  570.     blk->SetIsObject(isObject);
  571. }
  572.  
  573.  
  574.  
  575. //----------------------------------------------------------------------------------------
  576. // BestFitHeap::DoBlockIsObject
  577. //----------------------------------------------------------------------------------------
  578. Boolean BestFitHeap::DoBlockIsObject( const void* ptr ) const
  579. {
  580. #if MM_DEBUG
  581.     MM_ASSERT(this->DoIsValidBlock(ptr));
  582. #endif
  583.     PrivBestFitBlock *blk
  584.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  585.     return blk->GetIsObject();
  586. }
  587.  
  588.  
  589. #if MM_DEBUG
  590. //----------------------------------------------------------------------------------------
  591. // BestFitHeap::IsMyBlock
  592. //----------------------------------------------------------------------------------------
  593. #pragma segment HeapSeg
  594.  
  595. Boolean BestFitHeap::IsMyBlock(const void* blk) const
  596. {
  597.     Boolean myBlock = false;
  598.  
  599.     PrivBestFitSegment * segment = fSegments;
  600.     while (segment != NULL && myBlock == false)
  601.     {
  602.         myBlock = segment->AddressInSegment(blk);
  603.         segment = segment->fNextSegment;
  604.     }
  605.  
  606.     return myBlock;
  607. }
  608. #endif
  609.  
  610. #if MM_DEBUG
  611. //----------------------------------------------------------------------------------------
  612. // BestFitHeap::Print
  613. //----------------------------------------------------------------------------------------
  614. #pragma segment HeapSeg
  615.  
  616. void BestFitHeap::Print(char* msg) const
  617. {
  618.     MM_PRINT("********** BestFitHeap **********\n");
  619.     fFreeTree.PrintTree();
  620.     MM_PRINT("\n");
  621. }
  622. #endif
  623.  
  624. //----------------------------------------------------------------------------------------
  625. // BestFitHeap::AddToFreeBlocks
  626. //----------------------------------------------------------------------------------------
  627. #pragma segment HeapSeg
  628.  
  629. void BestFitHeap::AddToFreeBlocks(PrivBestFitBlock* blk)
  630. {
  631.     fFreeTree.AddBlock(blk);
  632. }
  633.  
  634. //----------------------------------------------------------------------------------------
  635. // BestFitHeap::Coalesce: Coalesce blk with the previous block if both are free.
  636. //----------------------------------------------------------------------------------------
  637. #pragma segment HeapSeg
  638.  
  639. PrivBestFitBlock* BestFitHeap::Coalesce(PrivBestFitBlock* blk)
  640. {
  641.     PrivBestFitBlock * prevBlk = NULL;
  642.  
  643.     if (!blk->GetBusy() && !blk->GetPreviousBusy())
  644.     {
  645. #if MM_DEBUG
  646.         if (blk->GetSize() < PrivBestFitBlock::kMinBlockSize)
  647.             MM_WARN("BestFitHeap::Coalesce: corrupt heap!");
  648. #endif
  649.             
  650.         prevBlk = *(PrivBestFitBlock **) ((ODBytePtr) blk - sizeof(ODBlockSize));
  651.         prevBlk->SetSize(prevBlk->GetSize() + blk->GetSize());
  652.         prevBlk->StuffAddressAtEnd();
  653.     }
  654.  
  655.     return prevBlk;
  656. }
  657.  
  658. //----------------------------------------------------------------------------------------
  659. // BestFitHeap::CreateNewSegment
  660. //----------------------------------------------------------------------------------------
  661. #pragma segment HeapSeg
  662.  
  663. PrivBestFitBlock* BestFitHeap::CreateNewSegment(unsigned long size)
  664. {
  665. #ifdef BUILD_WIN16
  666.     MM_ASSERT(size < 64L * 1024L);
  667. #endif
  668.  
  669. #if BLOCKS_ON_4BYTE
  670.     // Make sure size is a multiple of 4 (to keep all blocks on 4byte boundaries)
  671.     // (Added this fix on 7/28/94 on Mike's advice. --jpa)
  672.     size = (size+3) & ~0x03L;
  673.     // For this to work, kSegmentPrefixSize and kSegmentSuffixSize must also be
  674.     // multiples of 4.
  675. #else
  676.     // Make sure segment size is even
  677.     if (size & 0x01)
  678.         size++;
  679. #endif
  680.  
  681.     Boolean disposable = (fSegments!=NULL);        // First segment is NOT disposable
  682.  
  683.     PrivBestFitSegment * segment
  684.         = (PrivBestFitSegment *)this->AllocateRawMemory((ODBlockSize) size);
  685.  
  686.     if (segment == NULL)
  687.         return NULL;
  688.     else {
  689.         // The actual usable space is offset by the size of the fields
  690.         // of a PrivBestFitSegment.
  691.     
  692.         segment->fSegmentSpace 
  693.             = (void *) ((ODBytePtr) segment + PrivBestFitSegment::kSegmentPrefixSize);
  694.         segment->fSegmentSize = size - PrivBestFitSegment::kSegmentPrefixSize;
  695.     
  696.         // Add the segment to the list of segments in this heap.
  697.     
  698.         segment->fNextSegment = fSegments;
  699.         fSegments = segment;
  700.     
  701.         // Suffix the segment with a busy block of zero length so that the last free
  702.         // block is not coalesced with a block past the fEnd of the segment.
  703.     
  704.         void * endOfSegment 
  705.             = (void *) ((ODBytePtr) segment->fSegmentSpace + segment->fSegmentSize);
  706.         PrivBestFitBlock *blk
  707.             = new((void *) ((ODBytePtr) endOfSegment - sizeof(PrivBestFitBlock)))
  708.                 PrivBestFitBlock(true, false, sizeof(PrivBestFitBlock));
  709.         blk->SetHeap(this);
  710.     
  711.         // Create one free block out of this entire segment and Add it to the
  712.         // free block list.
  713.     
  714.         blk = new(segment->fSegmentSpace)PrivBestFitBlock(false, true, segment->fSegmentSize - sizeof(PrivBestFitBlock));
  715.     
  716.         if( disposable )
  717.             // This is the 1st block (positionally) in the heap, so set its bit:  --jpa
  718.             blk->SetIsFirst(true); 
  719.         
  720.         this->AddToFreeBlocks(blk);
  721.         
  722.         return blk;
  723.     }
  724. }
  725.  
  726. //----------------------------------------------------------------------------------------
  727. // BestFitHeap::DeleteSegment
  728. //----------------------------------------------------------------------------------------
  729. #pragma segment HeapSeg
  730.  
  731. void BestFitHeap::DeleteSegment( PrivBestFitSegment *seg )
  732. {
  733.     // The segment MUST be empty, and its single free block
  734.     // must already have been removed from the free block tree.  --jpa
  735.     
  736.     PrivBestFitSegment *segment = fSegments;
  737.     
  738.     if( segment == seg ) {
  739.         fSegments = seg->fNextSegment;
  740.         this->FreeRawMemory(seg);
  741.         return;
  742.         
  743.     } else
  744.         while (segment != NULL)
  745.             if( segment->fNextSegment == seg ) {
  746.                 segment->fNextSegment = seg->fNextSegment;
  747.                 this->FreeRawMemory(seg);
  748.                 return;
  749.             } else
  750.                 segment = segment->fNextSegment;
  751.  
  752.     MM_WARN("Segment not found in list!");
  753. }
  754.  
  755. //----------------------------------------------------------------------------------------
  756. // BestFitHeap::DeleteSegments
  757. //----------------------------------------------------------------------------------------
  758. #pragma segment HeapSeg
  759.  
  760. void BestFitHeap::DeleteSegments()
  761. {
  762.     PrivBestFitSegment * segment = fSegments;
  763.     while (segment != NULL)
  764.     {
  765.         PrivBestFitSegment * nextSegment = segment->fNextSegment;
  766.         this->FreeRawMemory(segment);
  767.         segment = nextSegment;
  768.     }
  769. }
  770.  
  771. //----------------------------------------------------------------------------------------
  772. // BestFitHeap::GrowHeap
  773. //----------------------------------------------------------------------------------------
  774. #pragma segment HeapSeg
  775.  
  776. void BestFitHeap::GrowHeap(unsigned long sizeIncrement)
  777. {
  778. #ifdef BUILD_WIN16
  779.     // To avoid crossing 64K boundries on pointer arithmatic, the size of each segment
  780.     // must be limited to 64K. So a single grow request may result in more than one
  781.     // segment being allocated.
  782.     
  783.     const unsigned long kSegmentSizeLimit = 1024L * 62L;     // Allow for 2K overhead
  784.     
  785.     while (sizeIncrement > 0)
  786.     {
  787.         unsigned long segmentSize = sizeIncrement;
  788.         if (segmentSize > kSegmentSizeLimit)
  789.             segmentSize = kSegmentSizeLimit;
  790.         this->CreateNewSegment(segmentSize);
  791.         sizeIncrement -= segmentSize;
  792.     }
  793. #else
  794.     this->CreateNewSegment(sizeIncrement);
  795. #endif
  796. }
  797.  
  798. //----------------------------------------------------------------------------------------
  799. // BestFitHeap::RemoveFromFreeBlocks
  800. //----------------------------------------------------------------------------------------
  801. #pragma segment HeapSeg
  802.  
  803. void BestFitHeap::RemoveFromFreeBlocks(PrivBestFitBlock* blk)
  804. {
  805.     fFreeTree.RemoveBlock(blk);
  806. }
  807.  
  808. //----------------------------------------------------------------------------------------
  809. // BestFitHeap::SearchFreeBlocks
  810. //----------------------------------------------------------------------------------------
  811. #pragma segment HeapSeg
  812.  
  813. PrivBestFitBlock* BestFitHeap::SearchFreeBlocks(ODBlockSize size)
  814. {
  815.     //all blocks are of even length, so round up to fNext even number
  816.  
  817.     if (size & 1)
  818.         size++;
  819.  
  820.     return fFreeTree.SearchForBlock(size, NULL, NULL);
  821. }
  822.  
  823. #if MM_DEBUG
  824. //----------------------------------------------------------------------------------------
  825. // BestFitHeap::CompilerCheck
  826. //----------------------------------------------------------------------------------------
  827. #pragma segment HeapSeg
  828.  
  829. void BestFitHeap::CompilerCheck()
  830. {
  831.     MemoryHeap::CompilerCheck();
  832.     
  833.     char buffer[sizeof(PrivBestFitBlock) + sizeof(void *)];
  834.     PrivBestFitBlock &block = *((PrivBestFitBlock *) buffer);
  835.         
  836.     // Check to make sure the bit field setters and getters work.
  837.     
  838.     block.SetBlockType(3);
  839.     block.SetBusy(true);
  840.     block.SetPrevBusy(false);
  841. #ifndef BUILD_WIN16
  842.     block.SetSize(100201);
  843. #endif
  844.     block.SetMagicNumber(3);
  845.  
  846.     MM_ASSERT(block.GetBlockType() == 3);
  847.     MM_ASSERT(block.GetBusy() == true);
  848.     MM_ASSERT(block.GetPreviousBusy() == false);
  849. #ifndef BUILD_WIN16
  850.     MM_ASSERT(block.GetSize() == 100201);
  851. #endif
  852.     MM_ASSERT(block.GetMagicNumber() == 3);
  853.     
  854.     block.SetBlockType(2);
  855.     block.SetBusy(false);
  856.     block.SetPrevBusy(true);
  857.     block.SetSize(150);
  858.     block.SetMagicNumber(2);
  859.  
  860.     MM_ASSERT(block.GetBlockType() == 2);
  861.     MM_ASSERT(block.GetBusy() == false);
  862.     MM_ASSERT(block.GetPreviousBusy() == true);
  863.     MM_ASSERT(block.GetSize() == 150);
  864.     MM_ASSERT(block.GetMagicNumber() == 2);
  865. }
  866. #endif
  867.  
  868.  
  869. //========================================================================================
  870. // CLASS PrivFreeBlockTree
  871. //========================================================================================
  872.  
  873. //----------------------------------------------------------------------------------------
  874. // PrivBestFitSegment::CheckSegment
  875. //----------------------------------------------------------------------------------------
  876.  
  877. Boolean PrivBestFitSegment::CheckSegment( HeapWalkProc proc, void *refCon, ODBlockSize hdrSize )
  878. {
  879.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  880.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  881.     unsigned long blksScanned = 0;
  882.  
  883.     // ----- spin through all the blocks in segment do some consistency checks
  884.     
  885.     while (blk < segmentEnd)
  886.     {
  887.         PrivBestFitBlock *nextBlk;
  888.         MM_ASSERT(blk->GetMagicNumber() == PrivBestFitBlock::kMagicNumber);
  889.         MM_ASSERT(blk->GetBlockType() == PrivBestFitBlock::kBlockTypeId);
  890.         nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  891.         if (nextBlk < segmentEnd)
  892.             MM_ASSERT(nextBlk->GetPreviousBusy() == blk->GetBusy());
  893.         
  894.         if( proc )            // Call user proc if they supplied one
  895.             if( blk->GetBusy() && nextBlk<segmentEnd ) {
  896.                 ODBytePtr userBlk = (ODBytePtr)blk + PrivBestFitBlock::kBusyOverhead + hdrSize;
  897.                 if( (*proc)((void*)userBlk, blk->GetSize()-hdrSize, blk->GetIsObject(), refCon) == false )
  898.                     return false;        // proc can return false to abort
  899.             }
  900.         
  901.         blksScanned++;
  902.         blk = nextBlk;
  903.     }
  904.  
  905.     // ----- if sizes are valid we should be exactly at the end of the segment
  906.     
  907.     MM_ASSERT(blk == segmentEnd);
  908.     return true;
  909. }
  910.  
  911. #if MM_DEBUG
  912. //----------------------------------------------------------------------------------------
  913. // PrivBestFitSegment::FindBlockContaining
  914. //----------------------------------------------------------------------------------------
  915.  
  916. MMBoolean
  917. PrivBestFitSegment::FindBlockContaining( const void *start, const void* end,
  918.                                          const void* &blockStart, const void* &blockEnd ) const
  919. {
  920.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  921.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  922.     
  923.     if( end<=blk || start>=segmentEnd )
  924.         return kMMFalse;
  925.     else {
  926.         // Memory range intersects range of this segment:
  927.         while (blk < segmentEnd)
  928.         {
  929.             blockStart = blockEnd = NULL;
  930.             PrivBestFitBlock *nextBlk;
  931.             nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  932.             if( blk->GetBusy() && nextBlk<segmentEnd ) {
  933.                 if( start <= nextBlk ) {
  934.                     // The memory range starts before the next block, so return:
  935.                     blockStart = (char*)blk + PrivBestFitBlock::kBusyOverhead;
  936.                     blockEnd   = nextBlk;
  937.                     break;
  938.                 }
  939.             }
  940.             blk = nextBlk;
  941.         }
  942.         return kMMTrue;
  943.     }
  944. }
  945.  
  946. #endif
  947.  
  948.  
  949. //========================================================================================
  950. // CLASS PrivFreeBlockTree
  951. //========================================================================================
  952.  
  953. //----------------------------------------------------------------------------------------
  954. // PrivFreeBlockTree::PrivFreeBlockTree
  955. //----------------------------------------------------------------------------------------
  956. #pragma segment HeapSeg
  957.  
  958. PrivFreeBlockTree::PrivFreeBlockTree() :
  959.     fRoot(true, true, 0)
  960. {
  961.     fRoot.SetRight(NULL);
  962.     fRoot.SetLeft(NULL);
  963. }
  964.  
  965. //----------------------------------------------------------------------------------------
  966. // PrivFreeBlockTree::PrivFreeBlockTree
  967. //----------------------------------------------------------------------------------------
  968. #pragma segment HeapSeg
  969.  
  970. PrivFreeBlockTree::PrivFreeBlockTree(const PrivFreeBlockTree& blk) :
  971.     fRoot(blk.fRoot)
  972. {
  973. }
  974.  
  975. //----------------------------------------------------------------------------------------
  976. // PrivFreeBlockTree::operator=
  977. //----------------------------------------------------------------------------------------
  978. #pragma segment HeapSeg
  979.  
  980. PrivFreeBlockTree& PrivFreeBlockTree::operator=(const PrivFreeBlockTree& blk)
  981. {
  982.     fRoot = blk.fRoot;
  983.     return (*this);
  984. }
  985.  
  986. //----------------------------------------------------------------------------------------
  987. // PrivFreeBlockTree::AddBlock
  988. //----------------------------------------------------------------------------------------
  989. #pragma segment HeapSeg
  990.  
  991. void PrivFreeBlockTree::AddBlock(PrivBestFitBlock* blk)
  992. {    
  993. #if MM_DEBUG
  994.     if( gValidate>0 )
  995.         this->CheckTree();
  996.  
  997. #ifdef OD_INTENSE_DEBUG
  998.     MM_PRINT("PrivFreeBlockTree::AddBlock Entry-------------------------------------\n");
  999.     this->PrintTree();
  1000. #endif
  1001. #endif
  1002.  
  1003.     PrivBestFitBlock * parent;
  1004.  
  1005.     this->SearchForBlock(blk->GetSize(), blk, &parent);
  1006.  
  1007.     blk->SetRight(NULL);
  1008.     blk->SetLeft(NULL);
  1009.     blk->SetParent(parent);
  1010.  
  1011.     if (*blk > *parent)
  1012.         parent->SetRight(blk);
  1013.     else
  1014.         parent->SetLeft(blk);
  1015.  
  1016. #if MM_DEBUG
  1017.     if( gValidate>0 )
  1018.         this->CheckTree();
  1019.  
  1020. #ifdef OD_INTENSE_DEBUG
  1021.     MM_PRINT("PrivFreeBlockTree::AddBlock Exit\n");
  1022.     this->PrintTree();
  1023.     MM_PRINT("\n");
  1024. #endif
  1025. #endif
  1026. }
  1027.  
  1028. #if MM_DEBUG
  1029. //----------------------------------------------------------------------------------------
  1030. // PrivFreeBlockTree::CheckTree
  1031. //----------------------------------------------------------------------------------------
  1032. #pragma segment HeapSeg
  1033.  
  1034. void PrivFreeBlockTree::CheckTree() const
  1035. {
  1036.     this->CheckTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1037. }
  1038. #endif
  1039.  
  1040. #if MM_DEBUG
  1041. //----------------------------------------------------------------------------------------
  1042. // PrivFreeBlockTree::PrintTree
  1043. //----------------------------------------------------------------------------------------
  1044. #pragma segment HeapSeg
  1045.  
  1046. void PrivFreeBlockTree::PrintTree() const
  1047. {
  1048.     this->PrintTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1049. }
  1050. #endif
  1051.  
  1052. //----------------------------------------------------------------------------------------
  1053. // PrivFreeBlockTree::RemoveBlock
  1054. //----------------------------------------------------------------------------------------
  1055. #pragma segment HeapSeg
  1056.  
  1057. void PrivFreeBlockTree::RemoveBlock(PrivBestFitBlock* blk)
  1058. {
  1059. #if MM_DEBUG
  1060.     if( gValidate > 0 )
  1061.         this->CheckTree();
  1062.  
  1063. #ifdef OD_INTENSE_DEBUG
  1064.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Entry----------------------------------\n");
  1065.     this->PrintTree();
  1066. #endif
  1067. #endif
  1068.  
  1069.     PrivBestFitBlock * spliceOutBlk;
  1070.  
  1071.     // Decide which block to splice out of the tree. Either the block being
  1072.     // removed, or its successor block in the tree.
  1073.  
  1074.     if (blk->GetLeft() == NULL || blk->GetRight() == NULL)
  1075.         spliceOutBlk = blk;
  1076.     else
  1077.         spliceOutBlk = this->GetSuccessorBlk(blk);
  1078.  
  1079.     // Splice the node out of the tree
  1080.  
  1081.     PrivBestFitBlock * tmp;
  1082.     PrivBestFitBlock * parent = spliceOutBlk->GetParent();
  1083.     if (spliceOutBlk->GetLeft())
  1084.         tmp = spliceOutBlk->GetLeft();
  1085.     else
  1086.         tmp = spliceOutBlk->GetRight();
  1087.     if (tmp)
  1088.         tmp->SetParent(parent);
  1089.     if (spliceOutBlk == parent->GetLeft())
  1090.         parent->SetLeft(tmp);
  1091.     else
  1092.         parent->SetRight(tmp);
  1093.  
  1094.     // If we spliced out the successor to blk above then we need to patch the successor
  1095.     // back in, in Place of blk.
  1096.  
  1097.     if (spliceOutBlk != blk)
  1098.     {
  1099.         PrivBestFitBlock * parent = blk->GetParent();
  1100.  
  1101.         // Fix up the parent's child pointer.
  1102.  
  1103.         if (parent->GetLeft() == blk)
  1104.             parent->SetLeft(spliceOutBlk);
  1105.         else
  1106.             parent->SetRight(spliceOutBlk);
  1107.  
  1108.         // Fix up the splice in block's pointers.
  1109.  
  1110.         spliceOutBlk->SetParent(parent);
  1111.         spliceOutBlk->SetLeft(blk->GetLeft());
  1112.         spliceOutBlk->SetRight(blk->GetRight());
  1113.  
  1114.         // Fix up the children of the splice in block's parent pointers.
  1115.  
  1116.         if (spliceOutBlk->GetLeft())
  1117.             (spliceOutBlk->GetLeft())->SetParent(spliceOutBlk);
  1118.         if (spliceOutBlk->GetRight())
  1119.             (spliceOutBlk->GetRight())->SetParent(spliceOutBlk);
  1120.     }
  1121.  
  1122. #if MM_DEBUG
  1123.     if( gValidate>0 )
  1124.         this->CheckTree();
  1125.  
  1126. #ifdef OD_INTENSE_DEBUG
  1127.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Exit\n");
  1128.     this->PrintTree();
  1129.     MM_PRINT("\n");
  1130. #endif
  1131. #endif
  1132. }
  1133.  
  1134. //----------------------------------------------------------------------------------------
  1135. // PrivFreeBlockTree::SearchForBlock
  1136. //----------------------------------------------------------------------------------------
  1137. #pragma segment HeapSeg
  1138.  
  1139. PrivBestFitBlock* PrivFreeBlockTree::SearchForBlock(ODBlockSize size,
  1140.                                             void* blk,
  1141.                                             PrivBestFitBlock** insertLeaf)
  1142. {
  1143. #if MM_DEBUG
  1144.     if( gValidate>0 )
  1145.         this->CheckTree();
  1146.  
  1147. #ifdef OD_INTENSE_DEBUG
  1148.     char str[80];
  1149.     sprintf(str, "PrivFreeBlockTree::SearchForBlock(%d)---------------------------------\n", size);
  1150.     MM_PRINT(str);
  1151.     this->PrintTree();
  1152. #endif
  1153. #endif
  1154.  
  1155.     long minDiff = LONG_MAX;
  1156.     PrivBestFitBlock * minDiffBlock = NULL;
  1157.     PrivBestFitBlock * currentBlock = &fRoot;
  1158.     do
  1159.     {
  1160.         long diff = currentBlock->GetSize() - size;
  1161.         if (diff >= 0 && diff < minDiff)
  1162.         {
  1163.             minDiffBlock = currentBlock;
  1164.             minDiff = diff;
  1165.         }
  1166.  
  1167.         if (insertLeaf)
  1168.             *insertLeaf = currentBlock;
  1169.  
  1170.         // Determine which branch of the tree to continue down. Since duplicate keys are
  1171.         // difficult to deal with in binary trees, we use the address of blocks to break
  1172.         // ties, in the case of two blocks whose size are equal.
  1173.  
  1174.         if (size < currentBlock->GetSize())
  1175.             currentBlock = currentBlock->GetLeft();
  1176.         else if (size > currentBlock->GetSize())
  1177.             currentBlock = currentBlock->GetRight();
  1178.         else if (blk)
  1179.         {
  1180.             if (blk <= currentBlock)
  1181.                 currentBlock = currentBlock->GetLeft();
  1182.             else
  1183.                 currentBlock = currentBlock->GetRight();
  1184.         }
  1185.         else
  1186.             currentBlock = currentBlock->GetLeft();
  1187.  
  1188.     } while (currentBlock != NULL);
  1189.  
  1190.     return minDiffBlock;
  1191. }
  1192.  
  1193. //----------------------------------------------------------------------------------------
  1194. // PrivFreeBlockTree::FindLargestBlock
  1195. //----------------------------------------------------------------------------------------
  1196. #pragma segment HeapSeg
  1197.  
  1198. const PrivBestFitBlock* PrivFreeBlockTree::FindLargestBlock( ) const
  1199. {
  1200.     // The block to the right in the tree is always larger...
  1201.     
  1202.     const PrivBestFitBlock * currentBlock = &fRoot;
  1203.     const PrivBestFitBlock * nextBlock;
  1204.     while( (nextBlock = currentBlock->GetRight()) != kMMNULL )
  1205.         currentBlock = nextBlock;
  1206.     return currentBlock;
  1207. }
  1208.  
  1209. //----------------------------------------------------------------------------------------
  1210. // PrivFreeBlockTree::TreeInfo
  1211. //----------------------------------------------------------------------------------------
  1212. #pragma segment HeapSeg
  1213.  
  1214. void PrivFreeBlockTree::TreeInfo(unsigned long& bytesFree,
  1215.                              unsigned long& numberOfNodes) const
  1216. {
  1217.     bytesFree = numberOfNodes = 0;
  1218.     this->TreeInfoHelper(&((PrivFreeBlockTree *)this)->fRoot, bytesFree, numberOfNodes);
  1219.  
  1220.     // Subtract one from the number of nodes to account for the header node which
  1221.     // is always empty.
  1222.  
  1223.     numberOfNodes--;
  1224. }
  1225.  
  1226. #if MM_DEBUG
  1227. //----------------------------------------------------------------------------------------
  1228. // PrivFreeBlockTree::CheckTreeHelper
  1229. //----------------------------------------------------------------------------------------
  1230. #pragma segment HeapSeg
  1231.  
  1232. void PrivFreeBlockTree::CheckTreeHelper(PrivBestFitBlock* blk) const
  1233. {
  1234.     if (blk == NULL)
  1235.         return;
  1236.  
  1237.     this->CheckTreeHelper(blk->GetLeft());
  1238.  
  1239.     PrivBestFitBlock * parent = blk->GetParent();
  1240.     if (parent != NULL)
  1241.     {
  1242.         if (parent->GetRight() == blk)
  1243.         {
  1244.             if (*blk < *parent)
  1245.             {
  1246.                 this->PrintTree();
  1247.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1248.                                              "Corrupt free list tree: "
  1249.                                              "right child less than parent.");
  1250.             }
  1251.         }
  1252.         else if (parent->GetLeft() == blk)
  1253.         {
  1254.             if (*blk > *parent)
  1255.             {
  1256.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1257.                                              "Corrupt free list tree: "
  1258.                                              "left child greater than parent.");
  1259.             }
  1260.         }
  1261.         else
  1262.         {
  1263.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1264.                                              "Corrupt free list tree: "
  1265.                                              "I am not my parent's child.");
  1266.         }
  1267.     }
  1268. }
  1269. #endif
  1270.  
  1271. //----------------------------------------------------------------------------------------
  1272. // PrivFreeBlockTree::GetSuccessorBlk
  1273. //----------------------------------------------------------------------------------------
  1274. #pragma segment HeapSeg
  1275.  
  1276. PrivBestFitBlock* PrivFreeBlockTree::GetSuccessorBlk(PrivBestFitBlock* blk)
  1277. {
  1278.     if (blk->GetRight())
  1279.     {
  1280.         PrivBestFitBlock * current = blk->GetRight();
  1281.         while (current->GetLeft())
  1282.             current = current->GetLeft();
  1283.         return current;
  1284.     }
  1285.     else
  1286.     {
  1287.         PrivBestFitBlock * parent = blk->GetParent();
  1288.         PrivBestFitBlock * current = NULL;
  1289.         while (parent != NULL && current == parent->GetRight())
  1290.         {
  1291.             current = parent;
  1292.             parent = parent->GetParent();
  1293.         }
  1294.         return parent;
  1295.     }
  1296. }
  1297.  
  1298. #if MM_DEBUG
  1299. //----------------------------------------------------------------------------------------
  1300. // PrivFreeBlockTree::PrintTreeHelper
  1301. //----------------------------------------------------------------------------------------
  1302. #pragma segment HeapSeg
  1303.  
  1304. void PrivFreeBlockTree::PrintTreeHelper(PrivBestFitBlock* blk,
  1305.                                         int level) const
  1306. {
  1307.     for (int i = 0; i < level; i++)
  1308.         MM_PRINT("\t");
  1309.  
  1310.     if (blk == NULL)
  1311.     {
  1312.         MM_PRINT("NULL\n");
  1313.         return;
  1314.     }
  1315.  
  1316.     char str[80];
  1317.     //sprintf(str, "Block=%lx fSize=%ld\n", blk, blk->GetSize());
  1318.     MM_PRINT(str);
  1319.  
  1320.     this->PrintTreeHelper(blk->GetLeft(), level + 1);
  1321.     this->PrintTreeHelper(blk->GetRight(), level + 1);
  1322. }
  1323. #endif
  1324.  
  1325. //----------------------------------------------------------------------------------------
  1326. // PrivFreeBlockTree::TreeInfoHelper
  1327. //----------------------------------------------------------------------------------------
  1328. #pragma segment HeapSeg
  1329.  
  1330. void PrivFreeBlockTree::TreeInfoHelper(PrivBestFitBlock* blk,
  1331.                                        unsigned long& bytesFree,
  1332.                                        unsigned long& numberOfNodes) const
  1333. {
  1334.     if (blk == NULL)
  1335.         return;
  1336.  
  1337.     this->TreeInfoHelper(blk->GetLeft(), bytesFree, numberOfNodes);
  1338.  
  1339.     numberOfNodes++;
  1340.     bytesFree += blk->GetSize();
  1341.  
  1342.     this->TreeInfoHelper(blk->GetRight(), bytesFree, numberOfNodes);
  1343. }
  1344.