6 #include "threads/malloc.h"
8 #include "filesys/file.h"
13 This must be an unsigned integer type at least as wide as int.
15 Each bit represents one bit in the bitmap.
16 If bit 0 in an element represents bit K in the bitmap,
17 then bit 1 in the element represents bit K+1 in the bitmap,
19 typedef unsigned long elem_type;
21 /* Number of bits in an element. */
22 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
24 /* From the outside, a bitmap is an array of bits. From the
25 inside, it's an array of elem_type (defined above) that
26 simulates an array of bits. */
29 size_t bit_cnt; /* Number of bits. */
30 elem_type *bits; /* Elements that represent bits. */
33 /* Returns the index of the element that contains the bit
36 elem_idx (size_t bit_idx)
38 return bit_idx / ELEM_BITS;
41 /* Returns an elem_type where only the bit corresponding to
42 BIT_IDX is turned on. */
43 static inline elem_type
44 bit_mask (size_t bit_idx)
46 return (elem_type) 1 << (bit_idx % ELEM_BITS);
49 /* Returns the number of elements required for BIT_CNT bits. */
51 elem_cnt (size_t bit_cnt)
53 return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
56 /* Returns the number of bytes required for BIT_CNT bits. */
58 byte_cnt (size_t bit_cnt)
60 return sizeof (elem_type) * elem_cnt (bit_cnt);
63 /* Returns a bit mask in which the bits actually used in the last
64 element of B's bits are set to 1 and the rest are set to 0. */
65 static inline elem_type
66 last_mask (const struct bitmap *b)
68 int last_bits = b->bit_cnt % ELEM_BITS;
69 return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
72 /* Creation and destruction. */
74 /* Initializes B to be a bitmap of BIT_CNT bits
75 and sets all of its bits to false.
76 Returns true if success, false if memory allocation
79 bitmap_create (size_t bit_cnt)
81 struct bitmap *b = malloc (sizeof *b);
85 b->bits = malloc (byte_cnt (bit_cnt));
86 if (b->bits != NULL || bit_cnt == 0)
88 bitmap_set_all (b, false);
96 /* Creates and returns a bitmap with BIT_CNT bits in the
97 BLOCK_SIZE bytes of storage preallocated at BLOCK.
98 BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
100 bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
102 struct bitmap *b = block;
104 ASSERT (block_size >= bitmap_buf_size (bit_cnt));
106 b->bit_cnt = bit_cnt;
107 b->bits = (elem_type *) (b + 1);
108 bitmap_set_all (b, false);
112 /* Returns the number of bytes required to accomodate a bitmap
113 with BIT_CNT bits (for use with bitmap_create_in_buf()). */
115 bitmap_buf_size (size_t bit_cnt)
117 return sizeof (struct bitmap) + byte_cnt (bit_cnt);
120 /* Destroys bitmap B, freeing its storage.
121 Not for use on bitmaps created by
122 bitmap_create_preallocated(). */
124 bitmap_destroy (struct bitmap *b)
135 /* Returns the number of bits in B. */
137 bitmap_size (const struct bitmap *b)
142 /* Setting and testing single bits. */
144 /* Atomically sets the bit numbered IDX in B to VALUE. */
146 bitmap_set (struct bitmap *b, size_t idx, bool value)
149 ASSERT (idx < b->bit_cnt);
151 bitmap_mark (b, idx);
153 bitmap_reset (b, idx);
156 /* Atomically sets the bit numbered BIT_IDX in B to true. */
158 bitmap_mark (struct bitmap *b, size_t bit_idx)
160 size_t idx = elem_idx (bit_idx);
161 elem_type mask = bit_mask (bit_idx);
163 /* This is equivalent to `b->bits[idx] |= mask' except that it
164 is guaranteed to be atomic on a uniprocessor machine. See
165 the description of the OR instruction in [IA32-v2b]. */
166 asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
169 /* Atomically sets the bit numbered BIT_IDX in B to false. */
171 bitmap_reset (struct bitmap *b, size_t bit_idx)
173 size_t idx = elem_idx (bit_idx);
174 elem_type mask = bit_mask (bit_idx);
176 /* This is equivalent to `b->bits[idx] &= ~mask' except that it
177 is guaranteed to be atomic on a uniprocessor machine. See
178 the description of the AND instruction in [IA32-v2a]. */
179 asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
182 /* Atomically toggles the bit numbered IDX in B;
183 that is, if it is true, makes it false,
184 and if it is false, makes it true. */
186 bitmap_flip (struct bitmap *b, size_t bit_idx)
188 size_t idx = elem_idx (bit_idx);
189 elem_type mask = bit_mask (bit_idx);
191 /* This is equivalent to `b->bits[idx] ^= mask' except that it
192 is guaranteed to be atomic on a uniprocessor machine. See
193 the description of the XOR instruction in [IA32-v2b]. */
194 asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
197 /* Returns the value of the bit numbered IDX in B. */
199 bitmap_test (const struct bitmap *b, size_t idx)
202 ASSERT (idx < b->bit_cnt);
203 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
206 /* Setting and testing multiple bits. */
208 /* Sets all bits in B to VALUE. */
210 bitmap_set_all (struct bitmap *b, bool value)
214 bitmap_set_multiple (b, 0, bitmap_size (b), value);
217 /* Sets the CNT bits starting at START in B to VALUE. */
219 bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
224 ASSERT (start <= b->bit_cnt);
225 ASSERT (start + cnt <= b->bit_cnt);
227 for (i = 0; i < cnt; i++)
228 bitmap_set (b, start + i, value);
231 /* Returns the number of bits in B between START and START + CNT,
232 exclusive, that are set to VALUE. */
234 bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
239 ASSERT (start <= b->bit_cnt);
240 ASSERT (start + cnt <= b->bit_cnt);
243 for (i = 0; i < cnt; i++)
244 if (bitmap_test (b, start + i) == value)
249 /* Returns true if any bits in B between START and START + CNT,
250 exclusive, are set to VALUE, and false otherwise. */
252 bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
257 ASSERT (start <= b->bit_cnt);
258 ASSERT (start + cnt <= b->bit_cnt);
260 for (i = 0; i < cnt; i++)
261 if (bitmap_test (b, start + i) == value)
266 /* Returns true if any bits in B between START and START + CNT,
267 exclusive, are set to true, and false otherwise.*/
269 bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
271 return bitmap_contains (b, start, cnt, true);
274 /* Returns true if no bits in B between START and START + CNT,
275 exclusive, are set to true, and false otherwise.*/
277 bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
279 return !bitmap_contains (b, start, cnt, true);
282 /* Returns true if every bit in B between START and START + CNT,
283 exclusive, is set to true, and false otherwise. */
285 bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
287 return !bitmap_contains (b, start, cnt, false);
290 /* Finding set or unset bits. */
292 /* Finds and returns the starting index of the first group of CNT
293 consecutive bits in B at or after START that are all set to
295 If there is no such group, returns BITMAP_ERROR. */
297 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
300 ASSERT (start <= b->bit_cnt);
302 if (cnt <= b->bit_cnt)
304 size_t last = b->bit_cnt - cnt;
306 for (i = start; i <= last; i++)
307 if (!bitmap_contains (b, i, cnt, !value))
313 /* Finds the first group of CNT consecutive bits in B at or after
314 START that are all set to VALUE, flips them all to !VALUE,
315 and returns the index of the first bit in the group.
316 If there is no such group, returns BITMAP_ERROR.
317 If CNT is zero, returns 0.
318 Bits are set atomically, but testing bits is not atomic with
321 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
323 size_t idx = bitmap_scan (b, start, cnt, value);
324 if (idx != BITMAP_ERROR)
325 bitmap_set_multiple (b, idx, cnt, !value);
329 /* File input and output. */
332 /* Returns the number of bytes needed to store B in a file. */
334 bitmap_file_size (const struct bitmap *b)
336 return byte_cnt (b->bit_cnt);
339 /* Reads B from FILE. Returns true if successful, false
342 bitmap_read (struct bitmap *b, struct file *file)
347 off_t size = byte_cnt (b->bit_cnt);
348 success = file_read_at (file, b->bits, size, 0) == size;
349 b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
354 /* Writes B to FILE. Return true if successful, false
357 bitmap_write (const struct bitmap *b, struct file *file)
359 off_t size = byte_cnt (b->bit_cnt);
360 return file_write_at (file, b->bits, size, 0) == size;
366 /* Dumps the contents of B to the console as hexadecimal. */
368 bitmap_dump (const struct bitmap *b)
370 hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);