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 * Duplicate a raw bitset on an obstack.
102 * @param obst the obstack where the bitset is allocated on
103 * @param old_bitset the bitset to be duplicated
104 * @param size number of bits in the bitset
106 * @return the new bitset
108 static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
109 const unsigned *old_bitset, unsigned size)
111 unsigned size_bytes = BITSET_SIZE_BYTES(size);
112 unsigned *res = obstack_alloc(obst, size_bytes);
113 memcpy(res, old_bitset, size_bytes);
119 * Check if a bitset is empty, ie all bits cleared.
121 static inline bool rbitset_is_empty(const unsigned *bitset, unsigned size)
124 unsigned n = BITSET_SIZE_ELEMS(size);
126 for (i = 0; i < n; ++i) {
127 if (bitset[i] != 0) {
135 * Set a bit at position pos.
137 * @param bitset the bitset
138 * @param pos the position of the bit to be set
140 static inline void rbitset_set(unsigned *bitset, unsigned pos)
142 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
146 * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero.
148 * @param bitset the bitset
149 * @param pos position of the bit to be flipped
151 static inline void rbitset_flip(unsigned *bitset, unsigned pos)
153 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
156 static inline unsigned rbitset_last_mask_(unsigned size)
161 p = size % BITS_PER_ELEM;
162 return p == 0 ? ~0u : (1u << p)-1u;
166 * Set all bits in a given bitset.
168 * @param bitset the bitset
169 * @param size number of bits in the bitset
171 static inline void rbitset_set_all(unsigned *bitset, unsigned size)
174 unsigned n = BITSET_SIZE_ELEMS(size);
179 for (i = 0; i < n-1; ++i) {
182 bitset[i] = rbitset_last_mask_(size);
186 * Clear a bit at position pos.
188 * @param bitset the bitset
189 * @param pos the position of the bit to be clear
191 static inline void rbitset_clear(unsigned *bitset, unsigned pos)
193 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
197 * Clear all bits in a given bitset.
199 * @param bitset the bitset
200 * @param size number of bits in the bitset
202 static inline void rbitset_clear_all(unsigned *bitset, unsigned size)
204 unsigned size_bytes = BITSET_SIZE_BYTES(size);
205 memset(bitset, 0, size_bytes);
209 * Flip all bits in a given bitset.
211 * @param bitset the bitset
212 * @param size number of bits in the bitset
214 static inline void rbitset_flip_all(unsigned *bitset, unsigned size)
217 unsigned n = BITSET_SIZE_ELEMS(size);
222 for (pos = 0; pos < n-1; ++pos) {
225 bitset[pos] ^= rbitset_last_mask_(size);
229 * Check if a bit is set at position pos.
231 * @param bitset the bitset
232 * @param pos the position of the bit to check
234 static inline bool rbitset_is_set(const unsigned *bitset, unsigned pos)
236 return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
240 * Calculate the number of set bits (number of elements).
242 * @param bitset the bitset
243 * @param size size of the bitset in bits
245 static inline unsigned rbitset_popcount(const unsigned *bitset, unsigned size)
248 unsigned n = BITSET_SIZE_ELEMS(size);
251 for (i = 0; i < n; ++i) {
252 res += popcount(bitset[i]);
259 * Returns the position of the next bit starting from (and including)
262 * @param bitset a bitset
263 * @param pos the first position to check
264 * @param set if 0 search for unset bit, else for set bit
266 * @return the first position where a matched bit was found
268 * @note Does NOT check the size of the bitset, so ensure that a bit
269 * will be found or use a sentinel bit!
271 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos,
275 unsigned elem_pos = pos / BITS_PER_ELEM;
276 unsigned bit_pos = pos % BITS_PER_ELEM;
278 unsigned elem = bitset[elem_pos];
279 unsigned mask = set ? 0 : ~0u;
282 * Mask out the bits smaller than pos in the current unit.
283 * We are only interested in bits set higher than pos.
285 unsigned in_elem_mask = (1 << bit_pos) - 1;
288 p = ntz(elem & ~in_elem_mask);
290 /* If there is a bit set in the current elem, exit. */
291 if (p < BITS_PER_ELEM) {
292 return elem_pos * BITS_PER_ELEM + p;
295 /* Else search for set bits in the next units. */
298 elem = bitset[elem_pos] ^ mask;
301 if (p < BITS_PER_ELEM) {
302 return elem_pos * BITS_PER_ELEM + p;
308 * Returns the position of the next bit starting from (and including)
311 * @param bitset a bitset
312 * @param pos the first position to check
313 * @param last first position that is not checked anymore
314 * @param set if 0 search for unset bit, else for set bit
316 * @return the first position where a matched bit was found.
317 * (unsigned)-1 if no bit was found.
319 static inline unsigned rbitset_next_max(const unsigned *bitset, unsigned pos,
320 unsigned last, bool set)
323 unsigned elem_pos = pos / BITS_PER_ELEM;
324 unsigned bit_pos = pos % BITS_PER_ELEM;
326 unsigned elem = bitset[elem_pos];
327 unsigned mask = set ? 0 : ~0u;
328 unsigned res = (unsigned)-1;
331 * Mask out the bits smaller than pos in the current unit.
332 * We are only interested in bits set higher than pos.
334 unsigned in_elem_mask = (1 << bit_pos) - 1;
339 p = ntz(elem & ~in_elem_mask);
341 /* If there is a bit set in the current elem, exit. */
342 if (p < BITS_PER_ELEM) {
343 res = elem_pos * BITS_PER_ELEM + p;
345 unsigned n = BITSET_SIZE_ELEMS(last);
346 /* Else search for set bits in the next units. */
347 for (elem_pos++; elem_pos < n; elem_pos++) {
348 elem = bitset[elem_pos] ^ mask;
351 if (p < BITS_PER_ELEM) {
352 res = elem_pos * BITS_PER_ELEM + p;
364 * Inplace Intersection of two sets.
366 * @param dst the destination bitset and first operand
367 * @param src the second bitset
368 * @param size size of both bitsets in bits
370 static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size)
372 unsigned i, n = BITSET_SIZE_ELEMS(size);
374 for (i = 0; i < n; ++i) {
380 * Inplace Union of two sets.
382 * @param dst the destination bitset and first operand
383 * @param src the second bitset
384 * @param size size of both bitsets in bits
386 static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size)
388 unsigned i, n = BITSET_SIZE_ELEMS(size);
390 for (i = 0; i < n; ++i) {
396 * Remove all bits in src from dst.
398 * @param dst the destination bitset and first operand
399 * @param src the second bitset
400 * @param size size of both bitsets in bits
402 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
404 unsigned i, n = BITSET_SIZE_ELEMS(size);
406 for (i = 0; i < n; ++i) {
412 * Xor of two bitsets.
414 * @param dst the destination bitset and first operand
415 * @param src the second bitset
416 * @param size size of both bitsets in bits
418 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
420 unsigned i, n = BITSET_SIZE_ELEMS(size);
422 for (i = 0; i < n; ++i) {
428 * Set bits in a range to zero or one
429 * @param bitset the bitset
430 * @param from first bit to set
431 * @param to last bit (the first bit which is not set anymore)
432 * @param val wether to set to 1 or 0
434 static inline void rbitset_set_range(unsigned *bitset, unsigned from,
435 unsigned to, bool val)
438 * A small example (for cleaning bits in the same unit).
442 * result: xxxxxxx000000000000xxxxxxxxxxxxx
443 * from_unit_mask: 00000001111111111111111111111111
444 * to_unit_mask: 11111111111111111110000000000000
445 * scale: 01234567890123456789012345678901
449 unsigned from_bit = from % BITS_PER_ELEM;
450 unsigned from_pos = from / BITS_PER_ELEM;
451 unsigned from_unit_mask = ~((1 << from_bit) - 1);
453 unsigned to_bit = to % BITS_PER_ELEM;
454 unsigned to_pos = to / BITS_PER_ELEM;
455 unsigned to_unit_mask = (1 << to_bit) - 1;
459 /* do we want to set the bits in the range? */
461 if (from_pos == to_pos) {
462 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
465 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
466 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
467 for (i = from_pos + 1; i < to_pos; ++i)
468 BITSET_ELEM(bitset, i) = ~0u;
471 /* ... or clear them? */
472 if (from_pos == to_pos) {
473 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
476 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
477 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
478 for (i = from_pos + 1; i < to_pos; ++i)
479 BITSET_ELEM(bitset, i) = 0;
485 * Returns 1 of two bitsets are equal.
487 * @param bitset1 the first bitset
488 * @param bitset2 the second bitset
489 * @param size size of both bitsets in bits
491 static inline bool rbitsets_equal(const unsigned *bitset1,
492 const unsigned *bitset2, unsigned size)
494 unsigned size_bytes = BITSET_SIZE_BYTES(size);
495 return memcmp(bitset1, bitset2, size_bytes) == 0;
499 * Tests wether 2 bitsets wether at least 1 bit is set in both.
501 * @param bitset1 the first bitset
502 * @param bitset2 the second bitset
503 * @param size size of both bitsets in bits
505 static inline bool rbitsets_have_common(const unsigned *bitset1,
506 const unsigned *bitset2, unsigned size)
509 unsigned n = BITSET_SIZE_ELEMS(size);
511 for (i = 0; i < n; ++i) {
512 if ((bitset1[i] & bitset2[i]) != 0)
519 * Tests wether all bits set in bitset1 are also set in bitset2.
521 * @param bitset1 the first bitset
522 * @param bitset2 the second bitset
523 * @param size size of both bitsets in bits
525 static inline bool rbitset_contains(const unsigned *bitset1,
526 const unsigned *bitset2, unsigned size)
529 unsigned n = BITSET_SIZE_ELEMS(size);
531 for (i = 0; i < n; ++i) {
532 if ((bitset1[i] & bitset2[i]) != bitset1[i])
539 * Treat the bitset as a number and subtract 1.
540 * @param bitset the bitset.
541 * @return size size of the bitset in bits
543 static inline void rbitset_minus1(unsigned *bitset, unsigned size)
546 unsigned n = BITSET_SIZE_ELEMS(size);
547 unsigned last_mask = rbitset_last_mask_(size);
549 for (i = 0; i < n; ++i) {
550 unsigned mask = i == n-1 ? last_mask : ~0u;
551 unsigned val = bitset[i] & mask;
552 unsigned val_minus1 = val - 1;
553 bitset[i] = val_minus1 & mask;
555 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
561 * Copy a raw bitset into another.
563 * @param dst the destination set
564 * @param src the source set
565 * @param size size of both bitsets in bits
567 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
570 memcpy(dst, src, BITSET_SIZE_BYTES(size));
573 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
576 unsigned n = BITSET_SIZE_ELEMS(size);
577 unsigned last_mask = rbitset_last_mask_(size);
579 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
580 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);