7 #include "threads/malloc.h"
9 #include "filesys/file.h"
14 This must be an unsigned integer type at least as wide as int.
16 Each bit represents one bit in the bitmap.
17 If bit 0 in an element represents bit K in the bitmap,
18 then bit 1 in the element represents bit K+1 in the bitmap,
20 typedef unsigned long elem_type;
22 /* Number of bits in an element. */
23 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
25 /* From the outside, a bitmap is an array of bits. From the
26 inside, it's an array of elem_type (defined above) that
27 simulates an array of bits. */
30 size_t bit_cnt; /* Number of bits. */
31 elem_type *bits; /* Elements that represent bits. */
34 /* Returns the index of the element that contains the bit
37 elem_idx (size_t bit_idx)
39 return bit_idx / ELEM_BITS;
42 /* Returns an elem_type where only the bit corresponding to
43 BIT_IDX is turned on. */
44 static inline elem_type
45 bit_mask (size_t bit_idx)
47 return (elem_type) 1 << (bit_idx % ELEM_BITS);
50 /* Returns the number of elements required for BIT_CNT bits. */
52 elem_cnt (size_t bit_cnt)
54 return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
57 /* Returns the number of bytes required for BIT_CNT bits. */
59 byte_cnt (size_t bit_cnt)
61 return sizeof (elem_type) * elem_cnt (bit_cnt);
64 /* Returns a bit mask in which the bits actually used in the last
65 element of B's bits are set to 1 and the rest are set to 0. */
66 static inline elem_type
67 last_mask (const struct bitmap *b)
69 int last_bits = b->bit_cnt % ELEM_BITS;
70 return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
73 /* Creation and destruction. */
75 /* Initializes B to be a bitmap of BIT_CNT bits
76 and sets all of its bits to false.
77 Returns true if success, false if memory allocation
80 bitmap_create (size_t bit_cnt)
82 struct bitmap *b = malloc (sizeof *b);
86 b->bits = malloc (byte_cnt (bit_cnt));
87 if (b->bits != NULL || bit_cnt == 0)
89 bitmap_set_all (b, false);
97 /* Creates and returns a bitmap with BIT_CNT bits in the
98 BLOCK_SIZE bytes of storage preallocated at BLOCK.
99 BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
101 bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
103 struct bitmap *b = block;
105 ASSERT (block_size >= bitmap_buf_size (bit_cnt));
107 b->bit_cnt = bit_cnt;
108 b->bits = (elem_type *) (b + 1);
109 bitmap_set_all (b, false);
113 /* Returns the number of bytes required to accomodate a bitmap
114 with BIT_CNT bits (for use with bitmap_create_in_buf()). */
116 bitmap_buf_size (size_t bit_cnt)
118 return sizeof (struct bitmap) + byte_cnt (bit_cnt);
121 /* Destroys bitmap B, freeing its storage.
122 Not for use on bitmaps created by
123 bitmap_create_preallocated(). */
125 bitmap_destroy (struct bitmap *b)
136 /* Returns the number of bits in B. */
138 bitmap_size (const struct bitmap *b)
143 /* Setting and testing single bits. */
145 /* Atomically sets the bit numbered IDX in B to VALUE. */
147 bitmap_set (struct bitmap *b, size_t idx, bool value)
150 ASSERT (idx < b->bit_cnt);
152 bitmap_mark (b, idx);
154 bitmap_reset (b, idx);
157 /* Atomically sets the bit numbered BIT_IDX in B to true. */
159 bitmap_mark (struct bitmap *b, size_t bit_idx)
161 size_t idx = elem_idx (bit_idx);
162 elem_type mask = bit_mask (bit_idx);
164 /* This is equivalent to `b->bits[idx] |= mask' except that it
165 is guaranteed to be atomic on a uniprocessor machine. See
166 the description of the OR instruction in [IA32-v2b]. */
167 asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
170 /* Atomically sets the bit numbered BIT_IDX in B to false. */
172 bitmap_reset (struct bitmap *b, size_t bit_idx)
174 size_t idx = elem_idx (bit_idx);
175 elem_type mask = bit_mask (bit_idx);
177 /* This is equivalent to `b->bits[idx] &= ~mask' except that it
178 is guaranteed to be atomic on a uniprocessor machine. See
179 the description of the AND instruction in [IA32-v2a]. */
180 asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
183 /* Atomically toggles the bit numbered IDX in B;
184 that is, if it is true, makes it false,
185 and if it is false, makes it true. */
187 bitmap_flip (struct bitmap *b, size_t bit_idx)
189 size_t idx = elem_idx (bit_idx);
190 elem_type mask = bit_mask (bit_idx);
192 /* This is equivalent to `b->bits[idx] ^= mask' except that it
193 is guaranteed to be atomic on a uniprocessor machine. See
194 the description of the XOR instruction in [IA32-v2b]. */
195 asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
198 /* Returns the value of the bit numbered IDX in B. */
200 bitmap_test (const struct bitmap *b, size_t idx)
203 ASSERT (idx < b->bit_cnt);
204 return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
207 /* Setting and testing multiple bits. */
209 /* Sets all bits in B to VALUE. */
211 bitmap_set_all (struct bitmap *b, bool value)
215 bitmap_set_multiple (b, 0, bitmap_size (b), value);
218 /* Sets the CNT bits starting at START in B to VALUE. */
220 bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
225 ASSERT (start <= b->bit_cnt);
226 ASSERT (start + cnt <= b->bit_cnt);
228 for (i = 0; i < cnt; i++)
229 bitmap_set (b, start + i, value);
232 /* Returns the number of bits in B between START and START + CNT,
233 exclusive, that are set to VALUE. */
235 bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
240 ASSERT (start <= b->bit_cnt);
241 ASSERT (start + cnt <= b->bit_cnt);
244 for (i = 0; i < cnt; i++)
245 if (bitmap_test (b, start + i) == value)
250 /* Returns true if any bits in B between START and START + CNT,
251 exclusive, are set to VALUE, and false otherwise. */
253 bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
258 ASSERT (start <= b->bit_cnt);
259 ASSERT (start + cnt <= b->bit_cnt);
261 for (i = 0; i < cnt; i++)
262 if (bitmap_test (b, start + i) == value)
267 /* Returns true if any bits in B between START and START + CNT,
268 exclusive, are set to true, and false otherwise.*/
270 bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
272 return bitmap_contains (b, start, cnt, true);
275 /* Returns true if no bits in B between START and START + CNT,
276 exclusive, are set to true, and false otherwise.*/
278 bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
280 return !bitmap_contains (b, start, cnt, true);
283 /* Returns true if every bit in B between START and START + CNT,
284 exclusive, is set to true, and false otherwise. */
286 bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
288 return !bitmap_contains (b, start, cnt, false);
291 /* Finding set or unset bits. */
293 /* Finds and returns the starting index of a group of CNT
294 consecutive bits in B at or after START that are all set to
296 If there is no such group, returns BITMAP_ERROR. */
298 bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
301 ASSERT (start <= b->bit_cnt);
303 if (cnt <= b->bit_cnt)
305 size_t last = b->bit_cnt - cnt;
306 size_t middle = start + random_ulong () % (last - start + 1);
310 if (!bitmap_contains (b, i, cnt, !value))
312 i = i != last ? i + 1 : start;
319 /* Finds a group of CNT consecutive bits in B at or after
320 START that are all set to VALUE, flips them all to !VALUE,
321 and returns the index of the first bit in the group.
322 If there is no such group, returns BITMAP_ERROR.
323 If CNT is zero, returns 0.
324 Bits are set atomically, but testing bits is not atomic with
327 bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
329 size_t idx = bitmap_scan (b, start, cnt, value);
330 if (idx != BITMAP_ERROR)
331 bitmap_set_multiple (b, idx, cnt, !value);
335 /* File input and output. */
338 /* Returns the number of bytes needed to store B in a file. */
340 bitmap_file_size (const struct bitmap *b)
342 return byte_cnt (b->bit_cnt);
345 /* Reads B from FILE. Returns true if successful, false
348 bitmap_read (struct bitmap *b, struct file *file)
353 off_t size = byte_cnt (b->bit_cnt);
354 success = file_read_at (file, b->bits, size, 0) == size;
355 b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
360 /* Writes B to FILE. Return true if successful, false
363 bitmap_write (const struct bitmap *b, struct file *file)
365 off_t size = byte_cnt (b->bit_cnt);
366 return file_write_at (file, b->bits, size, 0) == size;
372 /* Dumps the contents of B to the console as hexadecimal. */
374 bitmap_dump (const struct bitmap *b)
376 hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);