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))
14 elem_cnt (const struct bitmap *b)
16 return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
20 byte_cnt (const struct bitmap *b)
22 return sizeof (elem_type) * elem_cnt (b);
26 bitmap_init (struct bitmap *b, size_t bit_cnt)
29 b->bits = malloc (byte_cnt (b));
30 if (b->bits == NULL && bit_cnt > 0)
33 bitmap_set_all (b, false);
38 bitmap_storage_size (const struct bitmap *b)
44 bitmap_destroy (struct bitmap *b)
52 bitmap_size (const struct bitmap *b)
58 bitmap_set (struct bitmap *b, size_t idx, bool value)
61 ASSERT (idx < b->bit_cnt);
63 b->bits[ELEM_IDX (idx)] |= BIT_MASK (idx);
65 b->bits[ELEM_IDX (idx)] &= ~BIT_MASK (idx);
69 bitmap_set_all (struct bitmap *b, bool value)
76 for (i = 0; i < elem_cnt (b); i++)
77 b->bits[i] = value ? (elem_type) -1 : 0;
79 leftover_bits = b->bit_cnt % ELEM_BITS;
80 if (leftover_bits != 0)
81 b->bits[i - 1] = ((elem_type) 1 << leftover_bits) - 1;
85 bitmap_mark (struct bitmap *b, size_t idx)
87 bitmap_set (b, idx, true);
91 bitmap_reset (struct bitmap *b, size_t idx)
93 bitmap_set (b, idx, false);
97 bitmap_flip (struct bitmap *b, size_t idx)
100 ASSERT (idx < b->bit_cnt);
101 b->bits[ELEM_IDX (idx)] ^= BIT_MASK (idx);
105 bitmap_test (const struct bitmap *b, size_t idx)
108 ASSERT (idx < b->bit_cnt);
109 return (b->bits[ELEM_IDX (idx)] & BIT_MASK (idx)) != 0;
113 bitmap_scan (const struct bitmap *b, bool value)
119 ignore = value ? 0 : (elem_type) -1;
120 for (idx = 0; idx < elem_cnt (b); idx++)
122 elem_type e = b->bits[idx];
123 if (e != (elem_type) -1)
140 bitmap_find_and_set (struct bitmap *b)
142 size_t idx = bitmap_scan (b, false);
143 if (idx != BITMAP_ERROR)
144 bitmap_mark (b, idx);
149 bitmap_find_and_clear (struct bitmap *b)
151 size_t idx = bitmap_scan (b, true);
152 if (idx != BITMAP_ERROR)
153 bitmap_reset (b, idx);
158 bitmap_set_cnt (const struct bitmap *b)
165 for (i = 0; i < elem_cnt (b); i++)
167 elem_type e = b->bits[i];
178 bitmap_any (const struct bitmap *b)
183 for (i = 0; i < elem_cnt (b); i++)
190 bitmap_clear_cnt (const struct bitmap *b)
192 return b->bit_cnt - bitmap_set_cnt (b);
196 bitmap_none (const struct bitmap *b)
198 return !bitmap_any (b);
202 bitmap_all (const struct bitmap *b)
204 size_t leftover_bits;
212 for (i = 0; i < elem_cnt (b) - 1; i++)
213 if (b->bits[i] != (elem_type) -1)
216 leftover_bits = b->bit_cnt % ELEM_BITS;
217 if (leftover_bits == 0)
218 return b->bits[i] == (elem_type) -1;
220 return b->bits[i] == ((elem_type) 1 << leftover_bits) - 1;