2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief convenience layer over raw_bitsets (stores number of bits
10 * @author Matthias Braun
12 #ifndef FIRM_ADT_BITSET_H
13 #define FIRM_ADT_BITSET_H
22 #include "bitfiddle.h"
23 #include "raw_bitset.h"
25 typedef struct bitset_t {
26 size_t size; /**< size of the bitset in bits */
27 unsigned data[1]; /**< data (should be declared data[] but this is only
32 * return the number of bytes a bitset would need
34 static inline size_t bitset_total_size(size_t n_bits)
36 return sizeof(bitset_t) - sizeof(((bitset_t*)0)->data)
37 + BITSET_SIZE_BYTES(n_bits);
41 * initialize a bitset for bitsize size (bitset should point to memory
42 * with a size calculated by bitset_total_size)
44 static inline bitset_t *bitset_init(void *memory, size_t size)
46 bitset_t *result = (bitset_t*) memory;
48 rbitset_clear_all(result->data, size);
53 * Allocate a bitset on an obstack.
54 * @param obst The obstack.
55 * @param size The greatest bit that shall be stored in the set.
56 * @return A pointer to an empty initialized bitset.
58 static inline bitset_t *bitset_obstack_alloc(struct obstack *obst,
61 size_t size = bitset_total_size(n_bits);
62 void *memory = obstack_alloc(obst, size);
63 return bitset_init(memory, n_bits);
67 * Allocate a bitset via malloc.
68 * @param size The greatest bit that shall be stored in the set.
69 * @return A pointer to an empty initialized bitset.
71 static inline bitset_t *bitset_malloc(size_t n_bits)
73 size_t size = bitset_total_size(n_bits);
74 void *memory = xmalloc(size);
75 return bitset_init(memory, n_bits);
79 * Free a bitset allocated with bitset_malloc().
80 * @param bs The bitset.
82 static inline void bitset_free(bitset_t *bitset)
88 * Allocate a bitset on the stack via alloca.
89 * @param size The greatest bit that shall be stored in the set.
90 * @return A pointer to an empty initialized bitset.
92 #define bitset_alloca(size) \
93 bitset_init(alloca(bitset_total_size(size)), (size))
96 * Get the size of the bitset in bits.
97 * @note Note the difference between capacity and size.
98 * @param bs The bitset.
99 * @return The highest bit which can be set or cleared plus 1.
101 static inline size_t bitset_size(const bitset_t *bitset)
107 * Set a bit in the bitset.
108 * @param bs The bitset.
109 * @param bit The bit to set.
111 static inline void bitset_set(bitset_t *bs, size_t bit)
113 assert(bit < bs->size);
114 rbitset_set(bs->data, bit);
118 * Clear a bit in the bitset.
119 * @param bs The bitset.
120 * @param bit The bit to clear.
122 static inline void bitset_clear(bitset_t *bs, size_t bit)
124 assert(bit < bs->size);
125 rbitset_clear(bs->data, bit);
129 * Check, if a bit is set.
130 * @param bs The bitset.
131 * @param bit The bit to check for.
132 * @return 1, if the bit was set, 0 if not.
134 static inline bool bitset_is_set(const bitset_t *bs, size_t bit)
136 assert(bit < bs->size);
137 return rbitset_is_set(bs->data, bit);
141 * Flip a bit in a bitset.
142 * @param bs The bitset.
143 * @param bit The bit to flip.
145 static inline void bitset_flip(bitset_t *bs, size_t bit)
147 assert(bit < bs->size);
148 rbitset_flip(bs->data, bit);
152 * Flip the whole bitset.
153 * @param bs The bitset.
155 static inline void bitset_flip_all(bitset_t *bs)
157 rbitset_flip_all(bs->data, bs->size);
161 * Copy a bitset to another. Both bitset must be initialized and have the same
163 * @param tgt The target bitset.
164 * @param src The source bitset.
165 * @return The target bitset.
167 static inline void bitset_copy(bitset_t *tgt, const bitset_t *src)
169 assert(tgt->size == src->size);
170 rbitset_copy(tgt->data, src->data, src->size);
173 static inline void bitset_copy_into(bitset_t *tgt, const bitset_t *src)
175 assert(tgt->size >= src->size);
176 rbitset_copy_into(tgt->data, src->data, src->size);
180 * Find the next unset bit from a given bit.
181 * @note Note that if pos is unset, pos is returned.
182 * @param bs The bitset.
183 * @param pos The bit from which to search for the next set bit.
184 * @return The next set bit from pos on, or (size_t)-1, if no unset bit was
187 static inline size_t bitset_next_clear(const bitset_t *bs, size_t pos)
189 return rbitset_next_max(bs->data, pos, bs->size, false);
193 * Find the next set bit from a given bit.
194 * @note Note that if pos is set, pos is returned.
195 * @param bs The bitset.
196 * @param pos The bit from which to search for the next set bit.
197 * @return The next set bit from pos on, or (size_t)-1, if no set bit was
200 static inline size_t bitset_next_set(const bitset_t *bs, size_t pos)
202 return rbitset_next_max(bs->data, pos, bs->size, true);
206 * Convenience macro for bitset iteration.
207 * @param bitset The bitset.
208 * @param elm A size_t variable.
210 #define bitset_foreach(bitset, elm) \
211 for (size_t elm = 0; (elm = bitset_next_set((bitset), elm)) != (size_t)-1; ++elm)
214 #define bitset_foreach_clear(bitset, elm) \
215 for (size_t elm = 0; (elm = bitset_next_clear((bitset), elm)) != (size_t)-1; ++elm)
218 * Count the bits set.
219 * This can also be seen as the cardinality of the set.
220 * @param bs The bitset.
221 * @return The number of bits set in the bitset.
223 static inline size_t bitset_popcount(const bitset_t *bs)
225 return rbitset_popcount(bs->data, bs->size);
230 * This sets all bits to zero.
231 * @param bs The bitset.
233 static inline void bitset_clear_all(bitset_t *bs)
235 rbitset_clear_all(bs->data, bs->size);
240 * This sets all bits to one.
241 * @param bs The bitset.
243 static inline void bitset_set_all(bitset_t *bs)
245 rbitset_set_all(bs->data, bs->size);
249 * Check, if one bitset is contained by another.
250 * That is, each bit set in lhs is also set in rhs.
251 * @param lhs A bitset.
252 * @param rhs Another bitset.
253 * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
255 static inline bool bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
257 assert(lhs->size == rhs->size);
258 return rbitset_contains(lhs->data, rhs->data, lhs->size);
262 * Treat the bitset as a number and subtract 1.
263 * @param bs The bitset.
264 * @return The same bitset.
266 static inline void bitset_minus1(bitset_t *bs)
268 rbitset_minus1(bs->data, bs->size);
272 * Check if two bitsets intersect.
273 * @param a The first bitset.
274 * @param b The second bitset.
275 * @return 1 if they have a bit in common, 0 if not.
277 static inline bool bitset_intersect(const bitset_t *a, const bitset_t *b)
279 assert(a->size == b->size);
280 return rbitsets_have_common(a->data, b->data, a->size);
284 * set or clear all bits in the range [from;to[.
285 * @param a The bitset.
286 * @param from The first index to set to one.
287 * @param to The last index plus one to set to one.
288 * @param do_set If 1 the bits are set, if 0, they are cleared.
290 static inline void bitset_mod_range(bitset_t *a, size_t from, size_t to,
305 rbitset_set_range(a->data, from, to, do_set);
308 #define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1)
309 #define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
312 * Check, if a bitset is empty.
313 * @param a The bitset.
314 * @return 1, if the bitset is empty, 0 if not.
316 static inline bool bitset_is_empty(const bitset_t *bs)
318 return rbitset_is_empty(bs->data, bs->size);
322 * Print a bitset to a stream.
323 * The bitset is printed as a comma separated list of bits set.
324 * @param file The stream.
325 * @param bs The bitset.
327 static inline void bitset_fprint(FILE *file, const bitset_t *bs)
329 const char *prefix = "";
333 for(i = bitset_next_set(bs, 0); i != (size_t)-1; i = bitset_next_set(bs, i + 1)) {
334 ir_fprintf(file, "%s%zu", prefix, i);
341 * Perform tgt = tgt & src operation.
342 * @param tgt The target bitset.
343 * @param src The source bitset.
344 * @return the tgt set.
346 static inline void bitset_and(bitset_t *tgt, const bitset_t *src)
348 assert(tgt->size == src->size);
349 rbitset_and(tgt->data, src->data, src->size);
353 * Perform tgt = tgt & ~src operation.
354 * @param tgt The target bitset.
355 * @param src The source bitset.
356 * @return the tgt set.
358 static inline void bitset_andnot(bitset_t *tgt, const bitset_t *src)
360 assert(tgt->size == src->size);
361 rbitset_andnot(tgt->data, src->data, src->size);
365 * Perform Union, tgt = tgt u src operation.
366 * @param tgt The target bitset.
367 * @param src The source bitset.
368 * @return the tgt set.
370 static inline void bitset_or(bitset_t *tgt, const bitset_t *src)
372 assert(tgt->size == src->size);
373 rbitset_or(tgt->data, src->data, src->size);
377 * Perform tgt = tgt ^ src operation.
378 * @param tgt The target bitset.
379 * @param src The source bitset.
380 * @return the tgt set.
382 static inline void bitset_xor(bitset_t *tgt, const bitset_t *src)
384 assert(tgt->size == src->size);
385 rbitset_xor(tgt->data, src->data, src->size);
389 * Copy a raw bitset into an bitset.
391 static inline void rbitset_copy_to_bitset(const unsigned *rbitset,
394 rbitset_copy(bitset->data, rbitset, bitset->size);