Return to gbit.c CVS log

Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff

Annotation of mstools/samples/sdktools/windiff/gbit.c, revision 1.1

1.1     ! root        1: 
        !             2: /******************************************************************************\
        !             3: *       This is a part of the Microsoft Source Code Samples. 
        !             4: *       Copyright (C) 1993 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: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.