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 unsigned 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(unsigned 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, unsigned 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(unsigned 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 unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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);
188 * Find the next unset bit from a given bit.
189 * @note Note that if pos is unset, pos is returned.
190 * @param bs The bitset.
191 * @param pos The bit from which to search for the next set bit.
192 * @return The next set bit from pos on, or (unsigned)-1, if no unset bit was
195 static inline unsigned bitset_next_clear(const bitset_t *bs, unsigned pos)
199 return rbitset_next_max(bs->data, pos, bs->size, false);
203 * Find the next set bit from a given bit.
204 * @note Note that if pos is set, pos is returned.
205 * @param bs The bitset.
206 * @param pos The bit from which to search for the next set bit.
207 * @return The next set bit from pos on, or (unsigned)-1, if no set bit was
210 static inline unsigned bitset_next_set(const bitset_t *bs, unsigned pos)
214 return rbitset_next_max(bs->data, pos, bs->size, true);
218 * Convenience macro for bitset iteration.
219 * @param bitset The bitset.
220 * @param elm A unsigned long variable.
222 #define bitset_foreach(bitset,elm) \
223 for(elm = bitset_next_set(bitset,0); elm != (unsigned) -1; elm = bitset_next_set(bitset,elm+1))
226 #define bitset_foreach_clear(bitset,elm) \
227 for(elm = bitset_next_clear(bitset,0); elm != (unsigned) -1; elm = bitset_next_clear(bitset,elm+1))
230 * Count the bits set.
231 * This can also be seen as the cardinality of the set.
232 * @param bs The bitset.
233 * @return The number of bits set in the bitset.
235 static inline unsigned bitset_popcount(const bitset_t *bs)
237 return rbitset_popcount(bs->data, bs->size);
242 * This sets all bits to zero.
243 * @param bs The bitset.
245 static inline void bitset_clear_all(bitset_t *bs)
247 rbitset_clear_all(bs->data, bs->size);
252 * This sets all bits to one.
253 * @param bs The bitset.
255 static inline void bitset_set_all(bitset_t *bs)
257 rbitset_set_all(bs->data, bs->size);
261 * Check, if one bitset is contained by another.
262 * That is, each bit set in lhs is also set in rhs.
263 * @param lhs A bitset.
264 * @param rhs Another bitset.
265 * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
267 static inline bool bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
269 assert(lhs->size == rhs->size);
270 return rbitset_contains(lhs->data, rhs->data, lhs->size);
274 * Treat the bitset as a number and subtract 1.
275 * @param bs The bitset.
276 * @return The same bitset.
278 static inline void bitset_minus1(bitset_t *bs)
280 rbitset_minus1(bs->data, bs->size);
284 * Check if two bitsets intersect.
285 * @param a The first bitset.
286 * @param b The second bitset.
287 * @return 1 if they have a bit in common, 0 if not.
289 static inline bool bitset_intersect(const bitset_t *a, const bitset_t *b)
291 assert(a->size == b->size);
292 return rbitsets_have_common(a->data, b->data, a->size);
296 * set or clear all bits in the range [from;to[.
297 * @param a The bitset.
298 * @param from The first index to set to one.
299 * @param to The last index plus one to set to one.
300 * @param do_set If 1 the bits are set, if 0, they are cleared.
302 static inline void bitset_mod_range(bitset_t *a, unsigned from, unsigned to,
317 rbitset_set_range(a->data, from, to, do_set);
320 #define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1)
321 #define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
324 * Check, if a bitset is empty.
325 * @param a The bitset.
326 * @return 1, if the bitset is empty, 0 if not.
328 static inline bool bitset_is_empty(const bitset_t *bs)
330 return rbitset_is_empty(bs->data, bs->size);
334 * Print a bitset to a stream.
335 * The bitset is printed as a comma separated list of bits set.
336 * @param file The stream.
337 * @param bs The bitset.
339 static inline void bitset_fprint(FILE *file, const bitset_t *bs)
341 const char *prefix = "";
345 for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) {
346 fprintf(file, "%s%d", prefix, i);
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_and(bitset_t *tgt, const bitset_t *src)
360 assert(tgt->size == src->size);
361 rbitset_and(tgt->data, src->data, src->size);
365 * Perform tgt = tgt & ~src operation.
366 * @param tgt The target bitset.
367 * @param src The source bitset.
368 * @return the tgt set.
370 static inline void bitset_andnot(bitset_t *tgt, const bitset_t *src)
372 assert(tgt->size == src->size);
373 rbitset_andnot(tgt->data, src->data, src->size);
377 * Perform Union, tgt = tgt u src operation.
378 * @param tgt The target bitset.
379 * @param src The source bitset.
380 * @return the tgt set.
382 static inline void bitset_or(bitset_t *tgt, const bitset_t *src)
384 assert(tgt->size == src->size);
385 rbitset_or(tgt->data, src->data, src->size);
389 * Perform tgt = tgt ^ src operation.
390 * @param tgt The target bitset.
391 * @param src The source bitset.
392 * @return the tgt set.
394 static inline void bitset_xor(bitset_t *tgt, const bitset_t *src)
396 assert(tgt->size == src->size);
397 rbitset_xor(tgt->data, src->data, src->size);
401 * Copy a raw bitset into an bitset.
403 static inline void rbitset_copy_to_bitset(const unsigned *rbitset,
406 rbitset_copy(bitset->data, rbitset, bitset->size);