home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 February: Technology Seed / Mac Tech Seed Feb '97.toast / OpenDoc 1.2b2c1 / Implementation / Memory / BestFitH.cpp next >
Encoding:
C/C++ Source or Header  |  1997-02-13  |  45.9 KB  |  1,590 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.          <4>     9/13/96    jpa        1371387: Deferred-coalesce optimization.
  13.                                     Other speedups. 1371387: Sped up BytesFree.
  14.          <3>     6/19/96    jpa        1298260: More consistency checks in
  15.                                     CheckSegment
  16.          <2>     1/15/96    TJ        Cleaned Up
  17.         <14>      8/4/95    DM        Leak checking [1267956]
  18.         <13>      5/4/95    jpa        Support for finding largest free block
  19.                                     [1235657] and validating memory ranges
  20.                                     [1246077]. Better calculation of dflt huge
  21.                                     block size [1233941]
  22.         <12>     2/14/95    jpa        Fixed DoIsValidBlock to do proper size
  23.                                     checking (was giving spurious warnings.)
  24.                                     [1215473]
  25.         <11>    12/20/94    jpa        Disallow case where fHugeBlockSize >
  26.                                     sizeIncrement. [1199188]
  27.         <10>     12/5/94    jpa        Nuked errant pragma lib_export's. [1195676]
  28.          <9>    10/24/94    jpa        Don't call CheckTree all over the place
  29.                                     unless gValidate>0.
  30.          <8>     9/29/94    RA        1189812: Mods for 68K build.
  31.          <7>     9/14/94    jpa        Eliminated dependencies on rest of OpenDoc.
  32.                                     Added support for getting the heap of a
  33.                                     block by stuffing heap ptr in busy block
  34.                                     header. [1186692]
  35.          <6>     8/17/94    jpa        Implemented huge-block support [1179565],
  36.                                     segment disposal [1181509] and the
  37.                                     SOM-block flag [1181510].
  38.          <5>      8/8/94    jpa        Added fHugeBlockSize -- not used yet
  39.                                     [1179565]
  40.          <4>      8/2/94    jpa        Install block cushion hooks. Allocate
  41.                                     blocks on 4byte boundaries. Fixed bug when
  42.                                     getting block size (didn't work right with
  43.                                     hooks installed.)
  44.          <3>     6/18/94    MB        Add #pragma lib_export lines
  45.          <2>     6/10/94    MB        Make it build
  46.          <1>      6/9/94    MB        first checked in
  47.          <5>     5/27/94    MB        #1165129: CreateNewSegment doesn't check
  48.                                     for NULL after allocating new segment.
  49.          <4>     5/27/94    MB        #1162181: Fixed MMM integration bug
  50.          <2>      5/9/94    MB        #1162181: Changes necessary to install MMM.
  51.          <1>     4/29/94    MB        first checked in
  52.          
  53.     To Do:
  54.     In Progress:
  55.         
  56. */
  57.  
  58. #ifndef _PLATFMEM_
  59. #include "PlatfMem.h"
  60. #endif
  61.  
  62. #ifndef _MEMMGRPV_
  63. #include "MemMgrPv.h"
  64. #endif
  65.  
  66. #ifndef _BESTFITH_
  67. #include "BestFitH.h"
  68. #endif
  69.  
  70. #if MM_DEBUG
  71. #ifndef _MEMHOOKS_
  72. #include "MemHooks.h"
  73. #endif
  74. #endif
  75.  
  76. #ifndef __MEMORY__
  77. #include <Memory.h>
  78. #endif
  79.  
  80. #ifndef __LIMITS__
  81. #include <limits.h>
  82. #endif
  83.  
  84. #ifndef __STRING__
  85. #include <string.h>
  86. #endif
  87.  
  88. #ifndef __STDIO__
  89. #include <stdio.h>
  90. #endif
  91.  
  92.  
  93. #if MM_DEBUG_COALESCE
  94.     static unsigned long gNFastAllocations =0;
  95.     static unsigned long gNSlowAllocations =0;
  96.     static unsigned long gNFastFrees =0;
  97.     static unsigned long gNSlowFrees =0;
  98. #endif
  99.  
  100.  
  101. #if MM_DEBUG
  102. //----------------------------------------------------------------------------------------
  103. // IsValidBlock
  104. //----------------------------------------------------------------------------------------
  105. #pragma segment HeapSeg
  106.  
  107. static const PrivBestFitBlock *ValidBlock(const void* ptr)
  108. {
  109.     if( ptr==kMMNULL )
  110.         return kMMNULL;
  111.     if( (long)ptr & 0x00000003 )
  112.         return kMMNULL;                    // Not on a 4-byte boundary
  113.         
  114.     const PrivBestFitBlock *blk 
  115.         = (const PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  116.  
  117.     ODBlockSize blkSize = blk->GetSize();
  118.     if( (blkSize >= PrivBestFitBlock::kMinBlockSize || blkSize <= BestFitBlock_kMaxBlockSize)
  119.             && blk->GetBusy()
  120.             && !blk->GetAvail()
  121.             && blk->GetMagicNumber() == (unsigned int)PrivBestFitBlock::kMagicNumber )
  122.         return blk;
  123.     else
  124.         return kMMNULL;
  125. }
  126. #endif
  127.  
  128.  
  129. #if 0 /* OBSOLETE */
  130. //----------------------------------------------------------------------------------------
  131. // PrivBestFitBlock::Coalesce: Coalesce blk with the previous block if both are free.
  132. //----------------------------------------------------------------------------------------
  133. #pragma segment HeapSeg
  134.  
  135. PrivBestFitBlock* PrivBestFitBlock::Coalesce( )
  136. {
  137.     PrivBestFitBlock * prevBlk = NULL;
  138.  
  139.     if (!this->GetBusy() && !this->GetPrevBusy())
  140.     {
  141. #if MM_DEBUG
  142.         if (this->GetSize() < PrivBestFitBlock::kMinBlockSize)
  143.             MM_WARN("BestFitHeap::Coalesce: corrupt heap!");
  144. #endif
  145.             
  146.         prevBlk = this->GetPrevBlock();
  147.         prevBlk->SetSize(prevBlk->GetSize() + this->GetSize());
  148.         prevBlk->StuffAddressAtEnd();
  149.     }
  150.  
  151.     return prevBlk;
  152. }
  153. #endif
  154.  
  155.  
  156. //========================================================================================
  157. // BestFitHeap
  158. //========================================================================================
  159.  
  160. //----------------------------------------------------------------------------------------
  161. // BestFitHeap::BestFitHeap
  162. //----------------------------------------------------------------------------------------
  163. #pragma segment HeapSeg
  164.  
  165. BestFitHeap::BestFitHeap(unsigned long sizeInitial,
  166.                                  unsigned long sizeIncrement,
  167.                                  unsigned long hugeBlockSize,        // "0" means sizeIncrement/2
  168.                                  MMHeapLocation memSrc) :
  169.     MemoryHeap(false, false, false, memSrc)
  170. {
  171. #if MM_DEBUG
  172.     CompilerCheck();
  173. #endif
  174.  
  175.     fSizeIncrement = sizeIncrement;
  176.     fSizeInitial = sizeInitial;
  177.     
  178.     if( hugeBlockSize!=0 )
  179.         fHugeBlockSize = hugeBlockSize;
  180.     else
  181.         fHugeBlockSize = sizeIncrement>>1;
  182.     
  183.     if( fHugeBlockSize > kMaxHugeBlockSize )
  184.         fHugeBlockSize = kMaxHugeBlockSize;
  185.     
  186.     fFreeBytes = fAvailBytes = 0;
  187.     if( fHugeBlockSize > sizeIncrement ) {
  188.         MM_WARN("hugeSize must be <= sizeIncrement");
  189.         fHugeBlockSize = sizeIncrement;        // Cannot allow range between huge size & sizeIncrement
  190.     }
  191.     
  192.     fSegments = NULL;
  193. }
  194.  
  195. //----------------------------------------------------------------------------------------
  196. // BestFitHeap::~BestFitHeap
  197. //----------------------------------------------------------------------------------------
  198. #pragma segment HeapSeg
  199.  
  200. BestFitHeap::~BestFitHeap()
  201. {
  202.     this->DeleteSegments();
  203. }
  204.  
  205. //----------------------------------------------------------------------------------------
  206. // BestFitHeap::IBestFitHeap    * MEB *
  207. //----------------------------------------------------------------------------------------
  208. #pragma segment HeapSeg
  209.  
  210. void BestFitHeap::IBestFitHeap()
  211. {
  212.     this->GrowHeap(fSizeInitial);
  213.  
  214. #if MM_DEBUG
  215.     ODMemoryHook *hook = new(this->GetLocation()) CBlockStackCrawlHook;
  216.     this->AdoptHook(hook);
  217.     // Block cushion hooks have to be installed before any blocks are allocated
  218.     // in the heap; so do so now if this is a debug build.
  219.     hook = new(this->GetLocation()) CBlockCushionHook;
  220.     this->AdoptHook(hook);
  221. #endif
  222. }
  223.  
  224. //----------------------------------------------------------------------------------------
  225. // BestFitHeap::ExpandHeap    * MEB *
  226. //----------------------------------------------------------------------------------------
  227. #pragma segment HeapSeg
  228.  
  229. void BestFitHeap::ExpandHeap(unsigned long sizeInitial, unsigned long sizeIncrement)
  230. {
  231.     if (sizeInitial > fSizeInitial)
  232.         fSizeInitial = sizeInitial;
  233.     if (sizeIncrement > fSizeIncrement)
  234.         fSizeIncrement = sizeIncrement;
  235.     
  236.     if (sizeInitial > this->HeapSize())
  237.         this->GrowHeap(sizeInitial);
  238.     else
  239.         this->GrowHeap(sizeIncrement);
  240. }
  241.  
  242. //----------------------------------------------------------------------------------------
  243. // BestFitHeap::AddBytesFree
  244. //----------------------------------------------------------------------------------------
  245. #if MM_DEBUG_COALESCE    /* In nondebug build this is an inline */
  246. void BestFitHeap::AddFreeBytes( long n )
  247. {
  248.     fFreeBytes += n;
  249.     unsigned long bytesFree, numberOfNodes;
  250.     fFreeTree.TreeInfo(bytesFree, numberOfNodes);
  251.     MM_ASSERT(fFreeBytes==bytesFree);
  252. }
  253. #endif
  254.  
  255. #if MM_DEBUG
  256. //----------------------------------------------------------------------------------------
  257. // BestFitHeap::Check (MM_DEBUG only)
  258. //----------------------------------------------------------------------------------------
  259. #pragma segment HeapSeg
  260.  
  261. void BestFitHeap::Check( HeapWalkProc proc, void *refCon ) const
  262. {
  263.     unsigned long bytesFree, numberOfNodes;
  264.     fFreeTree.TreeInfo(bytesFree, numberOfNodes);
  265.     if(fFreeBytes!=bytesFree)
  266.         MM_WARN("Free byte count of %ld doesn't match tree size %ld", fFreeBytes,bytesFree);
  267.  
  268.     ODBlockSize blockHeaderSize = this->CallGetHeaderSize();
  269.     ODBlockSize sizeDelta = this->CallAboutToAllocateHooks(0);
  270.  
  271.     // ----- validate each segment
  272.     
  273.     PrivBestFitSegment * segment;
  274.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  275.         if( !segment->CheckSegment(proc,refCon,blockHeaderSize,sizeDelta) )
  276.             return;
  277.  
  278.     // ----- check the free tree
  279.     
  280.     fFreeTree.CheckTree();
  281. }
  282. #endif
  283.  
  284. #if MM_DEBUG
  285. //----------------------------------------------------------------------------------------
  286. // BestFitHeap::DoFindBlockContaining (MM_DEBUG only)
  287. //----------------------------------------------------------------------------------------
  288. mmboolean
  289. BestFitHeap::DoFindBlockContaining( const void *start, const void* end,
  290.                                     const void* &blockStart, const void* &blockEnd ) const
  291. {
  292.     PrivBestFitSegment * segment;
  293.     for( segment=fSegments; segment != NULL; segment=segment->fNextSegment )
  294.         if( segment->FindBlockContaining(start,end, blockStart,blockEnd) )
  295.             return kMMTrue;
  296.     return kMMFalse;
  297. }
  298. #endif
  299.  
  300. //----------------------------------------------------------------------------------------
  301. // BestFitHeap::DoGetBlockHeap
  302. //----------------------------------------------------------------------------------------
  303. #pragma segment HeapSeg
  304.  
  305. MemoryHeap*
  306. BestFitHeap::DoGetBlockHeap( const void *block ) const
  307. {
  308. #if MM_DEBUG
  309.     if(!ValidBlock(block)) {
  310.         MM_WARN("GetBlockHeap(%p): bogus block",block);
  311.         return kMMNULL;
  312.     }
  313. #endif
  314.     
  315.     PrivBestFitBlock * blk
  316.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  317.  
  318.     BestFitHeap *heap = blk->GetHeap();
  319. #if MM_DEBUG
  320.     if( !heap->ValidateMagicNumber() )
  321.         return kMMNULL;
  322. #endif
  323.     return heap;
  324. }
  325.  
  326. //----------------------------------------------------------------------------------------
  327. // BestFitHeap::DoBlockSize
  328. //----------------------------------------------------------------------------------------
  329. #pragma segment HeapSeg
  330.  
  331. ODBlockSize BestFitHeap::DoBlockSize(const void* block) const
  332. {
  333.     PrivBestFitBlock * blk
  334.         = (PrivBestFitBlock *) ((ODBytePtr) block - PrivBestFitBlock::kBusyOverhead);
  335.  
  336. #if MM_DEBUG
  337.     MM_ASSERT(blk->GetBusy());
  338. #endif
  339.     
  340.     return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  341. }
  342.  
  343. //----------------------------------------------------------------------------------------
  344. // BestFitHeap::DoAllocate
  345. //----------------------------------------------------------------------------------------
  346. #pragma segment HeapSeg
  347.  
  348. void* BestFitHeap::DoAllocate(ODBlockSize size, ODBlockSize& allocatedSize)
  349. {
  350.     ODBlockSize blkSize = size + PrivBestFitBlock::kBusyOverhead;
  351.  
  352.     if (blkSize < PrivBestFitBlock::kMinBlockSize)
  353.         blkSize = PrivBestFitBlock::kMinBlockSize;
  354.  
  355.     // Make sure blkSize is a multiple of 4 (to keep all blocks on 4byte boundaries)
  356.     blkSize = (blkSize+3) & ~0x03L;
  357.  
  358. #if MM_DEBUG
  359.     MM_ASSERT(blkSize <= BestFitBlock_kMaxBlockSize);
  360. #endif
  361.  
  362.     PrivBestFitBlock * blk;
  363.     
  364. #ifdef MM_DEFER_COALESCE
  365.     if( blkSize < kAvailBlockSizeLimit+PrivBestFitBlock::kBusyOverhead ) {
  366.         // See if there are blocks on the avail lists for the desired size or larger:
  367.         PrivFreeBlockList *list = &fAvailBlocks[ (blkSize-PrivBestFitBlock::kMinBlockSize) >>2 ];
  368.         for( int i=kNAvailListsToCheck; i>0; i--,list++ )
  369.             if( list->NotEmpty() ) {
  370.                 // If so, unhook the block from its list and return it:
  371.                 blk = list->GetBlock();
  372.                 blk->SetAvail(false);
  373.                 blk->SetIsObject(false);
  374.                 blk->SetHeap(this);
  375.                 ODBlockSize itsSize = blk->GetSize();
  376.                 MM_ASSERT(itsSize>=blkSize);
  377.                 allocatedSize = itsSize - PrivBestFitBlock::kBusyOverhead;
  378.                 fAvailBytes -= itsSize;
  379.                 #if MM_DEBUG_COALESCE
  380.                     gNFastAllocations++;
  381.                 #endif
  382.                 return (void *) ((ODBytePtr) blk + PrivBestFitBlock::kBusyOverhead);
  383.             }
  384.         // If not, allocate the block as usual...
  385.     }
  386. #endif
  387.         
  388.     // A "Huge" block is always allocated its own segment, so the memory can be freed
  389.     // to the platform memory manager as soon as the huge block is deleted:
  390.     
  391.     if( size >= fHugeBlockSize ) {
  392.         blk = this->CreateNewSegment(blkSize + PrivBestFitSegment::kSegmentPrefixSize
  393.                                              + sizeof(PrivBestFitBlock) );
  394.         if( blk==NULL ) {
  395.             this->Coalesce();    // might dispose a segment...
  396.             blk = this->CreateNewSegment(blkSize + PrivBestFitSegment::kSegmentPrefixSize
  397.                                                  + sizeof(PrivBestFitBlock) );
  398.         }
  399.         if( blk )
  400.             MM_ASSERT(blk->GetSize()==blkSize);
  401.             
  402.     } else {
  403.         // Normal block allocation, searching the free tree:
  404.         blk = this->SearchFreeBlocks(blkSize);
  405.         if( blk != NULL )
  406.             this->RemoveFromFreeBlocks(blk);
  407.         else {
  408.             // Try coalescing avail blocks until we get a big enough free space:
  409.             blk = this->Coalesce(blkSize);
  410.             if (blk == NULL && fSizeIncrement > 0)
  411.             {
  412.                 // Finally make an attempt to expand the heap:
  413.                 this->GrowHeap(fSizeIncrement);
  414.                 blk = this->SearchFreeBlocks(blkSize);
  415.                 if( blk != NULL )
  416.                     this->RemoveFromFreeBlocks(blk);
  417.             }
  418.         }
  419.     }
  420.  
  421.     if (blk == NULL) {
  422.         allocatedSize = 0;
  423.         return NULL;
  424.     }
  425.     
  426. #if MM_DEBUG_COALESCE
  427.     gNSlowAllocations++;
  428. #endif
  429.  
  430.     // We found a block, so mark it busy and remove it from the free list.
  431.  
  432.     blk->SetBusy(true);
  433.     blk->SetHeap(this);
  434.     blk->SetIsObject(false);
  435.  
  436.     ODBlockSize extra = blk->GetSize() - blkSize;
  437.     if (extra >= PrivBestFitBlock::kMinBlockSize) {
  438.         // The block is big enough to split, so here we do the split.
  439.  
  440.         PrivBestFitBlock *newBlk
  441.             = new((void *) ((ODBytePtr) blk + blkSize))
  442.                 PrivBestFitBlock(false, true, extra);
  443.         this->AddToFreeBlocks(newBlk);
  444.         blk->SetSize(blkSize);
  445.     } else {
  446.         blk->GetNextBlock()->SetPrevBusy(true);
  447.     }
  448.  
  449.     allocatedSize = blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  450.     return (void *) ((ODBytePtr) blk + PrivBestFitBlock::kBusyOverhead);
  451. }
  452.  
  453. //----------------------------------------------------------------------------------------
  454. // BestFitHeap::DoFree
  455. //----------------------------------------------------------------------------------------
  456. #pragma segment HeapSeg
  457.  
  458. void BestFitHeap::DoFree(void* ptr)
  459. {
  460.     PrivBestFitBlock *blk
  461.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  462.  
  463. #if MM_DEBUG
  464.     MM_ASSERT(blk->GetBusy());
  465. #endif
  466.     
  467.     size_t blkSize = blk->GetSize();
  468.  
  469. #ifdef MM_DEFER_COALESCE
  470.     // If the block is small, just return it to the end of the free list for its size:
  471.     // (reusing blocks in FIFO order greatly reduces fragmentation, say the experts.)
  472.     if( blkSize < kAvailBlockSizeLimit+PrivBestFitBlock::kBusyOverhead ) {
  473.         blk->SetAvail(true);
  474.         long index = (blkSize-PrivBestFitBlock::kMinBlockSize)>>2;
  475.         fAvailBlocks[index].AddBlock(blk);
  476.         fAvailBytes += blkSize;
  477.         #if MM_DEBUG_COALESCE
  478.             gNFastFrees++;
  479.         #endif
  480.         return;
  481.     }
  482. #endif
  483.     
  484.     // Update block flags and coalesce with free neighbors:
  485.     blk = this->BasicFreeBlock(blk);
  486.     
  487.     // Delete segment if freeing its only block:
  488.     if( blk->GetIsFirst() && this->DeleteSegmentIfEmpty(blk) )
  489.         return;
  490.     
  491.     // If the segment remains, add the free block to the tree:
  492.     this->AddToFreeBlocks(blk);
  493.  
  494. #if MM_DEBUG_COALESCE
  495.     gNSlowFrees++;
  496. #endif
  497. }
  498.  
  499. //----------------------------------------------------------------------------------------
  500. // BestFitHeap::BasicFreeBlock: Set block flags & coalesce with free neighbors
  501. //----------------------------------------------------------------------------------------
  502. #pragma segment HeapSeg
  503.  
  504. PrivBestFitBlock*
  505. BestFitHeap::BasicFreeBlock( PrivBestFitBlock *blk )
  506. {
  507.     // Free this busy block, coalescing it with free neighbors.
  508.     // Returns new addr of block (may not be same as it may have coalesced with prev block.)
  509.     // Block is *NOT* added to free tree!
  510.     
  511.     MM_ASSERT(blk->GetBusy());
  512.     
  513.     ODBlockSize size = blk->GetSize();
  514.     PrivBestFitBlock *nextBlock = blk->GetNextBlock();
  515.  
  516.     if( !blk->GetPrevBusy() ) {
  517.         // Merge with previous free block:
  518.         blk = blk->GetPrevBlock();
  519.         this->RemoveFromFreeBlocks(blk);
  520.         size += blk->GetSize();
  521.     } else {
  522.         blk->SetBusy(false);
  523.         blk->SetAvail(false);
  524.     }
  525.     
  526.     if( !nextBlock->GetBusy() ) {
  527.         // Merge with next free block:
  528.         this->RemoveFromFreeBlocks(nextBlock);
  529.         size += nextBlock->GetSize();
  530.     } else
  531.         nextBlock->SetPrevBusy(false);
  532.     
  533.     blk->SetSize(size);
  534.     blk->StuffAddressAtEnd();
  535.     return blk;
  536. }
  537.  
  538.  
  539. //----------------------------------------------------------------------------------------
  540. // BestFitHeap::DeleteSegmentIfEmpty: Delete segment if freeing its last block
  541. //----------------------------------------------------------------------------------------
  542. mmboolean
  543. BestFitHeap::DeleteSegmentIfEmpty( PrivBestFitBlock *blk )
  544. {
  545.     // To be called on the first block in a segment when freeing it:
  546.     
  547.     MM_ASSERT(blk->GetIsFirst());
  548.     MM_ASSERT(!blk->GetBusy());
  549.     // Look just before it for the seg hdr:
  550.     PrivBestFitSegment *segment;
  551.     segment = (PrivBestFitSegment*)( (ODBytePtr)blk - PrivBestFitSegment::kSegmentPrefixSize );
  552. #if MM_DEBUG
  553.     MM_ASSERT(segment->fSegmentSpace==blk);
  554.     MM_ASSERT(blk->GetSize() + sizeof(PrivBestFitBlock) <= segment->fSegmentSize);
  555. #endif
  556.     if( blk->GetSize() + sizeof(PrivBestFitBlock) == segment->fSegmentSize ) {
  557.         this->DeleteSegment(segment);        // Entire seg is free, so delete it
  558.         return true;
  559.     } else
  560.         return false;
  561. }
  562.  
  563. #ifdef MM_DEFER_COALESCE
  564. //----------------------------------------------------------------------------------------
  565. // BestFitHeap::Coalesce: Do deferred coalesce of entire heap
  566. //----------------------------------------------------------------------------------------
  567. #pragma segment HeapSeg
  568.  
  569. PrivBestFitBlock* BestFitHeap::Coalesce( ODBlockSize sizeNeeded /*=BestFitBlock_kMaxBlockSize*/ )
  570. {
  571.     if( fAvailBytes == 0 )
  572.         return NULL;                // Nothing to coalesce
  573.     if( sizeNeeded > fFreeBytes+fAvailBytes && sizeNeeded!=BestFitBlock_kMaxBlockSize )
  574.         return NULL;                // Not enough room in heap
  575.                                     // (but BestFitBlock_kMaxBlockSize forces a coalesce anyway)
  576.     PrivFreeBlockList *list;
  577.     
  578. #if MM_DEBUG_COALESCE
  579.     MM_WARN_COALESCE("Coalescing (need %ld bytes)...", sizeNeeded);
  580.     ODBlockSize freed = 0;
  581.     long nFreed = 0;
  582. #endif
  583.  
  584.     if( sizeNeeded < kAvailBlockSizeLimit+PrivBestFitBlock::kBusyOverhead ) {
  585.         // If size could be on avail list, check all avail lists for that size & larger.
  586.         // Note that DoAllocate only checks 4 lists larger than the size, so this could
  587.         // succeed where that failed...
  588.         long index = (sizeNeeded-PrivBestFitBlock::kMinBlockSize) >>2;
  589.         list = &fAvailBlocks[index];
  590.         for( int i=kNAvailBlockLists-index; i>0; i--,list++ )
  591.             if( list->NotEmpty() ) {
  592.                 // If so, unhook the block from its list and return it:
  593.                 PrivBestFitBlock *blk = list->GetBlock();
  594.                 MM_ASSERT(blk->GetSize()>=sizeNeeded);
  595.                 fAvailBytes -= blk->GetSize();
  596.                 blk = this->BasicFreeBlock(blk);
  597.                 MM_WARN_COALESCE("...found avail block of size %ld.",blk->GetSize());
  598.                 return blk;
  599.             }
  600.     }
  601.  
  602.     list = &fAvailBlocks[kNAvailBlockLists-1];    // start w/large blocks
  603.     for( int i=kNAvailBlockLists-1; i!=0; i--,list-- ) {
  604.         PrivBestFitBlock *next;
  605.         for( PrivBestFitBlock *blk = list->First(); blk; blk = next ) {
  606.             if( MM_DEBUG )
  607.                 if( !blk->GetBusy() || !blk->GetAvail()
  608.                         || blk->GetMagicNumber() != (unsigned int)PrivBestFitBlock::kMagicNumber )
  609.                     MM_WARN("Avail block %p looks bogus",blk);
  610.             
  611.             next = blk->GetNext();
  612.  
  613.             #if MM_DEBUG_COALESCE
  614.             freed += blk->GetSize();
  615.             nFreed++;
  616.             #endif
  617.             
  618.             // Free this block, coalescing it with free neighbors:
  619.             fAvailBytes -= blk->GetSize();
  620.             blk = this->BasicFreeBlock(blk);
  621.             ODBlockSize size = blk->GetSize();
  622.             
  623.             if( size >= sizeNeeded ) {
  624.                 list->ForceFirst(next);                // Remove blocks we've processed so far
  625.                 #if MM_DEBUG_COALESCE
  626.                 MM_WARN_COALESCE("...Freed %ld bytes (%ld left) in %ld blocks, created %ld byte free block.",
  627.                                  freed,fAvailBytes,nFreed,size);
  628.                 #endif
  629.                 #if MM_DEBUG
  630.                     if( gValidate )
  631.                         this->Check();
  632.                 #endif
  633.                 return blk;
  634.             } else if( blk->GetIsFirst() && this->DeleteSegmentIfEmpty(blk) )
  635.                 ;
  636.             else
  637.                 this->AddToFreeBlocks(blk);
  638.         }
  639.         
  640.         list->ForceEmpty();
  641.     }
  642.     
  643.     #if MM_DEBUG_COALESCE
  644.     MM_WARN_COALESCE("...failed. Freed %ld bytes (%ld left) in %ld blocks.",
  645.                      freed,fAvailBytes,nFreed);
  646.     #endif
  647.  
  648. #if MM_DEBUG
  649.     if( gValidate )
  650.         this->Check();
  651. #endif
  652.         
  653.     return NULL;
  654. }
  655.  
  656.  
  657. /*
  658. mmboolean BestFitHeap::Coalesce( )
  659. {
  660.     long n = 0;
  661.     
  662. //    MM_WARN_COALESCE("Coalescing. Freeing small blocks...");
  663.     
  664.     // First mark each small block as unbusy, still without coalescing them:
  665.     PrivFreeBlockList *list = &fAvailBlocks[0];
  666.     for( int i=kNAvailBlockLists-1; i!=0; i--,list++ ) {
  667.         PrivBestFitBlock *next;
  668.         for( PrivBestFitBlock *blk = list->First(); blk; blk = next ) {
  669.             n++;
  670.             next = blk->GetNext();
  671.             blk->SetBusy(false);
  672.             MM_ASSERT(blk->GetAvail());    // Avail will be cleared in segment coalesce
  673.             blk->StuffAddressAtEnd();
  674.             PrivBestFitBlock *nextBlk
  675.                 = (PrivBestFitBlock *) ((ODBytePtr) blk + blk->GetSize());
  676.             nextBlk->SetPrevBusy(false);
  677.         }
  678.         list->ForceEmpty();
  679.     }
  680.     
  681.     if( n==0 ) {
  682. //        MM_WARN_COALESCE("...done coalescing, nothing to do.");
  683.         return false;            // Nothing happened
  684.     }
  685.     
  686. //    MM_WARN_COALESCE("...Freed %ld small blocks...",n);
  687.     
  688.     // Now walk the entire heap, coalescing sequences of free blocks:
  689.     mmboolean coalescence = false;
  690.     PrivBestFitSegment* *prev = &fSegments;
  691.     PrivBestFitSegment* next;
  692.     for( PrivBestFitSegment *segment=fSegments; segment != NULL; segment=next ) {
  693.         next = segment->fNextSegment;
  694.         if( !segment->Coalesce(this,coalescence) ) {
  695.             this->FreeRawMemory(segment);        // segment is empty, dispose it
  696.             *prev = next;
  697.         } else
  698.             prev = &segment->fNextSegment;
  699.     }
  700.     
  701. #if MM_DEBUG_COALESCE
  702.     this->Check();
  703. #endif
  704.  
  705. //    MM_WARN_COALESCE("...done coalescing.");
  706.     return coalescence;
  707. }
  708. */
  709. #endif /* MM_DEFER_COALESCE */
  710.  
  711. //----------------------------------------------------------------------------------------
  712. // BestFitHeap::DoLargestFreeBlock
  713. //----------------------------------------------------------------------------------------
  714. #pragma segment HeapSeg
  715.  
  716. unsigned long BestFitHeap::DoLargestFreeBlock() const
  717. {
  718.     const PrivBestFitBlock *blk = fFreeTree.FindLargestBlock();
  719.     if( blk )
  720.         return blk->GetSize() - PrivBestFitBlock::kBusyOverhead;
  721.     else
  722.         return 0;
  723. }
  724.  
  725. #if MM_DEBUG
  726. //----------------------------------------------------------------------------------------
  727. // BestFitHeap::DoIsValidBlock
  728. //----------------------------------------------------------------------------------------
  729. #pragma segment HeapSeg
  730.  
  731. mmboolean BestFitHeap::DoIsValidBlock(const void* ptr) const
  732. {
  733.     const PrivBestFitBlock *blk = ValidBlock(ptr);
  734.     if( !blk )
  735.         return kMMFalse;
  736.     else
  737.         // Verify that a huge block must be the first block in its segment:
  738.         return blk->GetIsFirst() || blk->GetSize()<fHugeBlockSize;
  739. }
  740. #endif
  741.  
  742. #if 0
  743. //----------------------------------------------------------------------------------------
  744. // BestFitHeap::DoReset
  745. //----------------------------------------------------------------------------------------
  746. #pragma segment HeapSeg
  747.  
  748. void BestFitHeap::DoReset()
  749. {
  750.     this->DeleteSegments();
  751.     fSegments = NULL;
  752.     fFreeTree = PrivFreeBlockTree();
  753.  
  754.     this->GrowHeap(fSizeInitial);
  755. }
  756. #endif
  757.  
  758. //----------------------------------------------------------------------------------------
  759. // BestFitHeap::HeapSize
  760. //----------------------------------------------------------------------------------------
  761. #pragma segment HeapSeg
  762.  
  763. unsigned long BestFitHeap::HeapSize() const
  764. {
  765.     PrivBestFitSegment * segment = fSegments;
  766.     unsigned long heapSize = 0;
  767.  
  768.     while (segment != NULL)
  769.     {
  770.         heapSize += segment->fSegmentSize;
  771.         segment = segment->fNextSegment;
  772.     }
  773.  
  774.     return heapSize;
  775. }
  776.  
  777.  
  778. //----------------------------------------------------------------------------------------
  779. // BestFitHeap::DoSetBlockIsObject
  780. //----------------------------------------------------------------------------------------
  781. void BestFitHeap::DoSetBlockIsObject( void* ptr, mmboolean isObject )
  782. {
  783. #if MM_DEBUG
  784.     MM_ASSERT(this->DoIsValidBlock(ptr));
  785. #endif
  786.     PrivBestFitBlock *blk
  787.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  788.     blk->SetIsObject(isObject);
  789. }
  790.  
  791.  
  792.  
  793. //----------------------------------------------------------------------------------------
  794. // BestFitHeap::DoBlockIsObject
  795. //----------------------------------------------------------------------------------------
  796. mmboolean BestFitHeap::DoBlockIsObject( const void* ptr ) const
  797. {
  798. #if MM_DEBUG
  799.     MM_ASSERT(this->DoIsValidBlock(ptr));
  800. #endif
  801.     PrivBestFitBlock *blk
  802.         = (PrivBestFitBlock *) ((ODBytePtr) ptr - PrivBestFitBlock::kBusyOverhead);
  803.     return blk->GetIsObject();
  804. }
  805.  
  806.  
  807. #if MM_DEBUG
  808. //----------------------------------------------------------------------------------------
  809. // BestFitHeap::IsMyBlock
  810. //----------------------------------------------------------------------------------------
  811. #pragma segment HeapSeg
  812.  
  813. mmboolean BestFitHeap::IsMyBlock(const void* blk) const
  814. {
  815.     mmboolean myBlock = false;
  816.  
  817.     PrivBestFitSegment * segment = fSegments;
  818.     while (segment != NULL && myBlock == false)
  819.     {
  820.         myBlock = segment->AddressInSegment(blk);
  821.         segment = segment->fNextSegment;
  822.     }
  823.  
  824.     return myBlock;
  825. }
  826. #endif
  827.  
  828. #if MM_DEBUG
  829. //----------------------------------------------------------------------------------------
  830. // BestFitHeap::Print
  831. //----------------------------------------------------------------------------------------
  832. #pragma segment HeapSeg
  833.  
  834. void BestFitHeap::Print(char* msg) const
  835. {
  836.     MM_PRINT("********** BestFitHeap **********\n");
  837.     fFreeTree.PrintTree();
  838.     MM_PRINT("\n");
  839. }
  840. #endif
  841.  
  842. //----------------------------------------------------------------------------------------
  843. // BestFitHeap::CreateNewSegment
  844. //----------------------------------------------------------------------------------------
  845. #pragma segment HeapSeg
  846.  
  847. PrivBestFitBlock* BestFitHeap::CreateNewSegment(unsigned long size)
  848. {
  849. #ifdef BUILD_WIN16
  850.     MM_ASSERT(size < 64L * 1024L);
  851. #endif
  852.  
  853.     // Make sure size is a multiple of 4 (to keep all blocks on 4byte boundaries)
  854.     size = (size+3) & ~0x03L;
  855.     // For this to work, kSegmentPrefixSize and kSegmentSuffixSize must also be
  856.     // multiples of 4.
  857.  
  858.     mmboolean disposable = (fSegments!=NULL);        // First segment is NOT disposable
  859.  
  860.     PrivBestFitSegment * segment
  861.         = (PrivBestFitSegment *)this->AllocateRawMemory((ODBlockSize) size);
  862.  
  863.     if (segment == NULL)
  864.         return NULL;
  865.     else {
  866.         // The actual usable space is offset by the size of the fields
  867.         // of a PrivBestFitSegment.
  868.     
  869.         segment->fSegmentSpace 
  870.             = (void *) ((ODBytePtr) segment + PrivBestFitSegment::kSegmentPrefixSize);
  871.         segment->fSegmentSize = size - PrivBestFitSegment::kSegmentPrefixSize;
  872.     
  873.         // Add the segment to the list of segments in this heap.
  874.     
  875.         segment->fNextSegment = fSegments;
  876.         fSegments = segment;
  877.     
  878.         // Suffix the segment with a busy block of zero length so that the last free
  879.         // block is not coalesced with a block past the fEnd of the segment.
  880.     
  881.         void * endOfSegment 
  882.             = (void *) ((ODBytePtr) segment->fSegmentSpace + segment->fSegmentSize);
  883.         PrivBestFitBlock *blk
  884.             = new((void *) ((ODBytePtr) endOfSegment - sizeof(PrivBestFitBlock)))
  885.                 PrivBestFitBlock(true, false, sizeof(PrivBestFitBlock));
  886.         blk->SetHeap(this);
  887.     
  888.         // Create one free block out of this entire segment and Add it to the
  889.         // free block list.
  890.     
  891.         blk = new(segment->fSegmentSpace)PrivBestFitBlock(false, true, segment->fSegmentSize - sizeof(PrivBestFitBlock));
  892.     
  893.         if( disposable )
  894.             // This is the 1st block (positionally) in the heap, so set its bit:
  895.             blk->SetIsFirst(true); 
  896.         
  897.         // Don't add to free blocks (speed optimization for DoAllocate)
  898.         
  899.         MM_WARN_COALESCE("** Created %ld byte segment **",size);
  900.  
  901.         return blk;
  902.     }
  903. }
  904.  
  905. //----------------------------------------------------------------------------------------
  906. // BestFitHeap::DeleteSegment
  907. //----------------------------------------------------------------------------------------
  908. #pragma segment HeapSeg
  909.  
  910. void BestFitHeap::DeleteSegment( PrivBestFitSegment *seg )
  911. {
  912.     // The segment MUST be empty, and its single free block
  913.     // must already have been removed from the free block tree.
  914.     
  915. #if MM_DEBUG_COALESCE
  916.     MM_WARN("Deleting a segment.");
  917. #endif
  918.     
  919.     PrivBestFitSegment *segment = fSegments;
  920.     
  921.     if( segment == seg ) {
  922.         fSegments = seg->fNextSegment;
  923.         this->FreeRawMemory(seg);
  924.         return;
  925.         
  926.     } else
  927.         while (segment != NULL)
  928.             if( segment->fNextSegment == seg ) {
  929.                 segment->fNextSegment = seg->fNextSegment;
  930.                 this->FreeRawMemory(seg);
  931.                 return;
  932.             } else
  933.                 segment = segment->fNextSegment;
  934.  
  935.     MM_WARN("Segment not found in list!");
  936. }
  937.  
  938. //----------------------------------------------------------------------------------------
  939. // BestFitHeap::DeleteSegments
  940. //----------------------------------------------------------------------------------------
  941. #pragma segment HeapSeg
  942.  
  943. void BestFitHeap::DeleteSegments()
  944. {
  945.     PrivBestFitSegment * segment = fSegments;
  946.     while (segment != NULL)
  947.     {
  948.         PrivBestFitSegment * nextSegment = segment->fNextSegment;
  949.         this->FreeRawMemory(segment);
  950.         segment = nextSegment;
  951.     }
  952. }
  953.  
  954. //----------------------------------------------------------------------------------------
  955. // BestFitHeap::GrowHeap
  956. //----------------------------------------------------------------------------------------
  957. #pragma segment HeapSeg
  958.  
  959. void BestFitHeap::GrowHeap(unsigned long sizeIncrement)
  960. {
  961. //    MM_WARN_COALESCE("Allocating new segment of %ld bytes.",sizeIncrement);
  962.  
  963. #ifdef BUILD_WIN16
  964.     // To avoid crossing 64K boundries on pointer arithmatic, the size of each segment
  965.     // must be limited to 64K. So a single grow request may result in more than one
  966.     // segment being allocated.
  967.     
  968.     const unsigned long kSegmentSizeLimit = 1024L * 62L;     // Allow for 2K overhead
  969.     
  970.     while (sizeIncrement > 0)
  971.     {
  972.         unsigned long segmentSize = sizeIncrement;
  973.         if (segmentSize > kSegmentSizeLimit)
  974.             segmentSize = kSegmentSizeLimit;
  975.         blk = this->CreateNewSegment(segmentSize);
  976.         if( !blk ) return;
  977.         this->AddToFreeBlocks(blk);
  978.         sizeIncrement -= segmentSize;
  979.     }
  980. #else
  981.     PrivBestFitBlock *blk = this->CreateNewSegment(sizeIncrement);
  982.     if( blk )
  983.         this->AddToFreeBlocks(blk);
  984. #endif
  985. }
  986.  
  987. #if MM_DEBUG
  988. //----------------------------------------------------------------------------------------
  989. // BestFitHeap::CompilerCheck
  990. //----------------------------------------------------------------------------------------
  991. #pragma segment HeapSeg
  992.  
  993. void BestFitHeap::CompilerCheck()
  994. {
  995.     MemoryHeap::CompilerCheck();
  996.     
  997.     char buffer[sizeof(PrivBestFitBlock) + sizeof(void *)];
  998.     PrivBestFitBlock &block = *((PrivBestFitBlock *) buffer);
  999.         
  1000.     // Check to make sure the bit field setters and getters work.
  1001.     
  1002. //    block.SetBlockType(3);
  1003.     block.SetBusy(true);
  1004.     block.SetPrevBusy(false);
  1005. #ifndef BUILD_WIN16
  1006.     block.SetSize(100201);
  1007. #endif
  1008.     block.SetMagicNumber(3);
  1009.  
  1010. //    MM_ASSERT(block.GetBlockType() == 3);
  1011.     MM_ASSERT(block.GetBusy() == true);
  1012.     MM_ASSERT(block.GetPrevBusy() == false);
  1013. #ifndef BUILD_WIN16
  1014.     MM_ASSERT(block.GetSize() == 100201);
  1015. #endif
  1016.     MM_ASSERT(block.GetMagicNumber() == 3);
  1017.     
  1018. //    block.SetBlockType(2);
  1019.     block.SetBusy(false);
  1020.     block.SetPrevBusy(true);
  1021.     block.SetSize(150);
  1022.     block.SetMagicNumber(2);
  1023.  
  1024. //    MM_ASSERT(block.GetBlockType() == 2);
  1025.     MM_ASSERT(block.GetBusy() == false);
  1026.     MM_ASSERT(block.GetPrevBusy() == true);
  1027.     MM_ASSERT(block.GetSize() == 150);
  1028.     MM_ASSERT(block.GetMagicNumber() == 2);
  1029. }
  1030. #endif
  1031.  
  1032.  
  1033. //========================================================================================
  1034. // CLASS PrivFreeBlockTree
  1035. //========================================================================================
  1036.  
  1037. //----------------------------------------------------------------------------------------
  1038. // PrivBestFitSegment::CheckSegment
  1039. //----------------------------------------------------------------------------------------
  1040.  
  1041. mmboolean PrivBestFitSegment::CheckSegment( HeapWalkProc proc, void *refCon,
  1042.                                           ODBlockSize hdrSize, ODBlockSize sizeDelta )
  1043. {
  1044.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  1045.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  1046.     unsigned long blksScanned = 0;
  1047.  
  1048.     // ----- spin through all the blocks in segment do some consistency checks
  1049.     
  1050.     while (blk < segmentEnd)
  1051.     {
  1052.         PrivBestFitBlock *nextBlk;
  1053.         MM_ASSERT(blk->GetMagicNumber() == PrivBestFitBlock::kMagicNumber);
  1054. //        MM_ASSERT(blk->GetBlockType() == PrivBestFitBlock::kBlockTypeId);
  1055.         nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  1056.         if(nextBlk==blk) {
  1057.             MM_WARN("Block %p header damaged -- skipping segment",blk);
  1058.             return false;
  1059.         } else if( nextBlk > segmentEnd ) {
  1060.             MM_WARN("Block %p unnaturally large -- skipping segment",blk);
  1061.             return false;
  1062.         } else if (nextBlk < segmentEnd)
  1063.             MM_ASSERT(nextBlk->GetPrevBusy() == blk->GetBusy());
  1064.         
  1065.         MM_ASSERT(blk->GetAvail()<=blk->GetBusy());
  1066.         
  1067.         if( proc )            // Call user proc if they supplied one
  1068.             if( blk->GetBusy() && !blk->GetAvail() && nextBlk<segmentEnd ) {
  1069.                 ODBytePtr userBlk = (ODBytePtr)blk + PrivBestFitBlock::kBusyOverhead + hdrSize;
  1070.                 if( (*proc)((void*)userBlk,
  1071.                              blk->GetSize()-PrivBestFitBlock::kBusyOverhead-sizeDelta,
  1072.                              blk->GetIsObject(),
  1073.                              refCon)
  1074.                         == false )
  1075.                     return false;        // proc can return false to abort
  1076.             }
  1077.         
  1078.         blksScanned++;
  1079.         blk = nextBlk;
  1080.     }
  1081.  
  1082.     // ----- if sizes are valid we should be exactly at the end of the segment
  1083.     
  1084.     MM_ASSERT(blk == segmentEnd);
  1085.     return true;
  1086. }
  1087.  
  1088. #if MM_DEBUG
  1089. //----------------------------------------------------------------------------------------
  1090. // PrivBestFitSegment::FindBlockContaining
  1091. //----------------------------------------------------------------------------------------
  1092.  
  1093. mmboolean
  1094. PrivBestFitSegment::FindBlockContaining( const void *start, const void* end,
  1095.                                          const void* &blockStart, const void* &blockEnd ) const
  1096. {
  1097.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  1098.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  1099.     
  1100.     if( end<=blk || start>=segmentEnd )
  1101.         return kMMFalse;
  1102.     else {
  1103.         // Memory range intersects range of this segment:
  1104.         while (blk < segmentEnd)
  1105.         {
  1106.             blockStart = blockEnd = NULL;
  1107.             PrivBestFitBlock *nextBlk;
  1108.             nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  1109.             if( blk->GetBusy() && nextBlk<segmentEnd ) {
  1110.                 if( start <= nextBlk ) {
  1111.                     // The memory range starts before the next block, so return:
  1112.                     blockStart = (char*)blk + PrivBestFitBlock::kBusyOverhead;
  1113.                     blockEnd   = nextBlk;
  1114.                     break;
  1115.                 }
  1116.             }
  1117.             blk = nextBlk;
  1118.         }
  1119.         return kMMTrue;
  1120.     }
  1121. }
  1122.  
  1123. #endif
  1124.  
  1125. #if 0 /* OBSOLETE CODE */
  1126. mmboolean
  1127. PrivBestFitSegment::Coalesce( BestFitHeap *heap, mmboolean &coalescence )
  1128. {
  1129.     /*    Loop through the blocks in the segment.
  1130.         When we hit the first free block in a row, we remember its location.
  1131.         On subsequent free blocks, remove the previous free block from the free tree.
  1132.         When we finally hit a busy block, coalesce the free blocks and add to free tree.
  1133.         If there was only one free block in a row, still need to fix it up somewhat
  1134.         (stuff address at end and set PrevBusy flag of next block.)
  1135.         
  1136.         We can tell newly freed small blocks because their Avail flag is true.
  1137.         They don't need to be removed from the free list 'cause they're not on it.
  1138.         
  1139.         If there are no busy blocks left in this segment, don't add the humongous
  1140.         single free block back to the free tree; instead return false so that the
  1141.         caller (BestFitHeap::Coalesce()) will know to dispose this segment. */
  1142.         
  1143.     PrivBestFitBlock *blk = (PrivBestFitBlock *) fSegmentSpace;
  1144.     void *segmentEnd = (char *) fSegmentSpace + fSegmentSize;
  1145.     
  1146.     PrivBestFitBlock *co = NULL;        // First free block in a row
  1147.     PrivBestFitBlock *prevBlk = NULL;
  1148.     
  1149. #if MM_DEBUG_COALESCE
  1150.     long nBlocks =1;
  1151. #endif
  1152.  
  1153.     // Remember that the last block is a fake busy block, which is just what we want.
  1154.  
  1155.     while( blk < segmentEnd ) {
  1156.         PrivBestFitBlock *nextBlk = (PrivBestFitBlock *)  ((char *) blk +  blk->GetSize());
  1157.         
  1158.         if( !blk->GetBusy() ) {
  1159.             if( !co )
  1160.                 co = blk;
  1161.             else {
  1162.                 if( !prevBlk->GetAvail() )
  1163.                     heap->RemoveFromFreeBlocks(prevBlk);
  1164.                 #if MM_DEBUG_COALESCE
  1165.                 nBlocks++;
  1166.                 #endif
  1167.             }
  1168.         } else {
  1169.             if( co ) {
  1170.                 if( co!=prevBlk ) {
  1171.                     // End of a string of free blocks:
  1172. //                    MM_WARN_COALESCE("    coalescing range %p -- %p (%d blocks)", co,blk,nBlocks);
  1173.                     if( !prevBlk->GetAvail() )
  1174.                         heap->RemoveFromFreeBlocks(prevBlk);
  1175.                     if( co==(PrivBestFitBlock*)fSegmentSpace && nextBlk==segmentEnd )
  1176.                         return false;                // entire segment is now free
  1177.                     co->SetSize((size_t)blk-(size_t)co);
  1178.                     co->SetAvail(false);
  1179.                     co->StuffAddressAtEnd();
  1180.                     heap->AddToFreeBlocks(co);
  1181.                     coalescence = true;                // something did get coalesced
  1182.                 } else if( co->GetAvail() ) {
  1183.                     // Single newly-free block:
  1184.                     co->SetAvail(false);
  1185.                     heap->AddToFreeBlocks(co);
  1186.                 }
  1187.                 co = NULL;
  1188.                 #if MM_DEBUG_COALESCE
  1189.                     nBlocks = 1;
  1190.                 #endif
  1191.             }
  1192.         }
  1193.         
  1194.         prevBlk = blk;
  1195.         blk = nextBlk;
  1196.     }
  1197.     
  1198.     return true;
  1199. }
  1200. #endif /* END OBSOLETE CODE */
  1201.  
  1202.  
  1203. //========================================================================================
  1204. // CLASS PrivFreeBlockTree
  1205. //========================================================================================
  1206.  
  1207. //----------------------------------------------------------------------------------------
  1208. // PrivFreeBlockTree::PrivFreeBlockTree
  1209. //----------------------------------------------------------------------------------------
  1210. #pragma segment HeapSeg
  1211.  
  1212. PrivFreeBlockTree::PrivFreeBlockTree() :
  1213.     fRoot(true, true, 0)
  1214. {
  1215.     fRoot.SetRight(NULL);
  1216.     fRoot.SetLeft(NULL);
  1217.     fRoot.SetParent(NULL);
  1218. }
  1219.  
  1220. //----------------------------------------------------------------------------------------
  1221. // PrivFreeBlockTree::PrivFreeBlockTree
  1222. //----------------------------------------------------------------------------------------
  1223. #pragma segment HeapSeg
  1224.  
  1225. PrivFreeBlockTree::PrivFreeBlockTree(const PrivFreeBlockTree& blk) :
  1226.     fRoot(blk.fRoot)
  1227. {
  1228. }
  1229.  
  1230. //----------------------------------------------------------------------------------------
  1231. // PrivFreeBlockTree::AddBlock
  1232. //----------------------------------------------------------------------------------------
  1233. #pragma segment HeapSeg
  1234.  
  1235. void PrivFreeBlockTree::AddBlock(PrivBestFitBlock* blk)
  1236. {    
  1237. #if MM_DEBUG
  1238.     if( gValidate>0 )
  1239.         this->CheckTree();
  1240.  
  1241. #ifdef OD_INTENSE_DEBUG
  1242.     MM_PRINT("PrivFreeBlockTree::AddBlock Entry-------------------------------------\n");
  1243.     this->PrintTree();
  1244. #endif
  1245. #endif
  1246.  
  1247.     PrivBestFitBlock * parent;
  1248.  
  1249.     this->SearchForBlock(blk->GetSize(), blk, &parent);
  1250.  
  1251.     blk->SetRight(NULL);
  1252.     blk->SetLeft(NULL);
  1253.     blk->SetParent(parent);
  1254.  
  1255.     if (*blk > *parent)
  1256.         parent->SetRight(blk);
  1257.     else
  1258.         parent->SetLeft(blk);
  1259.  
  1260. #if MM_DEBUG
  1261.     if( gValidate>0 )
  1262.         this->CheckTree();
  1263.  
  1264. #ifdef OD_INTENSE_DEBUG
  1265.     MM_PRINT("PrivFreeBlockTree::AddBlock Exit\n");
  1266.     this->PrintTree();
  1267.     MM_PRINT("\n");
  1268. #endif
  1269. #endif
  1270. }
  1271.  
  1272. #if MM_DEBUG
  1273. //----------------------------------------------------------------------------------------
  1274. // PrivFreeBlockTree::CheckTree
  1275. //----------------------------------------------------------------------------------------
  1276. #pragma segment HeapSeg
  1277.  
  1278. void PrivFreeBlockTree::CheckTree() const
  1279. {
  1280.     this->CheckTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1281. }
  1282. #endif
  1283.  
  1284. #if MM_DEBUG
  1285. //----------------------------------------------------------------------------------------
  1286. // PrivFreeBlockTree::PrintTree
  1287. //----------------------------------------------------------------------------------------
  1288. #pragma segment HeapSeg
  1289.  
  1290. void PrivFreeBlockTree::PrintTree() const
  1291. {
  1292.     this->PrintTreeHelper(&((PrivFreeBlockTree *)this)->fRoot);
  1293. }
  1294. #endif
  1295.  
  1296. //----------------------------------------------------------------------------------------
  1297. // PrivFreeBlockTree::RemoveBlock
  1298. //----------------------------------------------------------------------------------------
  1299. #pragma segment HeapSeg
  1300.  
  1301. void PrivFreeBlockTree::RemoveBlock(PrivBestFitBlock* blk)
  1302. {
  1303. #if MM_DEBUG
  1304.     if( gValidate > 0 )
  1305.         this->CheckTree();
  1306.  
  1307. #ifdef OD_INTENSE_DEBUG
  1308.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Entry----------------------------------\n");
  1309.     this->PrintTree();
  1310. #endif
  1311. #endif
  1312.  
  1313.     PrivBestFitBlock * spliceOutBlk;
  1314.  
  1315.     // Decide which block to splice out of the tree. Either the block being
  1316.     // removed, or its successor block in the tree.
  1317.  
  1318.     if (blk->GetLeft() == NULL || blk->GetRight() == NULL)
  1319.         spliceOutBlk = blk;
  1320.     else
  1321.         spliceOutBlk = this->GetSuccessorBlk(blk);
  1322.  
  1323.     // Splice the node out of the tree
  1324.  
  1325.     PrivBestFitBlock * tmp;
  1326.     PrivBestFitBlock * parent = spliceOutBlk->GetParent();
  1327.     if (spliceOutBlk->GetLeft())
  1328.         tmp = spliceOutBlk->GetLeft();
  1329.     else
  1330.         tmp = spliceOutBlk->GetRight();
  1331.     if (tmp)
  1332.         tmp->SetParent(parent);
  1333.     if (spliceOutBlk == parent->GetLeft())
  1334.         parent->SetLeft(tmp);
  1335.     else
  1336.         parent->SetRight(tmp);
  1337.  
  1338.     // If we spliced out the successor to blk above then we need to patch the successor
  1339.     // back in, in Place of blk.
  1340.  
  1341.     if (spliceOutBlk != blk)
  1342.     {
  1343.         PrivBestFitBlock * parent = blk->GetParent();
  1344.  
  1345.         // Fix up the parent's child pointer.
  1346.  
  1347.         if (parent->GetLeft() == blk)
  1348.             parent->SetLeft(spliceOutBlk);
  1349.         else
  1350.             parent->SetRight(spliceOutBlk);
  1351.  
  1352.         // Fix up the splice in block's pointers.
  1353.  
  1354.         spliceOutBlk->SetParent(parent);
  1355.         spliceOutBlk->SetLeft(blk->GetLeft());
  1356.         spliceOutBlk->SetRight(blk->GetRight());
  1357.  
  1358.         // Fix up the children of the splice in block's parent pointers.
  1359.  
  1360.         if (spliceOutBlk->GetLeft())
  1361.             (spliceOutBlk->GetLeft())->SetParent(spliceOutBlk);
  1362.         if (spliceOutBlk->GetRight())
  1363.             (spliceOutBlk->GetRight())->SetParent(spliceOutBlk);
  1364.     }
  1365.  
  1366. #if MM_DEBUG
  1367.     if( gValidate>0 )
  1368.         this->CheckTree();
  1369.  
  1370. #ifdef OD_INTENSE_DEBUG
  1371.     MM_PRINT("PrivFreeBlockTree::RemoveBlock Exit\n");
  1372.     this->PrintTree();
  1373.     MM_PRINT("\n");
  1374. #endif
  1375. #endif
  1376. }
  1377.  
  1378. //----------------------------------------------------------------------------------------
  1379. // PrivFreeBlockTree::SearchForBlock
  1380. //----------------------------------------------------------------------------------------
  1381. #pragma segment HeapSeg
  1382.  
  1383. PrivBestFitBlock* PrivFreeBlockTree::SearchForBlock(ODBlockSize size,
  1384.                                             void* blk,
  1385.                                             PrivBestFitBlock** insertLeaf)
  1386. {
  1387. #if MM_DEBUG
  1388.     if( gValidate>0 )
  1389.         this->CheckTree();
  1390.  
  1391. #ifdef OD_INTENSE_DEBUG
  1392.     char str[80];
  1393.     sprintf(str, "PrivFreeBlockTree::SearchForBlock(%d)---------------------------------\n", size);
  1394.     MM_PRINT(str);
  1395.     this->PrintTree();
  1396. #endif
  1397. #endif
  1398.  
  1399.     long minDiff = LONG_MAX;
  1400.     PrivBestFitBlock * minDiffBlock = NULL;
  1401.     PrivBestFitBlock * currentBlock = &fRoot;
  1402.     PrivBestFitBlock * lastBlock;
  1403.     do
  1404.     {
  1405.         lastBlock = currentBlock;
  1406.         long diff = currentBlock->GetSize() - size;
  1407.         if (diff >= 0 && diff <= minDiff)
  1408.         {
  1409.             minDiffBlock = currentBlock;
  1410.             minDiff = diff;
  1411.         }
  1412.  
  1413.         // Determine which branch of the tree to continue down. Since duplicate keys are
  1414.         // difficult to deal with in binary trees, we use the address of blocks to break
  1415.         // ties, in the case of two blocks whose size are equal.
  1416.  
  1417.         if ( diff>0 )
  1418.             currentBlock = currentBlock->GetLeft();
  1419.         else if ( diff<0 )
  1420.             currentBlock = currentBlock->GetRight();
  1421.         else if (blk)
  1422.         {
  1423.             if (blk <= currentBlock)
  1424.                 currentBlock = currentBlock->GetLeft();
  1425.             else
  1426.                 currentBlock = currentBlock->GetRight();
  1427.         }
  1428.         else
  1429.             currentBlock = currentBlock->GetLeft();
  1430.  
  1431.     } while (currentBlock != NULL);
  1432.  
  1433.     if (insertLeaf)
  1434.         *insertLeaf = lastBlock;
  1435.  
  1436.     return minDiffBlock;
  1437. }
  1438.  
  1439. //----------------------------------------------------------------------------------------
  1440. // PrivFreeBlockTree::FindLargestBlock
  1441. //----------------------------------------------------------------------------------------
  1442. #pragma segment HeapSeg
  1443.  
  1444. const PrivBestFitBlock* PrivFreeBlockTree::FindLargestBlock( ) const
  1445. {
  1446.     // The block to the right in the tree is always larger...
  1447.     
  1448.     const PrivBestFitBlock * currentBlock = &fRoot;
  1449.     const PrivBestFitBlock * nextBlock;
  1450.     while( (nextBlock = currentBlock->GetRight()) != kMMNULL )
  1451.         currentBlock = nextBlock;
  1452.     return currentBlock;
  1453. }
  1454.  
  1455. //----------------------------------------------------------------------------------------
  1456. // PrivFreeBlockTree::TreeInfo
  1457. //----------------------------------------------------------------------------------------
  1458. #pragma segment HeapSeg
  1459.  
  1460. void PrivFreeBlockTree::TreeInfo(unsigned long& bytesFree,
  1461.                              unsigned long& numberOfNodes) const
  1462. {
  1463.     bytesFree = numberOfNodes = 0;
  1464.     this->TreeInfoHelper(&((PrivFreeBlockTree *)this)->fRoot, bytesFree, numberOfNodes);
  1465.  
  1466.     // Subtract one from the number of nodes to account for the header node which
  1467.     // is always empty.
  1468.  
  1469.     numberOfNodes--;
  1470. }
  1471.  
  1472. #if MM_DEBUG
  1473. //----------------------------------------------------------------------------------------
  1474. // PrivFreeBlockTree::CheckTreeHelper
  1475. //----------------------------------------------------------------------------------------
  1476. #pragma segment HeapSeg
  1477.  
  1478. void PrivFreeBlockTree::CheckTreeHelper(PrivBestFitBlock* blk) const
  1479. {
  1480.     if (blk == NULL)
  1481.         return;
  1482.  
  1483.     this->CheckTreeHelper(blk->GetLeft());
  1484.  
  1485.     PrivBestFitBlock * parent = blk->GetParent();
  1486.     if (parent != NULL)
  1487.     {
  1488.         if (parent->GetRight() == blk)
  1489.         {
  1490.             if (*blk < *parent)
  1491.             {
  1492.                 this->PrintTree();
  1493.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1494.                                              "Corrupt free list tree: "
  1495.                                              "right child less than parent.");
  1496.             }
  1497.         }
  1498.         else if (parent->GetLeft() == blk)
  1499.         {
  1500.             if (*blk > *parent)
  1501.             {
  1502.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1503.                                              "Corrupt free list tree: "
  1504.                                              "left child greater than parent.");
  1505.             }
  1506.         }
  1507.         else
  1508.         {
  1509.                 MM_WARN("PrivFreeBlockTree::CheckTreeHelper"
  1510.                                              "Corrupt free list tree: "
  1511.                                              "I am not my parent's child.");
  1512.         }
  1513.     }
  1514. }
  1515. #endif
  1516.  
  1517. //----------------------------------------------------------------------------------------
  1518. // PrivFreeBlockTree::GetSuccessorBlk
  1519. //----------------------------------------------------------------------------------------
  1520. #pragma segment HeapSeg
  1521.  
  1522. PrivBestFitBlock* PrivFreeBlockTree::GetSuccessorBlk(PrivBestFitBlock* blk)
  1523. {
  1524.     PrivBestFitBlock * current = blk->GetRight();
  1525.     if (current)
  1526.     {
  1527.         PrivBestFitBlock *left;
  1528.         while( (left=current->GetLeft()) != NULL )
  1529.             current = left;
  1530.         return current;
  1531.     }
  1532.     else
  1533.     {
  1534.         PrivBestFitBlock * parent = blk->GetParent();
  1535.         while (parent != NULL && current == parent->GetRight())
  1536.         {
  1537.             current = parent;
  1538.             parent = parent->GetParent();
  1539.         }
  1540.         return parent;
  1541.     }
  1542. }
  1543.  
  1544. #if MM_DEBUG
  1545. //----------------------------------------------------------------------------------------
  1546. // PrivFreeBlockTree::PrintTreeHelper
  1547. //----------------------------------------------------------------------------------------
  1548. #pragma segment HeapSeg
  1549.  
  1550. void PrivFreeBlockTree::PrintTreeHelper(PrivBestFitBlock* blk,
  1551.                                         int level) const
  1552. {
  1553.     for (int i = 0; i < level; i++)
  1554.         MM_PRINT("\t");
  1555.  
  1556.     if (blk == NULL)
  1557.     {
  1558.         MM_PRINT("NULL\n");
  1559.         return;
  1560.     }
  1561.  
  1562.     char str[80];
  1563.     //sprintf(str, "Block=%lx fSize=%ld\n", blk, blk->GetSize());
  1564.     MM_PRINT(str);
  1565.  
  1566.     this->PrintTreeHelper(blk->GetLeft(), level + 1);
  1567.     this->PrintTreeHelper(blk->GetRight(), level + 1);
  1568. }
  1569. #endif
  1570.  
  1571. //----------------------------------------------------------------------------------------
  1572. // PrivFreeBlockTree::TreeInfoHelper
  1573. //----------------------------------------------------------------------------------------
  1574. #pragma segment HeapSeg
  1575.  
  1576. void PrivFreeBlockTree::TreeInfoHelper(PrivBestFitBlock* blk,
  1577.                                        unsigned long& bytesFree,
  1578.                                        unsigned long& numberOfNodes) const
  1579. {
  1580.     if (blk == NULL)
  1581.         return;
  1582.  
  1583.     this->TreeInfoHelper(blk->GetLeft(), bytesFree, numberOfNodes);
  1584.  
  1585.     numberOfNodes++;
  1586.     bytesFree += blk->GetSize();
  1587.  
  1588.     this->TreeInfoHelper(blk->GetRight(), bytesFree, numberOfNodes);
  1589. }
  1590.