2 * Copyright (C) 1995-2007 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 helper functions for working with raw bitsets
24 * @author Matthias Braun
27 * Raw bitsets are constructed from int arrays. Additional information
28 * like the size of the bitset or the used memory aren't saved for
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. It is assumed that
37 * exactly 32 bits may be put into each element of the array. If there are
38 * remaining bits, then they should be 0
40 #ifndef FIRM_ADT_RAW_BITSET_H
41 #define FIRM_ADT_RAW_BITSET_H
45 #include "bitset_std.h"
48 #define BITS_PER_ELEM 32
49 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits)/32 + 1)
50 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits)*4)
51 #define BITSET_ELEM(bitset,pos) bitset[pos / 32]
53 static INLINE unsigned *rbitset_alloca(unsigned size)
55 unsigned size_bytes = BITSET_SIZE_BYTES(size);
56 unsigned *res = alloca(size_bytes);
57 memset(res, 0, size_bytes);
62 static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size)
64 unsigned size_bytes = BITSET_SIZE_BYTES(size);
65 unsigned *res = obstack_alloc(obst, size_bytes);
66 memset(res, 0, size_bytes);
72 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
73 const unsigned *old_bitset,
76 unsigned size_bytes = BITSET_SIZE_BYTES(size);
77 unsigned *res = obstack_alloc(obst, size_bytes);
78 memcpy(res, old_bitset, size_bytes);
83 static INLINE void rbitset_set(unsigned *bitset, unsigned pos)
85 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
88 static INLINE void rbitset_clear(unsigned *bitset, unsigned pos)
90 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
93 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos)
95 return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
98 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size)
101 unsigned n = BITSET_SIZE_ELEMS(size);
103 const unsigned *elem = bitset;
105 for(pos = 0; pos < n; ++pos) {
106 res += _bitset_inside_pop(elem);
113 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set)
116 unsigned elem_pos = pos / BITS_PER_ELEM;
117 unsigned bit_pos = pos % BITS_PER_ELEM;
119 unsigned elem = bitset[elem_pos];
122 * Mask out the bits smaller than pos in the current unit.
123 * We are only interested in bits set higher than pos.
125 unsigned in_elem_mask = (1 << bit_pos) - 1;
129 p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
131 /* If there is a bit set in the current elem, exit. */
132 if(p < BITS_PER_ELEM) {
133 return elem_pos * BITS_PER_ELEM + p;
136 /* Else search for set bits in the next units. */
139 elem = bitset[elem_pos];
143 p = _bitset_inside_ntz_value(elem);
144 if(p < BITS_PER_ELEM) {
145 return elem_pos * BITS_PER_ELEM + p;
153 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
157 unsigned n = BITSET_SIZE_ELEMS(size);
159 for(i = 0; i < n; ++i) {
160 bitset1[i] &= bitset2[i];
164 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
168 unsigned n = BITSET_SIZE_ELEMS(size);
170 for(i = 0; i < n; ++i) {
171 bitset1[i] |= bitset2[i];
175 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
179 unsigned n = BITSET_SIZE_ELEMS(size);
181 for(i = 0; i < n; ++i) {
182 bitset1[i] &= ~bitset2[i];
186 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
190 unsigned n = BITSET_SIZE_ELEMS(size);
192 for(i = 0; i < n; ++i) {
193 bitset1[i] ^= bitset2[i];
198 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset)
200 // TODO optimize me (or remove me)
202 unsigned n = bitset_size(bitset);
203 for(i = 0; i < n; ++i) {
204 if(rbitset_is_set(rbitset, i))
205 bitset_set(bitset, i);