2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief raw bitsets (low-level bitset operations)
10 * @author Matthias Braun
12 * Raw bitsets are constructed from unsigned int arrays. Additional
13 * information like the size of the bitset or the used memory are not
14 * stored for (memory) efficiency reasons.
16 * These bitsets need less space than bitset_t and their representation
17 * as int arrays allows having constant bitsets in the ro data segment.
18 * They should for smaller bitset, whose length is known through other means
19 * (a typical usage case is a set of cpu registers)
21 * The bitset is built as an array of unsigned integers. The unused bits
24 #ifndef FIRM_ADT_RAW_BITSET_H
25 #define FIRM_ADT_RAW_BITSET_H
29 #include "bitfiddle.h"
32 #define BITS_PER_ELEM (sizeof(unsigned) * 8)
33 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits+BITS_PER_ELEM-1)/BITS_PER_ELEM)
34 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits) * sizeof(unsigned))
35 #define BITSET_ELEM(bitset,pos) bitset[pos / BITS_PER_ELEM]
38 * Allocate an empty raw bitset on the heap.
40 * @param size number of bits in the bitset
42 * @return the new bitset
44 static inline unsigned *rbitset_malloc(size_t size)
46 return XMALLOCNZ(unsigned, BITSET_SIZE_ELEMS(size));
50 * Allocate an empty raw bitset on the stack.
52 * @param size number of bits in the bitset
54 #define rbitset_alloca(size) \
55 ((unsigned*)memset(alloca(BITSET_SIZE_BYTES(size)), 0, BITSET_SIZE_BYTES(size)))
58 * Allocate an empty raw bitset on an obstack.
60 * @param obst the obstack where the bitset is allocated on
61 * @param size number of bits in the bitset
63 * @return the new bitset
65 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst,
68 return OALLOCNZ(obst, unsigned, BITSET_SIZE_ELEMS(size));
72 * Duplicate a raw bitset on an obstack.
74 * @param obst the obstack where the bitset is allocated on
75 * @param old_bitset the bitset to be duplicated
76 * @param size number of bits in the bitset
78 * @return the new bitset
80 static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
81 const unsigned *old_bitset, size_t size)
83 size_t size_bytes = BITSET_SIZE_BYTES(size);
84 unsigned *res = OALLOCN(obst, unsigned, BITSET_SIZE_ELEMS(size));
85 memcpy(res, old_bitset, size_bytes);
91 * Check if a bitset is empty, ie all bits cleared.
93 static inline bool rbitset_is_empty(const unsigned *bitset, size_t size)
96 size_t n = BITSET_SIZE_ELEMS(size);
98 for (i = 0; i < n; ++i) {
107 * Set a bit at position pos.
109 * @param bitset the bitset
110 * @param pos the position of the bit to be set
112 static inline void rbitset_set(unsigned *bitset, size_t pos)
114 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
118 * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero.
120 * @param bitset the bitset
121 * @param pos position of the bit to be flipped
123 static inline void rbitset_flip(unsigned *bitset, size_t pos)
125 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
128 static inline unsigned rbitset_last_mask_(size_t size)
133 p = size % BITS_PER_ELEM;
134 return p == 0 ? ~0u : (1u << p)-1u;
138 * Set all bits in a given bitset.
140 * @param bitset the bitset
141 * @param size number of bits in the bitset
143 static inline void rbitset_set_all(unsigned *bitset, size_t size)
146 size_t n = BITSET_SIZE_ELEMS(size);
151 for (i = 0; i < n-1; ++i) {
154 bitset[i] = rbitset_last_mask_(size);
158 * Clear a bit at position pos.
160 * @param bitset the bitset
161 * @param pos the position of the bit to be clear
163 static inline void rbitset_clear(unsigned *bitset, size_t pos)
165 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
169 * Clear all bits in a given bitset.
171 * @param bitset the bitset
172 * @param size number of bits in the bitset
174 static inline void rbitset_clear_all(unsigned *bitset, size_t size)
176 size_t size_bytes = BITSET_SIZE_BYTES(size);
177 memset(bitset, 0, size_bytes);
181 * Flip all bits in a given bitset.
183 * @param bitset the bitset
184 * @param size number of bits in the bitset
186 static inline void rbitset_flip_all(unsigned *bitset, size_t size)
189 size_t n = BITSET_SIZE_ELEMS(size);
194 for (pos = 0; pos < n-1; ++pos) {
197 bitset[pos] ^= rbitset_last_mask_(size);
201 * Check if a bit is set at position pos.
203 * @param bitset the bitset
204 * @param pos the position of the bit to check
206 static inline bool rbitset_is_set(const unsigned *bitset, size_t pos)
208 return (BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM))) != 0;
212 * Calculate the number of set bits (number of elements).
214 * @param bitset the bitset
215 * @param size size of the bitset in bits
217 static inline size_t rbitset_popcount(const unsigned *bitset, size_t size)
219 size_t i, n = BITSET_SIZE_ELEMS(size);
222 for (i = 0; i < n; ++i) {
223 res += popcount(bitset[i]);
230 * Returns the position of the next bit starting from (and including)
233 * @param bitset a bitset
234 * @param pos the first position to check
235 * @param set if 0 search for unset bit, else for set bit
237 * @return the first position where a matched bit was found
239 * @note Does NOT check the size of the bitset, so ensure that a bit
240 * will be found or use a sentinel bit!
242 static inline size_t rbitset_next(const unsigned *bitset, size_t pos,
246 size_t elem_pos = pos / BITS_PER_ELEM;
247 size_t bit_pos = pos % BITS_PER_ELEM;
249 unsigned elem = bitset[elem_pos];
250 unsigned mask = set ? 0 : ~0u;
253 * Mask out the bits smaller than pos in the current unit.
254 * We are only interested in bits set higher than pos.
256 unsigned in_elem_mask = (1 << bit_pos) - 1;
259 p = ntz(elem & ~in_elem_mask);
261 /* If there is a bit set in the current elem, exit. */
262 if (p < BITS_PER_ELEM) {
263 return elem_pos * BITS_PER_ELEM + p;
266 /* Else search for set bits in the next units. */
269 elem = bitset[elem_pos] ^ mask;
272 if (p < BITS_PER_ELEM) {
273 return elem_pos * BITS_PER_ELEM + p;
279 * Returns the position of the next bit starting from (and including)
282 * @param bitset a bitset
283 * @param pos the first position to check
284 * @param last first position that is not checked anymore
285 * @param set if 0 search for unset bit, else for set bit
287 * @return the first position where a matched bit was found.
288 * (size_t)-1 if no bit was found.
290 static inline size_t rbitset_next_max(const unsigned *bitset, size_t pos,
291 size_t last, bool set)
298 size_t elem_pos = pos / BITS_PER_ELEM;
299 size_t bit_pos = pos % BITS_PER_ELEM;
301 unsigned elem = bitset[elem_pos];
302 unsigned mask = set ? 0u : ~0u;
303 size_t res = (size_t)-1;
306 * Mask out the bits smaller than pos in the current unit.
307 * We are only interested in bits set higher than pos.
309 unsigned in_elem_mask = (1u << bit_pos) - 1;
312 p = ntz(elem & ~in_elem_mask);
314 /* If there is a bit set in the current elem, exit. */
315 if (p < BITS_PER_ELEM) {
316 res = elem_pos * BITS_PER_ELEM + p;
318 size_t n = BITSET_SIZE_ELEMS(last);
319 /* Else search for set bits in the next units. */
320 for (elem_pos++; elem_pos < n; elem_pos++) {
321 elem = bitset[elem_pos] ^ mask;
324 if (p < BITS_PER_ELEM) {
325 res = elem_pos * BITS_PER_ELEM + p;
337 * Inplace Intersection of two sets.
339 * @param dst the destination bitset and first operand
340 * @param src the second bitset
341 * @param size size of both bitsets in bits
343 static inline void rbitset_and(unsigned *dst, const unsigned *src, size_t size)
345 size_t i, n = BITSET_SIZE_ELEMS(size);
347 for (i = 0; i < n; ++i) {
353 * Inplace Union of two sets.
355 * @param dst the destination bitset and first operand
356 * @param src the second bitset
357 * @param size size of both bitsets in bits
359 static inline void rbitset_or(unsigned *dst, const unsigned *src, size_t size)
361 size_t i, n = BITSET_SIZE_ELEMS(size);
363 for (i = 0; i < n; ++i) {
369 * Remove all bits in src from dst.
371 * @param dst the destination bitset and first operand
372 * @param src the second bitset
373 * @param size size of both bitsets in bits
375 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, size_t size)
377 size_t i, n = BITSET_SIZE_ELEMS(size);
379 for (i = 0; i < n; ++i) {
385 * Xor of two bitsets.
387 * @param dst the destination bitset and first operand
388 * @param src the second bitset
389 * @param size size of both bitsets in bits
391 static inline void rbitset_xor(unsigned *dst, const unsigned *src, size_t size)
393 size_t i, n = BITSET_SIZE_ELEMS(size);
395 for (i = 0; i < n; ++i) {
401 * Set bits in a range to zero or one
402 * @param bitset the bitset
403 * @param from first bit to set
404 * @param to last bit (the first bit which is not set anymore)
405 * @param val whether to set to 1 or 0
407 static inline void rbitset_set_range(unsigned *bitset, size_t from,
411 * A small example (for cleaning bits in the same unit).
415 * result: xxxxxxx000000000000xxxxxxxxxxxxx
416 * from_unit_mask: 00000001111111111111111111111111
417 * to_unit_mask: 11111111111111111110000000000000
418 * scale: 01234567890123456789012345678901
422 size_t from_bit = from % BITS_PER_ELEM;
423 size_t from_pos = from / BITS_PER_ELEM;
424 unsigned from_unit_mask = ~((1 << from_bit) - 1);
426 size_t to_bit = to % BITS_PER_ELEM;
427 size_t to_pos = to / BITS_PER_ELEM;
428 unsigned to_unit_mask = (1 << to_bit) - 1;
432 /* do we want to set the bits in the range? */
434 if (from_pos == to_pos) {
435 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
438 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
439 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
440 for (i = from_pos + 1; i < to_pos; ++i)
441 BITSET_ELEM(bitset, i) = ~0u;
444 /* ... or clear them? */
445 if (from_pos == to_pos) {
446 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
449 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
450 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
451 for (i = from_pos + 1; i < to_pos; ++i)
452 BITSET_ELEM(bitset, i) = 0;
458 * Returns 1 of two bitsets are equal.
460 * @param bitset1 the first bitset
461 * @param bitset2 the second bitset
462 * @param size size of both bitsets in bits
464 static inline bool rbitsets_equal(const unsigned *bitset1,
465 const unsigned *bitset2, size_t size)
467 size_t size_bytes = BITSET_SIZE_BYTES(size);
468 return memcmp(bitset1, bitset2, size_bytes) == 0;
472 * Tests whether 2 bitsets have at least one common set bit.
474 * @param bitset1 the first bitset
475 * @param bitset2 the second bitset
476 * @param size size of both bitsets in bits
478 static inline bool rbitsets_have_common(const unsigned *bitset1,
479 const unsigned *bitset2, size_t size)
481 size_t i, n = BITSET_SIZE_ELEMS(size);
483 for (i = 0; i < n; ++i) {
484 if ((bitset1[i] & bitset2[i]) != 0)
491 * Tests whether all bits set in bitset1 are also set in bitset2.
493 * @param bitset1 the first bitset
494 * @param bitset2 the second bitset
495 * @param size size of both bitsets in bits
497 static inline bool rbitset_contains(const unsigned *bitset1,
498 const unsigned *bitset2, size_t size)
500 size_t i, n = BITSET_SIZE_ELEMS(size);
502 for (i = 0; i < n; ++i) {
503 if ((bitset1[i] & bitset2[i]) != bitset1[i])
510 * Treat the bitset as a number and subtract 1.
511 * @param bitset the bitset.
512 * @return size size of the bitset in bits
514 static inline void rbitset_minus1(unsigned *bitset, size_t size)
516 size_t i, n = BITSET_SIZE_ELEMS(size);
517 unsigned last_mask = rbitset_last_mask_(size);
519 for (i = 0; i < n; ++i) {
520 unsigned mask = i == n-1 ? last_mask : ~0u;
521 unsigned val = bitset[i] & mask;
522 unsigned val_minus1 = val - 1;
523 bitset[i] = val_minus1 & mask;
525 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
531 * Copy a raw bitset into another.
533 * @param dst the destination set
534 * @param src the source set
535 * @param size size of both bitsets in bits
537 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
540 memcpy(dst, src, BITSET_SIZE_BYTES(size));
543 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
546 size_t n = BITSET_SIZE_ELEMS(size);
547 unsigned last_mask = rbitset_last_mask_(size);
549 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
550 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);
554 * Convenience macro for raw bitset iteration.
555 * @param bitset The bitset.
556 * @param size Size of the bitset.
557 * @param elm A size_t variable.
559 #define rbitset_foreach(bitset, size, elm) \
560 for (size_t elm = 0; (elm = rbitset_next_max((bitset), elm, size, 1)) != (size_t)-1; ++elm)
563 * Convenience macro for raw bitset iteration.
564 * @param bitset The bitset.
565 * @param size Size of the bitset.
566 * @param elm A size_t variable.
568 #define rbitset_foreach_clear(bitset, size, elm) \
569 for (size_t elm = 0; (elm = rbitset_next_max((bitset), elm, size, 0)) != (size_t)-1; ++elm)