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(unsigned size)
61 unsigned size_bytes = BITSET_SIZE_BYTES(size);
62 unsigned *res = xmalloc(size_bytes);
63 memset(res, 0, size_bytes);
69 * Allocate an empty raw bitset on the stack.
71 * @param res will contain the newly allocated bitset
72 * @param size number of bits in the bitset
74 #define rbitset_alloca(res, size) \
76 unsigned size_bytes = BITSET_SIZE_BYTES(size); \
77 res = alloca(size_bytes); \
78 memset(res, 0, size_bytes); \
82 * Allocate an empty raw bitset on an obstack.
84 * @param obst the obstack where the bitset is allocated on
85 * @param size number of bits in the bitset
87 * @return the new bitset
89 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst,
92 unsigned size_bytes = BITSET_SIZE_BYTES(size);
93 unsigned *res = obstack_alloc(obst, size_bytes);
94 memset(res, 0, size_bytes);
100 * Allocate an empty raw bitset including the size on an obstack.
101 * The size of this bitset can be accessed by bitset[-1].
103 * @param obst the obstack where the bitset is allocated on
104 * @param size number of bits in the bitset
106 * @return the new bitset
108 static inline unsigned *rbitset_w_size_obstack_alloc(struct obstack *obst,
111 unsigned size_bytes = BITSET_SIZE_BYTES(size);
112 unsigned *res = obstack_alloc(obst, size_bytes + sizeof(unsigned));
115 memset(res, 0, size_bytes);
120 /** Return the size of a bitset allocated with a *_w_size_* function */
121 #define rbitset_size(set) (set)[-1]
124 * Duplicate a raw bitset on an obstack.
126 * @param obst the obstack where the bitset is allocated on
127 * @param old_bitset the bitset to be duplicated
128 * @param size number of bits in the bitset
130 * @return the new bitset
132 static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
133 const unsigned *old_bitset, unsigned size)
135 unsigned size_bytes = BITSET_SIZE_BYTES(size);
136 unsigned *res = obstack_alloc(obst, size_bytes);
137 memcpy(res, old_bitset, size_bytes);
143 * Check if a bitset is empty, ie all bits cleared.
145 static inline bool rbitset_is_empty(const unsigned *bitset, unsigned size)
148 unsigned n = BITSET_SIZE_ELEMS(size);
150 for (i = 0; i < n; ++i) {
151 if (bitset[i] != 0) {
159 * Set a bit at position pos.
161 * @param bitset the bitset
162 * @param pos the position of the bit to be set
164 static inline void rbitset_set(unsigned *bitset, unsigned pos)
166 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
170 * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero.
172 * @param bitset the bitset
173 * @param pos position of the bit to be flipped
175 static inline void rbitset_flip(unsigned *bitset, unsigned pos)
177 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
180 static inline unsigned rbitset_last_mask_(unsigned size)
185 p = size % BITS_PER_ELEM;
186 return p == 0 ? ~0u : (1u << p)-1u;
190 * Set all bits in a given bitset.
192 * @param bitset the bitset
193 * @param size number of bits in the bitset
195 static inline void rbitset_set_all(unsigned *bitset, unsigned size)
198 unsigned n = BITSET_SIZE_ELEMS(size);
203 for (i = 0; i < n-1; ++i) {
206 bitset[i] = rbitset_last_mask_(size);
210 * Clear a bit at position pos.
212 * @param bitset the bitset
213 * @param pos the position of the bit to be clear
215 static inline void rbitset_clear(unsigned *bitset, unsigned pos)
217 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
221 * Clear all bits in a given bitset.
223 * @param bitset the bitset
224 * @param size number of bits in the bitset
226 static inline void rbitset_clear_all(unsigned *bitset, unsigned size)
228 unsigned size_bytes = BITSET_SIZE_BYTES(size);
229 memset(bitset, 0, size_bytes);
233 * Flip all bits in a given bitset.
235 * @param bitset the bitset
236 * @param size number of bits in the bitset
238 static inline void rbitset_flip_all(unsigned *bitset, unsigned size)
241 unsigned n = BITSET_SIZE_ELEMS(size);
246 for (pos = 0; pos < n-1; ++pos) {
249 bitset[pos] ^= rbitset_last_mask_(size);
253 * Check if a bit is set at position pos.
255 * @param bitset the bitset
256 * @param pos the position of the bit to check
258 static inline bool rbitset_is_set(const unsigned *bitset, unsigned pos)
260 return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
264 * Calculate the number of set bits (number of elements).
266 * @param bitset the bitset
267 * @param size size of the bitset in bits
269 static inline unsigned rbitset_popcount(const unsigned *bitset, unsigned size)
272 unsigned n = BITSET_SIZE_ELEMS(size);
275 for (i = 0; i < n; ++i) {
276 res += popcount(bitset[i]);
283 * Returns the position of the next bit starting from (and including)
286 * @param bitset a bitset
287 * @param pos the first position to check
288 * @param set if 0 search for unset bit, else for set bit
290 * @return the first position where a matched bit was found
292 * @note Does NOT check the size of the bitset, so ensure that a bit
293 * will be found or use a sentinel bit!
295 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos,
299 unsigned elem_pos = pos / BITS_PER_ELEM;
300 unsigned bit_pos = pos % BITS_PER_ELEM;
302 unsigned elem = bitset[elem_pos];
303 unsigned mask = set ? 0 : ~0u;
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 = (1 << 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 return elem_pos * BITS_PER_ELEM + p;
319 /* Else search for set bits in the next units. */
322 elem = bitset[elem_pos] ^ mask;
325 if (p < BITS_PER_ELEM) {
326 return elem_pos * BITS_PER_ELEM + p;
332 * Returns the position of the next bit starting from (and including)
335 * @param bitset a bitset
336 * @param pos the first position to check
337 * @param last first position that is not checked anymore
338 * @param set if 0 search for unset bit, else for set bit
340 * @return the first position where a matched bit was found.
341 * (unsigned)-1 if no bit was found.
343 static inline unsigned rbitset_next_max(const unsigned *bitset, unsigned pos,
344 unsigned last, bool set)
347 unsigned elem_pos = pos / BITS_PER_ELEM;
348 unsigned bit_pos = pos % BITS_PER_ELEM;
350 unsigned elem = bitset[elem_pos];
351 unsigned mask = set ? 0 : ~0u;
352 unsigned res = (unsigned)-1;
355 * Mask out the bits smaller than pos in the current unit.
356 * We are only interested in bits set higher than pos.
358 unsigned in_elem_mask = (1 << bit_pos) - 1;
363 p = ntz(elem & ~in_elem_mask);
365 /* If there is a bit set in the current elem, exit. */
366 if (p < BITS_PER_ELEM) {
367 res = elem_pos * BITS_PER_ELEM + p;
369 unsigned n = BITSET_SIZE_ELEMS(last);
370 /* Else search for set bits in the next units. */
371 for (elem_pos++; elem_pos < n; elem_pos++) {
372 elem = bitset[elem_pos] ^ mask;
375 if (p < BITS_PER_ELEM) {
376 res = elem_pos * BITS_PER_ELEM + p;
388 * Inplace Intersection of two sets.
390 * @param dst the destination bitset and first operand
391 * @param src the second bitset
392 * @param size size of both bitsets in bits
394 static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size)
396 unsigned i, n = BITSET_SIZE_ELEMS(size);
398 for (i = 0; i < n; ++i) {
404 * Inplace Union of two sets.
406 * @param dst the destination bitset and first operand
407 * @param src the second bitset
408 * @param size size of both bitsets in bits
410 static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size)
412 unsigned i, n = BITSET_SIZE_ELEMS(size);
414 for (i = 0; i < n; ++i) {
420 * Remove all bits in src from dst.
422 * @param dst the destination bitset and first operand
423 * @param src the second bitset
424 * @param size size of both bitsets in bits
426 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
428 unsigned i, n = BITSET_SIZE_ELEMS(size);
430 for (i = 0; i < n; ++i) {
436 * Xor of two bitsets.
438 * @param dst the destination bitset and first operand
439 * @param src the second bitset
440 * @param size size of both bitsets in bits
442 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
444 unsigned i, n = BITSET_SIZE_ELEMS(size);
446 for (i = 0; i < n; ++i) {
452 * Set bits in a range to zero or one
453 * @param bitset the bitset
454 * @param from first bit to set
455 * @param to last bit (the first bit which is not set anymore)
456 * @param val wether to set to 1 or 0
458 static inline void rbitset_set_range(unsigned *bitset, unsigned from,
459 unsigned to, bool val)
462 * A small example (for cleaning bits in the same unit).
466 * result: xxxxxxx000000000000xxxxxxxxxxxxx
467 * from_unit_mask: 00000001111111111111111111111111
468 * to_unit_mask: 11111111111111111110000000000000
469 * scale: 01234567890123456789012345678901
473 unsigned from_bit = from % BITS_PER_ELEM;
474 unsigned from_pos = from / BITS_PER_ELEM;
475 unsigned from_unit_mask = ~((1 << from_bit) - 1);
477 unsigned to_bit = to % BITS_PER_ELEM;
478 unsigned to_pos = to / BITS_PER_ELEM;
479 unsigned to_unit_mask = (1 << to_bit) - 1;
483 /* do we want to set the bits in the range? */
485 if (from_pos == to_pos) {
486 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
489 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
490 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
491 for (i = from_pos + 1; i < to_pos; ++i)
492 BITSET_ELEM(bitset, i) = ~0u;
495 /* ... or clear them? */
496 if (from_pos == to_pos) {
497 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
500 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
501 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
502 for (i = from_pos + 1; i < to_pos; ++i)
503 BITSET_ELEM(bitset, i) = 0;
509 * Returns 1 of two bitsets are equal.
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 rbitsets_equal(const unsigned *bitset1,
516 const unsigned *bitset2, unsigned size)
518 unsigned size_bytes = BITSET_SIZE_BYTES(size);
519 return memcmp(bitset1, bitset2, size_bytes) == 0;
523 * Tests wether 2 bitsets wether at least 1 bit is set in both.
525 * @param bitset1 the first bitset
526 * @param bitset2 the second bitset
527 * @param size size of both bitsets in bits
529 static inline bool rbitsets_have_common(const unsigned *bitset1,
530 const unsigned *bitset2, unsigned size)
533 unsigned n = BITSET_SIZE_ELEMS(size);
535 for (i = 0; i < n; ++i) {
536 if ((bitset1[i] & bitset2[i]) != 0)
543 * Tests wether all bits set in bitset1 are also set in bitset2.
545 * @param bitset1 the first bitset
546 * @param bitset2 the second bitset
547 * @param size size of both bitsets in bits
549 static inline bool rbitset_contains(const unsigned *bitset1,
550 const unsigned *bitset2, unsigned size)
553 unsigned n = BITSET_SIZE_ELEMS(size);
555 for (i = 0; i < n; ++i) {
556 if ((bitset1[i] & bitset2[i]) != bitset1[i])
563 * Treat the bitset as a number and subtract 1.
564 * @param bitset the bitset.
565 * @return size size of the bitset in bits
567 static inline void rbitset_minus1(unsigned *bitset, unsigned size)
570 unsigned n = BITSET_SIZE_ELEMS(size);
571 unsigned last_mask = rbitset_last_mask_(size);
573 for (i = 0; i < n; ++i) {
574 unsigned mask = i == n-1 ? last_mask : ~0u;
575 unsigned val = bitset[i] & mask;
576 unsigned val_minus1 = val - 1;
577 bitset[i] = val_minus1 & mask;
579 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
585 * Copy a raw bitset into another.
587 * @param dst the destination set
588 * @param src the source set
589 * @param size size of both bitsets in bits
591 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
594 memcpy(dst, src, BITSET_SIZE_BYTES(size));
597 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
600 unsigned n = BITSET_SIZE_ELEMS(size);
601 unsigned last_mask = rbitset_last_mask_(size);
603 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
604 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);