home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 July: Mac OS SDK / Dev.CD Jul 96 SDK / Dev.CD Jul 96 SDK1.toast / Development Kits (Disc 1) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Memory / ObjectHe.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  17.9 KB  |  568 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        ObjectHe.cpp
  3.  
  4.     Contains:    ObjectHeap class implementation
  5.  
  6.     Written by:    Michael Burbidge
  7.  
  8.     Copyright:    © 1993-4 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.     
  12.          <4>     8/17/94    jpa        Minimal changes to keep it compiling
  13.                                     against current MemoryHeap API.
  14.          <3>      8/8/94    jpa        OD_DEBUG --> ODDebug
  15.          <2>     6/10/94    MB        Make it build
  16.          <1>      6/9/94    MB        first checked in
  17.          <2>      5/9/94    MB        #1162181: Changes necessary to install MMM.
  18.          <1>     4/29/94    MB        first checked in
  19.     To Do:
  20. */
  21.  
  22. #ifndef _PLATFMEM_
  23. #include "PlatfMem.h"
  24. #endif
  25.  
  26. #ifndef _OBJECTHE_
  27. #include "ObjectHe.h"
  28. #endif
  29.  
  30.  
  31. //========================================================================================
  32. // CLASS PrivChunkyBlock
  33. //========================================================================================
  34.  
  35. //----------------------------------------------------------------------------------------
  36. // PrivChunkyBlock::PrivChunkyBlock
  37. //----------------------------------------------------------------------------------------
  38.  
  39. PrivChunkyBlock::PrivChunkyBlock()
  40. {
  41.     SetBlockType(kBlockTypeId);
  42.     SetMagicNumber(kMagicNumber);
  43.     fNext = NULL;
  44. }
  45.  
  46. //----------------------------------------------------------------------------------------
  47. // PrivChunkyBlock::PrivChunkyBlock
  48. //----------------------------------------------------------------------------------------
  49.  
  50. PrivChunkyBlock::PrivChunkyBlock(unsigned int sizeIndex,
  51.                                  unsigned int blockIndex)
  52. {
  53.     SetSizeIndex(sizeIndex);
  54.     SetBlockIndex(blockIndex);
  55.     SetBlockType(kBlockTypeId);
  56.     SetMagicNumber(kMagicNumber);
  57.     fNext = NULL;
  58. }
  59.  
  60. //----------------------------------------------------------------------------------------
  61. // PrivChunkyBlock::GetChunk
  62. //----------------------------------------------------------------------------------------
  63.  
  64. PrivChunk* PrivChunkyBlock::GetChunk(ODBlockSize blkSize)
  65. {
  66.     PrivChunk *chk 
  67.         = (PrivChunk *) ((ODBytePtr) this - sizeof(ODPrivChunkHeader) - blkSize * GetBlockIndex());
  68.     return chk;
  69. }
  70.  
  71. //----------------------------------------------------------------------------------------
  72. // PrivChunkyBlock::IsBusy
  73. //----------------------------------------------------------------------------------------
  74.  
  75. Boolean PrivChunkyBlock::IsBusy(ODBlockSize blockSize)
  76. {
  77.     return this->GetChunk(blockSize)->IsBlockBusy(GetBlockIndex());
  78. }
  79.  
  80. //----------------------------------------------------------------------------------------
  81. // PrivChunkyBlock::SetBusy
  82. //----------------------------------------------------------------------------------------
  83.  
  84. void PrivChunkyBlock::SetBusy(ODBlockSize blockSize, Boolean busy)
  85. {
  86.     this->GetChunk(blockSize)->SetBlockBusy(GetBlockIndex(), busy);
  87. }
  88.  
  89.  
  90. //========================================================================================
  91. // PrivChunk
  92. //========================================================================================
  93.  
  94. //----------------------------------------------------------------------------------------
  95. // PrivChunk::PrivChunk
  96. //----------------------------------------------------------------------------------------
  97. #pragma segment HeapSeg
  98.  
  99. PrivChunk::PrivChunk(short blocksPerChunk,
  100.                      unsigned int sizeIndex,
  101.                      ODBlockSize blockSize)
  102. {
  103.     fHeader.fBlockBusyBits = 0;
  104.     void* blkPtr = (void *) ((ODBytePtr) this + sizeof(ODPrivChunkHeader));
  105.     for (unsigned int i = 0; i < blocksPerChunk; i++)
  106.     {
  107.         PrivChunkyBlock *blk = new(blkPtr)PrivChunkyBlock(sizeIndex, i);
  108.         blkPtr = (void *) ((ODBytePtr) blkPtr + blockSize);
  109.     }
  110. }
  111.  
  112. //----------------------------------------------------------------------------------------
  113. // PrivChunk::IsBlockBusy
  114. //----------------------------------------------------------------------------------------
  115. #pragma segment HeapSeg
  116.  
  117. Boolean PrivChunk::IsBlockBusy(unsigned int whichBlock)
  118. {
  119.     unsigned short mask = 0x0001;
  120.  
  121.     for (short i = 0; i < whichBlock; i++)
  122.         mask = mask << 1;
  123.  
  124.     return (fHeader.fBlockBusyBits & mask) != 0;
  125. }
  126.  
  127. //----------------------------------------------------------------------------------------
  128. // PrivChunk::SetBlockBusy
  129. //----------------------------------------------------------------------------------------
  130.  
  131. void PrivChunk::SetBlockBusy(unsigned int whichBlock, Boolean busy)
  132. {
  133.     unsigned short mask = 0x0001;
  134.  
  135.     for (short i = 0; i < whichBlock; i++)
  136.         mask = mask << 1;
  137.  
  138.     if (busy)
  139.         fHeader.fBlockBusyBits |= mask;
  140.     else
  141.         fHeader.fBlockBusyBits &= ~mask;
  142. }
  143.  
  144. //----------------------------------------------------------------------------------------
  145. // PrivChunk::GetBlock
  146. //----------------------------------------------------------------------------------------
  147.  
  148. PrivChunkyBlock* PrivChunk::GetBlock(unsigned int blkIndex, ODBlockSize blkSize)
  149. {
  150.     PrivChunkyBlock * blk 
  151.         = (PrivChunkyBlock *) ((ODBytePtr) this + sizeof(ODPrivChunkHeader) + blkIndex * blkSize);
  152.     return blk;
  153. }
  154.  
  155.  
  156. //========================================================================================
  157. // ObjectHeap
  158. //========================================================================================
  159.  
  160. const ODBlockSize ObjectHeap_kDefaultBlockSizes[]
  161.     = { (ODBlockSize) sizeof(PrivChunkyBlock), 10, 14, 18, 0 };
  162.  
  163. //----------------------------------------------------------------------------------------
  164. // ObjectHeap::ObjectHeap
  165. //----------------------------------------------------------------------------------------
  166. #pragma segment HeapSeg
  167.  
  168. ObjectHeap::ObjectHeap(unsigned long initialSize,
  169.                    unsigned long incrementSize,
  170.                    unsigned long hugeBlockSize,
  171.                    Boolean fromSysMemory,
  172.                    short blocksPerChunk) :
  173.     BestFitHeap(initialSize, incrementSize, hugeBlockSize, fromSysMemory),
  174.     fBlockSizes(ObjectHeap_kDefaultBlockSizes)
  175. {
  176. #if ODDebug
  177.     CompilerCheck();
  178. #endif
  179.  
  180.     fBlocksPerChunk = blocksPerChunk;
  181.  
  182.     for (fNumberOfBlockSizes = 0; fBlockSizes[fNumberOfBlockSizes]; fNumberOfBlockSizes++)
  183.         ;
  184. }
  185.  
  186. //----------------------------------------------------------------------------------------
  187. // ObjectHeap::ObjectHeap
  188. //----------------------------------------------------------------------------------------
  189. #pragma segment HeapSeg
  190.  
  191. ObjectHeap::ObjectHeap(const ODBlockSize* blockSizes,
  192.                    unsigned long initialSize,
  193.                    unsigned long incrementSize,
  194.                    unsigned long hugeBlockSize,
  195.                    Boolean fromSysMemory,
  196.                    short blocksPerChunk) :
  197.     BestFitHeap(initialSize, incrementSize, hugeBlockSize, fromSysMemory),
  198.     fBlockSizes(blockSizes)
  199. {
  200. #if ODDebug
  201.     CompilerCheck();
  202. #endif
  203.  
  204.     fBlocksPerChunk = blocksPerChunk;
  205.  
  206.     for (fNumberOfBlockSizes = 0; fBlockSizes[fNumberOfBlockSizes]; fNumberOfBlockSizes++)
  207.         ;
  208. }
  209.  
  210. //----------------------------------------------------------------------------------------
  211. // ObjectHeap::IObjectHeap
  212. //----------------------------------------------------------------------------------------
  213. #pragma segment HeapSeg
  214.  
  215. void ObjectHeap::IObjectHeap()
  216. {
  217.     this->IBestFitHeap();
  218. }
  219.  
  220. //----------------------------------------------------------------------------------------
  221. // ObjectHeap::~ObjectHeap
  222. //----------------------------------------------------------------------------------------
  223. #pragma segment HeapSeg
  224.  
  225. ObjectHeap::~ObjectHeap()
  226. {
  227. }
  228.  
  229. //----------------------------------------------------------------------------------------
  230. // ObjectHeap::DoAllocate
  231. //----------------------------------------------------------------------------------------
  232. #pragma segment HeapSeg
  233.  
  234. void* ObjectHeap::DoAllocate(ODBlockSize size, ODBlockSize& allocatedSize)
  235. {
  236.     if (size + PrivChunkyBlock::kBusyOverhead > fBlockSizes[fNumberOfBlockSizes - 1])
  237.         return BestFitHeap::DoAllocate(size, allocatedSize);
  238.     else
  239.     {
  240.         unsigned int sizeIndex = this->SizeIndex(size);
  241.         allocatedSize = fBlockSizes[sizeIndex] - PrivChunkyBlock::kBusyOverhead;
  242.         return this->AllocateBlock(sizeIndex);
  243.     }
  244. }
  245.  
  246. //----------------------------------------------------------------------------------------
  247. // ObjectHeap::DoBlockSize
  248. //----------------------------------------------------------------------------------------
  249. #pragma segment HeapSeg
  250.  
  251. ODBlockSize ObjectHeap::DoBlockSize(const void* ptr) const
  252. {
  253.     PrivChunkyBlock *block
  254.         = (PrivChunkyBlock *) ((ODBytePtr) ptr - PrivChunkyBlock::kBusyOverhead);
  255.         
  256.     if (block->GetBlockType() == PrivBestFitBlock::kBlockTypeId)
  257.         return BestFitHeap::DoBlockSize(ptr);
  258.     else
  259.         return fBlockSizes[block->GetSizeIndex()] - PrivChunkyBlock::kBusyOverhead;
  260. }
  261.  
  262. //----------------------------------------------------------------------------------------
  263. // ObjectHeap::DoFree
  264. //----------------------------------------------------------------------------------------
  265. #pragma segment HeapSeg
  266.  
  267. void ObjectHeap::DoFree(void* ptr)
  268. {
  269.     PrivChunkyBlock *block 
  270.         = (PrivChunkyBlock *) ((ODBytePtr) ptr - PrivChunkyBlock::kBusyOverhead);
  271.         
  272.     if (block->GetBlockType() == PrivBestFitBlock::kBlockTypeId)
  273.         BestFitHeap::DoFree(ptr);
  274.     else
  275.         this->FreeBlock(block);
  276. }
  277.  
  278. #if ODDebug
  279. //----------------------------------------------------------------------------------------
  280. // ObjectHeap::DoIsValidBlock
  281. //----------------------------------------------------------------------------------------
  282. #pragma segment HeapSeg
  283.  
  284. Boolean ObjectHeap::DoIsValidBlock(void* ptr) const
  285. {
  286.     Boolean isBlockValid = false;
  287.     
  288.     PrivChunkyBlock *block
  289.         = (PrivChunkyBlock *) ((ODBytePtr) ptr - PrivChunkyBlock::kBusyOverhead);
  290.  
  291.     if (block->GetBlockType() == PrivBestFitBlock::kBlockTypeId)
  292.         isBlockValid = BestFitHeap::DoIsValidBlock(ptr);
  293.     else
  294.         isBlockValid
  295.             = block->GetSizeIndex() <= fNumberOfBlockSizes &&
  296.               block->GetBlockIndex() <= fBlocksPerChunk &&
  297.               block->GetMagicNumber() == (unsigned int) PrivChunkyBlock::kMagicNumber;
  298.  
  299.     return isBlockValid;
  300. }
  301. #endif
  302.  
  303. //----------------------------------------------------------------------------------------
  304. // ObjectHeap::DoReset
  305. //----------------------------------------------------------------------------------------
  306. #pragma segment HeapSeg
  307.  
  308. void ObjectHeap::DoReset()
  309. {
  310.     PrivChunkyBlockStack clr;
  311.  
  312.     for (int i = 0; i < fNumberOfBlockSizes; i++)
  313.         fFreeLists[i] = clr;
  314.  
  315.     BestFitHeap::DoReset();
  316. }
  317.  
  318. //----------------------------------------------------------------------------------------
  319. // ObjectHeap::AllocateBlock
  320. //----------------------------------------------------------------------------------------
  321. #pragma segment HeapSeg
  322.  
  323. void *ObjectHeap::AllocateBlock(unsigned int sizeIndex)
  324. {
  325.     if (fFreeLists[sizeIndex].Top() == NULL)
  326.         this->CreateNewChunk(sizeIndex);
  327.  
  328.     PrivChunkyBlock * blk = fFreeLists[sizeIndex].Pop();
  329.     if (blk != NULL)
  330.     {
  331.         blk->SetBusy(fBlockSizes[sizeIndex], true);
  332.         return (void *) ((ODBytePtr) blk + PrivChunkyBlock::kBusyOverhead);
  333.     }
  334.     else
  335.         return NULL;
  336. }
  337.  
  338. //----------------------------------------------------------------------------------------
  339. // ObjectHeap::CreateNewChunk
  340. //----------------------------------------------------------------------------------------
  341. #pragma segment HeapSeg
  342.  
  343. void ObjectHeap::CreateNewChunk(unsigned int sizeIndex)
  344. {
  345.     ODBlockSize allocatedSize;
  346.     ODBlockSize allocSize = sizeof(ODPrivChunkHeader) + fBlocksPerChunk * fBlockSizes[sizeIndex];
  347.     PrivChunk * chk = new(BestFitHeap::DoAllocate(allocSize, allocatedSize))PrivChunk(fBlocksPerChunk, sizeIndex, fBlockSizes[sizeIndex]);
  348.     if (chk != NULL)
  349.     {
  350.         for (unsigned int i = 0; i < fBlocksPerChunk; i++)
  351.         {
  352.             PrivChunkyBlock * blk = chk->GetBlock(i, fBlockSizes[sizeIndex]);
  353.             blk->SetBusy(fBlockSizes[sizeIndex], false);
  354.             fFreeLists[sizeIndex].Push(blk);
  355.         }
  356.     }
  357. }
  358.  
  359. //----------------------------------------------------------------------------------------
  360. // ObjectHeap::FreeBlock
  361. //----------------------------------------------------------------------------------------
  362. #pragma segment HeapSeg
  363.  
  364. void ObjectHeap::FreeBlock(PrivChunkyBlock* blk)
  365. {
  366.     blk->SetBusy(fBlockSizes[blk->GetSizeIndex()], false);
  367.     fFreeLists[blk->GetSizeIndex()].Push(blk);
  368.  
  369.     // Check to see if all blocks in this block's PrivChunk are free, if so then free the
  370.     // PrivChunk.
  371.  
  372.     PrivChunk *chk = blk->GetChunk(fBlockSizes[blk->GetSizeIndex()]);
  373.     if (!chk->IsBusy())
  374.     {
  375.         // Remove blocks in this PrivChunk from the free list. This is the achililles hill
  376.         // of the Heap. Its difficult to remove blocks from a singly linked list
  377.         // rapidly.
  378.  
  379.         void *begAddr = chk;
  380.         void *endAddr = (void *) ((ODBytePtr) chk + 
  381.                                     sizeof(ODPrivChunkHeader) +
  382.                                     fBlocksPerChunk * fBlockSizes[chk->GetSizeIndex()]);
  383.         fFreeLists[chk->GetSizeIndex()].RemoveRange(begAddr, endAddr);
  384.         BestFitHeap::DoFree(chk);
  385.     }
  386. }
  387.  
  388. //----------------------------------------------------------------------------------------
  389. // ObjectHeap::SizeIndex
  390. //----------------------------------------------------------------------------------------
  391. #pragma segment HeapSeg
  392.  
  393. unsigned int ObjectHeap::SizeIndex(ODBlockSize size)
  394. {
  395.     for (unsigned int i = 0; i < fNumberOfBlockSizes; i++)
  396.         if (size + PrivChunkyBlock::kBusyOverhead <= fBlockSizes[i])
  397.             return i;
  398.  
  399.     // Uh oh! An internal error:
  400.     
  401.     PLATFORM_DEBUGGER_STRING("Internal error in ObjectHeap::SizeIndex");
  402.     
  403.     return 0xFFFFFFFF;    // the former way of handling the internal error
  404.                         // we leave it in to defeat an xlC warning
  405. }
  406.  
  407. #if ODDebug
  408. //----------------------------------------------------------------------------------------
  409. // ObjectHeap::CompilerCheck
  410. //----------------------------------------------------------------------------------------
  411. #pragma segment HeapSeg
  412.  
  413. void ObjectHeap::CompilerCheck()
  414. {
  415.     BestFitHeap::CompilerCheck();
  416.     
  417.     PrivChunkyBlock block;
  418.     
  419.     block.SetSizeIndex(0xF);
  420.     block.SetBlockIndex(0xE);
  421.     block.SetBlockType(PrivChunkyBlock::kBlockTypeId);
  422.     block.SetMagicNumber(0xC);
  423.     
  424.     PLATFORM_ASSERT(block.GetSizeIndex() == 0xF);
  425.     PLATFORM_ASSERT(block.GetBlockIndex() == 0xE);
  426.     PLATFORM_ASSERT(block.GetBlockType() == PrivChunkyBlock::kBlockTypeId);
  427.     PLATFORM_ASSERT(block.GetBlockType() != PrivBestFitBlock::kBlockTypeId);
  428.     PLATFORM_ASSERT(block.GetMagicNumber() == 0xC);
  429.     
  430.     block.SetSizeIndex(0x7);
  431.     block.SetBlockIndex(0x6);
  432.     block.SetBlockType(PrivBestFitBlock::kBlockTypeId);
  433.     block.SetMagicNumber(0x4);
  434.     
  435.     PLATFORM_ASSERT(block.GetSizeIndex() == 0x7);
  436.     PLATFORM_ASSERT(block.GetBlockIndex() == 0x6);
  437.     PLATFORM_ASSERT(block.GetBlockType() == PrivBestFitBlock::kBlockTypeId);
  438.     PLATFORM_ASSERT(block.GetBlockType() != PrivChunkyBlock::kBlockTypeId);
  439.     PLATFORM_ASSERT(block.GetMagicNumber() == 0x4);
  440. }
  441. #endif
  442.  
  443. //========================================================================================
  444. // PrivChunkyBlockStack
  445. //========================================================================================
  446.  
  447. //----------------------------------------------------------------------------------------
  448. // PrivChunkyBlockStack::PrivChunkyBlockStack
  449. //----------------------------------------------------------------------------------------
  450. #pragma segment HeapSeg
  451.  
  452. PrivChunkyBlockStack::PrivChunkyBlockStack()
  453. {
  454.     fHead.SetNext(NULL);
  455. }
  456.  
  457. //----------------------------------------------------------------------------------------
  458. // PrivChunkyBlockStack::PrivChunkyBlockStack
  459. //----------------------------------------------------------------------------------------
  460. #pragma segment HeapSeg
  461.  
  462. PrivChunkyBlockStack::PrivChunkyBlockStack(const PrivChunkyBlockStack& blk) :
  463.     fHead(blk.fHead)
  464. {
  465. }
  466.  
  467. //----------------------------------------------------------------------------------------
  468. // PrivChunkyBlockStack::operator=
  469. //----------------------------------------------------------------------------------------
  470. #pragma segment HeapSeg
  471.  
  472. PrivChunkyBlockStack& PrivChunkyBlockStack::operator=(const PrivChunkyBlockStack& blk)
  473. {
  474.     fHead = blk.fHead;
  475.     return *this;
  476. }
  477.  
  478. //----------------------------------------------------------------------------------------
  479. // PrivChunkyBlockStack::Pop
  480. //----------------------------------------------------------------------------------------
  481. #pragma segment HeapSeg
  482.  
  483. PrivChunkyBlock* PrivChunkyBlockStack::Pop()
  484. {
  485.     PrivChunkyBlock * blk = fHead.GetNext();
  486.     fHead.SetNext(blk->GetNext());
  487.     return blk;
  488. }
  489.  
  490. //----------------------------------------------------------------------------------------
  491. // PrivChunkyBlockStack::Push
  492. //----------------------------------------------------------------------------------------
  493. #pragma segment HeapSeg
  494.  
  495. void PrivChunkyBlockStack::Push(PrivChunkyBlock* blk)
  496. {
  497.     blk->SetNext(fHead.GetNext());
  498.     fHead.SetNext(blk);
  499. }
  500.  
  501. //----------------------------------------------------------------------------------------
  502. // PrivChunkyBlockStack::RemoveRange
  503. //----------------------------------------------------------------------------------------
  504. #pragma segment HeapSeg
  505.  
  506. void PrivChunkyBlockStack::RemoveRange(void *begAddr, void *endAddr)
  507. {
  508.     PrivChunkyBlock *prevBlk = &fHead;
  509.     PrivChunkyBlock *curBlk = fHead.GetNext();
  510.  
  511.     while (curBlk != NULL)
  512.     {
  513.         void *curAddr = curBlk;
  514.  
  515.         if (curAddr >= begAddr && curAddr <= endAddr)
  516.         {
  517.             prevBlk->SetNext(curBlk->GetNext());
  518.             curBlk = curBlk->GetNext();
  519.         }
  520.         else
  521.         {
  522.             prevBlk = curBlk;
  523.             curBlk = curBlk->GetNext();
  524.         }
  525.     }
  526. }
  527.  
  528. //----------------------------------------------------------------------------------------
  529. // PrivChunkyBlockStack::Top
  530. //----------------------------------------------------------------------------------------
  531. #pragma segment HeapSeg
  532.  
  533. PrivChunkyBlock* PrivChunkyBlockStack::Top()
  534. {
  535.     return fHead.GetNext();
  536. }
  537.  
  538. //----------------------------------------------------------------------------------------
  539. // PrivChunkyBlockStack::~PrivChunkyBlockStack
  540. //----------------------------------------------------------------------------------------
  541. #pragma segment HeapSeg
  542.  
  543. PrivChunkyBlockStack::~PrivChunkyBlockStack()
  544. {
  545. }
  546.  
  547. //----------------------------------------------------------------------------------------
  548. // PrivChunkyBlockStack::operator new
  549. //----------------------------------------------------------------------------------------
  550. #pragma segment HeapSeg
  551.  
  552. void *PrivChunkyBlockStack::operator new(size_t)
  553. {
  554.     PLATFORM_DEBUGGER_STRING("\pPrivChunkyBlockStack should not be dynamically allocated");
  555.     return NULL;
  556. }
  557.  
  558. //----------------------------------------------------------------------------------------
  559. // PrivChunkyBlockStack::operator delete
  560. //----------------------------------------------------------------------------------------
  561. #pragma segment HeapSeg
  562.  
  563. void PrivChunkyBlockStack::operator delete(void *)
  564. {
  565.     PLATFORM_DEBUGGER_STRING("\pPrivChunkyBlockStack should not be dynamically allocated");
  566. }
  567.  
  568.