8 typedef unsigned long elem_type;
9 #define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
10 #define ELEM_IDX(BIT_IDX) ((BIT_IDX) / ELEM_BITS)
11 #define BIT_MASK(BIT_IDX) ((elem_type) 1 << ((BIT_IDX) % ELEM_BITS))
20 elem_cnt (const struct bitmap *b)
22 return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
26 byte_cnt (const struct bitmap *b)
28 return sizeof (elem_type) * elem_cnt (b);
32 bitmap_create (size_t bit_cnt)
34 struct bitmap *b = malloc (sizeof *b);
39 b->bits = malloc (byte_cnt (b));
40 if (b->bits == NULL && bit_cnt > 0)
45 bitmap_set_all (b, false);
50 bitmap_destroy (struct bitmap *b)
59 bitmap_size (const struct bitmap *b)
65 bitmap_set (struct bitmap *b, size_t idx, bool value)
68 ASSERT (idx < b->bit_cnt);
70 b->bits[ELEM_IDX (idx)] |= BIT_MASK (idx);
72 b->bits[ELEM_IDX (idx)] &= ~BIT_MASK (idx);
76 bitmap_set_all (struct bitmap *b, bool value)
83 for (i = 0; i < elem_cnt (b); i++)
84 b->bits[i] = value ? (elem_type) -1 : 0;
86 leftover_bits = b->bit_cnt % ELEM_BITS;
87 if (leftover_bits != 0)
88 b->bits[i - 1] = ((elem_type) 1 << leftover_bits) - 1;
92 bitmap_mark (struct bitmap *b, size_t idx)
94 bitmap_set (b, idx, true);
98 bitmap_reset (struct bitmap *b, size_t idx)
100 bitmap_set (b, idx, false);
104 bitmap_flip (struct bitmap *b, size_t idx)
107 ASSERT (idx < b->bit_cnt);
108 b->bits[ELEM_IDX (idx)] ^= BIT_MASK (idx);
112 bitmap_test (const struct bitmap *b, size_t idx)
115 ASSERT (idx < b->bit_cnt);
116 return (b->bits[ELEM_IDX (idx)] & BIT_MASK (idx)) != 0;
120 bitmap_scan (const struct bitmap *b, bool value)
126 ignore = value ? 0 : (elem_type) -1;
127 for (idx = 0; idx < elem_cnt (b); idx++)
129 elem_type e = b->bits[idx];
130 if (e != (elem_type) -1)
147 bitmap_find_and_set (struct bitmap *b)
149 size_t idx = bitmap_scan (b, false);
150 if (idx != BITMAP_ERROR)
151 bitmap_mark (b, idx);
156 bitmap_find_and_clear (struct bitmap *b)
158 size_t idx = bitmap_scan (b, true);
159 if (idx != BITMAP_ERROR)
160 bitmap_reset (b, idx);
165 bitmap_set_cnt (const struct bitmap *b)
172 for (i = 0; i < elem_cnt (b); i++)
174 elem_type e = b->bits[i];
185 bitmap_any (const struct bitmap *b)
190 for (i = 0; i < elem_cnt (b); i++)
197 bitmap_clear_cnt (const struct bitmap *b)
199 return b->bit_cnt - bitmap_set_cnt (b);
203 bitmap_none (const struct bitmap *b)
205 return !bitmap_any (b);
209 bitmap_all (const struct bitmap *b)
211 size_t leftover_bits;
219 for (i = 0; i < elem_cnt (b) - 1; i++)
220 if (b->bits[i] != (elem_type) -1)
223 leftover_bits = b->bit_cnt % ELEM_BITS;
224 if (leftover_bits == 0)
225 return b->bits[i] == (elem_type) -1;
227 return b->bits[i] == ((elem_type) 1 << leftover_bits) - 1;