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 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 /** The base type for raw bitsets. */
48 typedef unsigned int rawbs_base_t;
50 #define BITS_PER_ELEM (sizeof(rawbs_base_t) * 8)
51 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits)/BITS_PER_ELEM + 1)
52 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits) * sizeof(rawbs_base_t))
53 #define BITSET_ELEM(bitset,pos) bitset[pos / BITS_PER_ELEM]
56 * Allocate an empty raw bitset on the heap.
58 * @param size number of bits in the bitset
60 * @return the new bitset
62 static inline unsigned *rbitset_malloc(unsigned size) {
63 unsigned size_bytes = BITSET_SIZE_BYTES(size);
64 unsigned *res = xmalloc(size_bytes);
65 memset(res, 0, size_bytes);
71 * Allocate an empty raw bitset on the stack.
73 * @param res will contain the newly allocated bitset
74 * @param size number of bits in the bitset
76 #define rbitset_alloca(res, size) \
78 unsigned size_bytes = BITSET_SIZE_BYTES(size); \
79 res = alloca(size_bytes); \
80 memset(res, 0, size_bytes); \
84 * Allocate an empty raw bitset on an obstack.
86 * @param obst the obstack where the bitset is allocated on
87 * @param size number of bits in the bitset
89 * @return the new bitset
91 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size)
93 unsigned size_bytes = BITSET_SIZE_BYTES(size);
94 unsigned *res = obstack_alloc(obst, size_bytes);
95 memset(res, 0, size_bytes);
101 * Allocate an empty raw bitset including the size on an obstack.
102 * The size of this bitset can be accessed by bitset[-1].
104 * @param obst the obstack where the bitset is allocated on
105 * @param size number of bits in the bitset
107 * @return the new bitset
109 static inline unsigned *rbitset_w_size_obstack_alloc(struct obstack *obst, unsigned size)
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 int rbitset_is_empty(unsigned *bitset, unsigned size)
147 unsigned n = BITSET_SIZE_ELEMS(size);
149 for (i = 0; i < n; ++i) {
158 * Set a bit at position pos.
160 * @param bitset the bitset
161 * @param pos the position of the bit to be set
163 static inline void rbitset_set(unsigned *bitset, unsigned pos)
165 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
169 * Set all bits in a given bitset.
171 * @param bitset the bitset
172 * @param size number of bits in the bitset
174 static inline void rbitset_set_all(unsigned *bitset, unsigned size)
176 unsigned size_bytes = BITSET_SIZE_BYTES(size);
177 memset(bitset, ~0, size_bytes);
182 * Clear a bit at position pos.
184 * @param bitset the bitset
185 * @param pos the position of the bit to be clear
187 static inline void rbitset_clear(unsigned *bitset, unsigned pos)
189 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
193 * Clear all bits in a given bitset.
195 * @param bitset the bitset
196 * @param size number of bits in the bitset
198 static inline void rbitset_clear_all(unsigned *bitset, unsigned size)
200 unsigned size_bytes = BITSET_SIZE_BYTES(size);
201 memset(bitset, 0, size_bytes);
205 * Check if a bit is set at position pos.
207 * @param bitset the bitset
208 * @param pos the position of the bit to check
210 static inline int rbitset_is_set(const unsigned *bitset, unsigned pos)
212 return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
216 * Calculate the number of set bits (number of elements).
218 * @param bitset the bitset
219 * @param size size of the bitset
221 static inline unsigned rbitset_popcnt(const unsigned *bitset, unsigned size)
224 unsigned n = BITSET_SIZE_ELEMS(size);
226 const unsigned *elem = bitset;
228 for (pos = 0; pos < n; ++pos) {
229 res += _bitset_inside_pop(elem);
237 * Returns the position of the next bit starting from (and including)
240 * @param bitset a bitset
241 * @param pos the first position to check
242 * @param set if 0 search for unset bit, else for set bit
244 * @return the first position where a matched bit was found
246 * @note Does NOT check the size of the bitset, so ensure that a bit
247 * will be found or use a sentinel bit!
249 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set)
252 unsigned elem_pos = pos / BITS_PER_ELEM;
253 unsigned bit_pos = pos % BITS_PER_ELEM;
255 unsigned elem = bitset[elem_pos];
259 * Mask out the bits smaller than pos in the current unit.
260 * We are only interested in bits set higher than pos.
262 unsigned in_elem_mask = (1 << bit_pos) - 1;
267 p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
269 /* If there is a bit set in the current elem, exit. */
270 if (p < BITS_PER_ELEM) {
271 return elem_pos * BITS_PER_ELEM + p;
274 /* Else search for set bits in the next units. */
277 elem = bitset[elem_pos] ^ mask;
279 p = _bitset_inside_ntz_value(elem);
280 if (p < BITS_PER_ELEM) {
281 return elem_pos * BITS_PER_ELEM + p;
287 * Inplace Intersection of two sets.
289 * @param dst the destination bitset and first operand
290 * @param src the second bitset
291 * @param size size of both bitsets
293 static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size)
295 unsigned i, n = BITSET_SIZE_ELEMS(size);
297 for (i = 0; i < n; ++i) {
303 * Inplace Union of two sets.
305 * @param dst the destination bitset and first operand
306 * @param src the second bitset
307 * @param size size of both bitsets
309 static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size)
311 unsigned i, n = BITSET_SIZE_ELEMS(size);
313 for (i = 0; i < n; ++i) {
319 * Remove all bits in src from dst.
321 * @param dst the destination bitset and first operand
322 * @param src the second bitset
323 * @param size size of both bitsets
325 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
327 unsigned i, n = BITSET_SIZE_ELEMS(size);
329 for (i = 0; i < n; ++i) {
335 * Xor of two bitsets.
337 * @param dst the destination bitset and first operand
338 * @param src the second bitset
339 * @param size size of both bitsets
341 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
343 unsigned i, n = BITSET_SIZE_ELEMS(size);
345 for (i = 0; i < n; ++i) {
351 * Returns 1 of two bitsets are equal.
353 * @param bitset1 the first bitset
354 * @param bitset2 the second bitset
355 * @param size size of both bitsets
357 static inline int rbitset_equal(const unsigned *bitset1,
358 const unsigned *bitset2, size_t size)
360 return memcmp(bitset1, bitset2, BITSET_SIZE_BYTES(size)) == 0;
364 * Tests wether 2 bitsets wether at least 1 bit is set in both.
366 * @param bitset1 the first bitset
367 * @param bitset2 the second bitset
368 * @param size size of both bitsets
370 static inline int rbitsets_have_common(const unsigned *bitset1,
371 const unsigned *bitset2, size_t size)
374 unsigned n = BITSET_SIZE_ELEMS(size);
376 for (i = 0; i < n; ++i) {
377 if ((bitset1[i] & bitset2[i]) != 0)
384 * Copy a raw bitset into another.
386 * @param dst the destination set
387 * @param src the source set
388 * @param size size of both bitsets
390 static inline void rbitset_copy(unsigned *dst, const unsigned *src, size_t size)
392 memcpy(dst, src, BITSET_SIZE_BYTES(size));
396 * Copy a raw bitset into an bitset.
400 static inline void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset)
402 // TODO optimize me (or remove me)
403 unsigned i, n = bitset_size(bitset);
404 for (i = 0; i < n; ++i) {
405 if (rbitset_is_set(rbitset, i))
406 bitset_set(bitset, i);
410 #endif /* FIRM_ADT_RAW_BITSET_H */