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 ANSI-C compliant implementation of bitsets
25 #ifndef FIRM_ADT_BITSET_STD_H
26 #define FIRM_ADT_BITSET_STD_H
28 #include "bitfiddle.h"
30 /** Use ordinary ints as unit types. */
31 typedef unsigned int bitset_unit_t;
33 #define BITSET_UNIT_FMT "%0x"
34 #define BITSET_UNIT_ALL_ONE ((unsigned int) -1)
37 * Units needed for a given highest bit.
38 * This implementation always allocates units in a multiple of 16 bytes.
39 * @param size The size of the bitset in bits.
40 * @return The number of units needed.
42 #define _bitset_units(size) (round_up2(size, BS_UNIT_SIZE_BITS) / BS_UNIT_SIZE_BITS)
45 * Compute the size in bytes needed for a bitseti, overall.
46 * This also include the size for the bitset data structure.
47 * This implementation computes the size in wat, that the bitset units
48 * can be aligned to 16 bytes.
49 * @param size The size of the bitset in bits.
50 * @return The overall amount of bytes needed for that bitset.
52 #define _bitset_overall_size(bitset_base_size,size) \
53 (bitset_base_size + _bitset_units(size) * BS_UNIT_SIZE)
56 * calculate the pointer to the data space of the bitset.
57 * @param data The base address of the allocated memory
58 * @param bitset_base_size The size of the basical bitset data structure
59 * which has to be taken into account.
60 * @param size The size of the bitset in bits.
62 #define _bitset_data_ptr(data,bitset_base_size,size) \
63 ((bitset_unit_t *) ((char *) data + bitset_base_size))
67 * Clear some units from a certain address on.
68 * @param addr The address from where to clear.
69 * @param n The number of units to set to 0.
71 #define _bitset_inside_clear_units(addr,n) \
72 memset(addr, 0, n * BS_UNIT_SIZE)
75 * Set a bit in a unit.
76 * @param unit A pointer to the unit.
77 * @param bit which bit to set.
79 #define _bitset_inside_set(unit_ptr,bit) (*unit_ptr) |= (1 << (bit))
82 * Clear a bit in a unit.
83 * @param unit A pointer to the unit.
84 * @param bit which bit to set.
86 #define _bitset_inside_clear(unit_ptr,bit) (*unit_ptr) &= ~(1 << (bit))
89 * Flip a bit in a unit.
90 * @param unit A pointer to the unit.
91 * @param bit which bit to set.
93 #define _bitset_inside_flip(unit_ptr,bit) (*unit_ptr) ^= (1 << (bit))
97 * @param unit_ptr The pointer to the unit.
99 #define _bitset_inside_flip_unit(unit_ptr) (*unit_ptr) = ~(*unit_ptr)
102 * Count the number of leading zeroes in a unit.
103 * @param unit A pointer to the unit.
104 * @return The Number of leading zeroes.
106 #define _bitset_inside_nlz(unit_ptr) (nlz(*unit_ptr))
110 * Count the number of trailing zeroes in a unit.
111 * @param unit A pointer to the unit.
112 * @return The Number of leading zeroes.
114 #define _bitset_inside_ntz(unit_ptr) _bitset_std_inside_ntz(unit_ptr)
115 static INLINE unsigned _bitset_std_inside_ntz(bitset_unit_t *unit_ptr)
117 unsigned long data = *unit_ptr;
118 return 32 - (unsigned) nlz(~data & (data - 1));
122 * Count the number of trailing zeroes in a unit (whereas the unit is no
123 * pointer but a value).
124 * @param unit A unit.
125 * @return The Number of leading zeroes.
127 #define _bitset_inside_ntz_value(unit) (32 - nlz(~(unit) & ((unit) - 1)))
130 * test if a bit is set in a unit.
131 * @param unit_ptr The pointer to the unit.
132 * @param bit The bit to check.
133 * @return 1, if the bit is set, 0 otherise.
135 #define _bitset_inside_is_set(unit_ptr,bit) \
136 (((*unit_ptr) & (1 << (bit))) != 0)
139 * count the number of bits set in a unit.
140 * @param unit_ptr The pointer to a unit.
141 * @return The number of bits set in the unit.
143 #define _bitset_inside_pop(unit_ptr) (popcnt(*unit_ptr))
145 #define _BITSET_BINOP_UNITS_INC 1
147 #define _bitset_inside_binop_and(tgt,src) ((*tgt) &= (*src))
148 #define _bitset_inside_binop_andnot(tgt,src) ((*tgt) &= ~(*src))
149 #define _bitset_inside_binop_or(tgt,src) ((*tgt) |= (*src))
150 #define _bitset_inside_binop_xor(tgt,src) ((*tgt) ^= (*src))