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 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 unsigned 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, unsigned size)
103 unsigned 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, unsigned size)
116 unsigned 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, unsigned 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, unsigned pos)
145 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
148 static inline unsigned rbitset_last_mask_(unsigned 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, unsigned size)
166 unsigned 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, unsigned 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, unsigned size)
196 unsigned 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, unsigned size)
209 unsigned 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, unsigned 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 unsigned rbitset_popcount(const unsigned *bitset, unsigned size)
240 unsigned n = BITSET_SIZE_ELEMS(size);
243 for (i = 0; i < n; ++i) {
244 res += popcount(bitset[i]);
251 * Returns the position of the next bit starting from (and including)
254 * @param bitset a bitset
255 * @param pos the first position to check
256 * @param set if 0 search for unset bit, else for set bit
258 * @return the first position where a matched bit was found
260 * @note Does NOT check the size of the bitset, so ensure that a bit
261 * will be found or use a sentinel bit!
263 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos,
267 unsigned elem_pos = pos / BITS_PER_ELEM;
268 unsigned bit_pos = pos % BITS_PER_ELEM;
270 unsigned elem = bitset[elem_pos];
271 unsigned mask = set ? 0 : ~0u;
274 * Mask out the bits smaller than pos in the current unit.
275 * We are only interested in bits set higher than pos.
277 unsigned in_elem_mask = (1 << bit_pos) - 1;
280 p = ntz(elem & ~in_elem_mask);
282 /* If there is a bit set in the current elem, exit. */
283 if (p < BITS_PER_ELEM) {
284 return elem_pos * BITS_PER_ELEM + p;
287 /* Else search for set bits in the next units. */
290 elem = bitset[elem_pos] ^ mask;
293 if (p < BITS_PER_ELEM) {
294 return elem_pos * BITS_PER_ELEM + p;
300 * Returns the position of the next bit starting from (and including)
303 * @param bitset a bitset
304 * @param pos the first position to check
305 * @param last first position that is not checked anymore
306 * @param set if 0 search for unset bit, else for set bit
308 * @return the first position where a matched bit was found.
309 * (unsigned)-1 if no bit was found.
311 static inline unsigned rbitset_next_max(const unsigned *bitset, unsigned pos,
312 unsigned last, bool set)
315 unsigned elem_pos = pos / BITS_PER_ELEM;
316 unsigned bit_pos = pos % BITS_PER_ELEM;
318 unsigned elem = bitset[elem_pos];
319 unsigned mask = set ? 0 : ~0u;
320 unsigned res = (unsigned)-1;
323 * Mask out the bits smaller than pos in the current unit.
324 * We are only interested in bits set higher than pos.
326 unsigned in_elem_mask = (1 << bit_pos) - 1;
331 p = ntz(elem & ~in_elem_mask);
333 /* If there is a bit set in the current elem, exit. */
334 if (p < BITS_PER_ELEM) {
335 res = elem_pos * BITS_PER_ELEM + p;
337 unsigned n = BITSET_SIZE_ELEMS(last);
338 /* Else search for set bits in the next units. */
339 for (elem_pos++; elem_pos < n; elem_pos++) {
340 elem = bitset[elem_pos] ^ mask;
343 if (p < BITS_PER_ELEM) {
344 res = elem_pos * BITS_PER_ELEM + p;
356 * Inplace Intersection of two sets.
358 * @param dst the destination bitset and first operand
359 * @param src the second bitset
360 * @param size size of both bitsets in bits
362 static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size)
364 unsigned i, n = BITSET_SIZE_ELEMS(size);
366 for (i = 0; i < n; ++i) {
372 * Inplace Union of two sets.
374 * @param dst the destination bitset and first operand
375 * @param src the second bitset
376 * @param size size of both bitsets in bits
378 static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size)
380 unsigned i, n = BITSET_SIZE_ELEMS(size);
382 for (i = 0; i < n; ++i) {
388 * Remove all bits in src from dst.
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_andnot(unsigned *dst, const unsigned *src, unsigned size)
396 unsigned i, n = BITSET_SIZE_ELEMS(size);
398 for (i = 0; i < n; ++i) {
404 * Xor of two bitsets.
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_xor(unsigned *dst, const unsigned *src, unsigned size)
412 unsigned i, n = BITSET_SIZE_ELEMS(size);
414 for (i = 0; i < n; ++i) {
420 * Set bits in a range to zero or one
421 * @param bitset the bitset
422 * @param from first bit to set
423 * @param to last bit (the first bit which is not set anymore)
424 * @param val wether to set to 1 or 0
426 static inline void rbitset_set_range(unsigned *bitset, unsigned from,
427 unsigned to, bool val)
430 * A small example (for cleaning bits in the same unit).
434 * result: xxxxxxx000000000000xxxxxxxxxxxxx
435 * from_unit_mask: 00000001111111111111111111111111
436 * to_unit_mask: 11111111111111111110000000000000
437 * scale: 01234567890123456789012345678901
441 unsigned from_bit = from % BITS_PER_ELEM;
442 unsigned from_pos = from / BITS_PER_ELEM;
443 unsigned from_unit_mask = ~((1 << from_bit) - 1);
445 unsigned to_bit = to % BITS_PER_ELEM;
446 unsigned to_pos = to / BITS_PER_ELEM;
447 unsigned to_unit_mask = (1 << to_bit) - 1;
451 /* do we want to set the bits in the range? */
453 if (from_pos == to_pos) {
454 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
457 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
458 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
459 for (i = from_pos + 1; i < to_pos; ++i)
460 BITSET_ELEM(bitset, i) = ~0u;
463 /* ... or clear them? */
464 if (from_pos == to_pos) {
465 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
468 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
469 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
470 for (i = from_pos + 1; i < to_pos; ++i)
471 BITSET_ELEM(bitset, i) = 0;
477 * Returns 1 of two bitsets are equal.
479 * @param bitset1 the first bitset
480 * @param bitset2 the second bitset
481 * @param size size of both bitsets in bits
483 static inline bool rbitsets_equal(const unsigned *bitset1,
484 const unsigned *bitset2, unsigned size)
486 unsigned size_bytes = BITSET_SIZE_BYTES(size);
487 return memcmp(bitset1, bitset2, size_bytes) == 0;
491 * Tests wether 2 bitsets wether at least 1 bit is set in both.
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 rbitsets_have_common(const unsigned *bitset1,
498 const unsigned *bitset2, unsigned size)
501 unsigned n = BITSET_SIZE_ELEMS(size);
503 for (i = 0; i < n; ++i) {
504 if ((bitset1[i] & bitset2[i]) != 0)
511 * Tests wether all bits set in bitset1 are also set in bitset2.
513 * @param bitset1 the first bitset
514 * @param bitset2 the second bitset
515 * @param size size of both bitsets in bits
517 static inline bool rbitset_contains(const unsigned *bitset1,
518 const unsigned *bitset2, unsigned size)
521 unsigned n = BITSET_SIZE_ELEMS(size);
523 for (i = 0; i < n; ++i) {
524 if ((bitset1[i] & bitset2[i]) != bitset1[i])
531 * Treat the bitset as a number and subtract 1.
532 * @param bitset the bitset.
533 * @return size size of the bitset in bits
535 static inline void rbitset_minus1(unsigned *bitset, unsigned size)
538 unsigned n = BITSET_SIZE_ELEMS(size);
539 unsigned last_mask = rbitset_last_mask_(size);
541 for (i = 0; i < n; ++i) {
542 unsigned mask = i == n-1 ? last_mask : ~0u;
543 unsigned val = bitset[i] & mask;
544 unsigned val_minus1 = val - 1;
545 bitset[i] = val_minus1 & mask;
547 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
553 * Copy a raw bitset into another.
555 * @param dst the destination set
556 * @param src the source set
557 * @param size size of both bitsets in bits
559 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
562 memcpy(dst, src, BITSET_SIZE_BYTES(size));
565 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
568 unsigned n = BITSET_SIZE_ELEMS(size);
569 unsigned last_mask = rbitset_last_mask_(size);
571 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
572 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);