5 #ifndef __FIRM_BITSET_H
6 #define __FIRM_BITSET_H
16 #define BITSET_USE_STD
18 #include "bitset_std.h"
20 typedef struct _bitset_t {
25 #define BS_UNIT_SIZE sizeof(bitset_unit_t)
26 #define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8)
27 #define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1)
31 * Units needed for a given highest bit.
32 * @param highest_bit The highest bit that should be storable.
33 * @return The number of units needed.
35 #define _bitset_units(highest_bit) (round_up2(highest_bit, BS_UNIT_SIZE_BITS) / BS_UNIT_SIZE_BITS)
38 * Compute the size in bytes needed for a bitset.
39 * This also include the size for the bitset data structure.
40 * @param highest_bit The highest bit that shall be storable.
41 * @return The overall amount of bytes needed for that bitset.
43 #define _bitset_overall_size(highest_bit) \
44 (sizeof(bitset_t) + _bitset_units(highest_bit) * BS_UNIT_SIZE)
47 * Initialize a bitset.
48 * This functions should not be called.
49 * @param area A pointer to memory reserved for the bitset.
50 * @param units The number of units that are allocated for the bitset.
51 * @return A pointer to the initialized bitset.
53 static INLINE bitset_t *_bitset_prepare(void *area, unsigned units)
57 ptr->data = (bitset_unit_t *) (ptr + 1);
58 memset(ptr->data, 0, BS_UNIT_SIZE * units);
63 * Allocate a bitset on an obstack.
64 * @param obst The obstack.
65 * @param highest_bit The greatest bit that shall be stored in the set.
66 * @return A pointer to an empty initialized bitset.
68 #define bitset_obstack_alloc(obst,highest_bit) \
69 _bitset_prepare(obstack_alloc(obst, _bitset_overall_size(highest_bit)), _bitset_units(highest_bit))
72 * Allocate a bitset via malloc.
73 * @param highest_bit The greatest bit that shall be stored in the set.
74 * @return A pointer to an empty initialized bitset.
76 #define bitset_malloc(highest_bit) \
77 _bitset_prepare(malloc(_bitset_overall_size(highest_bit)), _bitset_units(highest_bit))
80 * Free a bitset allocated with bitset_malloc().
81 * @param bs The bitset.
83 #define bitset_free(bs) free(bs)
86 * Allocate a bitset on the stack via alloca.
87 * @param highest_bit The greatest bit that shall be stored in the set.
88 * @return A pointer to an empty initialized bitset.
90 #define bitset_alloca(highest_bit) \
91 _bitset_prepare(alloca(_bitset_overall_size(highest_bit)), _bitset_units(highest_bit))
94 * Print a bitset to a stream.
95 * The bitset is printed as a comma seperated list of bits set.
96 * @param file The stream.
97 * @param bs The bitset.
99 static INLINE void bitset_fprint(FILE *file, bitset_t *bs)
101 const char *prefix = "";
106 for(i = 0; i < bs->units; i++) {
108 bitset_unit_t unit = bs->data[i];
111 printf("%s%08x", prefix, unit);
115 for(j = 1; j != 0; j <<= 1, k++) {
117 fprintf(file, "%s%u", prefix, k);
126 * Get the unit which contains a specific bit.
127 * This function is internal.
128 * @param bs The bitset.
129 * @param bit The bit.
130 * @return A pointer to the unit containing the bit.
132 static INLINE bitset_unit_t *_bitset_get_unit(const bitset_t *bs, unsigned bit)
134 assert(bit < bs->units * BS_UNIT_SIZE_BITS && "Bit too large");
135 return bs->data + bit / BS_UNIT_SIZE_BITS;
139 * Set a bit in the bitset.
140 * @param bs The bitset.
141 * @param bit The bit to set.
143 static INLINE void bitset_set(bitset_t *bs, unsigned bit)
145 bitset_unit_t *unit = _bitset_get_unit(bs, bit);
146 _bitset_inside_set(unit, bit & BS_UNIT_MASK);
150 * Clear a bit in the bitset.
151 * @param bs The bitset.
152 * @param bit The bit to clear.
154 static INLINE void bitset_clear(bitset_t *bs, unsigned bit)
156 bitset_unit_t *unit = _bitset_get_unit(bs, bit);
157 _bitset_inside_clear(unit, bit & BS_UNIT_MASK);
161 * Flip a bit in a bitset.
162 * @param bs The bitset.
163 * @param bit The bit to flip.
165 static INLINE void bitset_flip(bitset_t *bs, unsigned bit)
167 bitset_unit_t *unit = _bitset_get_unit(bs, bit);
168 _bitset_inside_flip(unit, bit & BS_UNIT_MASK);
172 * Find the smallest bit set in the bitset.
173 * @param bs The bitset.
174 * @return The smallest bit set in the bitset.
176 static INLINE unsigned bitset_min(bitset_t *bs)
181 for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit) {
182 unsigned pos = _bitset_inside_ntz(unit);
185 ofs += BS_UNIT_SIZE_BITS;
192 * Find the greatest bit set in the bitset.
193 * @param bs The bitset.
194 * @return The greatest bit set in the bitset.
196 static INLINE unsigned bitset_max(bitset_t *bs)
198 unsigned i, max = 0, ofs = 0;
201 for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit) {
202 unsigned pos = _bitset_inside_nlz(unit);
205 ofs += BS_UNIT_SIZE_BITS;
212 * Count the bits set.
213 * This can also be seen as the cardinality of the set.
214 * @param bs The bitset.
215 * @return The number of bits set in the bitset.
217 static INLINE unsigned bitset_pop(bitset_t *bs)
222 for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit)
223 pop += _bitset_inside_pop(unit);
229 * Here, the binary operations follow.
230 * And, Or, And Not, Xor are available.
233 #define BINARY_OP(op) \
234 static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, bitset_t *src) \
237 int n = tgt->units > src->units ? src->units : tgt->units; \
238 bitset_unit_t *tgt_unit, *src_unit; \
239 src_unit = src->data; \
240 tgt_unit = tgt->data; \
241 for(i = 0; i < n; ++i) \
242 _bitset_inside_ ## op(tgt_unit++, src_unit++); \