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 /* 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 (bit_cnt));
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 CNT bits starting at START in B to VALUE. */
137 bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
142 ASSERT (start <= b->bit_cnt);
143 ASSERT (start + cnt <= b->bit_cnt);
145 for (i = 0; i < cnt; i++)
146 bitmap_set (b, start + i, value);
149 /* Atomically sets the bit numbered IDX in B to true. */
151 bitmap_mark (struct bitmap *b, size_t idx)
154 : "=m" (b->bits[elem_idx (idx)])
155 : "r" (bit_mask (idx)));
158 /* Atomically sets the bit numbered IDX in B to false. */
160 bitmap_reset (struct bitmap *b, size_t idx)
163 : "=m" (b->bits[elem_idx (idx)])
164 : "r" (~bit_mask (idx)));
167 /* Atomically toggles the bit numbered IDX in B;
168 that is, if it is true, makes it false,
169 and if it is false, makes it true. */
171 bitmap_flip (struct bitmap *b, size_t idx)
174 ASSERT (idx < b->bit_cnt);
176 : "=m" (b->bits[elem_idx (idx)])
177 : "r" (bit_mask (idx)));
180 /* Returns the value of the bit numbered IDX in B. */
182 bitmap_test (const struct bitmap *b, size_t idx)
185 ASSERT (idx < b->bit_cnt);
186 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
189 /* Returns true if any of the CNT bits starting at START is set
192 contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
197 ASSERT (start <= b->bit_cnt);
198 ASSERT (start + cnt <= b->bit_cnt);
200 for (i = 0; i < cnt; i++)
201 if (bitmap_test (b, start + i) == value)
206 /* Finds and returns the starting index of the first group of CNT
207 consecutive bits in B at or after START that are all set to
209 If there is no such group, returns BITMAP_ERROR. */
211 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
216 ASSERT (start <= b->bit_cnt);
218 if (cnt <= b->bit_cnt)
219 for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
220 if (!contains (b, idx, cnt, !value))
225 /* Finds the first group of CNT consecutive bits in B at or after
226 START that are all set to VALUE, flips them all to !VALUE,
227 and returns the index of the first bit in the group.
228 If there is no such group, returns BITMAP_ERROR.
229 If CNT is zero, returns 0.
230 Bits are set atomically, but testing bits is not atomic with
233 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
235 size_t idx = bitmap_scan (b, start, cnt, value);
236 if (idx != BITMAP_ERROR)
237 bitmap_set_multiple (b, idx, cnt, !value);
241 /* Returns the number of bits in B between START and START + CNT,
242 exclusive, that are set to VALUE. */
244 bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
249 ASSERT (start <= b->bit_cnt);
250 ASSERT (start + cnt <= b->bit_cnt);
253 for (i = 0; i < cnt; i++)
254 if (bitmap_test (b, start + i) == value)
259 /* Returns true if any bits in B between START and START + CNT,
260 exclusive, are set to true, and false otherwise.*/
262 bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
264 return contains (b, start, cnt, true);
267 /* Returns true if no bits in B between START and START + CNT,
268 exclusive, are set to true, and false otherwise.*/
270 bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
272 return !contains (b, start, cnt, true);
275 /* Returns true if every bit in B between START and START + CNT,
276 exclusive, is set to true, and false otherwise. */
278 bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
280 return !contains (b, start, cnt, false);
284 /* Returns the number of bytes needed to store B in a file. */
286 bitmap_file_size (const struct bitmap *b)
288 return byte_cnt (b->bit_cnt);
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->bit_cnt), 0);
298 b->bits[elem_cnt (b->bit_cnt) - 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->bit_cnt), 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->bit_cnt), 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)
322 return sizeof (struct bitmap) + byte_cnt (bit_cnt);
325 /* Creates and returns a bitmap with BIT_CNT bits in the
326 BLOCK_SIZE bytes of storage preallocated at BLOCK.
327 BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
329 bitmap_create_preallocated (size_t bit_cnt, void *block, size_t block_size)
331 struct bitmap *b = block;
333 ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
335 b->bit_cnt = bit_cnt;
336 b->bits = (elem_type *) (b + 1);
337 bitmap_set_all (b, false);