home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / crt / src / heapadd.c < prev    next >
C/C++ Source or Header  |  1998-06-17  |  12KB  |  426 lines
  1. /***
  2. *heapadd.c - Add a block of memory to the heap
  3. *
  4. *       Copyright (c) 1989-1997, Microsoft Corporation. All rights reserved.
  5. *
  6. *Purpose:
  7. *       Add a block of memory to the heap.
  8. *
  9. *******************************************************************************/
  10.  
  11.  
  12. #ifdef WINHEAP
  13.  
  14.  
  15. #include <cruntime.h>
  16. #include <errno.h>
  17. #include <malloc.h>
  18. #include <winheap.h>
  19.  
  20. int __cdecl _heapadd (
  21.         void * block,
  22.         size_t size
  23.         )
  24. {
  25.         errno = ENOSYS;
  26.         return(-1);
  27. }
  28.  
  29.  
  30. #else  /* WINHEAP */
  31.  
  32.  
  33. #include <cruntime.h>
  34. #include <heap.h>
  35. #include <malloc.h>
  36. #include <mtdll.h>
  37. #include <stdlib.h>
  38.  
  39. static void __cdecl _before(_PBLKDESC, size_t, _PBLKDESC, _PBLKDESC **);
  40.  
  41. /***
  42. *int _heapadd(block, size) - Add a block of memory to the heap
  43. *
  44. *Purpose:
  45. *       Add a block of user memory the heap.
  46. *
  47. *       NOTE:  The reason for the level of indirection between _heapadd
  48. *       and _heap_addblock is (1) to validate the input, and (2) for
  49. *       mthread locking/unlocking purposes.
  50. *
  51. *       NOTE: _heapadd() DOES NOT enter the block of memory into the region
  52. *       table! This is the cleanest way to avoid nasty bugs such as attempting
  53. *       to grow, shrink or free static memory (e.g., a block that started out
  54. *       being a static array). If the memory block does in fact belong in the
  55. *       region table, it is the caller's responsibility to do it (internal
  56. *       routines only, user programs should NEVER do this).
  57. *
  58. *Entry:
  59. *       void * block = block of memory
  60. *       size_t size = size of memory block
  61. *
  62. *Exit:
  63. *        0 = success
  64. *       -1 = failure
  65. *
  66. *Exceptions:
  67. *
  68. *******************************************************************************/
  69.  
  70. int __cdecl _heapadd (
  71.         void * block,
  72.         size_t size
  73.         )
  74. {
  75.         int retval;
  76.  
  77.         /*
  78.          * Validate user's input. Note that _GRANULARITY must be a power
  79.          * of 2 for the tests below to be valid!
  80.          */
  81.  
  82.         if ( (size == 0) ||
  83.              ((unsigned)block & (_GRANULARITY - 1)) ||
  84.              (size & (_GRANULARITY - 1))
  85.            )
  86.                 return(-1);
  87.  
  88.         /*
  89.          * Add the block to the heap.
  90.          */
  91.  
  92.         _mlock(_HEAP_LOCK);
  93.         retval = _heap_addblock(block, size);
  94.         _munlock(_HEAP_LOCK);
  95.  
  96.         return(retval);
  97.  
  98. }
  99.  
  100.  
  101. /***
  102. *int _heap_addblock(block, size) - Add a block of memory to the heap
  103. *
  104. *Purpose:
  105. *       Add a block of memory to the heap.
  106. *
  107. *       Notes:
  108. *       (1) Must handle case where new memory is already in heap
  109. *       (i.e., could be the address of a previous 'dummy' entry).
  110. *
  111. *Entry:
  112. *       void * block = address of memory block
  113. *       size_t size = size of memory block
  114. *
  115. *Exit:
  116. *       0 = success
  117. *       -1 = failure
  118. *
  119. *Exceptions:
  120. *
  121. *******************************************************************************/
  122.  
  123. int __cdecl _heap_addblock (
  124.         void * block,
  125.         size_t size
  126.         )
  127. {
  128.         _PBLKDESC pdesc;
  129.         REG1 _PBLKDESC pnewdesc;
  130.         _PBLKDESC pdescs[4] = { NULL, NULL, NULL, NULL };
  131.         _PBLKDESC *ppdesc = pdescs;
  132.         size_t lastsize;
  133.         int find;
  134.  
  135.         /*
  136.          * Make sure we enough empty descriptors to do the job! Do it here
  137.          * and now because recovering from an out-of-descriptors condition
  138.          * is too dicey later on.
  139.          */
  140.         if ( ((pdescs[0] = __getempty()) == NULL) ||
  141.              ((pdescs[1] = __getempty()) == NULL) ||
  142.              ((pdescs[2] = __getempty()) == NULL) )
  143.         {
  144.                 goto error;
  145.         }
  146.  
  147.         /*
  148.          * Find where the address fits into the heap.
  149.          */
  150.  
  151.         find = _heap_findaddr(block, &pdesc);
  152.  
  153.  
  154.         /*
  155.          * Fill in the new heap descriptor.
  156.          * (1) If the new address is an exact fit, use the dummy
  157.          *     descriptor that already exists for it.
  158.          * (2) If the address is NOT in the heap, allocate a new one.
  159.          */
  160.  
  161.         if ( find == _HEAPFIND_EXACT ) {
  162.  
  163.                 if ( !(_IS_DUMMY(pdesc)) )
  164.                         goto error;
  165.  
  166.                 pnewdesc = pdesc;
  167.         }
  168.         else {
  169.                 pnewdesc = *(ppdesc++);
  170.         }
  171.  
  172.         pnewdesc->pblock = block;       /* pointer to block */
  173.         _SET_FREE(pnewdesc);            /* set me free (why don't ya, babe) */
  174.         *(_PBLKDESC*)block = pnewdesc;  /* init back pointer */
  175.  
  176.  
  177.         /*
  178.          * Put the block in the heap
  179.          * find = result of _heap_findaddr() call
  180.          * pnewdesc = points to desc to be inserted
  181.          * pdesc = filled in by _heap_findaddr() call as appropriate
  182.          */
  183.  
  184.         switch (find) {
  185.  
  186.  
  187.                 case(_HEAPFIND_EMPTY):
  188.  
  189.                         /*
  190.                          * No memory in heap yet
  191.                          */
  192.  
  193.                         _heap_desc.sentinel.pblock = (char *) block + size;
  194.                         _before(pnewdesc, size, &_heap_desc.sentinel,
  195.                                 &ppdesc);
  196.  
  197.                         _heap_desc.pfirstdesc = _heap_desc.proverdesc =
  198.                                 pnewdesc;
  199.  
  200.                         break;
  201.  
  202.  
  203.                 case(_HEAPFIND_BEFORE):
  204.  
  205.                         /*
  206.                          * New block is before the heap
  207.                          */
  208.  
  209.                         _before(pnewdesc, size, _heap_desc.pfirstdesc,
  210.                                 &ppdesc);
  211.                         _heap_desc.pfirstdesc = pnewdesc;
  212.                         break;
  213.  
  214.  
  215.                 case(_HEAPFIND_AFTER):
  216.  
  217.                         /*
  218.                          * New block is after the heap
  219.                          *
  220.                          * Find the current last block in the heap
  221.                          */
  222.  
  223.                         if ( _heap_findaddr((void *)((char *)
  224.                             (_heap_desc.sentinel.pblock) - 1), &pdesc) !=
  225.                             _HEAPFIND_WITHIN )
  226.                                 _heap_abort();
  227.  
  228.                         lastsize = _MEMSIZE(pdesc);
  229.  
  230.                         /*
  231.                          * Start insertion by placing new block immediately
  232.                          * in front of the sentinel
  233.                          */
  234.  
  235.                         _heap_desc.sentinel.pblock = (char *) block + size;
  236.                         pnewdesc->pnextdesc = &_heap_desc.sentinel;
  237.  
  238.                         /*
  239.                          * Finish insertion by placing new block after the
  240.                          * old last block (with a possible intervening dummy
  241.                          * block being created)
  242.                          */
  243.  
  244.                         _before(pdesc, lastsize, pnewdesc,
  245.                                 &ppdesc);
  246.                         break;
  247.  
  248.  
  249.                 case(_HEAPFIND_EXACT):
  250.  
  251.                         /*
  252.                          * Block is already in the heap (and we've checked
  253.                          * that it was a "dummy" before this call).
  254.                          *
  255.                          * [NOTES: (1) pnewdesc and pdesc are the same,
  256.                          * (2) pnewdesc is already linked to the previous
  257.                          * heap entry, (3) pdesc->pnextdesc is still valid!
  258.                          * (4) Also, if pdesc->pnextdesc is the sentinel,
  259.                          * then simply update the sentinel size (calling
  260.                          * before will cause an error if the previous last
  261.                          * block was bigger than the current one!).
  262.                          * (see code at top of this routine).]
  263.                          */
  264.  
  265.                         if (pdesc->pnextdesc == &_heap_desc.sentinel)
  266.  
  267.                                 _heap_desc.sentinel.pblock =
  268.                                         (char *) _ADDRESS(pdesc) + size;
  269.  
  270.                         else
  271.                                 _before(pnewdesc, size, pdesc->pnextdesc,
  272.                                         &ppdesc);
  273.  
  274.                         break;
  275.  
  276.                 default:
  277.                         /*
  278.                          * New block is within heap
  279.                          */
  280.  
  281.                         if (!(_IS_DUMMY(pdesc)))
  282.                                 goto error;
  283.  
  284.                         /*
  285.                          * If the last block in the heap is a dummy region
  286.                          * and a new region is allocated which lies within
  287.                          * that region, we need to update sentinel.pblock.
  288.                          */
  289.                         if (pdesc->pnextdesc == &_heap_desc.sentinel)
  290.                         {
  291.                             void * newend = (char *) _ADDRESS(pnewdesc) + size;
  292.  
  293.                             if (_heap_desc.sentinel.pblock < newend)
  294.                                 _heap_desc.sentinel.pblock = newend;
  295.                         }
  296.  
  297.                         _before(pnewdesc, size, pdesc->pnextdesc,
  298.                                 &ppdesc);
  299.                         _before(pdesc, _MEMSIZE(pdesc), pnewdesc,
  300.                                 &ppdesc);
  301.                         break;
  302.  
  303.  
  304.                 }
  305.  
  306.         /*
  307.          * Update rover, if appropriate
  308.          */
  309.  
  310.          if ( (block < _ADDRESS(_heap_desc.proverdesc)) &&
  311.          (_BLKSIZE(pnewdesc) >= _heap_resetsize) )
  312.                 _heap_desc.proverdesc = pnewdesc;
  313.  
  314.         /*
  315.          * Good return
  316.          */
  317.  
  318.         /* good:   unreferenced label to be removed */
  319.                 return(0);
  320.  
  321.         /*
  322.          * Error return
  323.          */
  324.  
  325.         error:
  326.                 while ( *ppdesc != NULL ) {
  327.                         _PUTEMPTY(*ppdesc);
  328.                         ppdesc++;
  329.                 }
  330.  
  331.                 return(-1);
  332.  
  333. }
  334.  
  335.  
  336. /***
  337. *static void _before(pdesc1, size, pdesc2, pppdesc) - Insert a block before
  338. *       a supplied descriptor
  339. *
  340. *Purpose:
  341. *       This routine inserts a new descriptor before another descriptor.
  342. *
  343. *       Notes:
  344. *       (1) A dummy descriptor will be inserted into the heap as
  345. *           necessary.
  346. *       (2) This routine only updates FORWARD links. Call this
  347. *           routine twice to update links in both directions.
  348. *
  349. *Entry:
  350. *       _PBLKDESC pdesc1    = new descriptor to insert in the heap
  351. *       size_t size         = size of pdesc1 block
  352. *       _PBLKDESC pdesc2    = descriptor before which block should go
  353. *       _PBLKDESC **pppdesc = pointer to a pointer to the list of pointers
  354. *                             of empty descriptors
  355. *
  356. *Exit:
  357. *       (void)
  358. *
  359. *Exceptions:
  360. *
  361. *******************************************************************************/
  362.  
  363. static void __cdecl _before (
  364.         REG1 _PBLKDESC pdesc1,
  365.         size_t size,
  366.         REG2 _PBLKDESC pdesc2,
  367.         _PBLKDESC **pppdesc
  368.         )
  369. {
  370.         size_t diff;
  371.         _PBLKDESC pdummydesc;
  372.         void * dummyaddr;
  373.  
  374.         /*
  375.          * Check for dummy descriptors:
  376.          * (1) If first block is dummy, no adjustement needed.
  377.          * (2) If second block is dummy, simply adjust size.
  378.          */
  379.  
  380.         if (_IS_DUMMY(pdesc1))
  381.                 goto link;
  382.  
  383.         if (_IS_DUMMY(pdesc2)) {
  384.                 pdesc2->pblock = (char *)_ADDRESS(pdesc1) + size;
  385.                 _SET_DUMMY(pdesc2);
  386.                 goto link;
  387.                 }
  388.  
  389.  
  390.         /*
  391.          * See how much space is between this block and the next one.
  392.          */
  393.  
  394.         diff = ( (char *) _ADDRESS(pdesc2) -
  395.                  (char *) (dummyaddr = (char *) _ADDRESS(pdesc1) + size) );
  396.  
  397.         if (diff != 0) {
  398.  
  399.                 /*
  400.                  * There is some space between the two blocks.  Insert
  401.                  * a fake "in use" block.  Remember, there is no 'back
  402.                  * pointer' in dummy blocks.
  403.                  */
  404.  
  405.                 pdummydesc = *((*pppdesc)++);
  406.  
  407.                 pdummydesc->pblock = (char *) dummyaddr;
  408.                 _SET_DUMMY(pdummydesc);
  409.  
  410.                 pdesc1->pnextdesc = pdummydesc;
  411.                 pdesc1 = pdummydesc;
  412.  
  413.                 }
  414.  
  415.         /*
  416.          * Put the new block in the heap.
  417.          */
  418.  
  419.         link:
  420.                 pdesc1->pnextdesc = pdesc2;
  421.  
  422. }
  423.  
  424.  
  425. #endif  /* WINHEAP */
  426.