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 raw bitsets (low-level bitset operations)
24 * @author Matthias Braun
26 * Raw bitsets are constructed from unsigned int arrays. Additional
27 * information like the size of the bitset or the used memory are not
28 * stored for (memory) efficiency reasons.
30 * These bitsets need less space than bitset_t and their representation
31 * as int arrays allows having constant bitsets in the ro data segment.
32 * They should for smaller bitset, whose length is known through other means
33 * (a typical usage case is a set of cpu registers)
35 * The bitset is built as an array of unsigned integers. The unused bits
38 #ifndef FIRM_ADT_RAW_BITSET_H
39 #define FIRM_ADT_RAW_BITSET_H
43 #include "bitfiddle.h"
46 #define BITS_PER_ELEM (sizeof(unsigned) * 8)
47 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits+BITS_PER_ELEM-1)/BITS_PER_ELEM)
48 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits) * sizeof(unsigned))
49 #define BITSET_ELEM(bitset,pos) bitset[pos / BITS_PER_ELEM]
52 * Allocate an empty raw bitset on the heap.
54 * @param size number of bits in the bitset
56 * @return the new bitset
58 static inline unsigned *rbitset_malloc(size_t size)
60 return XMALLOCNZ(unsigned, BITSET_SIZE_ELEMS(size));
64 * Allocate an empty raw bitset on the stack.
66 * @param size number of bits in the bitset
68 #define rbitset_alloca(size) \
69 ((unsigned*)memset(alloca(BITSET_SIZE_BYTES(size)), 0, BITSET_SIZE_BYTES(size)))
72 * Allocate an empty raw bitset on an obstack.
74 * @param obst the obstack where the bitset is allocated on
75 * @param size number of bits in the bitset
77 * @return the new bitset
79 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst,
82 return OALLOCNZ(obst, unsigned, BITSET_SIZE_ELEMS(size));
86 * Duplicate a raw bitset on an obstack.
88 * @param obst the obstack where the bitset is allocated on
89 * @param old_bitset the bitset to be duplicated
90 * @param size number of bits in the bitset
92 * @return the new bitset
94 static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
95 const unsigned *old_bitset, size_t size)
97 size_t size_bytes = BITSET_SIZE_BYTES(size);
98 unsigned *res = OALLOCN(obst, unsigned, BITSET_SIZE_ELEMS(size));
99 memcpy(res, old_bitset, size_bytes);
105 * Check if a bitset is empty, ie all bits cleared.
107 static inline bool rbitset_is_empty(const unsigned *bitset, size_t size)
110 size_t n = BITSET_SIZE_ELEMS(size);
112 for (i = 0; i < n; ++i) {
113 if (bitset[i] != 0) {
121 * Set a bit at position pos.
123 * @param bitset the bitset
124 * @param pos the position of the bit to be set
126 static inline void rbitset_set(unsigned *bitset, size_t pos)
128 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
132 * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero.
134 * @param bitset the bitset
135 * @param pos position of the bit to be flipped
137 static inline void rbitset_flip(unsigned *bitset, size_t pos)
139 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
142 static inline unsigned rbitset_last_mask_(size_t size)
147 p = size % BITS_PER_ELEM;
148 return p == 0 ? ~0u : (1u << p)-1u;
152 * Set all bits in a given bitset.
154 * @param bitset the bitset
155 * @param size number of bits in the bitset
157 static inline void rbitset_set_all(unsigned *bitset, size_t size)
160 size_t n = BITSET_SIZE_ELEMS(size);
165 for (i = 0; i < n-1; ++i) {
168 bitset[i] = rbitset_last_mask_(size);
172 * Clear a bit at position pos.
174 * @param bitset the bitset
175 * @param pos the position of the bit to be clear
177 static inline void rbitset_clear(unsigned *bitset, size_t pos)
179 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
183 * Clear all bits in a given bitset.
185 * @param bitset the bitset
186 * @param size number of bits in the bitset
188 static inline void rbitset_clear_all(unsigned *bitset, size_t size)
190 size_t size_bytes = BITSET_SIZE_BYTES(size);
191 memset(bitset, 0, size_bytes);
195 * Flip all bits in a given bitset.
197 * @param bitset the bitset
198 * @param size number of bits in the bitset
200 static inline void rbitset_flip_all(unsigned *bitset, size_t size)
203 size_t n = BITSET_SIZE_ELEMS(size);
208 for (pos = 0; pos < n-1; ++pos) {
211 bitset[pos] ^= rbitset_last_mask_(size);
215 * Check if a bit is set at position pos.
217 * @param bitset the bitset
218 * @param pos the position of the bit to check
220 static inline bool rbitset_is_set(const unsigned *bitset, size_t pos)
222 return (BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM))) != 0;
226 * Calculate the number of set bits (number of elements).
228 * @param bitset the bitset
229 * @param size size of the bitset in bits
231 static inline size_t rbitset_popcount(const unsigned *bitset, size_t size)
233 size_t i, n = BITSET_SIZE_ELEMS(size);
236 for (i = 0; i < n; ++i) {
237 res += popcount(bitset[i]);
244 * Returns the position of the next bit starting from (and including)
247 * @param bitset a bitset
248 * @param pos the first position to check
249 * @param set if 0 search for unset bit, else for set bit
251 * @return the first position where a matched bit was found
253 * @note Does NOT check the size of the bitset, so ensure that a bit
254 * will be found or use a sentinel bit!
256 static inline size_t rbitset_next(const unsigned *bitset, size_t pos,
260 size_t elem_pos = pos / BITS_PER_ELEM;
261 size_t bit_pos = pos % BITS_PER_ELEM;
263 unsigned elem = bitset[elem_pos];
264 unsigned mask = set ? 0 : ~0u;
267 * Mask out the bits smaller than pos in the current unit.
268 * We are only interested in bits set higher than pos.
270 unsigned in_elem_mask = (1 << bit_pos) - 1;
273 p = ntz(elem & ~in_elem_mask);
275 /* If there is a bit set in the current elem, exit. */
276 if (p < BITS_PER_ELEM) {
277 return elem_pos * BITS_PER_ELEM + p;
280 /* Else search for set bits in the next units. */
283 elem = bitset[elem_pos] ^ mask;
286 if (p < BITS_PER_ELEM) {
287 return elem_pos * BITS_PER_ELEM + p;
293 * Returns the position of the next bit starting from (and including)
296 * @param bitset a bitset
297 * @param pos the first position to check
298 * @param last first position that is not checked anymore
299 * @param set if 0 search for unset bit, else for set bit
301 * @return the first position where a matched bit was found.
302 * (size_t)-1 if no bit was found.
304 static inline size_t rbitset_next_max(const unsigned *bitset, size_t pos,
305 size_t last, bool set)
308 size_t elem_pos = pos / BITS_PER_ELEM;
309 size_t bit_pos = pos % BITS_PER_ELEM;
311 unsigned elem = bitset[elem_pos];
312 unsigned mask = set ? 0u : ~0u;
313 size_t res = (size_t)-1;
316 * Mask out the bits smaller than pos in the current unit.
317 * We are only interested in bits set higher than pos.
319 unsigned in_elem_mask = (1u << bit_pos) - 1;
324 p = ntz(elem & ~in_elem_mask);
326 /* If there is a bit set in the current elem, exit. */
327 if (p < BITS_PER_ELEM) {
328 res = elem_pos * BITS_PER_ELEM + p;
330 size_t n = BITSET_SIZE_ELEMS(last);
331 /* Else search for set bits in the next units. */
332 for (elem_pos++; elem_pos < n; elem_pos++) {
333 elem = bitset[elem_pos] ^ mask;
336 if (p < BITS_PER_ELEM) {
337 res = elem_pos * BITS_PER_ELEM + p;
349 * Inplace Intersection of two sets.
351 * @param dst the destination bitset and first operand
352 * @param src the second bitset
353 * @param size size of both bitsets in bits
355 static inline void rbitset_and(unsigned *dst, const unsigned *src, size_t size)
357 size_t i, n = BITSET_SIZE_ELEMS(size);
359 for (i = 0; i < n; ++i) {
365 * Inplace Union of two sets.
367 * @param dst the destination bitset and first operand
368 * @param src the second bitset
369 * @param size size of both bitsets in bits
371 static inline void rbitset_or(unsigned *dst, const unsigned *src, size_t size)
373 size_t i, n = BITSET_SIZE_ELEMS(size);
375 for (i = 0; i < n; ++i) {
381 * Remove all bits in src from dst.
383 * @param dst the destination bitset and first operand
384 * @param src the second bitset
385 * @param size size of both bitsets in bits
387 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, size_t size)
389 size_t i, n = BITSET_SIZE_ELEMS(size);
391 for (i = 0; i < n; ++i) {
397 * Xor of two bitsets.
399 * @param dst the destination bitset and first operand
400 * @param src the second bitset
401 * @param size size of both bitsets in bits
403 static inline void rbitset_xor(unsigned *dst, const unsigned *src, size_t size)
405 size_t i, n = BITSET_SIZE_ELEMS(size);
407 for (i = 0; i < n; ++i) {
413 * Set bits in a range to zero or one
414 * @param bitset the bitset
415 * @param from first bit to set
416 * @param to last bit (the first bit which is not set anymore)
417 * @param val whether to set to 1 or 0
419 static inline void rbitset_set_range(unsigned *bitset, size_t from,
423 * A small example (for cleaning bits in the same unit).
427 * result: xxxxxxx000000000000xxxxxxxxxxxxx
428 * from_unit_mask: 00000001111111111111111111111111
429 * to_unit_mask: 11111111111111111110000000000000
430 * scale: 01234567890123456789012345678901
434 size_t from_bit = from % BITS_PER_ELEM;
435 size_t from_pos = from / BITS_PER_ELEM;
436 unsigned from_unit_mask = ~((1 << from_bit) - 1);
438 size_t to_bit = to % BITS_PER_ELEM;
439 size_t to_pos = to / BITS_PER_ELEM;
440 unsigned to_unit_mask = (1 << to_bit) - 1;
444 /* do we want to set the bits in the range? */
446 if (from_pos == to_pos) {
447 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
450 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
451 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
452 for (i = from_pos + 1; i < to_pos; ++i)
453 BITSET_ELEM(bitset, i) = ~0u;
456 /* ... or clear them? */
457 if (from_pos == to_pos) {
458 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
461 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
462 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
463 for (i = from_pos + 1; i < to_pos; ++i)
464 BITSET_ELEM(bitset, i) = 0;
470 * Returns 1 of two bitsets are equal.
472 * @param bitset1 the first bitset
473 * @param bitset2 the second bitset
474 * @param size size of both bitsets in bits
476 static inline bool rbitsets_equal(const unsigned *bitset1,
477 const unsigned *bitset2, size_t size)
479 size_t size_bytes = BITSET_SIZE_BYTES(size);
480 return memcmp(bitset1, bitset2, size_bytes) == 0;
484 * Tests whether 2 bitsets have at least one common set bit.
486 * @param bitset1 the first bitset
487 * @param bitset2 the second bitset
488 * @param size size of both bitsets in bits
490 static inline bool rbitsets_have_common(const unsigned *bitset1,
491 const unsigned *bitset2, size_t size)
493 size_t i, n = BITSET_SIZE_ELEMS(size);
495 for (i = 0; i < n; ++i) {
496 if ((bitset1[i] & bitset2[i]) != 0)
503 * Tests whether all bits set in bitset1 are also set in bitset2.
505 * @param bitset1 the first bitset
506 * @param bitset2 the second bitset
507 * @param size size of both bitsets in bits
509 static inline bool rbitset_contains(const unsigned *bitset1,
510 const unsigned *bitset2, size_t size)
512 size_t i, n = BITSET_SIZE_ELEMS(size);
514 for (i = 0; i < n; ++i) {
515 if ((bitset1[i] & bitset2[i]) != bitset1[i])
522 * Treat the bitset as a number and subtract 1.
523 * @param bitset the bitset.
524 * @return size size of the bitset in bits
526 static inline void rbitset_minus1(unsigned *bitset, size_t size)
528 size_t i, n = BITSET_SIZE_ELEMS(size);
529 unsigned last_mask = rbitset_last_mask_(size);
531 for (i = 0; i < n; ++i) {
532 unsigned mask = i == n-1 ? last_mask : ~0u;
533 unsigned val = bitset[i] & mask;
534 unsigned val_minus1 = val - 1;
535 bitset[i] = val_minus1 & mask;
537 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
543 * Copy a raw bitset into another.
545 * @param dst the destination set
546 * @param src the source set
547 * @param size size of both bitsets in bits
549 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
552 memcpy(dst, src, BITSET_SIZE_BYTES(size));
555 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
558 size_t n = BITSET_SIZE_ELEMS(size);
559 unsigned last_mask = rbitset_last_mask_(size);
561 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
562 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);
566 * Convenience macro for raw bitset iteration.
567 * @param bitset The bitset.
568 * @param size Size of the bitset.
569 * @param elm A size_t variable.
571 #define rbitset_foreach(bitset, size, elm) \
572 for (size_t elm = 0; (elm = rbitset_next_max((bitset), elm, size, 1)) != (size_t)-1; ++elm)