4 * @author Matthias Braun
5 * @brief helper functions for working with raw bitsets
7 * Raw bitsets are constructed from int arrays. Additional information
8 * like the size of the bitset or the used memory aren't saved for
11 * These bitsets need less space than bitset_t and their representation
12 * as int arrays allows having constant bitsets in the ro data segment.
13 * They should for smaller bitset, whose length is known through other means
14 * (a typical usage case is a set of cpu registers)
16 * The bitset is built as an array of unsigned integers. It is assumed that
17 * exactly 32 bits may be put into each element of the array. If there are
18 * remaining bits, then they should be 0
20 #ifndef __FIRM_RAW_BITSET_H
21 #define __FIRM_RAW_BITSET_H
25 #include "bitset_std.h"
28 #define BITS_PER_ELEM 32
29 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits)/32 + 1)
30 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits)*4)
31 #define BITSET_ELEM(bitset,pos) bitset[pos / 32]
33 static INLINE unsigned *rbitset_alloca(unsigned size)
35 unsigned size_bytes = BITSET_SIZE_BYTES(size);
36 unsigned *res = alloca(size_bytes);
37 memset(res, 0, size_bytes);
42 static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size)
44 unsigned size_bytes = BITSET_SIZE_BYTES(size);
45 unsigned *res = obstack_alloc(obst, size_bytes);
46 memset(res, 0, size_bytes);
52 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
53 const unsigned *old_bitset,
56 unsigned size_bytes = BITSET_SIZE_BYTES(size);
57 unsigned *res = obstack_alloc(obst, size_bytes);
58 memcpy(res, old_bitset, size_bytes);
63 static INLINE void rbitset_set(unsigned *bitset, unsigned pos)
65 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
68 static INLINE void rbitset_clear(unsigned *bitset, unsigned pos)
70 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
73 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos)
75 return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
78 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size)
81 unsigned n = BITSET_SIZE_ELEMS(size);
83 const unsigned *elem = bitset;
85 for(pos = 0; pos < n; ++pos) {
86 res += _bitset_inside_pop(elem);
93 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set)
96 unsigned elem_pos = pos / BITS_PER_ELEM;
97 unsigned bit_pos = pos % BITS_PER_ELEM;
99 unsigned elem = bitset[elem_pos];
102 * Mask out the bits smaller than pos in the current unit.
103 * We are only interested in bits set higher than pos.
105 unsigned in_elem_mask = (1 << bit_pos) - 1;
109 p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
111 /* If there is a bit set in the current elem, exit. */
112 if(p < BITS_PER_ELEM) {
113 return elem_pos * BITS_PER_ELEM + p;
116 /* Else search for set bits in the next units. */
119 elem = bitset[elem_pos];
123 p = _bitset_inside_ntz_value(elem);
124 if(p < BITS_PER_ELEM) {
125 return elem_pos * BITS_PER_ELEM + p;
133 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
137 unsigned n = BITSET_SIZE_ELEMS(size);
139 for(i = 0; i < n; ++i) {
140 bitset1[i] &= bitset2[i];
144 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
148 unsigned n = BITSET_SIZE_ELEMS(size);
150 for(i = 0; i < n; ++i) {
151 bitset1[i] |= bitset2[i];
155 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
159 unsigned n = BITSET_SIZE_ELEMS(size);
161 for(i = 0; i < n; ++i) {
162 bitset1[i] &= ~bitset2[i];
166 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
170 unsigned n = BITSET_SIZE_ELEMS(size);
172 for(i = 0; i < n; ++i) {
173 bitset1[i] ^= bitset2[i];
178 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset)
180 // TODO optimize me (or remove me)
182 unsigned n = bitset_size(bitset);
183 for(i = 0; i < n; ++i) {
184 if(rbitset_is_set(rbitset, i))
185 bitset_set(bitset, i);