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 Returns true if successfalse, false if memory allocation
76 bitmap_create (size_t bit_cnt)
78 struct bitmap *b = malloc (sizeof *b);
82 b->bits = malloc (byte_cnt (b));
83 if (b->bits != NULL || bit_cnt == 0)
85 bitmap_set_all (b, false);
93 /* Destroys bitmap B, freeing its storage. */
95 bitmap_destroy (struct bitmap *b)
104 /* Returns the number of bits in B. */
106 bitmap_size (const struct bitmap *b)
111 /* Sets the bit numbered IDX in B to VALUE. */
113 bitmap_set (struct bitmap *b, size_t idx, bool value)
116 ASSERT (idx < b->bit_cnt);
118 b->bits[elem_idx (idx)] |= bit_mask (idx);
120 b->bits[elem_idx (idx)] &= ~bit_mask (idx);
123 /* Sets all bits in B to VALUE. */
125 bitmap_set_all (struct bitmap *b, bool value)
133 for (i = 0; i < elem_cnt (b); i++)
134 b->bits[i] = value ? (elem_type) -1 : 0;
135 b->bits[elem_cnt (b) - 1] &= last_mask (b);
139 /* Sets the bit numbered IDX in B to true. */
141 bitmap_mark (struct bitmap *b, size_t idx)
143 bitmap_set (b, idx, true);
146 /* Sets the bit numbered IDX in B to false. */
148 bitmap_reset (struct bitmap *b, size_t idx)
150 bitmap_set (b, idx, false);
153 /* Toggles the bit numbered IDX in B;
154 that is, if it is true, makes it false,
155 and if it is false, makes it true. */
157 bitmap_flip (struct bitmap *b, size_t idx)
160 ASSERT (idx < b->bit_cnt);
161 b->bits[elem_idx (idx)] ^= bit_mask (idx);
164 /* Returns the value of the bit numbered IDX in B. */
166 bitmap_test (const struct bitmap *b, size_t idx)
169 ASSERT (idx < b->bit_cnt);
170 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
173 /* Returns the smallest index of a bit set to VALUE in B.
174 If no bits in B are set to VALUE, returns BITMAP_ERROR. */
176 bitmap_scan (const struct bitmap *b, bool value)
178 elem_type ignore = value ? 0 : (elem_type) -1;
182 for (idx = 0; idx < elem_cnt (b); idx++)
184 elem_type e = b->bits[idx];
189 while ((e & 1) != value)
195 return idx < b->bit_cnt ? idx : BITMAP_ERROR;
201 /* Finds the smallest index of a bit set to false in B,
202 sets it to true, and returns the index.
203 If no bits in B are set to false, changes no bits and
204 returns BITMAP_ERROR. */
206 bitmap_find_and_set (struct bitmap *b)
208 size_t idx = bitmap_scan (b, false);
209 if (idx != BITMAP_ERROR)
210 bitmap_mark (b, idx);
214 /* Finds the smallest index of a bit set to true in B,
215 sets it to false, and returns the index.
216 If no bits in B are set to true, changes no bits and
217 returns BITMAP_ERROR. */
219 bitmap_find_and_clear (struct bitmap *b)
221 size_t idx = bitmap_scan (b, true);
222 if (idx != BITMAP_ERROR)
223 bitmap_reset (b, idx);
227 /* Returns the number of bits in B set to true. */
229 bitmap_set_cnt (const struct bitmap *b)
236 for (i = 0; i < elem_cnt (b); i++)
238 elem_type e = b->bits[i];
248 /* Returns true if any bits in B are set to true,
249 and false otherwise.*/
251 bitmap_any (const struct bitmap *b)
256 for (i = 0; i < elem_cnt (b); i++)
262 /* Returns the number of bits in B set to false. */
264 bitmap_clear_cnt (const struct bitmap *b)
266 return b->bit_cnt - bitmap_set_cnt (b);
269 /* Returns true if no bits in B are set to true,
270 and false otherwise.*/
272 bitmap_none (const struct bitmap *b)
274 return !bitmap_any (b);
277 /* Returns true if every bit in B is set to true,
278 and false otherwise. */
280 bitmap_all (const struct bitmap *b)
289 for (i = 0; i < elem_cnt (b) - 1; i++)
290 if (b->bits[i] != (elem_type) -1)
292 return b->bits[i] == last_mask (b);
296 /* Returns the number of bytes needed to store B in a file. */
298 bitmap_file_size (const struct bitmap *b)
303 /* Reads FILE into B, ignoring errors. */
305 bitmap_read (struct bitmap *b, struct file *file)
309 file_read_at (file, b->bits, byte_cnt (b), 0);
310 b->bits[elem_cnt (b) - 1] &= last_mask (b);
314 /* Writes FILE to B, ignoring errors. */
316 bitmap_write (const struct bitmap *b, struct file *file)
318 file_write_at (file, b->bits, byte_cnt (b), 0);
322 /* Dumps the contents of B to the console as hexadecimal. */
324 bitmap_dump (const struct bitmap *b)
326 hex_dump (0, b->bits, byte_cnt (b), false);