2 * Copyright (C) 1995-2008 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
36 #include "bitfiddle.h"
37 #include "raw_bitset.h"
39 typedef struct bitset_t {
40 size_t size; /**< size of the bitset in bits */
41 unsigned data[1]; /**< data (should be declared data[] but this is only
46 * return the number of bytes a bitset would need
48 static inline size_t bitset_total_size(size_t n_bits)
50 return sizeof(bitset_t) - sizeof(((bitset_t*)0)->data)
51 + BITSET_SIZE_BYTES(n_bits);
55 * initialize a bitset for bitsize size (bitset should point to memory
56 * with a size calculated by bitset_total_size)
58 static inline bitset_t *bitset_init(void *memory, size_t size)
60 bitset_t *result = (bitset_t*) memory;
62 rbitset_clear_all(result->data, size);
67 * Allocate a bitset on an obstack.
68 * @param obst The obstack.
69 * @param size The greatest bit that shall be stored in the set.
70 * @return A pointer to an empty initialized bitset.
72 static inline bitset_t *bitset_obstack_alloc(struct obstack *obst,
75 size_t size = bitset_total_size(n_bits);
76 void *memory = obstack_alloc(obst, size);
77 return bitset_init(memory, n_bits);
81 * Allocate a bitset via malloc.
82 * @param size The greatest bit that shall be stored in the set.
83 * @return A pointer to an empty initialized bitset.
85 static inline bitset_t *bitset_malloc(size_t n_bits)
87 size_t size = bitset_total_size(n_bits);
88 void *memory = xmalloc(size);
89 return bitset_init(memory, n_bits);
93 * Free a bitset allocated with bitset_malloc().
94 * @param bs The bitset.
96 static inline void bitset_free(bitset_t *bitset)
102 * Allocate a bitset on the stack via alloca.
103 * @param size The greatest bit that shall be stored in the set.
104 * @return A pointer to an empty initialized bitset.
106 #define bitset_alloca(size) \
107 bitset_init(alloca(bitset_total_size(size)), (size))
110 * Get the size of the bitset in bits.
111 * @note Note the difference between capacity and size.
112 * @param bs The bitset.
113 * @return The highest bit which can be set or cleared plus 1.
115 static inline size_t bitset_size(const bitset_t *bitset)
121 * Set a bit in the bitset.
122 * @param bs The bitset.
123 * @param bit The bit to set.
125 static inline void bitset_set(bitset_t *bs, size_t bit)
127 assert(bit < bs->size);
128 rbitset_set(bs->data, bit);
132 * Clear a bit in the bitset.
133 * @param bs The bitset.
134 * @param bit The bit to clear.
136 static inline void bitset_clear(bitset_t *bs, size_t bit)
138 assert(bit < bs->size);
139 rbitset_clear(bs->data, bit);
143 * Check, if a bit is set.
144 * @param bs The bitset.
145 * @param bit The bit to check for.
146 * @return 1, if the bit was set, 0 if not.
148 static inline bool bitset_is_set(const bitset_t *bs, size_t bit)
150 assert(bit < bs->size);
151 return rbitset_is_set(bs->data, bit);
155 * Flip a bit in a bitset.
156 * @param bs The bitset.
157 * @param bit The bit to flip.
159 static inline void bitset_flip(bitset_t *bs, size_t bit)
161 assert(bit < bs->size);
162 rbitset_flip(bs->data, bit);
166 * Flip the whole bitset.
167 * @param bs The bitset.
169 static inline void bitset_flip_all(bitset_t *bs)
171 rbitset_flip_all(bs->data, bs->size);
175 * Copy a bitset to another. Both bitset must be initialized and have the same
177 * @param tgt The target bitset.
178 * @param src The source bitset.
179 * @return The target bitset.
181 static inline void bitset_copy(bitset_t *tgt, const bitset_t *src)
183 assert(tgt->size == src->size);
184 rbitset_copy(tgt->data, src->data, src->size);
187 static inline void bitset_copy_into(bitset_t *tgt, const bitset_t *src)
189 assert(tgt->size >= src->size);
190 rbitset_copy_into(tgt->data, src->data, src->size);
194 * Find the next unset bit from a given bit.
195 * @note Note that if pos is unset, pos is returned.
196 * @param bs The bitset.
197 * @param pos The bit from which to search for the next set bit.
198 * @return The next set bit from pos on, or (size_t)-1, if no unset bit was
201 static inline size_t bitset_next_clear(const bitset_t *bs, size_t pos)
205 return rbitset_next_max(bs->data, pos, bs->size, false);
209 * Find the next set bit from a given bit.
210 * @note Note that if pos is set, pos is returned.
211 * @param bs The bitset.
212 * @param pos The bit from which to search for the next set bit.
213 * @return The next set bit from pos on, or (size_t)-1, if no set bit was
216 static inline size_t bitset_next_set(const bitset_t *bs, size_t pos)
220 return rbitset_next_max(bs->data, pos, bs->size, true);
224 * Convenience macro for bitset iteration.
225 * @param bitset The bitset.
226 * @param elm A size_t variable.
228 #define bitset_foreach(bitset,elm) \
229 for(elm = bitset_next_set(bitset,0); elm != (size_t)-1; elm = bitset_next_set(bitset,elm+1))
232 #define bitset_foreach_clear(bitset,elm) \
233 for(elm = bitset_next_clear(bitset,0); elm != (size_t) -1; elm = bitset_next_clear(bitset,elm+1))
236 * Count the bits set.
237 * This can also be seen as the cardinality of the set.
238 * @param bs The bitset.
239 * @return The number of bits set in the bitset.
241 static inline size_t bitset_popcount(const bitset_t *bs)
243 return rbitset_popcount(bs->data, bs->size);
248 * This sets all bits to zero.
249 * @param bs The bitset.
251 static inline void bitset_clear_all(bitset_t *bs)
253 rbitset_clear_all(bs->data, bs->size);
258 * This sets all bits to one.
259 * @param bs The bitset.
261 static inline void bitset_set_all(bitset_t *bs)
263 rbitset_set_all(bs->data, bs->size);
267 * Check, if one bitset is contained by another.
268 * That is, each bit set in lhs is also set in rhs.
269 * @param lhs A bitset.
270 * @param rhs Another bitset.
271 * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
273 static inline bool bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
275 assert(lhs->size == rhs->size);
276 return rbitset_contains(lhs->data, rhs->data, lhs->size);
280 * Treat the bitset as a number and subtract 1.
281 * @param bs The bitset.
282 * @return The same bitset.
284 static inline void bitset_minus1(bitset_t *bs)
286 rbitset_minus1(bs->data, bs->size);
290 * Check if two bitsets intersect.
291 * @param a The first bitset.
292 * @param b The second bitset.
293 * @return 1 if they have a bit in common, 0 if not.
295 static inline bool bitset_intersect(const bitset_t *a, const bitset_t *b)
297 assert(a->size == b->size);
298 return rbitsets_have_common(a->data, b->data, a->size);
302 * set or clear all bits in the range [from;to[.
303 * @param a The bitset.
304 * @param from The first index to set to one.
305 * @param to The last index plus one to set to one.
306 * @param do_set If 1 the bits are set, if 0, they are cleared.
308 static inline void bitset_mod_range(bitset_t *a, size_t from, size_t to,
323 rbitset_set_range(a->data, from, to, do_set);
326 #define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1)
327 #define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
330 * Check, if a bitset is empty.
331 * @param a The bitset.
332 * @return 1, if the bitset is empty, 0 if not.
334 static inline bool bitset_is_empty(const bitset_t *bs)
336 return rbitset_is_empty(bs->data, bs->size);
340 * Print a bitset to a stream.
341 * The bitset is printed as a comma separated list of bits set.
342 * @param file The stream.
343 * @param bs The bitset.
345 static inline void bitset_fprint(FILE *file, const bitset_t *bs)
347 const char *prefix = "";
351 for(i = bitset_next_set(bs, 0); i != (size_t)-1; i = bitset_next_set(bs, i + 1)) {
352 fprintf(file, "%s%lu", prefix, (unsigned long) i);
359 * Perform tgt = tgt & src operation.
360 * @param tgt The target bitset.
361 * @param src The source bitset.
362 * @return the tgt set.
364 static inline void bitset_and(bitset_t *tgt, const bitset_t *src)
366 assert(tgt->size == src->size);
367 rbitset_and(tgt->data, src->data, src->size);
371 * Perform tgt = tgt & ~src operation.
372 * @param tgt The target bitset.
373 * @param src The source bitset.
374 * @return the tgt set.
376 static inline void bitset_andnot(bitset_t *tgt, const bitset_t *src)
378 assert(tgt->size == src->size);
379 rbitset_andnot(tgt->data, src->data, src->size);
383 * Perform Union, tgt = tgt u src operation.
384 * @param tgt The target bitset.
385 * @param src The source bitset.
386 * @return the tgt set.
388 static inline void bitset_or(bitset_t *tgt, const bitset_t *src)
390 assert(tgt->size == src->size);
391 rbitset_or(tgt->data, src->data, src->size);
395 * Perform tgt = tgt ^ src operation.
396 * @param tgt The target bitset.
397 * @param src The source bitset.
398 * @return the tgt set.
400 static inline void bitset_xor(bitset_t *tgt, const bitset_t *src)
402 assert(tgt->size == src->size);
403 rbitset_xor(tgt->data, src->data, src->size);
407 * Copy a raw bitset into an bitset.
409 static inline void rbitset_copy_to_bitset(const unsigned *rbitset,
412 rbitset_copy(bitset->data, rbitset, bitset->size);