home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / sdktools / windiff / gbit.c < prev    next >
C/C++ Source or Header  |  1997-10-05  |  9KB  |  279 lines
  1.  
  2. /******************************************************************************\
  3. *       This is a part of the Microsoft Source Code Samples. 
  4. *       Copyright (C) 1993-1997 Microsoft Corporation.
  5. *       All rights reserved. 
  6. *       This source code is only intended as a supplement to 
  7. *       Microsoft Development Tools and/or WinHelp documentation.
  8. *       See these sources for detailed information regarding the 
  9. *       Microsoft samples programs.
  10. \******************************************************************************/
  11.  
  12. /****************************** Module Header *******************************
  13. * Module Name: GBIT.C
  14. *
  15. * Bitmap allocation routines to manage a bit-mapped free list, and find
  16. * free sections.
  17. *
  18. * Functions:
  19. *
  20. * gbit_set()
  21. * gbit_init()
  22. * gbit_alloc()
  23. * gbit_free()
  24. * gbit_findfree()
  25. *
  26. * Comments:
  27. *
  28. * Each map is an array of unsigned longs where bit 0 of the first 
  29. * long represents block 1.
  30. *
  31. ****************************************************************************/
  32.  
  33. #include <windows.h>
  34. #include "gutils.h"
  35.  
  36.  
  37. BOOL gbit_set(DWORD FAR * map, long blknr, long nblks, BOOL op_set);
  38.  
  39. /***************************************************************************
  40.  * Function: gbit_init
  41.  *
  42.  * Purpose:
  43.  *
  44.  * Initialise a pre-allocated map of ulongs to represent a free
  45.  * area of nblks
  46.  */
  47. void APIENTRY
  48. gbit_init(DWORD FAR * map, long nblks)
  49. {
  50.         long i;
  51.         long leftover = nblks % 32;
  52.         long blks = nblks / 32;
  53.         DWORD last = 0;
  54.  
  55.         for (i=0; i < blks; i++) {
  56.                 map[i] = 0xffffffff;
  57.         }
  58.         for (i = 0; i < leftover; i++) {
  59.                 last = (last << 1) | 1;
  60.         }
  61.         if(leftover)
  62.                 map[blks] = last;
  63. }
  64.  
  65. /***************************************************************************
  66.  * Function: gbit_alloc
  67.  *
  68.  * Purpose:
  69.  *
  70.  * Mark a region starting at blknr for nblks, as busy (ie 0) 
  71.  */
  72. BOOL APIENTRY
  73. gbit_alloc(DWORD FAR * map, long blknr, long nblks)
  74. {
  75.         return(gbit_set(map, blknr, nblks, FALSE));
  76. }
  77.  
  78.  
  79. /***************************************************************************
  80.  * Function: gbit_set
  81.  *
  82.  * Purpose:
  83.  *
  84.  * Mark region - if op_set, to 1s, otherwise to 0s 
  85.  */
  86. BOOL
  87. gbit_set(DWORD FAR * map, long blknr, long nblks, BOOL op_set)
  88. {
  89.         long first;
  90.         long last;
  91.         long fullwords;
  92.         long startbit, startword;
  93.         long i;
  94.         DWORD dword = 0;
  95.  
  96.         blknr--;
  97.         first = min(32 - (blknr % 32), nblks);
  98.         nblks -= first;
  99.         last = nblks % 32;
  100.         fullwords = (nblks - last) / 32;
  101.         
  102.         startword = blknr / 32;
  103.         startbit = blknr % 32;
  104.         for (i = 0; i < first; i++) {
  105.                 dword = (dword << 1) | 1;
  106.         }
  107.         dword <<= startbit;
  108.         if (op_set) {
  109.                 map[startword] |= dword;
  110.                 dword = 0xffffffff;
  111.         } else {
  112.                 map[startword] &= ~dword;
  113.                 dword = 0;
  114.         }
  115.         startword++;
  116.         for (i = 0; i < fullwords; i++) {
  117.                 map[startword+i] = dword;
  118.         }
  119.         startword += fullwords;
  120.         for(i = 0, dword = 0; i < last; i++) {
  121.                 dword = (dword << 1) | 1;
  122.         }
  123.         if (last) {
  124.                 if (op_set) {
  125.                         map[startword] |= dword;
  126.                 } else {
  127.                         map[startword] &= ~dword;
  128.                 }
  129.         }
  130.  
  131.         return(TRUE);
  132. }
  133.  
  134. /***************************************************************************
  135.  * Function: gbit_free
  136.  *
  137.  * Purpose:
  138.  *
  139.  * Mark region of nblks starting at blknr to 0s - ie not busy 
  140.  */
  141. BOOL APIENTRY
  142. gbit_free(DWORD FAR * map, long blknr, long nblks)
  143. {
  144.         return(gbit_set(map, blknr, nblks, TRUE));
  145. }
  146.  
  147.  
  148. /***************************************************************************
  149.  * Function: gbit_findfree
  150.  *
  151.  * Purpose:
  152.  *
  153.  * Find a free segment (ie contiguous sequence of 1s) of nblks in length.
  154.  * If not found, find longest sequence. Store address of segment in *blknr.
  155.  *
  156.  * Return value is nr of blks in sequence found. Region is *not* marked busy.
  157.  */
  158. long APIENTRY
  159. gbit_findfree(DWORD FAR* map, long nblks, long mapsize, long FAR * blknr)
  160. {
  161.         long curblk, startblk, len, i;
  162.         long startbit, nfull, nlast, nbitsleft;
  163.         DWORD mask;
  164.         long mapblks = (mapsize + 31) / 32;
  165.         long aubegin = 0, aulen = 0;
  166.         long curbit = 0;
  167.  
  168.         /* main loop looking at segments */
  169.         for (curblk = 0; curblk < mapblks; ) {
  170. loop:
  171.                 /* loop finding first 1 */
  172.                 for (; curblk < mapblks; curblk++, curbit = 0) {
  173.                         if (map[curblk] > 0) {
  174.                                 break;
  175.                         }
  176.                 }
  177.                 if (curblk >= mapblks) 
  178.                         break;
  179.                 
  180.                 /* find first 1 in this long */
  181.                 startblk = curblk;
  182.                 for (mask = 1, i = 0; i < curbit; i++) {
  183.                         mask <<= 1;
  184.                 }
  185.                 for(; curbit < 32; curbit++, mask <<= 1) {
  186.                         if (map[curblk] & mask) {
  187.                                 break;
  188.                         }
  189.                 } 
  190.                 if (curbit >= 32) {
  191.                         /* abandon this word - start again with next word */
  192.                         curblk++;
  193.                         curbit = 0;
  194.                         goto loop;
  195.                 }
  196.  
  197.                 /* we've now found a 1 - calc remaining
  198.                  * bits in this word, complete words etc required.
  199.                  */
  200.                 startbit = curbit;
  201.                 nbitsleft = min( (32 - curbit), nblks);
  202.                 nfull = (nblks - nbitsleft) / 32;
  203.                 nlast = (nblks - nbitsleft) % 32;
  204.  
  205.                 /* check for required sequence within this word */
  206.  
  207.                 for (i = 0; i < nbitsleft; i++, curbit++, mask <<= 1) {
  208.                         if ((map[curblk] & mask) == 0) {
  209.                                 /* abandon and start again - start
  210.                                  * next pass at curbit in same word
  211.                                  */
  212.                                 /* store free region if longest yet */
  213.                                 if (i > aulen) {
  214.                                         aulen = i;
  215.                                         aubegin = curblk * 32 + startbit +1;
  216.                                 }
  217.                                 goto loop;
  218.                         }
  219.                 }
  220.                 
  221.                 /* check for nfull full words */
  222.                 for (curblk++; curblk <= startblk + nfull; curblk++) {
  223.                         if (curblk >= mapblks) {
  224.                                 /* end of map - abandon here and exit at top
  225.                                  * of loop
  226.                                  */
  227.                                 len = nbitsleft +
  228.                                         ((curblk - (startblk + 1)) * 32);
  229.                                 if (len > aulen) {
  230.                                         aubegin = startblk * 32 + startbit + 1;
  231.                                         aulen = len;
  232.                                 }
  233.                                 goto loop;
  234.                         }
  235.                         if (map[curblk] != 0xffffffff) {
  236.                                 /* not a full word - start again at this bit */
  237.                                 len = 0;
  238.                                 curbit = 0;
  239.                                 for (mask = 1; mask & map[curblk]; mask <<= 1) {
  240.                                         len++;
  241.                                         curbit++;
  242.                                 }
  243.                                 len += nbitsleft +
  244.                                         (curblk - (startblk+ 1)) * 32;
  245.                                 if (len > aulen) {
  246.                                         aulen = len;
  247.                                         aubegin = startblk * 32 + startbit + 1;
  248.                                 }
  249.                                 /* continue with current blk, bit */
  250.                                 goto loop;
  251.                         }
  252.                 }
  253.  
  254.                 /* left-over bits required in last word */
  255.                 mask = 1;
  256.                 for (curbit = 0; curbit < nlast;  curbit++, mask <<= 1) {
  257.                         if ((map[curblk] & mask) == 0) {
  258.                                 len = nbitsleft + (nfull * 32);
  259.                                 len += curbit;
  260.                                 if (len > aulen) {
  261.                                         aulen = len;
  262.                                         aubegin = startblk * 32 + startbit + 1;
  263.                                 }
  264.                                 goto loop;
  265.                         }
  266.                 }
  267.                 /* ok - found a block big enough! */
  268.                 aubegin = startblk * 32 + startbit + 1;
  269.                 *blknr = aubegin;
  270.                 return(nblks);
  271.         }
  272.  
  273.         /* end of map - return longest sequence */
  274.         *blknr = aubegin;
  275.         return(aulen);
  276. }
  277.  
  278.  
  279.