5 #include "threads/malloc.h"
7 #include "filesys/file.h"
10 /* Number of bits in an element. */
11 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
13 /* Returns the index of the element that contains the bit
16 elem_idx (size_t bit_idx)
18 return bit_idx / ELEM_BITS;
21 /* Returns an elem_type where only the bit corresponding to
22 BIT_IDX is turned on. */
23 static inline elem_type
24 bit_mask (size_t bit_idx)
26 return (elem_type) 1 << (bit_idx % ELEM_BITS);
29 /* Returns the number of elements required for B's bits. */
31 elem_cnt (const struct bitmap *b)
33 return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
36 /* Returns the number of bytes required by B's elements. */
38 byte_cnt (const struct bitmap *b)
40 return sizeof (elem_type) * elem_cnt (b);
43 /* Returns a bit mask in which the bits actually used in the last
44 element of B's bits are set to 1 and the rest are set to 0. */
45 static inline elem_type
46 last_mask (const struct bitmap *b)
48 int last_bits = b->bit_cnt % ELEM_BITS;
49 return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
52 /* Initializes B to be a bitmap of BIT_CNT bits.
53 Returns true if successfalse, false if memory allocation
56 bitmap_init (struct bitmap *b, size_t bit_cnt)
59 b->bits = malloc (byte_cnt (b));
60 if (b->bits == NULL && bit_cnt > 0)
63 bitmap_set_all (b, false);
67 /* Destroys bitmap B, freeing its storage. */
69 bitmap_destroy (struct bitmap *b)
76 /* Returns the number of bits in B. */
78 bitmap_size (const struct bitmap *b)
83 /* Sets the bit numbered IDX in B to VALUE. */
85 bitmap_set (struct bitmap *b, size_t idx, bool value)
88 ASSERT (idx < b->bit_cnt);
90 b->bits[elem_idx (idx)] |= bit_mask (idx);
92 b->bits[elem_idx (idx)] &= ~bit_mask (idx);
95 /* Sets all bits in B to VALUE. */
97 bitmap_set_all (struct bitmap *b, bool value)
105 for (i = 0; i < elem_cnt (b); i++)
106 b->bits[i] = value ? (elem_type) -1 : 0;
107 b->bits[elem_cnt (b) - 1] &= last_mask (b);
111 /* Sets the bit numbered IDX in B to true. */
113 bitmap_mark (struct bitmap *b, size_t idx)
115 bitmap_set (b, idx, true);
118 /* Sets the bit numbered IDX in B to false. */
120 bitmap_reset (struct bitmap *b, size_t idx)
122 bitmap_set (b, idx, false);
125 /* Toggles the bit numbered IDX in B;
126 that is, if it is true, makes it false,
127 and if it is false, makes it true. */
129 bitmap_flip (struct bitmap *b, size_t idx)
132 ASSERT (idx < b->bit_cnt);
133 b->bits[elem_idx (idx)] ^= bit_mask (idx);
136 /* Returns the value of the bit numbered IDX in B. */
138 bitmap_test (const struct bitmap *b, size_t idx)
141 ASSERT (idx < b->bit_cnt);
142 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
145 /* Returns the smallest index of a bit set to VALUE in B.
146 If no bits in B are set to VALUE, returns BITMAP_ERROR. */
148 bitmap_scan (const struct bitmap *b, bool value)
150 elem_type ignore = value ? 0 : (elem_type) -1;
154 for (idx = 0; idx < elem_cnt (b); idx++)
156 elem_type e = b->bits[idx];
161 while ((e & 1) != value)
167 return idx < b->bit_cnt ? idx : BITMAP_ERROR;
173 /* Finds the smallest index of a bit set to false in B,
174 sets it to true, and returns the index.
175 If no bits in B are set to false, changes no bits and
176 returns BITMAP_ERROR. */
178 bitmap_find_and_set (struct bitmap *b)
180 size_t idx = bitmap_scan (b, false);
181 if (idx != BITMAP_ERROR)
182 bitmap_mark (b, idx);
186 /* Finds the smallest index of a bit set to true in B,
187 sets it to false, and returns the index.
188 If no bits in B are set to true, changes no bits and
189 returns BITMAP_ERROR. */
191 bitmap_find_and_clear (struct bitmap *b)
193 size_t idx = bitmap_scan (b, true);
194 if (idx != BITMAP_ERROR)
195 bitmap_reset (b, idx);
199 /* Returns the number of bits in B set to true. */
201 bitmap_set_cnt (const struct bitmap *b)
208 for (i = 0; i < elem_cnt (b); i++)
210 elem_type e = b->bits[i];
220 /* Returns true if any bits in B are set to true,
221 and false otherwise.*/
223 bitmap_any (const struct bitmap *b)
228 for (i = 0; i < elem_cnt (b); i++)
234 /* Returns the number of bits in B set to false. */
236 bitmap_clear_cnt (const struct bitmap *b)
238 return b->bit_cnt - bitmap_set_cnt (b);
241 /* Returns true if no bits in B are set to true,
242 and false otherwise.*/
244 bitmap_none (const struct bitmap *b)
246 return !bitmap_any (b);
249 /* Returns true if every bit in B is set to true,
250 and false otherwise. */
252 bitmap_all (const struct bitmap *b)
261 for (i = 0; i < elem_cnt (b) - 1; i++)
262 if (b->bits[i] != (elem_type) -1)
264 return b->bits[i] == last_mask (b);
268 /* Returns the number of bytes needed to store B in a file. */
270 bitmap_file_size (const struct bitmap *b)
275 /* Reads FILE into B, ignoring errors. */
277 bitmap_read (struct bitmap *b, struct file *file)
281 file_read_at (file, b->bits, byte_cnt (b), 0);
282 b->bits[elem_cnt (b) - 1] &= last_mask (b);
286 /* Writes FILE to B, ignoring errors. */
288 bitmap_write (const struct bitmap *b, struct file *file)
290 file_write_at (file, b->bits, byte_cnt (b), 0);
294 /* Dumps the contents of B to the console as hexadecimal. */
296 bitmap_dump (const struct bitmap *b)
298 hex_dump (b->bits, byte_cnt (b), false);