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)
136 for (i = 0; i < elem_cnt (b); i++)
137 b->bits[i] = value ? (elem_type) -1 : 0;
138 b->bits[elem_cnt (b) - 1] &= last_mask (b);
142 /* Sets the bits numbered START through END, exclusive, in B to
145 bitmap_set_multiple (struct bitmap *b, size_t start, size_t end, bool value)
150 ASSERT (start <= end);
151 ASSERT (end <= b->bit_cnt);
153 for (idx = start; idx < end; idx++)
154 bitmap_set (b, idx, value);
157 /* Sets the bit numbered IDX in B to true. */
159 bitmap_mark (struct bitmap *b, size_t idx)
161 bitmap_set (b, idx, true);
164 /* Sets the bit numbered IDX in B to false. */
166 bitmap_reset (struct bitmap *b, size_t idx)
168 bitmap_set (b, idx, false);
171 /* Toggles the bit numbered IDX in B;
172 that is, if it is true, makes it false,
173 and if it is false, makes it true. */
175 bitmap_flip (struct bitmap *b, size_t idx)
178 ASSERT (idx < b->bit_cnt);
179 b->bits[elem_idx (idx)] ^= bit_mask (idx);
182 /* Returns the value of the bit numbered IDX in B. */
184 bitmap_test (const struct bitmap *b, size_t idx)
187 ASSERT (idx < b->bit_cnt);
188 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
191 /* Returns true if any bit from START to END, exclusive, is set
194 contains (const struct bitmap *b, size_t start, size_t end, bool value)
199 ASSERT (start <= end);
200 ASSERT (end <= b->bit_cnt);
202 for (idx = start; idx < end; idx++)
203 if (bitmap_test (b, idx) == value)
208 /* Finds and returns the starting index of the first group of CNT
209 consecutive bits in B at or after START that are all set to
211 If there is no such group, returns BITMAP_ERROR. */
213 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
218 ASSERT (start <= 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. */
231 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
233 size_t idx = bitmap_scan (b, start, cnt, value);
234 if (idx != BITMAP_ERROR)
235 bitmap_set_multiple (b, idx, idx + cnt, !value);
239 /* Returns the number of bits in B between START and END,
240 exclusive, that are set to VALUE. */
242 bitmap_count (const struct bitmap *b, size_t start, size_t end, bool value)
247 ASSERT (start <= end);
248 ASSERT (end <= b->bit_cnt);
251 for (idx = start; idx < end; idx++)
252 cnt += bitmap_test (b, idx) == value;
256 /* Returns true if any bits in B between START and END,
257 exclusive, are set to true, and false otherwise.*/
259 bitmap_any (const struct bitmap *b, size_t start, size_t end)
261 return contains (b, start, end, true);
264 /* Returns true if no bits in B between START and END, exclusive,
265 are set to true, and false otherwise.*/
267 bitmap_none (const struct bitmap *b, size_t start, size_t end)
269 return !contains (b, start, end, true);
272 /* Returns true if every bit in B between START and END,
273 exclusive, is set to true, and false otherwise. */
275 bitmap_all (const struct bitmap *b, size_t start, size_t end)
277 return !contains (b, start, end, false);
281 /* Returns the number of bytes needed to store B in a file. */
283 bitmap_file_size (const struct bitmap *b)
288 /* Reads FILE into B, ignoring errors. */
290 bitmap_read (struct bitmap *b, struct file *file)
294 file_read_at (file, b->bits, byte_cnt (b), 0);
295 b->bits[elem_cnt (b) - 1] &= last_mask (b);
299 /* Writes FILE to B, ignoring errors. */
301 bitmap_write (const struct bitmap *b, struct file *file)
303 file_write_at (file, b->bits, byte_cnt (b), 0);
307 /* Dumps the contents of B to the console as hexadecimal. */
309 bitmap_dump (const struct bitmap *b)
311 hex_dump (0, b->bits, byte_cnt (b), false);
314 /* Returns the number of bytes required to accomodate a bitmap
315 with BIT_CNT bits. */
317 bitmap_needed_bytes (size_t bit_cnt)
321 return byte_cnt (&b) + sizeof b;
324 /* Creates and returns a bitmap with BIT_CNT bits in the
325 BLOCK_SIZE bytes of storage preallocated at BLOCK.
326 BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
328 bitmap_create_preallocated (size_t bit_cnt, void *block, size_t block_size)
330 struct bitmap *b = block;
332 ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
334 b->bit_cnt = bit_cnt;
335 b->bits = (elem_type *) (b + 1);
336 bitmap_set_all (b, false);