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 unsigned int arrays. Additional information
28 * like the size of the bitset or the used memory are not stored 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
47 #define BITS_PER_ELEM 32
48 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits)/32 + 1)
49 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits)*4)
50 #define BITSET_ELEM(bitset,pos) bitset[pos / 32]
53 * Allocate an empty raw bitset on the heap.
55 * @param size element size of the bitset
57 * @return the new bitset
59 static INLINE unsigned *rbitset_malloc(unsigned size) {
60 unsigned size_bytes = BITSET_SIZE_BYTES(size);
61 unsigned *res = malloc(size_bytes);
62 memset(res, 0, size_bytes);
68 * Allocate an empty raw bitset on the stack.
70 * @param res will contain the newly allocated bitset
71 * @param size element size of the bitset
73 #define rbitset_alloca(res, size) \
75 unsigned size_bytes = BITSET_SIZE_BYTES(size); \
76 res = alloca(size_bytes); \
77 memset(res, 0, size_bytes); \
81 * Allocate an empty raw bitset on an obstack.
83 * @param obst the obstack where the bitset is allocated on
84 * @param size element size of the bitset
86 * @return the new bitset
88 static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size) {
89 unsigned size_bytes = BITSET_SIZE_BYTES(size);
90 unsigned *res = obstack_alloc(obst, size_bytes);
91 memset(res, 0, size_bytes);
97 * Allocate an empty raw bitset including the size on an obstack.
98 * The size of this bitset can be accessed by bitset[-1].
100 * @param obst the obstack where the bitset is allocated on
101 * @param size element size of the bitset
103 * @return the new bitset
105 static INLINE unsigned *rbitset_w_size_obstack_alloc(struct obstack *obst, unsigned size) {
106 unsigned size_bytes = BITSET_SIZE_BYTES(size);
107 unsigned *res = obstack_alloc(obst, size_bytes + sizeof(unsigned));
110 memset(res, 0, size_bytes);
115 /** Return the size of a bitset allocated with a *_w_size_* function */
116 #define rbitset_size(set) (set)[-1]
119 * Duplicate a raw bitset on an obstack.
121 * @param obst the obstack where the bitset is allocated on
122 * @param old_bitset the bitset to be duplicated
123 * @param size element size of the bitset
125 * @return the new bitset
128 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
129 const unsigned *old_bitset,
132 unsigned size_bytes = BITSET_SIZE_BYTES(size);
133 unsigned *res = obstack_alloc(obst, size_bytes);
134 memcpy(res, old_bitset, size_bytes);
140 * Check if a bitset is empty, ie all bits cleared.
142 static INLINE int rbitset_is_empty(unsigned *bitset, unsigned size) {
143 unsigned i, size_bytes = BITSET_SIZE_BYTES(size);
144 for (i = 0; i < size_bytes; ++i)
145 if (bitset[i]) return 0;
150 * Set a bit at position pos.
152 * @param bitset the bitset
153 * @param pos the position of the bit to be set
155 static INLINE void rbitset_set(unsigned *bitset, unsigned pos) {
156 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
160 * Clear a bit at position pos.
162 * @param bitset the bitset
163 * @param pos the position of the bit to be clear
165 static INLINE void rbitset_clear(unsigned *bitset, unsigned pos) {
166 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
170 * Check if a bit is set at position pos.
172 * @param bitset the bitset
173 * @param pos the position of the bit to check
175 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos) {
176 return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
180 * Calculate the number of set bits (number of elements).
182 * @param bitset the bitset
184 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) {
186 unsigned n = BITSET_SIZE_ELEMS(size);
188 const unsigned *elem = bitset;
190 for(pos = 0; pos < n; ++pos) {
191 res += _bitset_inside_pop(elem);
198 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) {
200 unsigned elem_pos = pos / BITS_PER_ELEM;
201 unsigned bit_pos = pos % BITS_PER_ELEM;
203 unsigned elem = bitset[elem_pos];
206 * Mask out the bits smaller than pos in the current unit.
207 * We are only interested in bits set higher than pos.
209 unsigned in_elem_mask = (1 << bit_pos) - 1;
213 p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
215 /* If there is a bit set in the current elem, exit. */
216 if(p < BITS_PER_ELEM) {
217 return elem_pos * BITS_PER_ELEM + p;
220 /* Else search for set bits in the next units. */
223 elem = bitset[elem_pos];
227 p = _bitset_inside_ntz_value(elem);
228 if(p < BITS_PER_ELEM) {
229 return elem_pos * BITS_PER_ELEM + p;
238 * Inplace Intersection of two sets.
240 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
243 unsigned i, n = BITSET_SIZE_ELEMS(size);
245 for(i = 0; i < n; ++i) {
246 bitset1[i] &= bitset2[i];
251 * Inplace Union of two sets.
253 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
256 unsigned i, n = BITSET_SIZE_ELEMS(size);
258 for(i = 0; i < n; ++i) {
259 bitset1[i] |= bitset2[i];
264 * Remove all bits in bitset2 from bitset 1.
266 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
269 unsigned i, n = BITSET_SIZE_ELEMS(size);
271 for(i = 0; i < n; ++i) {
272 bitset1[i] &= ~bitset2[i];
277 * Xor of two bitsets.
279 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
282 unsigned i, n = BITSET_SIZE_ELEMS(size);
284 for(i = 0; i < n; ++i) {
285 bitset1[i] ^= bitset2[i];
290 * Copy a raw bitset into an bitset.
294 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) {
295 // TODO optimize me (or remove me)
296 unsigned i, n = bitset_size(bitset);
297 for(i = 0; i < n; ++i) {
298 if(rbitset_is_set(rbitset, i))
299 bitset_set(bitset, i);
303 #endif /* FIRM_ADT_RAW_BITSET_H */