home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / crt / src / heapsrch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-17  |  5.1 KB  |  138 lines
  1. /***
  2. *heapsrch.c - search the heap for a free block
  3. *
  4. *       Copyright (c) 1989-1997, Microsoft Corporation. All rights reserved.
  5. *
  6. *Purpose:
  7. *       Defines the _heap_search() function.
  8. *
  9. *******************************************************************************/
  10.  
  11.  
  12. #ifndef WINHEAP
  13.  
  14.  
  15. #include <cruntime.h>
  16. #include <heap.h>
  17. #include <stddef.h>
  18.  
  19. #define LOOP_FOREVER    while(1)
  20.  
  21. /***
  22. *_PBLKDESC _heap_search(unsigned size) - Find a free block of a least size
  23. *       bytes.
  24. *
  25. *Purpose:
  26. *       Finds a free block of at least size bytes. Searches the list of block
  27. *       descriptors from *proverdesc to the end (marked by the sentinel). The
  28. *       search is strictly first fit. Adjacent free blocks are coalesced as
  29. *       they are encountered during the search.
  30. *
  31. *Entry:
  32. *       unsigned size   - size of block requested
  33. *
  34. *Exit:
  35. *       Success:  Pointer to descriptor for free memory block of at least size
  36. *               bytes
  37. *       Failure:  NULL
  38. *
  39. *Uses:
  40. *
  41. *Exceptions:
  42. *
  43. *******************************************************************************/
  44.  
  45. _PBLKDESC __cdecl _heap_search (
  46.         unsigned size
  47.         )
  48. {
  49.         REG1 _PBLKDESC pdesc;
  50.         REG2 _PBLKDESC pdesc2;
  51.         _PBLKDESC pretdesc = NULL;
  52.  
  53.         /* search from proverdesc thru plastdesc, looking for free block of
  54.          * at least size bytes. coalesce adjacent free blocks during the
  55.          * search. the search is strictly first fit. that is, it terminates
  56.          * when the first block is found of adequate size.
  57.          */
  58.         for ( pdesc = _heap_desc.proverdesc ; pdesc != &(_heap_desc.sentinel) ;
  59.         pdesc = pdesc->pnextdesc )
  60.                 /* is pdesc free?
  61.                  */
  62.                 if ( _IS_FREE(pdesc) )
  63.                         /* coalesce loop
  64.                          */
  65.                         LOOP_FOREVER {
  66.                                 /* if pdesc is big enough, return it
  67.                                  */
  68.                                 if ( _BLKSIZE(pdesc) >= size ) {
  69.                                         pretdesc = pdesc;
  70.                                         goto searchdone;
  71.                                 }
  72.  
  73.                                 /* see if the next block is free and, if so,
  74.                                  * coalesce it with pdesc
  75.                                  */
  76.                                 pdesc2 = pdesc->pnextdesc;
  77.                                 if ( _IS_FREE(pdesc2) ) {
  78.                                         /* coalesce pdesc2 with pdesc
  79.                                          */
  80.                                         pdesc->pnextdesc = pdesc2->pnextdesc;
  81.                                         _PUTEMPTY(pdesc2);
  82.                                 }
  83.                                 else
  84.                                         break;
  85.                         } /* end LOOP_FOREVER */
  86.  
  87.         for ( pdesc = _heap_desc.pfirstdesc ; pdesc != _heap_desc.proverdesc ;
  88.         pdesc = pdesc->pnextdesc )
  89.                 /* is pdesc free?
  90.                  */
  91.                 if ( _IS_FREE(pdesc) )
  92.                         /* coalesce loop
  93.                          */
  94.                         LOOP_FOREVER {
  95.                                 /* if pdesc is big enough, return it
  96.                                  */
  97.                                 if ( _BLKSIZE(pdesc) >= size ) {
  98.                                         pretdesc = pdesc;
  99.                                         goto searchdone;
  100.                                 }
  101.  
  102.                                 /* see if the next block is free and, if so,
  103.                                  * coalesce it with pdesc
  104.                                  */
  105.                                 pdesc2 = pdesc->pnextdesc;
  106.                                 if ( _IS_FREE(pdesc2) ) {
  107.                                         /* coalesce pdesc2 with pdesc
  108.                                          */
  109.                                         pdesc->pnextdesc = pdesc2->pnextdesc;
  110.                                         _PUTEMPTY(pdesc2);
  111.  
  112.                                         /* special handling for the case where
  113.                                          * the rover has been coalesced (search
  114.                                          * ends)
  115.                                          */
  116.                                         if ( _heap_desc.proverdesc == pdesc2 )
  117.                                         {
  118.                                                 _heap_desc.proverdesc = pdesc;
  119.                                                 if ( _BLKSIZE(pdesc) >= size )
  120.                                                         pretdesc = pdesc;
  121.                                                 goto searchdone;
  122.                                         }
  123.                                 }
  124.                                 else
  125.                                         break;
  126.                         } /* end LOOP_FOREVER */
  127.  
  128. searchdone:
  129.  
  130.         /* common exit for all code paths. win, lose or draw, this is the
  131.          * only code path back to the caller.
  132.          */
  133.         return(pretdesc);
  134. }
  135.  
  136.  
  137. #endif  /* WINHEAP */
  138.