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)
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);
200 for (i = 0; i < n-1; ++i) {
203 bitset[i] = rbitset_last_mask_(size);
207 * Clear a bit at position pos.
209 * @param bitset the bitset
210 * @param pos the position of the bit to be clear
212 static inline void rbitset_clear(unsigned *bitset, unsigned pos)
214 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
218 * Clear all bits in a given bitset.
220 * @param bitset the bitset
221 * @param size number of bits in the bitset
223 static inline void rbitset_clear_all(unsigned *bitset, unsigned size)
225 unsigned size_bytes = BITSET_SIZE_BYTES(size);
226 memset(bitset, 0, size_bytes);
230 * Flip all bits in a given bitset.
232 * @param bitset the bitset
233 * @param size number of bits in the bitset
235 static inline void rbitset_flip_all(unsigned *bitset, unsigned size)
238 unsigned n = BITSET_SIZE_ELEMS(size);
239 for (pos = 0; pos < n-1; ++pos) {
242 bitset[pos] ^= rbitset_last_mask_(size);
246 * Check if a bit is set at position pos.
248 * @param bitset the bitset
249 * @param pos the position of the bit to check
251 static inline bool rbitset_is_set(const unsigned *bitset, unsigned pos)
253 return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
257 * Calculate the number of set bits (number of elements).
259 * @param bitset the bitset
260 * @param size size of the bitset in bits
262 static inline unsigned rbitset_popcount(const unsigned *bitset, unsigned size)
265 unsigned n = BITSET_SIZE_ELEMS(size);
268 for (i = 0; i < n; ++i) {
269 res += popcount(bitset[i]);
276 * Returns the position of the next bit starting from (and including)
279 * @param bitset a bitset
280 * @param pos the first position to check
281 * @param set if 0 search for unset bit, else for set bit
283 * @return the first position where a matched bit was found
285 * @note Does NOT check the size of the bitset, so ensure that a bit
286 * will be found or use a sentinel bit!
288 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos,
292 unsigned elem_pos = pos / BITS_PER_ELEM;
293 unsigned bit_pos = pos % BITS_PER_ELEM;
295 unsigned elem = bitset[elem_pos];
296 unsigned mask = set ? 0 : ~0u;
299 * Mask out the bits smaller than pos in the current unit.
300 * We are only interested in bits set higher than pos.
302 unsigned in_elem_mask = (1 << bit_pos) - 1;
305 p = ntz(elem & ~in_elem_mask);
307 /* If there is a bit set in the current elem, exit. */
308 if (p < BITS_PER_ELEM) {
309 return elem_pos * BITS_PER_ELEM + p;
312 /* Else search for set bits in the next units. */
315 elem = bitset[elem_pos] ^ mask;
318 if (p < BITS_PER_ELEM) {
319 return elem_pos * BITS_PER_ELEM + p;
325 * Returns the position of the next bit starting from (and including)
328 * @param bitset a bitset
329 * @param pos the first position to check
330 * @param last first position that is not checked anymore
331 * @param set if 0 search for unset bit, else for set bit
333 * @return the first position where a matched bit was found.
334 * (unsigned)-1 if no bit was found.
336 static inline unsigned rbitset_next_max(const unsigned *bitset, unsigned pos,
337 unsigned last, bool set)
340 unsigned elem_pos = pos / BITS_PER_ELEM;
341 unsigned bit_pos = pos % BITS_PER_ELEM;
343 unsigned elem = bitset[elem_pos];
344 unsigned mask = set ? 0 : ~0u;
345 unsigned res = (unsigned)-1;
348 * Mask out the bits smaller than pos in the current unit.
349 * We are only interested in bits set higher than pos.
351 unsigned in_elem_mask = (1 << bit_pos) - 1;
356 p = ntz(elem & ~in_elem_mask);
358 /* If there is a bit set in the current elem, exit. */
359 if (p < BITS_PER_ELEM) {
360 res = elem_pos * BITS_PER_ELEM + p;
362 unsigned n = BITSET_SIZE_ELEMS(last);
363 /* Else search for set bits in the next units. */
364 for (elem_pos++; elem_pos < n; elem_pos++) {
365 elem = bitset[elem_pos] ^ mask;
368 if (p < BITS_PER_ELEM) {
369 res = elem_pos * BITS_PER_ELEM + p;
381 * Inplace Intersection of two sets.
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_and(unsigned *dst, const unsigned *src, unsigned size)
389 unsigned i, n = BITSET_SIZE_ELEMS(size);
391 for (i = 0; i < n; ++i) {
397 * Inplace Union of two sets.
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_or(unsigned *dst, const unsigned *src, unsigned size)
405 unsigned i, n = BITSET_SIZE_ELEMS(size);
407 for (i = 0; i < n; ++i) {
413 * Remove all bits in src from dst.
415 * @param dst the destination bitset and first operand
416 * @param src the second bitset
417 * @param size size of both bitsets in bits
419 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
421 unsigned i, n = BITSET_SIZE_ELEMS(size);
423 for (i = 0; i < n; ++i) {
429 * Xor of two bitsets.
431 * @param dst the destination bitset and first operand
432 * @param src the second bitset
433 * @param size size of both bitsets in bits
435 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
437 unsigned i, n = BITSET_SIZE_ELEMS(size);
439 for (i = 0; i < n; ++i) {
445 * Set bits in a range to zero or one
446 * @param bitset the bitset
447 * @param from first bit to set
448 * @param to last bit (the first bit which is not set anymore)
449 * @param val wether to set to 1 or 0
451 static inline void rbitset_set_range(unsigned *bitset, unsigned from,
452 unsigned to, bool val)
455 * A small example (for cleaning bits in the same unit).
459 * result: xxxxxxx000000000000xxxxxxxxxxxxx
460 * from_unit_mask: 00000001111111111111111111111111
461 * to_unit_mask: 11111111111111111110000000000000
462 * scale: 01234567890123456789012345678901
466 unsigned from_bit = from % BITS_PER_ELEM;
467 unsigned from_pos = from / BITS_PER_ELEM;
468 unsigned from_unit_mask = ~((1 << from_bit) - 1);
470 unsigned to_bit = to % BITS_PER_ELEM;
471 unsigned to_pos = to / BITS_PER_ELEM;
472 unsigned to_unit_mask = (1 << to_bit) - 1;
476 /* do we want to set the bits in the range? */
478 if (from_pos == to_pos) {
479 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
482 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
483 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
484 for (i = from_pos + 1; i < to_pos; ++i)
485 BITSET_ELEM(bitset, i) = ~0u;
488 /* ... or clear them? */
489 if (from_pos == to_pos) {
490 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
493 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
494 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
495 for (i = from_pos + 1; i < to_pos; ++i)
496 BITSET_ELEM(bitset, i) = 0;
502 * Returns 1 of two bitsets are equal.
504 * @param bitset1 the first bitset
505 * @param bitset2 the second bitset
506 * @param size size of both bitsets in bits
508 static inline bool rbitsets_equal(const unsigned *bitset1,
509 const unsigned *bitset2, unsigned size)
511 unsigned size_bytes = BITSET_SIZE_BYTES(size);
512 return memcmp(bitset1, bitset2, size_bytes) == 0;
516 * Tests wether 2 bitsets wether at least 1 bit is set in both.
518 * @param bitset1 the first bitset
519 * @param bitset2 the second bitset
520 * @param size size of both bitsets in bits
522 static inline bool rbitsets_have_common(const unsigned *bitset1,
523 const unsigned *bitset2, unsigned size)
526 unsigned n = BITSET_SIZE_ELEMS(size);
528 for (i = 0; i < n; ++i) {
529 if ((bitset1[i] & bitset2[i]) != 0)
536 * Tests wether all bits set in bitset1 are also set in bitset2.
538 * @param bitset1 the first bitset
539 * @param bitset2 the second bitset
540 * @param size size of both bitsets in bits
542 static inline bool rbitset_contains(const unsigned *bitset1,
543 const unsigned *bitset2, unsigned size)
546 unsigned n = BITSET_SIZE_ELEMS(size);
548 for (i = 0; i < n; ++i) {
549 if ((bitset1[i] & bitset2[i]) != bitset1[i])
556 * Treat the bitset as a number and subtract 1.
557 * @param bitset the bitset.
558 * @return size size of the bitset in bits
560 static inline void rbitset_minus1(unsigned *bitset, unsigned size)
563 unsigned n = BITSET_SIZE_ELEMS(size);
564 unsigned last_mask = rbitset_last_mask_(size);
566 for (i = 0; i < n; ++i) {
567 unsigned mask = i == n-1 ? last_mask : ~0u;
568 unsigned val = bitset[i] & mask;
569 unsigned val_minus1 = val - 1;
570 bitset[i] = val_minus1 & mask;
572 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
578 * Copy a raw bitset into another.
580 * @param dst the destination set
581 * @param src the source set
582 * @param size size of both bitsets in bits
584 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
587 memcpy(dst, src, BITSET_SIZE_BYTES(size));
590 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
593 unsigned n = BITSET_SIZE_ELEMS(size);
594 unsigned last_mask = rbitset_last_mask_(size);
596 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
597 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);