/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- bitmap_create
- bitmap_getdata
- bitmap_alloc
- bitmap_translate
- bitmap_mark
- bitmap_unmark
- bitmap_isset
- bitmap_destroy
1 /*
2 * Copyright (c) 2000, 2001, 2002
3 * The President and Fellows of Harvard College.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * Fixed-size array of bits. (Intended for storage management.)
32 */
33
34 #include <types.h>
35 #include <kern/errno.h>
36 #include <lib.h>
37 #include <bitmap.h>
38
39 /*
40 * It would be a lot more efficient on most platforms to use uint32_t
41 * or unsigned long as the base type for holding bits. But we don't,
42 * because if one uses any data type more than a single byte wide,
43 * bitmap data saved on disk becomes endian-dependent, which is a
44 * severe nuisance.
45 */
46 #define BITS_PER_WORD (CHAR_BIT)
47 #define WORD_TYPE unsigned char
48 #define WORD_ALLBITS (0xff)
49
50 struct bitmap {
51 unsigned nbits;
52 WORD_TYPE *v;
53 };
54
55
56 struct bitmap *
57 bitmap_create(unsigned nbits)
58 {
59 struct bitmap *b;
60 unsigned words;
61
62 words = DIVROUNDUP(nbits, BITS_PER_WORD);
63 b = kmalloc(sizeof(struct bitmap));
64 if (b == NULL) {
65 return NULL;
66 }
67 b->v = kmalloc(words*sizeof(WORD_TYPE));
68 if (b->v == NULL) {
69 kfree(b);
70 return NULL;
71 }
72
73 bzero(b->v, words*sizeof(WORD_TYPE));
74 b->nbits = nbits;
75
76 /* Mark any leftover bits at the end in use */
77 if (words > nbits / BITS_PER_WORD) {
78 unsigned j, ix = words-1;
79 unsigned overbits = nbits - ix*BITS_PER_WORD;
80
81 KASSERT(nbits / BITS_PER_WORD == words-1);
82 KASSERT(overbits > 0 && overbits < BITS_PER_WORD);
83
84 for (j=overbits; j<BITS_PER_WORD; j++) {
85 b->v[ix] |= ((WORD_TYPE)1 << j);
86 }
87 }
88
89 return b;
90 }
91
92 void *
93 bitmap_getdata(struct bitmap *b)
94 {
95 return b->v;
96 }
97
98 int
99 bitmap_alloc(struct bitmap *b, unsigned *index)
100 {
101 unsigned ix;
102 unsigned maxix = DIVROUNDUP(b->nbits, BITS_PER_WORD);
103 unsigned offset;
104
105 for (ix=0; ix<maxix; ix++) {
106 if (b->v[ix]!=WORD_ALLBITS) {
107 for (offset = 0; offset < BITS_PER_WORD; offset++) {
108 WORD_TYPE mask = ((WORD_TYPE)1) << offset;
109
110 if ((b->v[ix] & mask)==0) {
111 b->v[ix] |= mask;
112 *index = (ix*BITS_PER_WORD)+offset;
113 KASSERT(*index < b->nbits);
114 return 0;
115 }
116 }
117 KASSERT(0);
118 }
119 }
120 return ENOSPC;
121 }
122
123 static
124 inline
125 void
126 bitmap_translate(unsigned bitno, unsigned *ix, WORD_TYPE *mask)
127 {
128 unsigned offset;
129 *ix = bitno / BITS_PER_WORD;
130 offset = bitno % BITS_PER_WORD;
131 *mask = ((WORD_TYPE)1) << offset;
132 }
133
134 void
135 bitmap_mark(struct bitmap *b, unsigned index)
136 {
137 unsigned ix;
138 WORD_TYPE mask;
139
140 KASSERT(index < b->nbits);
141 bitmap_translate(index, &ix, &mask);
142
143 KASSERT((b->v[ix] & mask)==0);
144 b->v[ix] |= mask;
145 }
146
147 void
148 bitmap_unmark(struct bitmap *b, unsigned index)
149 {
150 unsigned ix;
151 WORD_TYPE mask;
152
153 KASSERT(index < b->nbits);
154 bitmap_translate(index, &ix, &mask);
155
156 KASSERT((b->v[ix] & mask)!=0);
157 b->v[ix] &= ~mask;
158 }
159
160
161 int
162 bitmap_isset(struct bitmap *b, unsigned index)
163 {
164 unsigned ix;
165 WORD_TYPE mask;
166
167 bitmap_translate(index, &ix, &mask);
168 return (b->v[ix] & mask);
169 }
170
171 void
172 bitmap_destroy(struct bitmap *b)
173 {
174 kfree(b->v);
175 kfree(b);
176 }