home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / crt / src / sbheap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-17  |  49.5 KB  |  1,426 lines
  1. /***
  2. *sbheap.c -  Small-block heap code
  3. *
  4. *       Copyright (c) 1996-1998, Microsoft Corporation. All rights reserved.
  5. *
  6. *Purpose:
  7. *       Core code for small-block heap.
  8. *
  9. *******************************************************************************/
  10.  
  11. #include <stddef.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include <winheap.h>
  15. #include <windows.h>
  16.  
  17. size_t       __sbh_threshold = MAX_ALLOC_DATA_SIZE;
  18.  
  19. PHEADER      __sbh_pHeaderList;        //  pointer to list start
  20. PHEADER      __sbh_pHeaderScan;        //  pointer to list rover
  21. int          __sbh_sizeHeaderList;     //  allocated size of list
  22. int          __sbh_cntHeaderList;      //  count of entries defined
  23.  
  24. PHEADER      __sbh_pHeaderDefer;
  25. int          __sbh_indGroupDefer;
  26.  
  27. /*
  28.  * Prototypes for user functions.
  29.  */
  30. size_t __cdecl _get_sbh_threshold(void);
  31. int    __cdecl _set_sbh_threshold(size_t);
  32.  
  33. void DumpEntry(char *, int *);
  34.  
  35. /***
  36. *size_t _get_sbh_threshold() - return small-block threshold
  37. *
  38. *Purpose:
  39. *       Return the current value of __sbh_threshold
  40. *
  41. *Entry:
  42. *       None.
  43. *
  44. *Exit:
  45. *       See above.
  46. *
  47. *Exceptions:
  48. *
  49. *******************************************************************************/
  50.  
  51. size_t __cdecl _get_sbh_threshold (void)
  52. {
  53.     return __sbh_threshold;
  54. }
  55.  
  56. /***
  57. *int _set_sbh_threshold(threshold) - set small-block heap threshold
  58. *
  59. *Purpose:
  60. *       Set the upper limit for the size of an allocation which will be
  61. *       supported from the small-block heap.
  62. *
  63. *Entry:
  64. *       size_t threshold - proposed new value for __sbh_theshold
  65. *
  66. *Exit:
  67. *       Returns 1 if successful. Returns 0 if threshold was too big.
  68. *
  69. *Exceptions:
  70. *
  71. *******************************************************************************/
  72.  
  73. int __cdecl _set_sbh_threshold (size_t threshold)
  74. {
  75.     //  test against maximum value - if too large, return error
  76.     if (threshold > MAX_ALLOC_DATA_SIZE)
  77.         return 0;
  78.  
  79.     //  set the threshold value
  80.     __sbh_threshold = threshold;
  81.     return 1;
  82. }
  83.  
  84. /***
  85. *int __sbh_heap_init() - set small-block heap threshold
  86. *
  87. *Purpose:
  88. *       Allocate space for initial header list and init variables.
  89. *
  90. *Entry:
  91. *       None.
  92. *
  93. *Exit:
  94. *       Returns 1 if successful. Returns 0 if initialization failed.
  95. *
  96. *Exceptions:
  97. *
  98. *******************************************************************************/
  99.  
  100. int __cdecl __sbh_heap_init (void)
  101. {
  102.     if (!(__sbh_pHeaderList = HeapAlloc(_crtheap, 0, 16 * sizeof(HEADER))))
  103.         return FALSE;
  104.  
  105.     __sbh_pHeaderScan = __sbh_pHeaderList;
  106.     __sbh_pHeaderDefer = NULL;
  107.     __sbh_cntHeaderList = 0;
  108.     __sbh_sizeHeaderList = 16;
  109.  
  110.     return TRUE;
  111. }
  112.  
  113. /***
  114. *PHEADER *__sbh_find_block(pvAlloc) - find block in small-block heap
  115. *
  116. *Purpose:
  117. *       Determine if the specified allocation block lies in the small-block
  118. *       heap and, if so, return the header to be used for the block.
  119. *
  120. *Entry:
  121. *       void * pvBlock - pointer to block to be freed
  122. *
  123. *Exit:
  124. *       If successful, a pointer to the header to use is returned.
  125. *       If unsuccessful, NULL is returned.
  126. *
  127. *Exceptions:
  128. *
  129. *******************************************************************************/
  130.  
  131. PHEADER __cdecl __sbh_find_block (void * pvAlloc)
  132. {
  133.     PHEADER         pHeaderLast = __sbh_pHeaderList + __sbh_cntHeaderList;
  134.     PHEADER         pHeader;
  135.     unsigned int    offRegion;
  136.  
  137.     //  scan through the header list to determine if entry
  138.     //  is in the region heap data reserved address space
  139.     pHeader = __sbh_pHeaderList;
  140.     while (pHeader < pHeaderLast)
  141.     {
  142.         offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
  143.         if (offRegion < BYTES_PER_REGION)
  144.             return pHeader;
  145.         pHeader++;
  146.     }
  147.     return NULL;
  148. }
  149.  
  150. #ifdef _DEBUG
  151.  
  152. /***
  153. *int __sbh_verify_block(pHeader, pvAlloc) - verify pointer in sbh
  154. *
  155. *Purpose:
  156. *       Test if pointer is valid within the heap header given.
  157. *
  158. *Entry:
  159. *       pHeader - pointer to HEADER where entry should be
  160. *       pvAlloc - pointer to test validity of
  161. *
  162. *Exit:
  163. *       Returns 1 if pointer is valid, else 0.
  164. *
  165. *Exceptions:
  166. *
  167. *******************************************************************************/
  168.  
  169. int __cdecl __sbh_verify_block (PHEADER pHeader, void * pvAlloc)
  170. {
  171.     unsigned int    indGroup;
  172.     unsigned int    offRegion;
  173.  
  174.     //  calculate region offset to determine the group index
  175.     offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
  176.     indGroup = offRegion / BYTES_PER_GROUP;
  177.  
  178.     //  return TRUE if:
  179.     //      group is committed (bit in vector cleared) AND
  180.     //      pointer is at paragraph boundary AND
  181.     //      pointer is not at start of page
  182.     return (!(pHeader->bitvCommit & (0x80000000UL >> indGroup))) &&
  183.            (!(offRegion & 0xf)) &&
  184.            (offRegion & (BYTES_PER_PAGE - 1));
  185. }
  186.  
  187. #endif  /* _DEBUG */
  188.  
  189. /***
  190. *void __sbh_free_block(preg, ppage, pmap) - free block
  191. *
  192. *Purpose:
  193. *       Free the specified block from the small-block heap.
  194. *
  195. *Entry:
  196. *       pHeader - pointer to HEADER of region to free memory
  197. *       pvAlloc - pointer to memory to free
  198. *
  199. *Exit:
  200. *       No return value.
  201. *
  202. *Exceptions:
  203. *
  204. *******************************************************************************/
  205.  
  206. void __cdecl __sbh_free_block (PHEADER pHeader, void * pvAlloc)
  207. {
  208.     PREGION         pRegion;
  209.     PGROUP          pGroup;
  210.     PENTRY          pHead;
  211.     PENTRY          pEntry;
  212.     PENTRY          pNext;
  213.     PENTRY          pPrev;
  214.     void *          pHeapDecommit;
  215.     int             sizeEntry;
  216.     int             sizeNext;
  217.     int             sizePrev;
  218.     unsigned int    indGroup;
  219.     unsigned int    indEntry;
  220.     unsigned int    indNext;
  221.     unsigned int    indPrev;
  222.     unsigned int    offRegion;
  223.  
  224.     //  region is determined by the header
  225.     pRegion = pHeader->pRegion;
  226.  
  227.     //  use the region offset to determine the group index
  228.     offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
  229.     indGroup = offRegion / BYTES_PER_GROUP;
  230.     pGroup = &pRegion->grpHeadList[indGroup];
  231.  
  232.     //  get size of entry - decrement value since entry is allocated
  233.     pEntry = (PENTRY)((char *)pvAlloc - sizeof(int));
  234.     sizeEntry = pEntry->sizeFront - 1;
  235.  
  236.     //  point to next entry to get its size
  237.     pNext = (PENTRY)((char *)pEntry + sizeEntry);
  238.     sizeNext = pNext->sizeFront;
  239.  
  240.     //  get size from end of previous entry
  241.     sizePrev = ((PENTRYEND)((char *)pEntry - sizeof(int)))->sizeBack;
  242.  
  243.     //  test if next entry is free by an even size value
  244.  
  245.     if ((sizeNext & 1) == 0)
  246.     {
  247.         //  free next entry - disconnect and add its size to sizeEntry
  248.  
  249.         //  determine index of next entry
  250.         indNext = (sizeNext >> 4) - 1;
  251.         if (indNext > 63)
  252.             indNext = 63;
  253.  
  254.         //  test entry is sole member of bucket (next == prev),
  255.         if (pNext->pEntryNext == pNext->pEntryPrev)
  256.         {
  257.             //  clear bit in group vector, decrement region count
  258.             //  if region count is now zero, clear bit in header
  259.             //  entry vector
  260.             if (indNext < 32)
  261.             {
  262.                 pRegion->bitvGroupHi[indGroup] &= ~(0x80000000L >> indNext);
  263.                 if (--pRegion->cntRegionSize[indNext] == 0)
  264.                     pHeader->bitvEntryHi &= ~(0x80000000L >> indNext);
  265.             }
  266.             else
  267.             {
  268.                 pRegion->bitvGroupLo[indGroup] &=
  269.                                             ~(0x80000000L >> (indNext - 32));
  270.                 if (--pRegion->cntRegionSize[indNext] == 0)
  271.                     pHeader->bitvEntryLo &= ~(0x80000000L >> (indNext - 32));
  272.             }
  273.         }
  274.  
  275.         //  unlink entry from list
  276.         pNext->pEntryPrev->pEntryNext = pNext->pEntryNext;
  277.         pNext->pEntryNext->pEntryPrev = pNext->pEntryPrev;
  278.  
  279.         //  add next entry size to freed entry size
  280.         sizeEntry += sizeNext;
  281.     }
  282.  
  283.     //  compute index of free entry (plus next entry if it was free)
  284.     indEntry = (sizeEntry >> 4) - 1;
  285.     if (indEntry > 63)
  286.         indEntry = 63;
  287.  
  288.     //  test if previous entry is free by an even size value
  289.     if ((sizePrev & 1) == 0)
  290.     {
  291.         //  free previous entry - add size to sizeEntry and
  292.         //  disconnect if index changes
  293.  
  294.         //  get pointer to previous entry
  295.         pPrev = (PENTRY)((char *)pEntry - sizePrev);
  296.  
  297.         //  determine index of previous entry
  298.         indPrev = (sizePrev >> 4) - 1;
  299.         if (indPrev > 63)
  300.             indPrev = 63;
  301.  
  302.         //  add previous entry size to sizeEntry and determine
  303.         //  its new index
  304.         sizeEntry += sizePrev;
  305.         indEntry = (sizeEntry >> 4) - 1;
  306.         if (indEntry > 63)
  307.             indEntry = 63;
  308.  
  309.         //  if index changed due to coalesing, reconnect to new size
  310.         if (indPrev != indEntry)
  311.         {
  312.             //  disconnect entry from indPrev
  313.             //  test entry is sole member of bucket (next == prev),
  314.             if (pPrev->pEntryNext == pPrev->pEntryPrev)
  315.             {
  316.                 //  clear bit in group vector, decrement region count
  317.                 //  if region count is now zero, clear bit in header
  318.                 //  entry vector
  319.                 if (indPrev < 32)
  320.                 {
  321.                     pRegion->bitvGroupHi[indGroup] &=
  322.                                                 ~(0x80000000L >> indPrev);
  323.                     if (--pRegion->cntRegionSize[indPrev] == 0)
  324.                         pHeader->bitvEntryHi &= ~(0x80000000L >> indPrev);
  325.                 }
  326.                 else
  327.                 {
  328.                     pRegion->bitvGroupLo[indGroup] &=
  329.                                             ~(0x80000000L >> (indPrev - 32));
  330.                     if (--pRegion->cntRegionSize[indPrev] == 0)
  331.                         pHeader->bitvEntryLo &=
  332.                                             ~(0x80000000L >> (indPrev - 32));
  333.                 }
  334.             }
  335.  
  336.             //  unlink entry from list
  337.             pPrev->pEntryPrev->pEntryNext = pPrev->pEntryNext;
  338.             pPrev->pEntryNext->pEntryPrev = pPrev->pEntryPrev;
  339.         }
  340.         //  set pointer to connect it instead of the free entry
  341.         pEntry = pPrev;
  342.     }
  343.  
  344.     //  test if previous entry was free with an index change or allocated
  345.     if (!((sizePrev & 1) == 0 && indPrev == indEntry))
  346.     {
  347.         //  connect pEntry entry to indEntry
  348.         //  add entry to the start of the bucket list
  349.         pHead = (PENTRY)((char *)&pGroup->listHead[indEntry] - sizeof(int));
  350.         pEntry->pEntryNext = pHead->pEntryNext;
  351.         pEntry->pEntryPrev = pHead;
  352.         pHead->pEntryNext = pEntry;
  353.         pEntry->pEntryNext->pEntryPrev = pEntry;
  354.  
  355.         //  test entry is sole member of bucket (next == prev),
  356.         if (pEntry->pEntryNext == pEntry->pEntryPrev)
  357.         {
  358.             //  if region count was zero, set bit in region vector
  359.             //  set bit in header entry vector, increment region count
  360.             if (indEntry < 32)
  361.             {
  362.                 if (pRegion->cntRegionSize[indEntry]++ == 0)
  363.                     pHeader->bitvEntryHi |= 0x80000000L >> indEntry;
  364.                 pRegion->bitvGroupHi[indGroup] |= 0x80000000L >> indEntry;
  365.             }
  366.             else
  367.             {
  368.                 if (pRegion->cntRegionSize[indEntry]++ == 0)
  369.                     pHeader->bitvEntryLo |= 0x80000000L >> (indEntry - 32);
  370.                 pRegion->bitvGroupLo[indGroup] |= 0x80000000L >>
  371.                                                            (indEntry - 32);
  372.             }
  373.         }
  374.     }
  375.  
  376.     //  adjust the entry size front and back
  377.     pEntry->sizeFront = sizeEntry;
  378.     ((PENTRYEND)((char *)pEntry + sizeEntry -
  379.                         sizeof(ENTRYEND)))->sizeBack = sizeEntry;
  380.  
  381.         //  one less allocation in group - test if empty
  382.     if (--pGroup->cntEntries == 0)
  383.     {
  384.         //  if a group has been deferred, free that group
  385.         if (__sbh_pHeaderDefer)
  386.         {
  387.             //  if now zero, decommit the group data heap
  388.             pHeapDecommit = (void *)((char *)__sbh_pHeaderDefer->pHeapData +
  389.                                     __sbh_indGroupDefer * BYTES_PER_GROUP);
  390.             VirtualFree(pHeapDecommit, BYTES_PER_GROUP, MEM_DECOMMIT);
  391.  
  392.             //  set bit in commit vector
  393.             __sbh_pHeaderDefer->bitvCommit |=
  394.                                           0x80000000 >> __sbh_indGroupDefer;
  395.  
  396.             //  clear entry vector for the group and header vector bit
  397.             //  if needed
  398.             __sbh_pHeaderDefer->pRegion->bitvGroupLo[__sbh_indGroupDefer] = 0;
  399.             if (--__sbh_pHeaderDefer->pRegion->cntRegionSize[63] == 0)
  400.                 __sbh_pHeaderDefer->bitvEntryLo &= ~0x00000001L;
  401.  
  402.             //  if commit vector is the initial value,
  403.             //  remove the region if it is not the last
  404.             if (__sbh_pHeaderDefer->bitvCommit == BITV_COMMIT_INIT)
  405.             {
  406.                 //  release the address space for heap data
  407.                 VirtualFree(__sbh_pHeaderDefer->pHeapData, 0, MEM_RELEASE);
  408.  
  409.                 //  free the region memory area
  410.                 HeapFree(_crtheap, 0, __sbh_pHeaderDefer->pRegion);
  411.  
  412.                 //  remove entry from header list by copying over
  413.                 memmove((void *)__sbh_pHeaderDefer,
  414.                             (void *)(__sbh_pHeaderDefer + 1),
  415.                             (int)(__sbh_pHeaderList + __sbh_cntHeaderList) -
  416.                             (int)(__sbh_pHeaderDefer + 1));
  417.                 __sbh_cntHeaderList--;
  418.  
  419.                 //  if pHeader was after the one just removed, adjust it
  420.                 if (pHeader > __sbh_pHeaderDefer)
  421.                     pHeader--;
  422.  
  423.                 //  initialize scan pointer to start of list
  424.                 __sbh_pHeaderScan = __sbh_pHeaderList;
  425.             }
  426.         }
  427.  
  428.         //  defer the group just freed
  429.         __sbh_pHeaderDefer = pHeader;
  430.         __sbh_indGroupDefer = indGroup;
  431.     }
  432. }
  433.  
  434. /***
  435. *void * __sbh_alloc_block(intSize) - allocate a block
  436. *
  437. *Purpose:
  438. *       Allocate a block from the small-block heap, the specified number of
  439. *       bytes in size.
  440. *
  441. *Entry:
  442. *       intSize - size of the allocation request in bytes
  443. *
  444. *Exit:
  445. *       Returns a pointer to the newly allocated block, if successful.
  446. *       Returns NULL, if failure.
  447. *
  448. *Exceptions:
  449. *
  450. *******************************************************************************/
  451.  
  452. void * __cdecl __sbh_alloc_block (int intSize)
  453. {
  454.     PHEADER     pHeaderLast = __sbh_pHeaderList + __sbh_cntHeaderList;
  455.     PHEADER     pHeader;
  456.     PREGION     pRegion;
  457.     PGROUP      pGroup;
  458.     PENTRY      pEntry;
  459.     PENTRY      pHead;
  460.     BITVEC      bitvEntryLo;
  461.     BITVEC      bitvEntryHi;
  462.     BITVEC      bitvTest;
  463.     int         sizeEntry;
  464.     int         indEntry;
  465.     int         indGroupUse;
  466.     int         sizeNewFree;
  467.     int         indNewFree;
  468.  
  469.     //  add 8 bytes entry overhead and round up to next para size
  470.     sizeEntry = (intSize + 2 * sizeof(int) + (BYTES_PER_PARA - 1))
  471.                                           & ~(BYTES_PER_PARA - 1);
  472.  
  473.     //  determine index and mask from entry size
  474.     //  Hi MSB: bit 0      size: 1 paragraph
  475.     //          bit 1            2 paragraphs
  476.     //          ...              ...
  477.     //          bit 30           31 paragraphs
  478.     //          bit 31           32 paragraphs
  479.     //  Lo MSB: bit 0      size: 33 paragraph
  480.     //          bit 1            34 paragraphs
  481.     //          ...              ...
  482.     //          bit 30           63 paragraphs
  483.     //          bit 31           64+ paragraphs
  484.     indEntry = (sizeEntry >> 4) - 1;
  485.     if (indEntry < 32)
  486.     {
  487.         bitvEntryHi = 0xffffffffUL >> indEntry;
  488.         bitvEntryLo = 0xffffffffUL;
  489.     }
  490.     else
  491.     {
  492.         bitvEntryHi = 0;
  493.         bitvEntryLo = 0xffffffffUL >> (indEntry - 32);
  494.     }
  495.  
  496.     //  scan header list from rover to end for region with a free
  497.     //  entry with an adequate size
  498.     pHeader = __sbh_pHeaderScan;
  499.     while (pHeader < pHeaderLast)
  500.     {
  501.         if ((bitvEntryHi & pHeader->bitvEntryHi) |
  502.             (bitvEntryLo & pHeader->bitvEntryLo))
  503.             break;
  504.         pHeader++;
  505.     }
  506.  
  507.     //  if no entry, scan from list start up to the rover
  508.     if (pHeader == pHeaderLast)
  509.     {
  510.         pHeader = __sbh_pHeaderList;
  511.         while (pHeader < __sbh_pHeaderScan)
  512.         {
  513.             if ((bitvEntryHi & pHeader->bitvEntryHi) |
  514.                 (bitvEntryLo & pHeader->bitvEntryLo))
  515.                 break;
  516.             pHeader++;
  517.         }
  518.  
  519.         //  no free entry exists, scan list from rover to end
  520.         //  for available groups to commit
  521.         if (pHeader == __sbh_pHeaderScan)
  522.         {
  523.             while (pHeader < pHeaderLast)
  524.             {
  525.                 if (pHeader->bitvCommit)
  526.                     break;
  527.                 pHeader++;
  528.             }
  529.  
  530.             //  if no available groups, scan from start to rover
  531.             if (pHeader == pHeaderLast)
  532.             {
  533.                 pHeader = __sbh_pHeaderList;
  534.                 while (pHeader < __sbh_pHeaderScan)
  535.                 {
  536.                     if (pHeader->bitvCommit)
  537.                         break;
  538.                     pHeader++;
  539.                 }
  540.  
  541.                 //  if no available groups, create a new region
  542.                 if (pHeader == __sbh_pHeaderScan)
  543.                     if (!(pHeader = __sbh_alloc_new_region()))
  544.                         return NULL;
  545.             }
  546.  
  547.             //  commit a new group in region associated with pHeader
  548.             if ((pHeader->pRegion->indGroupUse =
  549.                                     __sbh_alloc_new_group(pHeader)) == -1)
  550.                 return NULL;
  551.         }
  552.     }
  553.     __sbh_pHeaderScan = pHeader;
  554.  
  555.     pRegion = pHeader->pRegion;
  556.     indGroupUse = pRegion->indGroupUse;
  557.  
  558.     //  determine the group to allocate from
  559.     if (indGroupUse == -1 ||
  560.                     !((bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]) |
  561.                       (bitvEntryLo & pRegion->bitvGroupLo[indGroupUse])))
  562.     {
  563.         //  preferred group could not allocate entry, so
  564.         //  scan through all defined vectors
  565.         indGroupUse = 0;
  566.         while (!((bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]) |
  567.                  (bitvEntryLo & pRegion->bitvGroupLo[indGroupUse])))
  568.             indGroupUse++;
  569.     }
  570.     pGroup = &pRegion->grpHeadList[indGroupUse];
  571.  
  572.     //  determine bucket index
  573.     indEntry = 0;
  574.  
  575.     //  get high entry intersection - if zero, use the lower one
  576.     if (!(bitvTest = bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]))
  577.     {
  578.         indEntry = 32;
  579.         bitvTest = bitvEntryLo & pRegion->bitvGroupLo[indGroupUse];
  580.     }
  581.        while ((int)bitvTest >= 0)
  582.     {
  583.            bitvTest <<= 1;
  584.            indEntry++;
  585.     }
  586.     pEntry = pGroup->listHead[indEntry].pEntryNext;
  587.  
  588.     //  compute size and bucket index of new free entry
  589.  
  590.     //  for zero-sized entry, the index is -1
  591.     sizeNewFree = pEntry->sizeFront - sizeEntry;
  592.     indNewFree = (sizeNewFree >> 4) - 1;
  593.     if (indNewFree > 63)
  594.         indNewFree = 63;
  595.  
  596.     //  only modify entry pointers if bucket index changed
  597.     if (indNewFree != indEntry)
  598.     {
  599.         //  test entry is sole member of bucket (next == prev),
  600.         if (pEntry->pEntryNext == pEntry->pEntryPrev)
  601.         {
  602.             //  clear bit in group vector, decrement region count
  603.             //  if region count is now zero, clear bit in region vector
  604.             if (indEntry < 32)
  605.             {
  606.                 pRegion->bitvGroupHi[indGroupUse] &=
  607.                                             ~(0x80000000L >> indEntry);
  608.                 if (--pRegion->cntRegionSize[indEntry] == 0)
  609.                     pHeader->bitvEntryHi &= ~(0x80000000L >> indEntry);
  610.             }
  611.             else
  612.             {
  613.                 pRegion->bitvGroupLo[indGroupUse] &=
  614.                                             ~(0x80000000L >> (indEntry - 32));
  615.                 if (--pRegion->cntRegionSize[indEntry] == 0)
  616.                     pHeader->bitvEntryLo &= ~(0x80000000L >> (indEntry - 32));
  617.             }
  618.         }
  619.  
  620.         //  unlink entry from list
  621.         pEntry->pEntryPrev->pEntryNext = pEntry->pEntryNext;
  622.         pEntry->pEntryNext->pEntryPrev = pEntry->pEntryPrev;
  623.  
  624.         //  if free entry size is still nonzero, reconnect it
  625.         if (sizeNewFree != 0)
  626.         {
  627.             //  add entry to the start of the bucket list
  628.             pHead = (PENTRY)((char *)&pGroup->listHead[indNewFree] -
  629.                                                            sizeof(int));
  630.             pEntry->pEntryNext = pHead->pEntryNext;
  631.             pEntry->pEntryPrev = pHead;
  632.             pHead->pEntryNext = pEntry;
  633.             pEntry->pEntryNext->pEntryPrev = pEntry;
  634.  
  635.             //  test entry is sole member of bucket (next == prev),
  636.             if (pEntry->pEntryNext == pEntry->pEntryPrev)
  637.             {
  638.                 //  if region count was zero, set bit in region vector
  639.                 //  set bit in group vector, increment region count
  640.                 if (indNewFree < 32)
  641.                 {
  642.                     if (pRegion->cntRegionSize[indNewFree]++ == 0)
  643.                         pHeader->bitvEntryHi |= 0x80000000L >> indNewFree;
  644.                     pRegion->bitvGroupHi[indGroupUse] |=
  645.                                                 0x80000000L >> indNewFree;
  646.                 }
  647.                 else
  648.                 {
  649.                     if (pRegion->cntRegionSize[indNewFree]++ == 0)
  650.                         pHeader->bitvEntryLo |=
  651.                                         0x80000000L >> (indNewFree - 32);
  652.                     pRegion->bitvGroupLo[indGroupUse] |=
  653.                                         0x80000000L >> (indNewFree - 32);
  654.                 }
  655.             }
  656.         }
  657.     }
  658.  
  659.     //  change size of free entry (front and back)
  660.     if (sizeNewFree != 0)
  661.     {
  662.         pEntry->sizeFront = sizeNewFree;
  663.         ((PENTRYEND)((char *)pEntry + sizeNewFree -
  664.                     sizeof(ENTRYEND)))->sizeBack = sizeNewFree;
  665.     }
  666.  
  667.     //  mark the allocated entry
  668.     pEntry = (PENTRY)((char *)pEntry + sizeNewFree);
  669.     pEntry->sizeFront = sizeEntry + 1;
  670.     ((PENTRYEND)((char *)pEntry + sizeEntry -
  671.                     sizeof(ENTRYEND)))->sizeBack = sizeEntry + 1;
  672.  
  673.     //  one more allocation in group - test if group was empty
  674.     if (pGroup->cntEntries++ == 0)
  675.     {
  676.         //  if allocating into deferred group, cancel deferral
  677.         if (pHeader == __sbh_pHeaderDefer &&
  678.                                   indGroupUse == __sbh_indGroupDefer)
  679.             __sbh_pHeaderDefer = NULL;
  680.     }
  681.  
  682.     pRegion->indGroupUse = indGroupUse;
  683.  
  684.     return (void *)((char *)pEntry + sizeof(int));
  685. }
  686.  
  687. /***
  688. *PHEADER __sbh_alloc_new_region()
  689. *
  690. *Purpose:
  691. *       Add a new HEADER structure in the header list.  Allocate a new
  692. *       REGION structure and initialize.  Reserve memory for future
  693. *       group commitments.
  694. *
  695. *Entry:
  696. *       None.
  697. *
  698. *Exit:
  699. *       Returns a pointer to newly created HEADER entry, if successful.
  700. *       Returns NULL, if failure.
  701. *
  702. *Exceptions:
  703. *
  704. *******************************************************************************/
  705.  
  706. PHEADER __cdecl __sbh_alloc_new_region (void)
  707. {
  708.     PHEADER     pHeader;
  709.  
  710.     //  create a new entry in the header list
  711.  
  712.     //  if list if full, realloc to extend its size
  713.     if (__sbh_cntHeaderList == __sbh_sizeHeaderList)
  714.     {
  715.         if (!(pHeader = (PHEADER)HeapReAlloc(_crtheap, 0, __sbh_pHeaderList,
  716.                             (__sbh_sizeHeaderList + 16) * sizeof(HEADER))))
  717.             return NULL;
  718.  
  719.         //  update pointer and counter values
  720.         __sbh_pHeaderList = pHeader;
  721.         __sbh_sizeHeaderList += 16;
  722.     }
  723.  
  724.     //  point to new header in list
  725.     pHeader = __sbh_pHeaderList + __sbh_cntHeaderList;
  726.  
  727.     //  allocate a new region associated with the new header
  728.     if (!(pHeader->pRegion = (PREGION)HeapAlloc(_crtheap, HEAP_ZERO_MEMORY,
  729.                                     sizeof(REGION))))
  730.         return NULL;
  731.  
  732.     //  reserve address space for heap data in the region
  733.     if ((pHeader->pHeapData = VirtualAlloc(0, BYTES_PER_REGION,
  734.                                      MEM_RESERVE, PAGE_READWRITE)) == NULL)
  735.     {
  736.         HeapFree(_crtheap, 0, pHeader->pRegion);
  737.         return NULL;
  738.     }
  739.  
  740.     //  initialize alloc and commit group vectors
  741.     pHeader->bitvEntryHi = 0;
  742.     pHeader->bitvEntryLo = 0;
  743.     pHeader->bitvCommit = BITV_COMMIT_INIT;
  744.  
  745.     //  complete entry by incrementing list count
  746.     __sbh_cntHeaderList++;
  747.  
  748.     //  initialize index of group to try first (none defined yet)
  749.     pHeader->pRegion->indGroupUse = -1;
  750.  
  751.     return pHeader;
  752. }
  753.  
  754. /***
  755. *int __sbh_alloc_new_group(pHeader)
  756. *
  757. *Purpose:
  758. *       Initializes a GROUP structure within HEADER pointed by pHeader.
  759. *       Commits and initializes the memory in the memory reserved by the
  760. *       REGION.
  761. *
  762. *Entry:
  763. *       pHeader - pointer to HEADER from which the GROUP is defined.
  764. *
  765. *Exit:
  766. *       Returns an index to newly created GROUP, if successful.
  767. *       Returns -1, if failure.
  768. *
  769. *Exceptions:
  770. *
  771. *******************************************************************************/
  772.  
  773. int __cdecl __sbh_alloc_new_group (PHEADER pHeader)
  774. {
  775.     PREGION     pRegion = pHeader->pRegion;
  776.     PGROUP      pGroup;
  777.     PENTRY      pEntry;
  778.     PENTRY      pHead;
  779.     PENTRYEND   pEntryEnd;
  780.     BITVEC      bitvCommit;
  781.     int         indCommit;
  782.     int         index;
  783.     void *      pHeapPage;
  784.     void *      pHeapStartPage;
  785.     void *      pHeapEndPage;
  786.  
  787.     //  determine next group to use by first bit set in commit vector
  788.     bitvCommit = pHeader->bitvCommit;
  789.     indCommit = 0;
  790.     while ((int)bitvCommit >= 0)
  791.     {
  792.         bitvCommit <<= 1;
  793.         indCommit++;
  794.     }
  795.  
  796.     //  allocate and initialize a new group
  797.     pGroup = &pRegion->grpHeadList[indCommit];
  798.  
  799.     for (index = 0; index < 63; index++)
  800.     {
  801.         pEntry = (PENTRY)((char *)&pGroup->listHead[index] - sizeof(int));
  802.         pEntry->pEntryNext = pEntry->pEntryPrev = pEntry;
  803.     }
  804.  
  805.     //  commit heap memory for new group
  806.     pHeapStartPage = (void *)((char *)pHeader->pHeapData +
  807.                                        indCommit * BYTES_PER_GROUP);
  808.     if ((VirtualAlloc(pHeapStartPage, BYTES_PER_GROUP, MEM_COMMIT,
  809.                                       PAGE_READWRITE)) == NULL)
  810.         return -1;
  811.  
  812.     //  initialize heap data with empty page entries
  813.     pHeapEndPage = (void *)((char *)pHeapStartPage +
  814.                         (PAGES_PER_GROUP - 1) * BYTES_PER_PAGE);
  815.  
  816.     for (pHeapPage = pHeapStartPage; pHeapPage <= pHeapEndPage;
  817.             pHeapPage = (void *)((char *)pHeapPage + BYTES_PER_PAGE))
  818.     {
  819.         //  set sentinel values at start and end of the page
  820.         *(int *)((char *)pHeapPage + 8) = -1;
  821.         *(int *)((char *)pHeapPage + BYTES_PER_PAGE - 4) = -1;
  822.  
  823.         //  set size and pointer info for one empty entry
  824.         pEntry = (PENTRY)((char *)pHeapPage + ENTRY_OFFSET);
  825.         pEntry->sizeFront = MAX_FREE_ENTRY_SIZE;
  826.         pEntry->pEntryNext = (PENTRY)((char *)pEntry +
  827.                                             BYTES_PER_PAGE);
  828.         pEntry->pEntryPrev = (PENTRY)((char *)pEntry -
  829.                                             BYTES_PER_PAGE);
  830.         pEntryEnd = (PENTRYEND)((char *)pEntry + MAX_FREE_ENTRY_SIZE -
  831.                                             sizeof(ENTRYEND));
  832.         pEntryEnd->sizeBack = MAX_FREE_ENTRY_SIZE;
  833.     }
  834.  
  835.     //  initialize group entry pointer for maximum size
  836.     //  and set terminate list entries
  837.     pHead = (PENTRY)((char *)&pGroup->listHead[63] - sizeof(int));
  838.     pEntry = pHead->pEntryNext =
  839.                         (PENTRY)((char *)pHeapStartPage + ENTRY_OFFSET);
  840.     pEntry->pEntryPrev = pHead;
  841.  
  842.     pEntry = pHead->pEntryPrev =
  843.                         (PENTRY)((char *)pHeapEndPage + ENTRY_OFFSET);
  844.     pEntry->pEntryNext = pHead;
  845.  
  846.     pRegion->bitvGroupHi[indCommit] = 0x00000000L;
  847.     pRegion->bitvGroupLo[indCommit] = 0x00000001L;
  848.     if (pRegion->cntRegionSize[63]++ == 0)
  849.         pHeader->bitvEntryLo |= 0x00000001L;
  850.  
  851.     //  clear bit in commit vector
  852.     pHeader->bitvCommit &= ~(0x80000000L >> indCommit);
  853.  
  854.     return indCommit;
  855. }
  856.  
  857. /***
  858. *int __sbh_resize_block(pHeader, pvAlloc, intNew) - resize block
  859. *
  860. *Purpose:
  861. *       Resize the specified block from the small-block heap.
  862. *       The allocation block is not moved.
  863. *
  864. *Entry:
  865. *       pHeader - pointer to HEADER containing block
  866. *       pvAlloc - pointer to block to resize
  867. *       intNew  - new size of block in bytes
  868. *
  869. *Exit:
  870. *       Returns 1, if successful. Otherwise, 0 is returned.
  871. *
  872. *Exceptions:
  873. *
  874. *******************************************************************************/
  875.  
  876. int __cdecl __sbh_resize_block (PHEADER pHeader, void * pvAlloc, int intNew)
  877. {
  878.     PREGION         pRegion;
  879.     PGROUP          pGroup;
  880.     PENTRY          pHead;
  881.     PENTRY          pEntry;
  882.     PENTRY          pNext;
  883.     int             sizeEntry;
  884.     int             sizeNext;
  885.     int             sizeNew;
  886.     unsigned int    indGroup;
  887.     unsigned int    indEntry;
  888.     unsigned int    indNext;
  889.     unsigned int    offRegion;
  890.  
  891.     //  add 8 bytes entry overhead and round up to next para size
  892.     sizeNew = (intNew + 2 * sizeof(int) + (BYTES_PER_PARA - 1))
  893.                                        & ~(BYTES_PER_PARA - 1);
  894.  
  895.     //  region is determined by the header
  896.     pRegion = pHeader->pRegion;
  897.  
  898.     //  use the region offset to determine the group index
  899.     offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
  900.     indGroup = offRegion / BYTES_PER_GROUP;
  901.     pGroup = &pRegion->grpHeadList[indGroup];
  902.  
  903.     //  get size of entry - decrement value since entry is allocated
  904.     pEntry = (PENTRY)((char *)pvAlloc - sizeof(int));
  905.     sizeEntry = pEntry->sizeFront - 1;
  906.  
  907.     //  point to next entry to get its size
  908.     pNext = (PENTRY)((char *)pEntry + sizeEntry);
  909.     sizeNext = pNext->sizeFront;
  910.  
  911.     //  test if new size is larger than the current one
  912.     if (sizeNew > sizeEntry)
  913.     {
  914.         //  if next entry not free, or not large enough, fail
  915.         if ((sizeNext & 1) || (sizeNew > sizeEntry + sizeNext))
  916.             return FALSE;
  917.  
  918.         //  disconnect next entry
  919.  
  920.         //  determine index of next entry
  921.         indNext = (sizeNext >> 4) - 1;
  922.         if (indNext > 63)
  923.             indNext = 63;
  924.  
  925.         //  test entry is sole member of bucket (next == prev),
  926.         if (pNext->pEntryNext == pNext->pEntryPrev)
  927.         {
  928.             //  clear bit in group vector, decrement region count
  929.             //  if region count is now zero, clear bit in header
  930.             //  entry vector
  931.             if (indNext < 32)
  932.             {
  933.                 pRegion->bitvGroupHi[indGroup] &= ~(0x80000000L >> indNext);
  934.                 if (--pRegion->cntRegionSize[indNext] == 0)
  935.                     pHeader->bitvEntryHi &= ~(0x80000000L >> indNext);
  936.             }
  937.             else
  938.             {
  939.                 pRegion->bitvGroupLo[indGroup] &=
  940.                                             ~(0x80000000L >> (indNext - 32));
  941.                 if (--pRegion->cntRegionSize[indNext] == 0)
  942.                     pHeader->bitvEntryLo &= ~(0x80000000L >> (indNext - 32));
  943.             }
  944.         }
  945.  
  946.         //  unlink entry from list
  947.         pNext->pEntryPrev->pEntryNext = pNext->pEntryNext;
  948.         pNext->pEntryNext->pEntryPrev = pNext->pEntryPrev;
  949.  
  950.         //  compute new size of the next entry, test if nonzero
  951.         if ((sizeNext = sizeEntry + sizeNext - sizeNew) > 0)
  952.         {
  953.             //  compute start of next entry and connect it
  954.             pNext = (PENTRY)((char *)pEntry + sizeNew);
  955.  
  956.             //  determine index of next entry
  957.             indNext = (sizeNext >> 4) - 1;
  958.             if (indNext > 63)
  959.                 indNext = 63;
  960.  
  961.             //  add next entry to the start of the bucket list
  962.             pHead = (PENTRY)((char *)&pGroup->listHead[indNext] -
  963.                                                            sizeof(int));
  964.             pNext->pEntryNext = pHead->pEntryNext;
  965.             pNext->pEntryPrev = pHead;
  966.             pHead->pEntryNext = pNext;
  967.             pNext->pEntryNext->pEntryPrev = pNext;
  968.  
  969.             //  test entry is sole member of bucket (next == prev),
  970.             if (pNext->pEntryNext == pNext->pEntryPrev)
  971.             {
  972.                 //  if region count was zero, set bit in region vector
  973.                 //  set bit in header entry vector, increment region count
  974.                 if (indNext < 32)
  975.                 {
  976.                     if (pRegion->cntRegionSize[indNext]++ == 0)
  977.                         pHeader->bitvEntryHi |= 0x80000000L >> indNext;
  978.                     pRegion->bitvGroupHi[indGroup] |= 0x80000000L >> indNext;
  979.                 }
  980.                 else
  981.                 {
  982.                     if (pRegion->cntRegionSize[indNext]++ == 0)
  983.                         pHeader->bitvEntryLo |= 0x80000000L >> (indNext - 32);
  984.                     pRegion->bitvGroupLo[indGroup] |=
  985.                                                 0x80000000L >> (indNext - 32);
  986.                 }
  987.             }
  988.  
  989.             //  adjust size fields of next entry
  990.             pNext->sizeFront = sizeNext;
  991.             ((PENTRYEND)((char *)pNext + sizeNext -
  992.                                 sizeof(ENTRYEND)))->sizeBack = sizeNext;
  993.         }
  994.  
  995.         //  adjust pEntry to its new size (plus one since allocated)
  996.         pEntry->sizeFront = sizeNew + 1;
  997.         ((PENTRYEND)((char *)pEntry + sizeNew -
  998.                             sizeof(ENTRYEND)))->sizeBack = sizeNew + 1;
  999.     }
  1000.  
  1001.     //  not larger, test if smaller
  1002.     else if (sizeNew < sizeEntry)
  1003.     {
  1004.         //  adjust pEntry to new smaller size
  1005.         pEntry->sizeFront = sizeNew + 1;
  1006.         ((PENTRYEND)((char *)pEntry + sizeNew -
  1007.                             sizeof(ENTRYEND)))->sizeBack = sizeNew + 1;
  1008.  
  1009.         //  set pEntry and sizeEntry to leftover space
  1010.         pEntry = (PENTRY)((char *)pEntry + sizeNew);
  1011.         sizeEntry -= sizeNew;
  1012.  
  1013.         //  determine index of entry
  1014.         indEntry = (sizeEntry >> 4) - 1;
  1015.         if (indEntry > 63)
  1016.             indEntry = 63;
  1017.  
  1018.         //  test if next entry is free
  1019.         if ((sizeNext & 1) == 0)
  1020.         {
  1021.             //  if so, disconnect it
  1022.  
  1023.             //  determine index of next entry
  1024.             indNext = (sizeNext >> 4) - 1;
  1025.             if (indNext > 63)
  1026.                 indNext = 63;
  1027.  
  1028.             //  test entry is sole member of bucket (next == prev),
  1029.             if (pNext->pEntryNext == pNext->pEntryPrev)
  1030.             {
  1031.                 //  clear bit in group vector, decrement region count
  1032.                 //  if region count is now zero, clear bit in header
  1033.                 //  entry vector
  1034.                 if (indNext < 32)
  1035.                 {
  1036.                     pRegion->bitvGroupHi[indGroup] &=
  1037.                                                 ~(0x80000000L >> indNext);
  1038.                     if (--pRegion->cntRegionSize[indNext] == 0)
  1039.                         pHeader->bitvEntryHi &= ~(0x80000000L >> indNext);
  1040.                 }
  1041.                 else
  1042.                 {
  1043.                     pRegion->bitvGroupLo[indGroup] &=
  1044.                                             ~(0x80000000L >> (indNext - 32));
  1045.                     if (--pRegion->cntRegionSize[indNext] == 0)
  1046.                         pHeader->bitvEntryLo &=
  1047.                                             ~(0x80000000L >> (indNext - 32));
  1048.                 }
  1049.             }
  1050.  
  1051.             //  unlink entry from list
  1052.             pNext->pEntryPrev->pEntryNext = pNext->pEntryNext;
  1053.             pNext->pEntryNext->pEntryPrev = pNext->pEntryPrev;
  1054.  
  1055.             //  add next entry size to present
  1056.             sizeEntry += sizeNext;
  1057.             indEntry = (sizeEntry >> 4) - 1;
  1058.             if (indEntry > 63)
  1059.                 indEntry = 63;
  1060.         }
  1061.  
  1062.         //  connect leftover space with any free next entry
  1063.  
  1064.         //  add next entry to the start of the bucket list
  1065.         pHead = (PENTRY)((char *)&pGroup->listHead[indEntry] - sizeof(int));
  1066.         pEntry->pEntryNext = pHead->pEntryNext;
  1067.         pEntry->pEntryPrev = pHead;
  1068.         pHead->pEntryNext = pEntry;
  1069.         pEntry->pEntryNext->pEntryPrev = pEntry;
  1070.  
  1071.         //  test entry is sole member of bucket (next == prev),
  1072.         if (pEntry->pEntryNext == pEntry->pEntryPrev)
  1073.         {
  1074.             //  if region count was zero, set bit in region vector
  1075.             //  set bit in header entry vector, increment region count
  1076.             if (indEntry < 32)
  1077.             {
  1078.                 if (pRegion->cntRegionSize[indEntry]++ == 0)
  1079.                     pHeader->bitvEntryHi |= 0x80000000L >> indEntry;
  1080.                 pRegion->bitvGroupHi[indGroup] |= 0x80000000L >> indEntry;
  1081.             }
  1082.             else
  1083.             {
  1084.                 if (pRegion->cntRegionSize[indEntry]++ == 0)
  1085.                     pHeader->bitvEntryLo |= 0x80000000L >> (indEntry - 32);
  1086.                 pRegion->bitvGroupLo[indGroup] |= 0x80000000L >>
  1087.                                                            (indEntry - 32);
  1088.             }
  1089.         }
  1090.  
  1091.         //  adjust size fields of entry
  1092.         pEntry->sizeFront = sizeEntry;
  1093.         ((PENTRYEND)((char *)pEntry + sizeEntry -
  1094.                             sizeof(ENTRYEND)))->sizeBack = sizeEntry;
  1095.     }
  1096.  
  1097.     return TRUE;
  1098. }
  1099.  
  1100. /***
  1101. *int __sbh_heapmin() - minimize heap
  1102. *
  1103. *Purpose:
  1104. *       Minimize the heap by freeing any deferred group.
  1105. *
  1106. *Entry:
  1107. *       __sbh_pHeaderDefer  - pointer to HEADER of deferred group
  1108. *       __sbh_indGroupDefer - index of GROUP to defer
  1109. *
  1110. *Exit:
  1111. *       None.
  1112. *
  1113. *Exceptions:
  1114. *
  1115. *******************************************************************************/
  1116.  
  1117. void __cdecl __sbh_heapmin (void)
  1118. {
  1119.     void *      pHeapDecommit;
  1120.  
  1121.     //  if a group has been deferred, free that group
  1122.     if (__sbh_pHeaderDefer)
  1123.     {
  1124.         //  if now zero, decommit the group data heap
  1125.         pHeapDecommit = (void *)((char *)__sbh_pHeaderDefer->pHeapData +
  1126.                                     __sbh_indGroupDefer * BYTES_PER_GROUP);
  1127.         VirtualFree(pHeapDecommit, BYTES_PER_GROUP, MEM_DECOMMIT);
  1128.  
  1129.         //  set bit in commit vector
  1130.         __sbh_pHeaderDefer->bitvCommit |= 0x80000000 >> __sbh_indGroupDefer;
  1131.  
  1132.         //  clear entry vector for the group and header vector bit
  1133.         //  if needed
  1134.         __sbh_pHeaderDefer->pRegion->bitvGroupLo[__sbh_indGroupDefer] = 0;
  1135.         if (--__sbh_pHeaderDefer->pRegion->cntRegionSize[63] == 0)
  1136.             __sbh_pHeaderDefer->bitvEntryLo &= ~0x00000001L;
  1137.  
  1138.         //  if commit vector is the initial value,
  1139.         //  remove the region if it is not the last
  1140.         if (__sbh_pHeaderDefer->bitvCommit == BITV_COMMIT_INIT &&
  1141.                                                 __sbh_cntHeaderList > 1)
  1142.         {
  1143.             //  free the region memory area
  1144.             HeapFree(_crtheap, 0, __sbh_pHeaderDefer->pRegion);
  1145.  
  1146.             //  remove entry from header list by copying over
  1147.             memmove((void *)__sbh_pHeaderDefer, (void *)(__sbh_pHeaderDefer + 1),
  1148.                             (int)(__sbh_pHeaderList + __sbh_cntHeaderList) -
  1149.                             (int)(__sbh_pHeaderDefer + 1));
  1150.             __sbh_cntHeaderList--;
  1151.         }
  1152.  
  1153.         //  clear deferred condition
  1154.         __sbh_pHeaderDefer = NULL;
  1155.     }
  1156. }
  1157.  
  1158. /***
  1159. *int __sbh_heap_check() - check small-block heap
  1160. *
  1161. *Purpose:
  1162. *       Perform validity checks on the small-block heap.
  1163. *
  1164. *Entry:
  1165. *       There are no arguments.
  1166. *
  1167. *Exit:
  1168. *       Returns 0 if the small-block is okay.
  1169. *       Returns < 0 if the small-block heap has an error. The exact value
  1170. *       identifies where, in the source code below, the error was detected.
  1171. *
  1172. *Exceptions:
  1173. *
  1174. *******************************************************************************/
  1175.  
  1176. int __cdecl __sbh_heap_check (void)
  1177. {
  1178.     PHEADER     pHeader;
  1179.     PREGION     pRegion;
  1180.     PGROUP      pGroup;
  1181.     PENTRY      pEntry;
  1182.     PENTRY      pNext;
  1183.     PENTRY      pEntryLast;
  1184.     PENTRY      pEntryHead;
  1185.     PENTRY      pEntryPage;
  1186.     PENTRY      pEntryPageLast;
  1187.     int         indHeader;
  1188.     int         indGroup;
  1189.     int         indPage;
  1190.     int         indEntry;
  1191.     int         indHead;
  1192.     int         sizeEntry;
  1193.     int         sizeTrue;
  1194.     int         cntAllocated;
  1195.     int         cntFree[64];
  1196.     int         cntEntries;
  1197.     void *      pHeapGroup;
  1198.     void *      pHeapPage;
  1199.     void *      pPageStart;
  1200.     BITVEC      bitvCommit;
  1201.     BITVEC      bitvGroupHi;
  1202.     BITVEC      bitvGroupLo;
  1203.     BITVEC      bitvEntryHi;
  1204.     BITVEC      bitvEntryLo;
  1205.  
  1206.     //  check validity of header list
  1207.     if (IsBadWritePtr(__sbh_pHeaderList,
  1208.                       __sbh_cntHeaderList * sizeof(HEADER)))
  1209.         return -1;
  1210.  
  1211.     //  scan for all headers in list
  1212.     pHeader = __sbh_pHeaderList;
  1213.     for (indHeader = 0; indHeader < __sbh_cntHeaderList; indHeader++)
  1214.     {
  1215.         //  define region and test if valid
  1216.         pRegion = pHeader->pRegion;
  1217.         if (IsBadWritePtr(pRegion, sizeof(REGION)))
  1218.             return -2;
  1219.  
  1220.         //  scan for all groups in region
  1221.         pHeapGroup = pHeader->pHeapData;
  1222.         pGroup = &pRegion->grpHeadList[0];
  1223.         bitvCommit = pHeader->bitvCommit;
  1224.         bitvEntryHi = 0;
  1225.         bitvEntryLo = 0;
  1226.         for (indGroup = 0; indGroup < GROUPS_PER_REGION; indGroup++)
  1227.         {
  1228.             //  initialize entry vector and entry counts for group
  1229.             bitvGroupHi = 0;
  1230.             bitvGroupLo = 0;
  1231.             cntAllocated = 0;
  1232.             for (indEntry = 0; indEntry < 64; indEntry++)
  1233.                 cntFree[indEntry] = 0;
  1234.  
  1235.             //  test if group is committed
  1236.             if ((int)bitvCommit >= 0)
  1237.             {
  1238.                 //  committed, ensure addresses are accessable
  1239.                 if (IsBadWritePtr(pHeapGroup, BYTES_PER_GROUP))
  1240.                     return -4;
  1241.  
  1242.                 //  for each page in group, check validity of entries
  1243.                 pHeapPage = pHeapGroup;
  1244.                 for (indPage = 0; indPage < PAGES_PER_GROUP; indPage++)
  1245.                 {
  1246.                     //  define pointers to first and past last entry
  1247.                     pEntry = (PENTRY)((char *)pHeapPage + ENTRY_OFFSET);
  1248.                     pEntryLast = (PENTRY)((char *)pEntry
  1249.                                                  + MAX_FREE_ENTRY_SIZE);
  1250.  
  1251.                     //  check front and back page sentinel values
  1252.                     if (*(int *)((char *)pEntry - sizeof(int)) != -1 ||
  1253.                                  *(int *)pEntryLast != -1)
  1254.                         return -5;
  1255.  
  1256.                     //  loop through each entry in page
  1257.                     do
  1258.                     {
  1259.                         //  get entry size and test if allocated
  1260.                         sizeEntry = sizeTrue = pEntry->sizeFront;
  1261.                         if (sizeEntry & 1)
  1262.                         {
  1263.                             //  allocated entry - set true size
  1264.                             sizeTrue--;
  1265.  
  1266.                             //  test against maximum allocated entry size
  1267.                             if (sizeTrue > MAX_ALLOC_ENTRY_SIZE)
  1268.                                 return -6;
  1269.  
  1270.                             //  increment allocated count for group
  1271.                             cntAllocated++;
  1272.                         }
  1273.                         else
  1274.                         {
  1275.                             //  free entry - determine index and increment
  1276.                             //  count for list head checking
  1277.                             indEntry = (sizeTrue >> 4) - 1;
  1278.                             if (indEntry > 63)
  1279.                                 indEntry = 63;
  1280.                             cntFree[indEntry]++;
  1281.                         }
  1282.  
  1283.                         //  check size validity
  1284.                         if (sizeTrue < 0x10 || sizeTrue & 0xf
  1285.                                         || sizeTrue > MAX_FREE_ENTRY_SIZE)
  1286.                             return -7;
  1287.  
  1288.                         //  check if back entry size same as front
  1289.                         if (((PENTRYEND)((char *)pEntry + sizeTrue
  1290.                                     - sizeof(int)))->sizeBack != sizeEntry)
  1291.                             return -8;
  1292.  
  1293.                         //  move to next entry in page
  1294.                         pEntry = (PENTRY)((char *)pEntry + sizeTrue);
  1295.                     }
  1296.                     while (pEntry < pEntryLast);
  1297.  
  1298.                     //  test if last entry did not overrun page end
  1299.                     if (pEntry != pEntryLast)
  1300.                         return -8;
  1301.  
  1302.                     //  point to next page in data heap
  1303.                     pHeapPage = (void *)((char *)pHeapPage + BYTES_PER_PAGE);
  1304.                 }
  1305.  
  1306.                 //  check if allocated entry count is correct
  1307.                 if (pGroup->cntEntries != cntAllocated)
  1308.                     return -9;
  1309.  
  1310.                 //  check validity of linked-lists of free entries
  1311.                 pEntryHead = (PENTRY)((char *)&pGroup->listHead[0] -
  1312.                                                            sizeof(int));
  1313.                 for (indHead = 0; indHead < 64; indHead++)
  1314.                 {
  1315.                     //  scan through list until head is reached or expected
  1316.                     //  number of entries traversed
  1317.                     cntEntries = 0;
  1318.                     pEntry = pEntryHead;
  1319.                     while ((pNext = pEntry->pEntryNext) != pEntryHead &&
  1320.                                         cntEntries != cntFree[indHead])
  1321.                     {
  1322.                         //  test if next pointer is in group data area
  1323.                         if ((void *)pNext < pHeapGroup || (void *)pNext >=
  1324.                             (void *)((char *)pHeapGroup + BYTES_PER_GROUP))
  1325.                             return -10;
  1326.  
  1327.                         //  determine page address of next entry
  1328.                         pPageStart = (void *)((int)pNext &
  1329.                                                     ~(BYTES_PER_PAGE - 1));
  1330.  
  1331.                         //  point to first entry and past last in the page
  1332.                         pEntryPage = (PENTRY)((char *)pPageStart +
  1333.                                                         ENTRY_OFFSET);
  1334.                         pEntryPageLast = (PENTRY)((char *)pEntryPage +
  1335.                                                         MAX_FREE_ENTRY_SIZE);
  1336.  
  1337.                         //  do scan from start of page
  1338.                         //  no error checking since it was already scanned
  1339.                         while (pEntryPage != pEntryPageLast)
  1340.                         {
  1341.                             //  if entry matches, exit loop
  1342.                             if (pEntryPage == pNext)
  1343.                                 break;
  1344.  
  1345.                             //  point to next entry
  1346.                             pEntryPage = (PENTRY)((char *)pEntryPage +
  1347.                                             (pEntryPage->sizeFront & ~1));
  1348.                         }
  1349.  
  1350.                         //  if page end reached, pNext was not valid
  1351.                         if (pEntryPage == pEntryPageLast)
  1352.                             return -11;
  1353.  
  1354.                         //  entry valid, but check if entry index matches
  1355.                         //  the header
  1356.                         indEntry = (pNext->sizeFront >> 4) - 1;
  1357.                         if (indEntry > 63)
  1358.                             indEntry = 63;
  1359.                         if (indEntry != indHead)
  1360.                             return -12;
  1361.  
  1362.                         //  check if previous pointer in pNext points
  1363.                         //  back to pEntry
  1364.                         if (pNext->pEntryPrev != pEntry)
  1365.                             return -13;
  1366.  
  1367.                         //  update scan pointer and counter
  1368.                         pEntry = pNext;
  1369.                         cntEntries++;
  1370.                     }
  1371.  
  1372.                     //  if nonzero number of entries, set bit in group
  1373.                     //  and region vectors
  1374.                     if (cntEntries)
  1375.                     {
  1376.                         if (indHead < 32)
  1377.                         {
  1378.                             bitvGroupHi |= 0x80000000L >> indHead;
  1379.                             bitvEntryHi |= 0x80000000L >> indHead;
  1380.                         }
  1381.                         else
  1382.                         {
  1383.                             bitvGroupLo |= 0x80000000L >> (indHead - 32);
  1384.                             bitvEntryLo |= 0x80000000L >> (indHead - 32);
  1385.                         }
  1386.                     }
  1387.  
  1388.                     //  check if list is exactly the expected size
  1389.                     if (pEntry->pEntryNext != pEntryHead ||
  1390.                                         cntEntries != cntFree[indHead])
  1391.                         return -14;
  1392.  
  1393.                     //  check if previous pointer in header points to
  1394.                     //  last entry processed
  1395.                     if (pEntryHead->pEntryPrev != pEntry)
  1396.                         return -15;
  1397.  
  1398.                     //  point to next linked-list header - note size
  1399.                     pEntryHead = (PENTRY)((char *)pEntryHead +
  1400.                                                       sizeof(LISTHEAD));
  1401.                 }
  1402.             }
  1403.  
  1404.             //  test if group vector is valid
  1405.             if (bitvGroupHi != pRegion->bitvGroupHi[indGroup] ||
  1406.                 bitvGroupLo != pRegion->bitvGroupLo[indGroup])
  1407.                 return -16;
  1408.  
  1409.             //  adjust for next group in region
  1410.             pHeapGroup = (void *)((char *)pHeapGroup + BYTES_PER_GROUP);
  1411.             pGroup++;
  1412.             bitvCommit <<= 1;
  1413.         }
  1414.  
  1415.         //  test if group vector is valid
  1416.         if (bitvEntryHi != pHeader->bitvEntryHi ||
  1417.             bitvEntryLo != pHeader->bitvEntryLo)
  1418.             return -17;
  1419.  
  1420.         //  adjust for next header in list
  1421.         pHeader++;
  1422.     }
  1423.     return 0;
  1424. }
  1425.  
  1426.