11 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
12 #define ELEM_IDX(BIT_IDX) ((BIT_IDX) / ELEM_BITS)
13 #define BIT_MASK(BIT_IDX) ((elem_type) 1 << ((BIT_IDX) % ELEM_BITS))
16 elem_cnt (const struct bitmap *b)
18 return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
22 byte_cnt (const struct bitmap *b)
24 return sizeof (elem_type) * elem_cnt (b);
27 static inline elem_type
28 last_mask (const struct bitmap *b)
30 int last_bits = b->bit_cnt % ELEM_BITS;
31 return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
35 bitmap_init (struct bitmap *b, size_t bit_cnt)
38 b->bits = malloc (byte_cnt (b));
39 if (b->bits == NULL && bit_cnt > 0)
42 bitmap_set_all (b, false);
47 bitmap_storage_size (const struct bitmap *b)
53 bitmap_destroy (struct bitmap *b)
61 bitmap_size (const struct bitmap *b)
67 bitmap_set (struct bitmap *b, size_t idx, bool value)
70 ASSERT (idx < b->bit_cnt);
72 b->bits[ELEM_IDX (idx)] |= BIT_MASK (idx);
74 b->bits[ELEM_IDX (idx)] &= ~BIT_MASK (idx);
78 bitmap_set_all (struct bitmap *b, bool value)
84 for (i = 0; i < elem_cnt (b); i++)
85 b->bits[i] = value ? (elem_type) -1 : 0;
86 b->bits[elem_cnt (b) - 1] &= last_mask (b);
90 bitmap_mark (struct bitmap *b, size_t idx)
92 bitmap_set (b, idx, true);
96 bitmap_reset (struct bitmap *b, size_t idx)
98 bitmap_set (b, idx, false);
102 bitmap_flip (struct bitmap *b, size_t idx)
105 ASSERT (idx < b->bit_cnt);
106 b->bits[ELEM_IDX (idx)] ^= BIT_MASK (idx);
110 bitmap_test (const struct bitmap *b, size_t idx)
113 ASSERT (idx < b->bit_cnt);
114 return (b->bits[ELEM_IDX (idx)] & BIT_MASK (idx)) != 0;
118 bitmap_scan (const struct bitmap *b, bool value)
120 elem_type ignore = value ? 0 : (elem_type) -1;
124 for (idx = 0; idx < elem_cnt (b); idx++)
126 elem_type e = b->bits[idx];
131 while ((e & 1) != value)
137 return idx < b->bit_cnt ? idx : BITMAP_ERROR;
144 bitmap_find_and_set (struct bitmap *b)
146 size_t idx = bitmap_scan (b, false);
147 if (idx != BITMAP_ERROR)
148 bitmap_mark (b, idx);
153 bitmap_find_and_clear (struct bitmap *b)
155 size_t idx = bitmap_scan (b, true);
156 if (idx != BITMAP_ERROR)
157 bitmap_reset (b, idx);
162 bitmap_set_cnt (const struct bitmap *b)
169 for (i = 0; i < elem_cnt (b); i++)
171 elem_type e = b->bits[i];
182 bitmap_any (const struct bitmap *b)
187 for (i = 0; i < elem_cnt (b); i++)
194 bitmap_clear_cnt (const struct bitmap *b)
196 return b->bit_cnt - bitmap_set_cnt (b);
200 bitmap_none (const struct bitmap *b)
202 return !bitmap_any (b);
206 bitmap_all (const struct bitmap *b)
215 for (i = 0; i < elem_cnt (b) - 1; i++)
216 if (b->bits[i] != (elem_type) -1)
218 return b->bits[i] == last_mask (b);
223 bitmap_read (struct bitmap *b, struct file *file)
225 file_read_at (file, b->bits, byte_cnt (b), 0);
226 b->bits[elem_cnt (b) - 1] &= last_mask (b);
230 bitmap_write (const struct bitmap *b, struct file *file)
232 file_write_at (file, b->bits, byte_cnt (b), 0);
237 bitmap_dump (const struct bitmap *b)
239 hex_dump (b->bits, byte_cnt (b), false);