2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief convenience layer over raw_bitsets (stores number of bits
24 * @author Matthias Braun
27 #ifndef FIRM_ADT_BITSET_H
28 #define FIRM_ADT_BITSET_H
37 #include "bitfiddle.h"
38 #include "raw_bitset.h"
40 typedef struct bitset_t {
41 size_t size; /**< size of the bitset in bits */
42 unsigned data[1]; /**< data (should be declared data[] but this is only
47 * return the number of bytes a bitset would need
49 static inline size_t bitset_total_size(size_t n_bits)
51 return sizeof(bitset_t) - sizeof(((bitset_t*)0)->data)
52 + BITSET_SIZE_BYTES(n_bits);
56 * initialize a bitset for bitsize size (bitset should point to memory
57 * with a size calculated by bitset_total_size)
59 static inline bitset_t *bitset_init(void *memory, size_t size)
61 bitset_t *result = (bitset_t*) memory;
63 rbitset_clear_all(result->data, size);
68 * Allocate a bitset on an obstack.
69 * @param obst The obstack.
70 * @param size The greatest bit that shall be stored in the set.
71 * @return A pointer to an empty initialized bitset.
73 static inline bitset_t *bitset_obstack_alloc(struct obstack *obst,
76 size_t size = bitset_total_size(n_bits);
77 void *memory = obstack_alloc(obst, size);
78 return bitset_init(memory, n_bits);
82 * Allocate a bitset via malloc.
83 * @param size The greatest bit that shall be stored in the set.
84 * @return A pointer to an empty initialized bitset.
86 static inline bitset_t *bitset_malloc(size_t n_bits)
88 size_t size = bitset_total_size(n_bits);
89 void *memory = xmalloc(size);
90 return bitset_init(memory, n_bits);
94 * Free a bitset allocated with bitset_malloc().
95 * @param bs The bitset.
97 static inline void bitset_free(bitset_t *bitset)
103 * Allocate a bitset on the stack via alloca.
104 * @param size The greatest bit that shall be stored in the set.
105 * @return A pointer to an empty initialized bitset.
107 #define bitset_alloca(size) \
108 bitset_init(alloca(bitset_total_size(size)), (size))
111 * Get the size of the bitset in bits.
112 * @note Note the difference between capacity and size.
113 * @param bs The bitset.
114 * @return The highest bit which can be set or cleared plus 1.
116 static inline size_t bitset_size(const bitset_t *bitset)
122 * Set a bit in the bitset.
123 * @param bs The bitset.
124 * @param bit The bit to set.
126 static inline void bitset_set(bitset_t *bs, size_t bit)
128 assert(bit < bs->size);
129 rbitset_set(bs->data, bit);
133 * Clear a bit in the bitset.
134 * @param bs The bitset.
135 * @param bit The bit to clear.
137 static inline void bitset_clear(bitset_t *bs, size_t bit)
139 assert(bit < bs->size);
140 rbitset_clear(bs->data, bit);
144 * Check, if a bit is set.
145 * @param bs The bitset.
146 * @param bit The bit to check for.
147 * @return 1, if the bit was set, 0 if not.
149 static inline bool bitset_is_set(const bitset_t *bs, size_t bit)
151 assert(bit < bs->size);
152 return rbitset_is_set(bs->data, bit);
156 * Flip a bit in a bitset.
157 * @param bs The bitset.
158 * @param bit The bit to flip.
160 static inline void bitset_flip(bitset_t *bs, size_t bit)
162 assert(bit < bs->size);
163 rbitset_flip(bs->data, bit);
167 * Flip the whole bitset.
168 * @param bs The bitset.
170 static inline void bitset_flip_all(bitset_t *bs)
172 rbitset_flip_all(bs->data, bs->size);
176 * Copy a bitset to another. Both bitset must be initialized and have the same
178 * @param tgt The target bitset.
179 * @param src The source bitset.
180 * @return The target bitset.
182 static inline void bitset_copy(bitset_t *tgt, const bitset_t *src)
184 assert(tgt->size == src->size);
185 rbitset_copy(tgt->data, src->data, src->size);
188 static inline void bitset_copy_into(bitset_t *tgt, const bitset_t *src)
190 assert(tgt->size >= src->size);
191 rbitset_copy_into(tgt->data, src->data, src->size);
195 * Find the next unset bit from a given bit.
196 * @note Note that if pos is unset, pos is returned.
197 * @param bs The bitset.
198 * @param pos The bit from which to search for the next set bit.
199 * @return The next set bit from pos on, or (size_t)-1, if no unset bit was
202 static inline size_t bitset_next_clear(const bitset_t *bs, size_t pos)
206 return rbitset_next_max(bs->data, pos, bs->size, false);
210 * Find the next set bit from a given bit.
211 * @note Note that if pos is set, pos is returned.
212 * @param bs The bitset.
213 * @param pos The bit from which to search for the next set bit.
214 * @return The next set bit from pos on, or (size_t)-1, if no set bit was
217 static inline size_t bitset_next_set(const bitset_t *bs, size_t pos)
221 return rbitset_next_max(bs->data, pos, bs->size, true);
225 * Convenience macro for bitset iteration.
226 * @param bitset The bitset.
227 * @param elm A size_t variable.
229 #define bitset_foreach(bitset,elm) \
230 for(elm = bitset_next_set(bitset,0); elm != (size_t)-1; elm = bitset_next_set(bitset,elm+1))
233 #define bitset_foreach_clear(bitset,elm) \
234 for(elm = bitset_next_clear(bitset,0); elm != (size_t) -1; elm = bitset_next_clear(bitset,elm+1))
237 * Count the bits set.
238 * This can also be seen as the cardinality of the set.
239 * @param bs The bitset.
240 * @return The number of bits set in the bitset.
242 static inline size_t bitset_popcount(const bitset_t *bs)
244 return rbitset_popcount(bs->data, bs->size);
249 * This sets all bits to zero.
250 * @param bs The bitset.
252 static inline void bitset_clear_all(bitset_t *bs)
254 rbitset_clear_all(bs->data, bs->size);
259 * This sets all bits to one.
260 * @param bs The bitset.
262 static inline void bitset_set_all(bitset_t *bs)
264 rbitset_set_all(bs->data, bs->size);
268 * Check, if one bitset is contained by another.
269 * That is, each bit set in lhs is also set in rhs.
270 * @param lhs A bitset.
271 * @param rhs Another bitset.
272 * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
274 static inline bool bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
276 assert(lhs->size == rhs->size);
277 return rbitset_contains(lhs->data, rhs->data, lhs->size);
281 * Treat the bitset as a number and subtract 1.
282 * @param bs The bitset.
283 * @return The same bitset.
285 static inline void bitset_minus1(bitset_t *bs)
287 rbitset_minus1(bs->data, bs->size);
291 * Check if two bitsets intersect.
292 * @param a The first bitset.
293 * @param b The second bitset.
294 * @return 1 if they have a bit in common, 0 if not.
296 static inline bool bitset_intersect(const bitset_t *a, const bitset_t *b)
298 assert(a->size == b->size);
299 return rbitsets_have_common(a->data, b->data, a->size);
303 * set or clear all bits in the range [from;to[.
304 * @param a The bitset.
305 * @param from The first index to set to one.
306 * @param to The last index plus one to set to one.
307 * @param do_set If 1 the bits are set, if 0, they are cleared.
309 static inline void bitset_mod_range(bitset_t *a, size_t from, size_t to,
324 rbitset_set_range(a->data, from, to, do_set);
327 #define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1)
328 #define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
331 * Check, if a bitset is empty.
332 * @param a The bitset.
333 * @return 1, if the bitset is empty, 0 if not.
335 static inline bool bitset_is_empty(const bitset_t *bs)
337 return rbitset_is_empty(bs->data, bs->size);
341 * Print a bitset to a stream.
342 * The bitset is printed as a comma separated list of bits set.
343 * @param file The stream.
344 * @param bs The bitset.
346 static inline void bitset_fprint(FILE *file, const bitset_t *bs)
348 const char *prefix = "";
352 for(i = bitset_next_set(bs, 0); i != (size_t)-1; i = bitset_next_set(bs, i + 1)) {
353 ir_fprintf(file, "%s%zu", prefix, i);
360 * Perform tgt = tgt & src operation.
361 * @param tgt The target bitset.
362 * @param src The source bitset.
363 * @return the tgt set.
365 static inline void bitset_and(bitset_t *tgt, const bitset_t *src)
367 assert(tgt->size == src->size);
368 rbitset_and(tgt->data, src->data, src->size);
372 * Perform tgt = tgt & ~src operation.
373 * @param tgt The target bitset.
374 * @param src The source bitset.
375 * @return the tgt set.
377 static inline void bitset_andnot(bitset_t *tgt, const bitset_t *src)
379 assert(tgt->size == src->size);
380 rbitset_andnot(tgt->data, src->data, src->size);
384 * Perform Union, tgt = tgt u src operation.
385 * @param tgt The target bitset.
386 * @param src The source bitset.
387 * @return the tgt set.
389 static inline void bitset_or(bitset_t *tgt, const bitset_t *src)
391 assert(tgt->size == src->size);
392 rbitset_or(tgt->data, src->data, src->size);
396 * Perform tgt = tgt ^ src operation.
397 * @param tgt The target bitset.
398 * @param src The source bitset.
399 * @return the tgt set.
401 static inline void bitset_xor(bitset_t *tgt, const bitset_t *src)
403 assert(tgt->size == src->size);
404 rbitset_xor(tgt->data, src->data, src->size);
408 * Copy a raw bitset into an bitset.
410 static inline void rbitset_copy_to_bitset(const unsigned *rbitset,
413 rbitset_copy(bitset->data, rbitset, bitset->size);