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
27 * Raw bitsets are constructed from unsigned int arrays. Additional
28 * information like the size of the bitset or the used memory are not
29 * stored for (memory) efficiency reasons.
31 * These bitsets need less space than bitset_t and their representation
32 * as int arrays allows having constant bitsets in the ro data segment.
33 * They should for smaller bitset, whose length is known through other means
34 * (a typical usage case is a set of cpu registers)
36 * The bitset is built as an array of unsigned integers. The unused bits
39 #ifndef FIRM_ADT_RAW_BITSET_H
40 #define FIRM_ADT_RAW_BITSET_H
44 #include "bitfiddle.h"
47 #define BITS_PER_ELEM (sizeof(unsigned) * 8)
48 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits+BITS_PER_ELEM-1)/BITS_PER_ELEM)
49 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits) * sizeof(unsigned))
50 #define BITSET_ELEM(bitset,pos) bitset[pos / BITS_PER_ELEM]
53 * Allocate an empty raw bitset on the heap.
55 * @param size number of bits in the bitset
57 * @return the new bitset
59 static inline unsigned *rbitset_malloc(size_t size)
61 return XMALLOCNZ(unsigned, BITSET_SIZE_ELEMS(size));
65 * Allocate an empty raw bitset on the stack.
67 * @param res will contain the newly allocated bitset
68 * @param size number of bits in the bitset
70 #define rbitset_alloca(res, size) \
72 size_t size_bytes = BITSET_SIZE_BYTES(size); \
73 res = (unsigned*)alloca(size_bytes); \
74 memset(res, 0, size_bytes); \
78 * Allocate an empty raw bitset on an obstack.
80 * @param obst the obstack where the bitset is allocated on
81 * @param size number of bits in the bitset
83 * @return the new bitset
85 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst,
88 return OALLOCNZ(obst, unsigned, BITSET_SIZE_ELEMS(size));
92 * Duplicate a raw bitset on an obstack.
94 * @param obst the obstack where the bitset is allocated on
95 * @param old_bitset the bitset to be duplicated
96 * @param size number of bits in the bitset
98 * @return the new bitset
100 static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
101 const unsigned *old_bitset, size_t size)
103 size_t size_bytes = BITSET_SIZE_BYTES(size);
104 unsigned *res = OALLOCN(obst, unsigned, BITSET_SIZE_ELEMS(size));
105 memcpy(res, old_bitset, size_bytes);
111 * Check if a bitset is empty, ie all bits cleared.
113 static inline bool rbitset_is_empty(const unsigned *bitset, size_t size)
116 size_t n = BITSET_SIZE_ELEMS(size);
118 for (i = 0; i < n; ++i) {
119 if (bitset[i] != 0) {
127 * Set a bit at position pos.
129 * @param bitset the bitset
130 * @param pos the position of the bit to be set
132 static inline void rbitset_set(unsigned *bitset, size_t pos)
134 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
138 * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero.
140 * @param bitset the bitset
141 * @param pos position of the bit to be flipped
143 static inline void rbitset_flip(unsigned *bitset, size_t pos)
145 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
148 static inline unsigned rbitset_last_mask_(size_t size)
153 p = size % BITS_PER_ELEM;
154 return p == 0 ? ~0u : (1u << p)-1u;
158 * Set all bits in a given bitset.
160 * @param bitset the bitset
161 * @param size number of bits in the bitset
163 static inline void rbitset_set_all(unsigned *bitset, size_t size)
166 size_t n = BITSET_SIZE_ELEMS(size);
171 for (i = 0; i < n-1; ++i) {
174 bitset[i] = rbitset_last_mask_(size);
178 * Clear a bit at position pos.
180 * @param bitset the bitset
181 * @param pos the position of the bit to be clear
183 static inline void rbitset_clear(unsigned *bitset, size_t pos)
185 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
189 * Clear all bits in a given bitset.
191 * @param bitset the bitset
192 * @param size number of bits in the bitset
194 static inline void rbitset_clear_all(unsigned *bitset, size_t size)
196 size_t size_bytes = BITSET_SIZE_BYTES(size);
197 memset(bitset, 0, size_bytes);
201 * Flip all bits in a given bitset.
203 * @param bitset the bitset
204 * @param size number of bits in the bitset
206 static inline void rbitset_flip_all(unsigned *bitset, size_t size)
209 size_t n = BITSET_SIZE_ELEMS(size);
214 for (pos = 0; pos < n-1; ++pos) {
217 bitset[pos] ^= rbitset_last_mask_(size);
221 * Check if a bit is set at position pos.
223 * @param bitset the bitset
224 * @param pos the position of the bit to check
226 static inline bool rbitset_is_set(const unsigned *bitset, size_t pos)
228 return (BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM))) != 0;
232 * Calculate the number of set bits (number of elements).
234 * @param bitset the bitset
235 * @param size size of the bitset in bits
237 static inline size_t rbitset_popcount(const unsigned *bitset, size_t size)
239 size_t i, n = BITSET_SIZE_ELEMS(size);
242 for (i = 0; i < n; ++i) {
243 res += popcount(bitset[i]);
250 * Returns the position of the next bit starting from (and including)
253 * @param bitset a bitset
254 * @param pos the first position to check
255 * @param set if 0 search for unset bit, else for set bit
257 * @return the first position where a matched bit was found
259 * @note Does NOT check the size of the bitset, so ensure that a bit
260 * will be found or use a sentinel bit!
262 static inline size_t rbitset_next(const unsigned *bitset, size_t pos,
266 size_t elem_pos = pos / BITS_PER_ELEM;
267 size_t bit_pos = pos % BITS_PER_ELEM;
269 unsigned elem = bitset[elem_pos];
270 unsigned mask = set ? 0 : ~0u;
273 * Mask out the bits smaller than pos in the current unit.
274 * We are only interested in bits set higher than pos.
276 unsigned in_elem_mask = (1 << bit_pos) - 1;
279 p = ntz(elem & ~in_elem_mask);
281 /* If there is a bit set in the current elem, exit. */
282 if (p < BITS_PER_ELEM) {
283 return elem_pos * BITS_PER_ELEM + p;
286 /* Else search for set bits in the next units. */
289 elem = bitset[elem_pos] ^ mask;
292 if (p < BITS_PER_ELEM) {
293 return elem_pos * BITS_PER_ELEM + p;
299 * Returns the position of the next bit starting from (and including)
302 * @param bitset a bitset
303 * @param pos the first position to check
304 * @param last first position that is not checked anymore
305 * @param set if 0 search for unset bit, else for set bit
307 * @return the first position where a matched bit was found.
308 * (size_t)-1 if no bit was found.
310 static inline size_t rbitset_next_max(const unsigned *bitset, size_t pos,
311 size_t last, bool set)
314 size_t elem_pos = pos / BITS_PER_ELEM;
315 size_t bit_pos = pos % BITS_PER_ELEM;
317 unsigned elem = bitset[elem_pos];
318 unsigned mask = set ? 0u : ~0u;
319 size_t res = (size_t)-1;
322 * Mask out the bits smaller than pos in the current unit.
323 * We are only interested in bits set higher than pos.
325 unsigned in_elem_mask = (1u << bit_pos) - 1;
330 p = ntz(elem & ~in_elem_mask);
332 /* If there is a bit set in the current elem, exit. */
333 if (p < BITS_PER_ELEM) {
334 res = elem_pos * BITS_PER_ELEM + p;
336 size_t n = BITSET_SIZE_ELEMS(last);
337 /* Else search for set bits in the next units. */
338 for (elem_pos++; elem_pos < n; elem_pos++) {
339 elem = bitset[elem_pos] ^ mask;
342 if (p < BITS_PER_ELEM) {
343 res = elem_pos * BITS_PER_ELEM + p;
355 * Inplace Intersection of two sets.
357 * @param dst the destination bitset and first operand
358 * @param src the second bitset
359 * @param size size of both bitsets in bits
361 static inline void rbitset_and(unsigned *dst, const unsigned *src, size_t size)
363 size_t i, n = BITSET_SIZE_ELEMS(size);
365 for (i = 0; i < n; ++i) {
371 * Inplace Union of two sets.
373 * @param dst the destination bitset and first operand
374 * @param src the second bitset
375 * @param size size of both bitsets in bits
377 static inline void rbitset_or(unsigned *dst, const unsigned *src, size_t size)
379 size_t i, n = BITSET_SIZE_ELEMS(size);
381 for (i = 0; i < n; ++i) {
387 * Remove all bits in src from dst.
389 * @param dst the destination bitset and first operand
390 * @param src the second bitset
391 * @param size size of both bitsets in bits
393 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, size_t size)
395 size_t i, n = BITSET_SIZE_ELEMS(size);
397 for (i = 0; i < n; ++i) {
403 * Xor of two bitsets.
405 * @param dst the destination bitset and first operand
406 * @param src the second bitset
407 * @param size size of both bitsets in bits
409 static inline void rbitset_xor(unsigned *dst, const unsigned *src, size_t size)
411 size_t i, n = BITSET_SIZE_ELEMS(size);
413 for (i = 0; i < n; ++i) {
419 * Set bits in a range to zero or one
420 * @param bitset the bitset
421 * @param from first bit to set
422 * @param to last bit (the first bit which is not set anymore)
423 * @param val wether to set to 1 or 0
425 static inline void rbitset_set_range(unsigned *bitset, size_t from,
429 * A small example (for cleaning bits in the same unit).
433 * result: xxxxxxx000000000000xxxxxxxxxxxxx
434 * from_unit_mask: 00000001111111111111111111111111
435 * to_unit_mask: 11111111111111111110000000000000
436 * scale: 01234567890123456789012345678901
440 size_t from_bit = from % BITS_PER_ELEM;
441 size_t from_pos = from / BITS_PER_ELEM;
442 unsigned from_unit_mask = ~((1 << from_bit) - 1);
444 size_t to_bit = to % BITS_PER_ELEM;
445 size_t to_pos = to / BITS_PER_ELEM;
446 unsigned to_unit_mask = (1 << to_bit) - 1;
450 /* do we want to set the bits in the range? */
452 if (from_pos == to_pos) {
453 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
456 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
457 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
458 for (i = from_pos + 1; i < to_pos; ++i)
459 BITSET_ELEM(bitset, i) = ~0u;
462 /* ... or clear them? */
463 if (from_pos == to_pos) {
464 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
467 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
468 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
469 for (i = from_pos + 1; i < to_pos; ++i)
470 BITSET_ELEM(bitset, i) = 0;
476 * Returns 1 of two bitsets are equal.
478 * @param bitset1 the first bitset
479 * @param bitset2 the second bitset
480 * @param size size of both bitsets in bits
482 static inline bool rbitsets_equal(const unsigned *bitset1,
483 const unsigned *bitset2, size_t size)
485 size_t size_bytes = BITSET_SIZE_BYTES(size);
486 return memcmp(bitset1, bitset2, size_bytes) == 0;
490 * Tests wether 2 bitsets wether at least 1 bit is set in both.
492 * @param bitset1 the first bitset
493 * @param bitset2 the second bitset
494 * @param size size of both bitsets in bits
496 static inline bool rbitsets_have_common(const unsigned *bitset1,
497 const unsigned *bitset2, size_t size)
499 size_t i, n = BITSET_SIZE_ELEMS(size);
501 for (i = 0; i < n; ++i) {
502 if ((bitset1[i] & bitset2[i]) != 0)
509 * Tests wether all bits set in bitset1 are also set in bitset2.
511 * @param bitset1 the first bitset
512 * @param bitset2 the second bitset
513 * @param size size of both bitsets in bits
515 static inline bool rbitset_contains(const unsigned *bitset1,
516 const unsigned *bitset2, size_t size)
518 size_t i, n = BITSET_SIZE_ELEMS(size);
520 for (i = 0; i < n; ++i) {
521 if ((bitset1[i] & bitset2[i]) != bitset1[i])
528 * Treat the bitset as a number and subtract 1.
529 * @param bitset the bitset.
530 * @return size size of the bitset in bits
532 static inline void rbitset_minus1(unsigned *bitset, size_t size)
534 size_t i, n = BITSET_SIZE_ELEMS(size);
535 unsigned last_mask = rbitset_last_mask_(size);
537 for (i = 0; i < n; ++i) {
538 unsigned mask = i == n-1 ? last_mask : ~0u;
539 unsigned val = bitset[i] & mask;
540 unsigned val_minus1 = val - 1;
541 bitset[i] = val_minus1 & mask;
543 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
549 * Copy a raw bitset into another.
551 * @param dst the destination set
552 * @param src the source set
553 * @param size size of both bitsets in bits
555 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
558 memcpy(dst, src, BITSET_SIZE_BYTES(size));
561 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
564 size_t n = BITSET_SIZE_ELEMS(size);
565 unsigned last_mask = rbitset_last_mask_(size);
567 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
568 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);