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 B's bits. */
51 elem_cnt (const struct bitmap *b)
53 return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
56 /* Returns the number of bytes required by B's elements. */
58 byte_cnt (const struct bitmap *b)
60 return sizeof (elem_type) * elem_cnt (b);
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 /* Initializes B to be a bitmap of BIT_CNT bits
73 and sets all of its bits to false.
74 Returns true if success, false if memory allocation
77 bitmap_create (size_t bit_cnt)
79 struct bitmap *b = malloc (sizeof *b);
83 b->bits = malloc (byte_cnt (b));
84 if (b->bits != NULL || bit_cnt == 0)
86 bitmap_set_all (b, false);
94 /* Destroys bitmap B, freeing its storage.
95 Not for use on bitmaps created by
96 bitmap_create_preallocated(). */
98 bitmap_destroy (struct bitmap *b)
107 /* Returns the number of bits in B. */
109 bitmap_size (const struct bitmap *b)
114 /* Sets the bit numbered IDX in B to VALUE. */
116 bitmap_set (struct bitmap *b, size_t idx, bool value)
119 ASSERT (idx < b->bit_cnt);
121 b->bits[elem_idx (idx)] |= bit_mask (idx);
123 b->bits[elem_idx (idx)] &= ~bit_mask (idx);
126 /* Sets all bits in B to VALUE. */
128 bitmap_set_all (struct bitmap *b, bool value)
132 bitmap_set_multiple (b, 0, bitmap_size (b), value);
135 /* Sets the bits numbered START through END, exclusive, in B to
138 bitmap_set_multiple (struct bitmap *b, size_t start, size_t end, bool value)
143 ASSERT (start <= end);
144 ASSERT (end <= b->bit_cnt);
146 for (idx = start; idx < end; idx++)
147 bitmap_set (b, idx, value);
150 /* Atomically sets the bit numbered IDX in B to true. */
152 bitmap_mark (struct bitmap *b, size_t idx)
155 : "=m" (b->bits[elem_idx (idx)])
156 : "r" (bit_mask (idx)));
159 /* Atomically sets the bit numbered IDX in B to false. */
161 bitmap_reset (struct bitmap *b, size_t idx)
164 : "=m" (b->bits[elem_idx (idx)])
165 : "r" (~bit_mask (idx)));
168 /* Atomically toggles the bit numbered IDX in B;
169 that is, if it is true, makes it false,
170 and if it is false, makes it true. */
172 bitmap_flip (struct bitmap *b, size_t idx)
175 ASSERT (idx < b->bit_cnt);
177 : "=m" (b->bits[elem_idx (idx)])
178 : "r" (bit_mask (idx)));
181 /* Returns the value of the bit numbered IDX in B. */
183 bitmap_test (const struct bitmap *b, size_t idx)
186 ASSERT (idx < b->bit_cnt);
187 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
190 /* Returns true if any bit from START to END, exclusive, is set
193 contains (const struct bitmap *b, size_t start, size_t end, bool value)
198 ASSERT (start <= end);
199 ASSERT (end <= b->bit_cnt);
201 for (idx = start; idx < end; idx++)
202 if (bitmap_test (b, idx) == value)
207 /* Finds and returns the starting index of the first group of CNT
208 consecutive bits in B at or after START that are all set to
210 If there is no such group, returns BITMAP_ERROR. */
212 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
217 ASSERT (start <= b->bit_cnt);
219 if (cnt <= b->bit_cnt)
220 for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
221 if (!contains (b, idx, idx + cnt, !value))
226 /* Finds the first group of CNT consecutive bits in B at or after
227 START that are all set to VALUE, flips them all to !VALUE,
228 and returns the index of the first bit in the group.
229 If there is no such group, returns BITMAP_ERROR.
230 If CNT is zero, returns 0.
231 Bits are set atomically, but testing bits is not atomic with
234 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
236 size_t idx = bitmap_scan (b, start, cnt, value);
237 if (idx != BITMAP_ERROR)
238 bitmap_set_multiple (b, idx, idx + cnt, !value);
242 /* Returns the number of bits in B between START and END,
243 exclusive, that are set to VALUE. */
245 bitmap_count (const struct bitmap *b, size_t start, size_t end, bool value)
250 ASSERT (start <= end);
251 ASSERT (end <= b->bit_cnt);
254 for (idx = start; idx < end; idx++)
255 cnt += bitmap_test (b, idx) == value;
259 /* Returns true if any bits in B between START and END,
260 exclusive, are set to true, and false otherwise.*/
262 bitmap_any (const struct bitmap *b, size_t start, size_t end)
264 return contains (b, start, end, true);
267 /* Returns true if no bits in B between START and END, exclusive,
268 are set to true, and false otherwise.*/
270 bitmap_none (const struct bitmap *b, size_t start, size_t end)
272 return !contains (b, start, end, true);
275 /* Returns true if every bit in B between START and END,
276 exclusive, is set to true, and false otherwise. */
278 bitmap_all (const struct bitmap *b, size_t start, size_t end)
280 return !contains (b, start, end, false);
284 /* Returns the number of bytes needed to store B in a file. */
286 bitmap_file_size (const struct bitmap *b)
291 /* Reads FILE into B, ignoring errors. */
293 bitmap_read (struct bitmap *b, struct file *file)
297 file_read_at (file, b->bits, byte_cnt (b), 0);
298 b->bits[elem_cnt (b) - 1] &= last_mask (b);
302 /* Writes FILE to B, ignoring errors. */
304 bitmap_write (const struct bitmap *b, struct file *file)
306 file_write_at (file, b->bits, byte_cnt (b), 0);
310 /* Dumps the contents of B to the console as hexadecimal. */
312 bitmap_dump (const struct bitmap *b)
314 hex_dump (0, b->bits, byte_cnt (b), false);
317 /* Returns the number of bytes required to accomodate a bitmap
318 with BIT_CNT bits. */
320 bitmap_needed_bytes (size_t bit_cnt)
324 return byte_cnt (&b) + sizeof b;
327 /* Creates and returns a bitmap with BIT_CNT bits in the
328 BLOCK_SIZE bytes of storage preallocated at BLOCK.
329 BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
331 bitmap_create_preallocated (size_t bit_cnt, void *block, size_t block_size)
333 struct bitmap *b = block;
335 ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
337 b->bit_cnt = bit_cnt;
338 b->bits = (elem_type *) (b + 1);
339 bitmap_set_all (b, false);