7bbc92868ca9fdf908798c919c168c7b3b44732b
[pintos-anon] / src / lib / kernel / bitmap.c
1 #include "bitmap.h"
2 #include <debug.h>
3 #include <limits.h>
4 #include <round.h>
5 #include <stdio.h>
6 #include "threads/malloc.h"
7 #ifdef FILESYS
8 #include "filesys/file.h"
9 #endif
10 \f
11 /* Number of bits in an element. */
12 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
13
14 /* Returns the index of the element that contains the bit
15    numbered BIT_IDX. */
16 static inline size_t
17 elem_idx (size_t bit_idx) 
18 {
19   return bit_idx / ELEM_BITS;
20 }
21
22 /* Returns an elem_type where only the bit corresponding to
23    BIT_IDX is turned on. */
24 static inline elem_type
25 bit_mask (size_t bit_idx) 
26 {
27   return (elem_type) 1 << (bit_idx % ELEM_BITS);
28 }
29
30 /* Returns the number of elements required for B's bits. */
31 static inline size_t
32 elem_cnt (const struct bitmap *b) 
33 {
34   return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
35 }
36
37 /* Returns the number of bytes required by B's elements. */
38 static inline size_t
39 byte_cnt (const struct bitmap *b) 
40 {
41   return sizeof (elem_type) * elem_cnt (b);
42 }
43
44 /* Returns a bit mask in which the bits actually used in the last
45    element of B's bits are set to 1 and the rest are set to 0. */
46 static inline elem_type
47 last_mask (const struct bitmap *b) 
48 {
49   int last_bits = b->bit_cnt % ELEM_BITS;
50   return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
51 }
52 \f
53 /* Initializes B to be a bitmap of BIT_CNT bits.
54    Returns true if successfalse, false if memory allocation
55    failed. */
56 bool
57 bitmap_init (struct bitmap *b, size_t bit_cnt) 
58 {
59   b->bit_cnt = bit_cnt;
60   b->bits = malloc (byte_cnt (b));
61   if (b->bits == NULL && bit_cnt > 0) 
62     return false;
63
64   bitmap_set_all (b, false);
65   return true;
66 }
67
68 /* Destroys bitmap B, freeing its storage. */
69 void
70 bitmap_destroy (struct bitmap *b) 
71 {
72   ASSERT (b);
73   
74   free (b->bits);
75 }
76
77 /* Returns the number of bits in B. */
78 size_t
79 bitmap_size (const struct bitmap *b)
80 {
81   return b->bit_cnt;
82 }
83
84 /* Sets the bit numbered IDX in B to VALUE. */
85 void
86 bitmap_set (struct bitmap *b, size_t idx, bool value) 
87 {
88   ASSERT (b != NULL);
89   ASSERT (idx < b->bit_cnt);
90   if (value)
91     b->bits[elem_idx (idx)] |= bit_mask (idx);
92   else
93     b->bits[elem_idx (idx)] &= ~bit_mask (idx);
94 }
95
96 /* Sets all bits in B to VALUE. */
97 void
98 bitmap_set_all (struct bitmap *b, bool value) 
99 {
100   size_t i;
101   
102   ASSERT (b != NULL);
103
104   if (b->bit_cnt > 0)
105     {
106       for (i = 0; i < elem_cnt (b); i++)
107         b->bits[i] = value ? (elem_type) -1 : 0;
108       b->bits[elem_cnt (b) - 1] &= last_mask (b); 
109     }
110 }
111
112 /* Sets the bit numbered IDX in B to true. */
113 void
114 bitmap_mark (struct bitmap *b, size_t idx) 
115 {
116   bitmap_set (b, idx, true);
117 }
118
119 /* Sets the bit numbered IDX in B to false. */
120 void
121 bitmap_reset (struct bitmap *b, size_t idx) 
122 {
123   bitmap_set (b, idx, false);
124 }
125
126 /* Toggles the bit numbered IDX in B;
127    that is, if it is true, makes it false,
128    and if it is false, makes it true. */
129 void
130 bitmap_flip (struct bitmap *b, size_t idx) 
131 {
132   ASSERT (b != NULL);
133   ASSERT (idx < b->bit_cnt);
134   b->bits[elem_idx (idx)] ^= bit_mask (idx);
135 }
136
137 /* Returns the value of the bit numbered IDX in B. */
138 bool
139 bitmap_test (const struct bitmap *b, size_t idx) 
140 {
141   ASSERT (b != NULL);
142   ASSERT (idx < b->bit_cnt);
143   return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
144 }
145
146 /* Returns the smallest index of a bit set to VALUE in B.
147    If no bits in B are set to VALUE, returns BITMAP_ERROR. */
148 size_t
149 bitmap_scan (const struct bitmap *b, bool value) 
150 {
151   elem_type ignore = value ? 0 : (elem_type) -1;
152   size_t idx;
153   
154   ASSERT (b != NULL);
155   for (idx = 0; idx < elem_cnt (b); idx++)
156     {
157       elem_type e = b->bits[idx];
158       if (e != ignore)
159         {
160           idx *= ELEM_BITS;
161
162           while ((e & 1) != value)
163             {
164               e >>= 1;
165               idx++;
166             }
167
168           return idx < b->bit_cnt ? idx : BITMAP_ERROR;
169         }
170     }
171   return BITMAP_ERROR;
172 }
173
174 /* Finds the smallest index of a bit set to false in B,
175    sets it to true, and returns the index.
176    If no bits in B are set to false, changes no bits and
177    returns BITMAP_ERROR. */
178 size_t
179 bitmap_find_and_set (struct bitmap *b) 
180 {
181   size_t idx = bitmap_scan (b, false);
182   if (idx != BITMAP_ERROR) 
183     bitmap_mark (b, idx);
184   return idx;
185 }
186
187 /* Finds the smallest index of a bit set to true in B,
188    sets it to false, and returns the index.
189    If no bits in B are set to true, changes no bits and
190    returns BITMAP_ERROR. */
191 size_t
192 bitmap_find_and_clear (struct bitmap *b) 
193 {
194   size_t idx = bitmap_scan (b, true);
195   if (idx != BITMAP_ERROR) 
196     bitmap_reset (b, idx);
197   return idx;
198 }
199
200 /* Returns the number of bits in B set to true. */
201 size_t
202 bitmap_set_cnt (const struct bitmap *b) 
203 {
204   size_t cnt;
205   size_t i;
206
207   ASSERT (b != NULL);
208   cnt = 0;
209   for (i = 0; i < elem_cnt (b); i++)
210     {
211       elem_type e = b->bits[i];
212       while (e != 0) 
213         {
214           cnt++;
215           e &= e - 1;
216         }
217     }
218   return cnt;
219 }
220
221 /* Returns true if any bits in B are set to true,
222    and false otherwise.*/
223 bool
224 bitmap_any (const struct bitmap *b) 
225 {
226   size_t i;
227
228   ASSERT (b != NULL);
229   for (i = 0; i < elem_cnt (b); i++)
230     if (b->bits[i])
231       return true;
232   return false;
233 }
234
235 /* Returns the number of bits in B set to false. */
236 bool
237 bitmap_clear_cnt (const struct bitmap *b) 
238 {
239   return b->bit_cnt - bitmap_set_cnt (b);
240 }
241
242 /* Returns true if no bits in B are set to true,
243    and false otherwise.*/
244 bool
245 bitmap_none (const struct bitmap *b) 
246 {
247   return !bitmap_any (b); 
248 }
249
250 /* Returns true if every bit in B is set to true,
251    and false otherwise. */
252 bool
253 bitmap_all (const struct bitmap *b) 
254 {
255   size_t i;
256
257   ASSERT (b != NULL);
258
259   if (b->bit_cnt == 0)
260     return true;
261   
262   for (i = 0; i < elem_cnt (b) - 1; i++)
263     if (b->bits[i] != (elem_type) -1)
264       return false;
265   return b->bits[i] == last_mask (b);
266 }
267
268 #ifdef FILESYS
269 /* Returns the number of bytes needed to store B in a file. */
270 size_t
271 bitmap_file_size (const struct bitmap *b) 
272 {
273   return byte_cnt (b);
274 }
275
276 /* Reads FILE into B, ignoring errors. */
277 void
278 bitmap_read (struct bitmap *b, struct file *file) 
279 {
280   if (b->bit_cnt > 0) 
281     {
282       file_read_at (file, b->bits, byte_cnt (b), 0);
283       b->bits[elem_cnt (b) - 1] &= last_mask (b);
284     }
285 }
286
287 /* Writes FILE to B, ignoring errors. */
288 void
289 bitmap_write (const struct bitmap *b, struct file *file)
290 {
291   file_write_at (file, b->bits, byte_cnt (b), 0);
292 }
293 #endif /* FILESYS */
294
295 /* Dumps the contents of B to the console as hexadecimal. */
296 void
297 bitmap_dump (const struct bitmap *b) 
298 {
299   hex_dump (b->bits, byte_cnt (b), false);
300 }