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 A bitset implementation.
23 * @author Sebastian Hack
27 #ifndef FIRM_ADT_BITSET_H
28 #define FIRM_ADT_BITSET_H
36 #include "bitfiddle.h"
38 typedef unsigned int bitset_pos_t;
40 #include "bitset_std.h"
42 #if defined(__GNUC__) && defined(__i386__)
43 #include "bitset_ia32.h"
46 typedef struct _bitset_t {
51 #define BS_UNIT_SIZE sizeof(bitset_unit_t)
52 #define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8)
53 #define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1)
55 #define BS_DATA(bs) ((bitset_unit_t *) ((char *) (bs) + sizeof(bitset_t)))
56 #define BS_UNITS(bits) (round_up2(bits, BS_UNIT_SIZE_BITS) / BS_UNIT_SIZE_BITS)
57 #define BS_TOTAL_SIZE(bits) (sizeof(bitset_t) + BS_UNITS(bits) * BS_UNIT_SIZE)
60 * Initialize a bitset.
61 * This functions should not be called.
63 * Note that this function needs three macros which must be provided by the
64 * bitfield implementor:
65 * - _bitset_overall_size(size) The overall size that must be
66 * allocated for the bitfield in bytes.
67 * - _bitset_units(size) The number of units that will be
68 * present in the bitfield for a given highest bit.
69 * - _bitset_data_ptr(data, size) This produces as pointer to the
70 * first unit in the allocated memory area. The main reason for this
71 * macro is, that some bitset implementors want control over memory
74 * @param area A pointer to memory reserved for the bitset.
75 * @param size The size of the bitset in bits.
76 * @return A pointer to the initialized bitset.
78 static inline bitset_t *_bitset_prepare(void *area, bitset_pos_t size)
81 memset(ptr, 0, BS_TOTAL_SIZE(size));
82 ptr->units = BS_UNITS(size);
88 * Mask out all bits, which are only there, because the number
89 * of bits in the set didn't match a unit size boundary.
90 * @param bs The bitset.
91 * @return The masked bitset.
93 static inline bitset_t *_bitset_mask_highest(bitset_t *bs)
95 bitset_pos_t rest = bs->size & BS_UNIT_MASK;
97 BS_DATA(bs)[bs->units - 1] &= (1 << rest) - 1;
102 * Get the capacity of the bitset in bits.
103 * @param bs The bitset.
104 * @return The capacity in bits of the bitset.
106 #define bitset_capacity(bs) ((bs)->units * BS_UNIT_SIZE_BITS)
109 * Get the size of the bitset in bits.
110 * @note Note the difference between capacity and size.
111 * @param bs The bitset.
112 * @return The highest bit which can be set or cleared plus 1.
114 #define bitset_size(bs) ((bs)->size)
117 * Allocate a bitset on an obstack.
118 * @param obst The obstack.
119 * @param size The greatest bit that shall be stored in the set.
120 * @return A pointer to an empty initialized bitset.
122 #define bitset_obstack_alloc(obst,size) \
123 _bitset_prepare(obstack_alloc(obst, BS_TOTAL_SIZE(size)), size)
126 * Allocate a bitset via malloc.
127 * @param size The greatest bit that shall be stored in the set.
128 * @return A pointer to an empty initialized bitset.
130 #define bitset_malloc(size) \
131 _bitset_prepare(xmalloc(BS_TOTAL_SIZE(size)), size)
134 * Free a bitset allocated with bitset_malloc().
135 * @param bs The bitset.
137 #define bitset_free(bs) free(bs)
140 * Allocate a bitset on the stack via alloca.
141 * @param size The greatest bit that shall be stored in the set.
142 * @return A pointer to an empty initialized bitset.
144 #define bitset_alloca(size) \
145 _bitset_prepare(alloca(BS_TOTAL_SIZE(size)), size)
149 * Get the unit which contains a specific bit.
150 * This function is internal.
151 * @param bs The bitset.
152 * @param bit The bit.
153 * @return A pointer to the unit containing the bit.
155 static inline bitset_unit_t *_bitset_get_unit(const bitset_t *bs, bitset_pos_t bit)
157 assert(bit <= bs->size && "Bit to large");
158 return BS_DATA(bs) + bit / BS_UNIT_SIZE_BITS;
162 * Set a bit in the bitset.
163 * @param bs The bitset.
164 * @param bit The bit to set.
166 static inline void bitset_set(bitset_t *bs, bitset_pos_t bit)
168 bitset_unit_t *unit = _bitset_get_unit(bs, bit);
169 _bitset_inside_set(unit, bit & BS_UNIT_MASK);
173 * Clear a bit in the bitset.
174 * @param bs The bitset.
175 * @param bit The bit to clear.
177 static inline void bitset_clear(bitset_t *bs, bitset_pos_t bit)
179 bitset_unit_t *unit = _bitset_get_unit(bs, bit);
180 _bitset_inside_clear(unit, bit & BS_UNIT_MASK);
184 * Check, if a bit is set.
185 * @param bs The bitset.
186 * @param bit The bit to check for.
187 * @return 1, if the bit was set, 0 if not.
189 static inline int bitset_is_set(const bitset_t *bs, bitset_pos_t bit)
191 bitset_unit_t *unit = _bitset_get_unit(bs, bit);
192 return _bitset_inside_is_set(unit, bit & BS_UNIT_MASK);
196 * Flip a bit in a bitset.
197 * @param bs The bitset.
198 * @param bit The bit to flip.
200 static inline void bitset_flip(bitset_t *bs, bitset_pos_t bit)
202 bitset_unit_t *unit = _bitset_get_unit(bs, bit);
203 _bitset_inside_flip(unit, bit & BS_UNIT_MASK);
207 * Flip the whole bitset.
208 * @param bs The bitset.
210 static inline void bitset_flip_all(bitset_t *bs)
213 for(i = 0; i < bs->units; i++)
214 _bitset_inside_flip_unit(&BS_DATA(bs)[i]);
215 _bitset_mask_highest(bs);
219 * Copy a bitset to another.
220 * @param tgt The target bitset.
221 * @param src The source bitset.
222 * @return The target bitset.
224 static inline bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src)
226 bitset_pos_t tu = tgt->units;
227 bitset_pos_t su = src->units;
228 bitset_pos_t min_units = tu < su ? tu : su;
229 memcpy(BS_DATA(tgt), BS_DATA(src), min_units * BS_UNIT_SIZE);
231 memset(BS_DATA(tgt) + min_units, 0, BS_UNIT_SIZE * (tu - min_units));
232 return _bitset_mask_highest(tgt);
236 * Find the next set bit from a given bit.
237 * @note Note that if pos is set, pos is returned.
238 * @param bs The bitset.
239 * @param pos The bit from which to search for the next set bit.
240 * @return The next set bit from pos on, or -1, if no set bit was found
243 static inline bitset_pos_t _bitset_next(const bitset_t *bs,
244 bitset_pos_t pos, int set)
246 bitset_pos_t unit_number = pos / BS_UNIT_SIZE_BITS;
253 bitset_pos_t bit_in_unit = pos & BS_UNIT_MASK;
254 bitset_pos_t in_unit_mask = (1 << bit_in_unit) - 1;
257 * Mask out the bits smaller than pos in the current unit.
258 * We are only interested in bits set higher than pos.
260 bitset_unit_t curr_unit = BS_DATA(bs)[unit_number];
263 * Find the next bit set in the unit.
264 * Mind that this function returns 0, if the unit is -1 and
265 * counts the bits from 1 on.
267 bitset_pos_t next_in_this_unit =
268 _bitset_inside_ntz_value((set ? curr_unit : ~curr_unit) & ~in_unit_mask);
270 /* If there is a bit set in the current unit, exit. */
271 if (next_in_this_unit < BS_UNIT_SIZE_BITS) {
272 res = next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS;
273 return res < bs->size ? res : (bitset_pos_t) -1;
276 /* Else search for set bits in the next units. */
279 for(i = unit_number + 1; i < bs->units; ++i) {
280 bitset_unit_t data = BS_DATA(bs)[i];
281 bitset_pos_t first_set =
282 _bitset_inside_ntz_value(set ? data : ~data);
284 if (first_set < BS_UNIT_SIZE_BITS) {
285 res = first_set + i * BS_UNIT_SIZE_BITS;
286 return res < bs->size ? res : (bitset_pos_t) -1;
295 #define bitset_next_clear(bs,pos) _bitset_next((bs), (pos), 0)
296 #define bitset_next_set(bs,pos) _bitset_next((bs), (pos), 1)
299 * Convenience macro for bitset iteration.
300 * @param bitset The bitset.
301 * @param elm A unsigned long variable.
303 #define bitset_foreach(bitset,elm) \
304 for(elm = bitset_next_set(bitset,0); elm != (bitset_pos_t) -1; elm = bitset_next_set(bitset,elm+1))
307 #define bitset_foreach_clear(bitset,elm) \
308 for(elm = bitset_next_clear(bitset,0); elm != (bitset_pos_t) -1; elm = bitset_next_clear(bitset,elm+1))
311 * Count the bits set.
312 * This can also be seen as the cardinality of the set.
313 * @param bs The bitset.
314 * @return The number of bits set in the bitset.
316 static inline unsigned bitset_popcnt(const bitset_t *bs)
322 for (i = 0, unit = BS_DATA(bs); i < bs->units; ++i, ++unit)
323 pop += _bitset_inside_pop(unit);
330 * This sets all bits to zero.
331 * @param bs The bitset.
333 static inline bitset_t *bitset_clear_all(bitset_t *bs)
335 memset(BS_DATA(bs), 0, BS_UNIT_SIZE * bs->units);
341 * This sets all bits to one.
342 * @param bs The bitset.
344 static inline bitset_t *bitset_set_all(bitset_t *bs)
346 memset(BS_DATA(bs), -1, bs->units * BS_UNIT_SIZE);
347 return _bitset_mask_highest(bs);
351 * Check, if one bitset is contained by another.
352 * That is, each bit set in lhs is also set in rhs.
353 * @param lhs A bitset.
354 * @param rhs Another bitset.
355 * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
357 static inline int bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
359 bitset_pos_t n = lhs->units < rhs->units ? lhs->units : rhs->units;
362 for(i = 0; i < n; ++i) {
363 bitset_unit_t lu = BS_DATA(lhs)[i];
364 bitset_unit_t ru = BS_DATA(rhs)[i];
371 * If the left hand sinde is a larger bitset than rhs,
372 * we have to check, that all extra bits in lhs are 0
375 for(i = n; i < lhs->units; ++i) {
376 if(BS_DATA(lhs)[i] != 0)
385 * Treat the bitset as a number and subtract 1.
386 * @param bs The bitset.
387 * @return The same bitset.
389 static inline void bitset_minus1(bitset_t *bs)
391 #define _SH (sizeof(bitset_unit_t) * 8 - 1)
395 for(i = 0; i < bs->units; ++i) {
396 bitset_unit_t unit = BS_DATA(bs)[i];
397 bitset_unit_t um1 = unit - 1;
399 BS_DATA(bs)[i] = um1;
401 if(((unit >> _SH) ^ (um1 >> _SH)) == 0)
408 * Check if two bitsets intersect.
409 * @param a The first bitset.
410 * @param b The second bitset.
411 * @return 1 if they have a bit in common, 0 if not.
413 static inline int bitset_intersect(const bitset_t *a, const bitset_t *b)
415 bitset_pos_t n = a->units < b->units ? a->units : b->units;
418 for (i = 0; i < n; ++i)
419 if (BS_DATA(a)[i] & BS_DATA(b)[i])
426 * set or clear all bits in the range [from;to[.
427 * @param a The bitset.
428 * @param from The first index to set to one.
429 * @param to The last index plus one to set to one.
430 * @param do_set If 1 the bits are set, if 0, they are cleared.
432 static inline void bitset_mod_range(bitset_t *a, bitset_pos_t from, bitset_pos_t to, int do_set)
434 bitset_pos_t from_unit, to_unit, i;
435 bitset_unit_t from_unit_mask, to_unit_mask;
441 bitset_pos_t tmp = from;
450 * A small example (for cleaning bits in the same unit).
454 * result: xxxxxxx000000000000xxxxxxxxxxxxx
455 * from_unit_mask: 00000001111111111111111111111111
456 * to_unit_mask: 11111111111111111110000000000000
457 * scale: 01234567890123456789012345678901
461 from_unit = from / BS_UNIT_SIZE_BITS;
462 from_unit_mask = ~((1 << from) - 1);
463 from = from & BS_UNIT_MASK;
465 to_unit = to / BS_UNIT_SIZE_BITS;
466 to_unit_mask = (1 << to) - 1;
467 to = to & BS_UNIT_MASK;
469 /* do we want to set the bits in the range? */
471 /* If from and to are in the same unit: */
472 if (from_unit == to_unit)
473 BS_DATA(a)[from_unit] |= from_unit_mask & to_unit_mask;
475 /* Else, we have to treat the from and to units seperately */
477 BS_DATA(a)[from_unit] |= from_unit_mask;
478 BS_DATA(a)[to_unit] |= to_unit_mask;
479 for (i = from_unit + 1; i < to_unit; i++)
480 BS_DATA(a)[i] = BITSET_UNIT_ALL_ONE;
484 /* ... or clear them? */
486 if (from_unit == to_unit)
487 BS_DATA(a)[from_unit] &= ~(from_unit_mask & to_unit_mask);
490 BS_DATA(a)[from_unit] &= ~from_unit_mask;
491 BS_DATA(a)[to_unit] &= ~to_unit_mask;
492 for (i = from_unit + 1; i < to_unit; i++)
498 #define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1)
499 #define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
502 * Check, if a bitset is empty.
503 * @param a The bitset.
504 * @return 1, if the bitset is empty, 0 if not.
506 static inline int bitset_is_empty(const bitset_t *a)
509 for (i = 0; i < a->units; ++i)
510 if (BS_DATA(a)[i] != 0)
516 * Print a bitset to a stream.
517 * The bitset is printed as a comma separated list of bits set.
518 * @param file The stream.
519 * @param bs The bitset.
521 static inline void bitset_fprint(FILE *file, const bitset_t *bs)
523 const char *prefix = "";
527 for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) {
528 fprintf(file, "%s%u", prefix, i);
534 static inline void bitset_debug_fprint(FILE *file, const bitset_t *bs)
538 fprintf(file, "%u:", bs->units);
539 for(i = 0; i < bs->units; ++i)
540 fprintf(file, " " BITSET_UNIT_FMT, BS_DATA(bs)[i]);
544 * Perform tgt = tgt \ src operation.
545 * @param tgt The target bitset.
546 * @param src The source bitset.
547 * @return the tgt set.
549 static inline bitset_t *bitset_andnot(bitset_t *tgt, const bitset_t *src);
552 * Perform Union, tgt = tgt u src operation.
553 * @param tgt The target bitset.
554 * @param src The source bitset.
555 * @return the tgt set.
557 static inline bitset_t *bitset_or(bitset_t *tgt, const bitset_t *src);
560 * Perform tgt = tgt ^ ~src operation.
561 * @param tgt The target bitset.
562 * @param src The source bitset.
563 * @return the tgt set.
565 static inline bitset_t *bitset_xor(bitset_t *tgt, const bitset_t *src);
568 * Here, the binary operations follow.
569 * And, Or, And Not, Xor are available.
571 #define BINARY_OP(op) \
572 static inline bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \
575 bitset_pos_t n = tgt->units > src->units ? src->units : tgt->units; \
576 for(i = 0; i < n; i += _BITSET_BINOP_UNITS_INC) \
577 _bitset_inside_binop_ ## op(&BS_DATA(tgt)[i], &BS_DATA(src)[i]); \
579 _bitset_clear_rest(&BS_DATA(tgt)[i], tgt->units - i); \
580 return _bitset_mask_highest(tgt); \
584 * Define the clear rest macro for the and, since it is the only case,
585 * were non existed (treated as 0) units in the src must be handled.
586 * For all other operations holds: x Op 0 = x for Op in { Andnot, Or, Xor }
588 * For and, each bitset implementer has to provide the macro
589 * _bitset_clear_units(data, n), which clears n units from the pointer
592 #define _bitset_clear_rest(data,n) _bitset_inside_clear_units(data, n)
594 #undef _bitset_clear_rest
595 #define _bitset_clear_rest(data,n) do { } while(0)