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 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 * Clear some units from a certain address on.
38 * @param addr The address from where to clear.
39 * @param n The number of units to set to 0.
41 #define _bitset_inside_clear_units(addr,n) \
42 memset(addr, 0, n * BS_UNIT_SIZE)
45 * Set a bit in a unit.
46 * @param unit A pointer to the unit.
47 * @param bit which bit to set.
49 #define _bitset_inside_set(unit_ptr,bit) (*unit_ptr) |= (1 << (bit))
52 * Clear a bit in a unit.
53 * @param unit A pointer to the unit.
54 * @param bit which bit to set.
56 #define _bitset_inside_clear(unit_ptr,bit) (*unit_ptr) &= ~(1 << (bit))
59 * Flip a bit in a unit.
60 * @param unit A pointer to the unit.
61 * @param bit which bit to set.
63 #define _bitset_inside_flip(unit_ptr,bit) (*unit_ptr) ^= (1 << (bit))
67 * @param unit_ptr The pointer to the unit.
69 #define _bitset_inside_flip_unit(unit_ptr) (*unit_ptr) = ~(*unit_ptr)
72 * Count the number of leading zeroes in a unit.
73 * @param unit A pointer to the unit.
74 * @return The Number of leading zeroes.
76 #define _bitset_inside_nlz(unit_ptr) (nlz(*unit_ptr))
80 * Count the number of trailing zeroes in a unit.
81 * @param unit A pointer to the unit.
82 * @return The Number of leading zeroes.
84 #define _bitset_inside_ntz(unit_ptr) _bitset_std_inside_ntz(unit_ptr)
85 static INLINE unsigned _bitset_std_inside_ntz(bitset_unit_t *unit_ptr)
87 unsigned long data = *unit_ptr;
88 return 32 - (unsigned) nlz(~data & (data - 1));
92 * Count the number of trailing zeroes in a unit (whereas the unit is no
93 * pointer but a value).
95 * @return The Number of leading zeroes.
97 #define _bitset_inside_ntz_value(unit) (32 - nlz(~(unit) & ((unit) - 1)))
100 * test if a bit is set in a unit.
101 * @param unit_ptr The pointer to the unit.
102 * @param bit The bit to check.
103 * @return 1, if the bit is set, 0 otherise.
105 #define _bitset_inside_is_set(unit_ptr,bit) \
106 (((*unit_ptr) & (1 << (bit))) != 0)
109 * count the number of bits set in a unit.
110 * @param unit_ptr The pointer to a unit.
111 * @return The number of bits set in the unit.
113 #define _bitset_inside_pop(unit_ptr) (popcnt(*unit_ptr))
115 #define _BITSET_BINOP_UNITS_INC 1
117 #define _bitset_inside_binop_and(tgt,src) ((*tgt) &= (*src))
118 #define _bitset_inside_binop_andnot(tgt,src) ((*tgt) &= ~(*src))
119 #define _bitset_inside_binop_or(tgt,src) ((*tgt) |= (*src))
120 #define _bitset_inside_binop_xor(tgt,src) ((*tgt) ^= (*src))