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 res will contain the newly allocated bitset
67 * @param size number of bits in the bitset
69 #define rbitset_alloca(res, size) \
71 size_t size_bytes = BITSET_SIZE_BYTES(size); \
72 res = (unsigned*)alloca(size_bytes); \
73 memset(res, 0, size_bytes); \
77 * Allocate an empty raw bitset on an obstack.
79 * @param obst the obstack where the bitset is allocated on
80 * @param size number of bits in the bitset
82 * @return the new bitset
84 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst,
87 return OALLOCNZ(obst, unsigned, BITSET_SIZE_ELEMS(size));
91 * Duplicate a raw bitset on an obstack.
93 * @param obst the obstack where the bitset is allocated on
94 * @param old_bitset the bitset to be duplicated
95 * @param size number of bits in the bitset
97 * @return the new bitset
99 static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
100 const unsigned *old_bitset, size_t size)
102 size_t size_bytes = BITSET_SIZE_BYTES(size);
103 unsigned *res = OALLOCN(obst, unsigned, BITSET_SIZE_ELEMS(size));
104 memcpy(res, old_bitset, size_bytes);
110 * Check if a bitset is empty, ie all bits cleared.
112 static inline bool rbitset_is_empty(const unsigned *bitset, size_t size)
115 size_t n = BITSET_SIZE_ELEMS(size);
117 for (i = 0; i < n; ++i) {
118 if (bitset[i] != 0) {
126 * Set a bit at position pos.
128 * @param bitset the bitset
129 * @param pos the position of the bit to be set
131 static inline void rbitset_set(unsigned *bitset, size_t pos)
133 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
137 * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero.
139 * @param bitset the bitset
140 * @param pos position of the bit to be flipped
142 static inline void rbitset_flip(unsigned *bitset, size_t pos)
144 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
147 static inline unsigned rbitset_last_mask_(size_t size)
152 p = size % BITS_PER_ELEM;
153 return p == 0 ? ~0u : (1u << p)-1u;
157 * Set all bits in a given bitset.
159 * @param bitset the bitset
160 * @param size number of bits in the bitset
162 static inline void rbitset_set_all(unsigned *bitset, size_t size)
165 size_t n = BITSET_SIZE_ELEMS(size);
170 for (i = 0; i < n-1; ++i) {
173 bitset[i] = rbitset_last_mask_(size);
177 * Clear a bit at position pos.
179 * @param bitset the bitset
180 * @param pos the position of the bit to be clear
182 static inline void rbitset_clear(unsigned *bitset, size_t pos)
184 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
188 * Clear all bits in a given bitset.
190 * @param bitset the bitset
191 * @param size number of bits in the bitset
193 static inline void rbitset_clear_all(unsigned *bitset, size_t size)
195 size_t size_bytes = BITSET_SIZE_BYTES(size);
196 memset(bitset, 0, size_bytes);
200 * Flip all bits in a given bitset.
202 * @param bitset the bitset
203 * @param size number of bits in the bitset
205 static inline void rbitset_flip_all(unsigned *bitset, size_t size)
208 size_t n = BITSET_SIZE_ELEMS(size);
213 for (pos = 0; pos < n-1; ++pos) {
216 bitset[pos] ^= rbitset_last_mask_(size);
220 * Check if a bit is set at position pos.
222 * @param bitset the bitset
223 * @param pos the position of the bit to check
225 static inline bool rbitset_is_set(const unsigned *bitset, size_t pos)
227 return (BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM))) != 0;
231 * Calculate the number of set bits (number of elements).
233 * @param bitset the bitset
234 * @param size size of the bitset in bits
236 static inline size_t rbitset_popcount(const unsigned *bitset, size_t size)
238 size_t i, n = BITSET_SIZE_ELEMS(size);
241 for (i = 0; i < n; ++i) {
242 res += popcount(bitset[i]);
249 * Returns the position of the next bit starting from (and including)
252 * @param bitset a bitset
253 * @param pos the first position to check
254 * @param set if 0 search for unset bit, else for set bit
256 * @return the first position where a matched bit was found
258 * @note Does NOT check the size of the bitset, so ensure that a bit
259 * will be found or use a sentinel bit!
261 static inline size_t rbitset_next(const unsigned *bitset, size_t pos,
265 size_t elem_pos = pos / BITS_PER_ELEM;
266 size_t bit_pos = pos % BITS_PER_ELEM;
268 unsigned elem = bitset[elem_pos];
269 unsigned mask = set ? 0 : ~0u;
272 * Mask out the bits smaller than pos in the current unit.
273 * We are only interested in bits set higher than pos.
275 unsigned in_elem_mask = (1 << bit_pos) - 1;
278 p = ntz(elem & ~in_elem_mask);
280 /* If there is a bit set in the current elem, exit. */
281 if (p < BITS_PER_ELEM) {
282 return elem_pos * BITS_PER_ELEM + p;
285 /* Else search for set bits in the next units. */
288 elem = bitset[elem_pos] ^ mask;
291 if (p < BITS_PER_ELEM) {
292 return elem_pos * BITS_PER_ELEM + p;
298 * Returns the position of the next bit starting from (and including)
301 * @param bitset a bitset
302 * @param pos the first position to check
303 * @param last first position that is not checked anymore
304 * @param set if 0 search for unset bit, else for set bit
306 * @return the first position where a matched bit was found.
307 * (size_t)-1 if no bit was found.
309 static inline size_t rbitset_next_max(const unsigned *bitset, size_t pos,
310 size_t last, bool set)
313 size_t elem_pos = pos / BITS_PER_ELEM;
314 size_t bit_pos = pos % BITS_PER_ELEM;
316 unsigned elem = bitset[elem_pos];
317 unsigned mask = set ? 0u : ~0u;
318 size_t res = (size_t)-1;
321 * Mask out the bits smaller than pos in the current unit.
322 * We are only interested in bits set higher than pos.
324 unsigned in_elem_mask = (1u << bit_pos) - 1;
329 p = ntz(elem & ~in_elem_mask);
331 /* If there is a bit set in the current elem, exit. */
332 if (p < BITS_PER_ELEM) {
333 res = elem_pos * BITS_PER_ELEM + p;
335 size_t n = BITSET_SIZE_ELEMS(last);
336 /* Else search for set bits in the next units. */
337 for (elem_pos++; elem_pos < n; elem_pos++) {
338 elem = bitset[elem_pos] ^ mask;
341 if (p < BITS_PER_ELEM) {
342 res = elem_pos * BITS_PER_ELEM + p;
354 * Inplace Intersection of two sets.
356 * @param dst the destination bitset and first operand
357 * @param src the second bitset
358 * @param size size of both bitsets in bits
360 static inline void rbitset_and(unsigned *dst, const unsigned *src, size_t size)
362 size_t i, n = BITSET_SIZE_ELEMS(size);
364 for (i = 0; i < n; ++i) {
370 * Inplace Union of two sets.
372 * @param dst the destination bitset and first operand
373 * @param src the second bitset
374 * @param size size of both bitsets in bits
376 static inline void rbitset_or(unsigned *dst, const unsigned *src, size_t size)
378 size_t i, n = BITSET_SIZE_ELEMS(size);
380 for (i = 0; i < n; ++i) {
386 * Remove all bits in src from dst.
388 * @param dst the destination bitset and first operand
389 * @param src the second bitset
390 * @param size size of both bitsets in bits
392 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, size_t size)
394 size_t i, n = BITSET_SIZE_ELEMS(size);
396 for (i = 0; i < n; ++i) {
402 * Xor of two bitsets.
404 * @param dst the destination bitset and first operand
405 * @param src the second bitset
406 * @param size size of both bitsets in bits
408 static inline void rbitset_xor(unsigned *dst, const unsigned *src, size_t size)
410 size_t i, n = BITSET_SIZE_ELEMS(size);
412 for (i = 0; i < n; ++i) {
418 * Set bits in a range to zero or one
419 * @param bitset the bitset
420 * @param from first bit to set
421 * @param to last bit (the first bit which is not set anymore)
422 * @param val whether to set to 1 or 0
424 static inline void rbitset_set_range(unsigned *bitset, size_t from,
428 * A small example (for cleaning bits in the same unit).
432 * result: xxxxxxx000000000000xxxxxxxxxxxxx
433 * from_unit_mask: 00000001111111111111111111111111
434 * to_unit_mask: 11111111111111111110000000000000
435 * scale: 01234567890123456789012345678901
439 size_t from_bit = from % BITS_PER_ELEM;
440 size_t from_pos = from / BITS_PER_ELEM;
441 unsigned from_unit_mask = ~((1 << from_bit) - 1);
443 size_t to_bit = to % BITS_PER_ELEM;
444 size_t to_pos = to / BITS_PER_ELEM;
445 unsigned to_unit_mask = (1 << to_bit) - 1;
449 /* do we want to set the bits in the range? */
451 if (from_pos == to_pos) {
452 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
455 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
456 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
457 for (i = from_pos + 1; i < to_pos; ++i)
458 BITSET_ELEM(bitset, i) = ~0u;
461 /* ... or clear them? */
462 if (from_pos == to_pos) {
463 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
466 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
467 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
468 for (i = from_pos + 1; i < to_pos; ++i)
469 BITSET_ELEM(bitset, i) = 0;
475 * Returns 1 of two bitsets are equal.
477 * @param bitset1 the first bitset
478 * @param bitset2 the second bitset
479 * @param size size of both bitsets in bits
481 static inline bool rbitsets_equal(const unsigned *bitset1,
482 const unsigned *bitset2, size_t size)
484 size_t size_bytes = BITSET_SIZE_BYTES(size);
485 return memcmp(bitset1, bitset2, size_bytes) == 0;
489 * Tests whether 2 bitsets have at least one common set bit.
491 * @param bitset1 the first bitset
492 * @param bitset2 the second bitset
493 * @param size size of both bitsets in bits
495 static inline bool rbitsets_have_common(const unsigned *bitset1,
496 const unsigned *bitset2, size_t size)
498 size_t i, n = BITSET_SIZE_ELEMS(size);
500 for (i = 0; i < n; ++i) {
501 if ((bitset1[i] & bitset2[i]) != 0)
508 * Tests whether all bits set in bitset1 are also set in bitset2.
510 * @param bitset1 the first bitset
511 * @param bitset2 the second bitset
512 * @param size size of both bitsets in bits
514 static inline bool rbitset_contains(const unsigned *bitset1,
515 const unsigned *bitset2, size_t size)
517 size_t i, n = BITSET_SIZE_ELEMS(size);
519 for (i = 0; i < n; ++i) {
520 if ((bitset1[i] & bitset2[i]) != bitset1[i])
527 * Treat the bitset as a number and subtract 1.
528 * @param bitset the bitset.
529 * @return size size of the bitset in bits
531 static inline void rbitset_minus1(unsigned *bitset, size_t size)
533 size_t i, n = BITSET_SIZE_ELEMS(size);
534 unsigned last_mask = rbitset_last_mask_(size);
536 for (i = 0; i < n; ++i) {
537 unsigned mask = i == n-1 ? last_mask : ~0u;
538 unsigned val = bitset[i] & mask;
539 unsigned val_minus1 = val - 1;
540 bitset[i] = val_minus1 & mask;
542 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
548 * Copy a raw bitset into another.
550 * @param dst the destination set
551 * @param src the source set
552 * @param size size of both bitsets in bits
554 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
557 memcpy(dst, src, BITSET_SIZE_BYTES(size));
560 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
563 size_t n = BITSET_SIZE_ELEMS(size);
564 unsigned last_mask = rbitset_last_mask_(size);
566 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
567 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);