![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to gbit.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff|
Return to gbit.c CVS log | Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff |
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.