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 /* Creates and returns a pointer to a newly allocated bitmap with room for
75 BIT_CNT (or more) bits. Returns a null pointer if memory allocation fails.
76 The caller is responsible for freeing the bitmap, with bitmap_destroy(),
77 when it is no longer needed. */
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 bitmap_create_in_buf(). */
123 bitmap_destroy (struct bitmap *b)
134 /* Returns the number of bits in B. */
136 bitmap_size (const struct bitmap *b)
141 /* Setting and testing single bits. */
143 /* Atomically sets the bit numbered IDX in B to VALUE. */
145 bitmap_set (struct bitmap *b, size_t idx, bool value)
148 ASSERT (idx < b->bit_cnt);
150 bitmap_mark (b, idx);
152 bitmap_reset (b, idx);
155 /* Atomically sets the bit numbered BIT_IDX in B to true. */
157 bitmap_mark (struct bitmap *b, size_t bit_idx)
159 size_t idx = elem_idx (bit_idx);
160 elem_type mask = bit_mask (bit_idx);
162 /* This is equivalent to `b->bits[idx] |= mask' except that it
163 is guaranteed to be atomic on a uniprocessor machine. See
164 the description of the OR instruction in [IA32-v2b]. */
165 asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
168 /* Atomically sets the bit numbered BIT_IDX in B to false. */
170 bitmap_reset (struct bitmap *b, size_t bit_idx)
172 size_t idx = elem_idx (bit_idx);
173 elem_type mask = bit_mask (bit_idx);
175 /* This is equivalent to `b->bits[idx] &= ~mask' except that it
176 is guaranteed to be atomic on a uniprocessor machine. See
177 the description of the AND instruction in [IA32-v2a]. */
178 asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
181 /* Atomically toggles the bit numbered IDX in B;
182 that is, if it is true, makes it false,
183 and if it is false, makes it true. */
185 bitmap_flip (struct bitmap *b, size_t bit_idx)
187 size_t idx = elem_idx (bit_idx);
188 elem_type mask = bit_mask (bit_idx);
190 /* This is equivalent to `b->bits[idx] ^= mask' except that it
191 is guaranteed to be atomic on a uniprocessor machine. See
192 the description of the XOR instruction in [IA32-v2b]. */
193 asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
196 /* Returns the value of the bit numbered IDX in B. */
198 bitmap_test (const struct bitmap *b, size_t idx)
201 ASSERT (idx < b->bit_cnt);
202 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
205 /* Setting and testing multiple bits. */
207 /* Sets all bits in B to VALUE. */
209 bitmap_set_all (struct bitmap *b, bool value)
213 bitmap_set_multiple (b, 0, bitmap_size (b), value);
216 /* Sets the CNT bits starting at START in B to VALUE. */
218 bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
223 ASSERT (start <= b->bit_cnt);
224 ASSERT (start + cnt <= b->bit_cnt);
226 for (i = 0; i < cnt; i++)
227 bitmap_set (b, start + i, value);
230 /* Returns the number of bits in B between START and START + CNT,
231 exclusive, that are set to VALUE. */
233 bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
238 ASSERT (start <= b->bit_cnt);
239 ASSERT (start + cnt <= b->bit_cnt);
242 for (i = 0; i < cnt; i++)
243 if (bitmap_test (b, start + i) == value)
248 /* Returns true if any bits in B between START and START + CNT,
249 exclusive, are set to VALUE, and false otherwise. */
251 bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
256 ASSERT (start <= b->bit_cnt);
257 ASSERT (start + cnt <= b->bit_cnt);
259 for (i = 0; i < cnt; i++)
260 if (bitmap_test (b, start + i) == value)
265 /* Returns true if any bits in B between START and START + CNT,
266 exclusive, are set to true, and false otherwise.*/
268 bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
270 return bitmap_contains (b, start, cnt, true);
273 /* Returns true if no bits in B between START and START + CNT,
274 exclusive, are set to true, and false otherwise.*/
276 bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
278 return !bitmap_contains (b, start, cnt, true);
281 /* Returns true if every bit in B between START and START + CNT,
282 exclusive, is set to true, and false otherwise. */
284 bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
286 return !bitmap_contains (b, start, cnt, false);
289 /* Finding set or unset bits. */
291 /* Finds and returns the starting index of the first group of CNT
292 consecutive bits in B at or after START that are all set to
294 If there is no such group, returns BITMAP_ERROR. */
296 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
299 ASSERT (start <= b->bit_cnt);
301 if (cnt <= b->bit_cnt)
303 size_t last = b->bit_cnt - cnt;
305 for (i = start; i <= last; i++)
306 if (!bitmap_contains (b, i, cnt, !value))
312 /* Finds the first group of CNT consecutive bits in B at or after
313 START that are all set to VALUE, flips them all to !VALUE,
314 and returns the index of the first bit in the group.
315 If there is no such group, returns BITMAP_ERROR.
316 If CNT is zero, returns 0.
317 Bits are set atomically, but testing bits is not atomic with
320 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
322 size_t idx = bitmap_scan (b, start, cnt, value);
323 if (idx != BITMAP_ERROR)
324 bitmap_set_multiple (b, idx, cnt, !value);
328 /* File input and output. */
331 /* Returns the number of bytes needed to store B in a file. */
333 bitmap_file_size (const struct bitmap *b)
335 return byte_cnt (b->bit_cnt);
338 /* Reads B from FILE. Returns true if successful, false
341 bitmap_read (struct bitmap *b, struct file *file)
346 off_t size = byte_cnt (b->bit_cnt);
347 success = file_read_at (file, b->bits, size, 0) == size;
348 b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
353 /* Writes B to FILE. Return true if successful, false
356 bitmap_write (const struct bitmap *b, struct file *file)
358 off_t size = byte_cnt (b->bit_cnt);
359 return file_write_at (file, b->bits, size, 0) == size;
365 /* Dumps the contents of B to the console as hexadecimal. */
367 bitmap_dump (const struct bitmap *b)
369 hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);