1 /*
2 * Mesa 3-D graphics library
3 *
4 * Copyright (C) 2006 Brian Paul All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included
14 * in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
17 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
20 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22 * OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25 /**
26 * \file bitset.h
27 * \brief Bitset of arbitrary size definitions.
28 * \author Michal Krol
29 */
30
31 #ifndef BITSET_H
32 #define BITSET_H
33
34 #include "util/bitscan.h"
35 #include "util/macros.h"
36
37 /****************************************************************************
38 * generic bitset implementation
39 */
40
41 #define BITSET_WORD unsigned int
42 #define BITSET_WORDBITS (sizeof (BITSET_WORD) * 8)
43
44 /* bitset declarations
45 */
46 #define BITSET_WORDS(bits) (((bits) + BITSET_WORDBITS - 1) / BITSET_WORDBITS)
47 #define BITSET_DECLARE(name, bits) BITSET_WORD name[BITSET_WORDS(bits)]
48
49 /* bitset operations
50 */
51 #define BITSET_COPY(x, y) memcpy( (x), (y), sizeof (x) )
52 #define BITSET_EQUAL(x, y) (memcmp( (x), (y), sizeof (x) ) == 0)
53 #define BITSET_ZERO(x) memset( (x), 0, sizeof (x) )
54 #define BITSET_ONES(x) memset( (x), 0xff, sizeof (x) )
55
56 #define BITSET_BITWORD(b) ((b) / BITSET_WORDBITS)
57 #define BITSET_BIT(b) (1u << ((b) % BITSET_WORDBITS))
58
59 /* single bit operations
60 */
61 #define BITSET_TEST(x, b) (((x)[BITSET_BITWORD(b)] & BITSET_BIT(b)) != 0)
62 #define BITSET_SET(x, b) ((x)[BITSET_BITWORD(b)] |= BITSET_BIT(b))
63 #define BITSET_CLEAR(x, b) ((x)[BITSET_BITWORD(b)] &= ~BITSET_BIT(b))
64
65 #define BITSET_MASK(b) (((b) % BITSET_WORDBITS == 0) ? ~0 : BITSET_BIT(b) - 1)
66 #define BITSET_RANGE(b, e) ((BITSET_MASK((e) + 1)) & ~(BITSET_BIT(b) - 1))
67
68 /* bit range operations
69 */
70 #define BITSET_TEST_RANGE(x, b, e) \
71 (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
72 (((x)[BITSET_BITWORD(b)] & BITSET_RANGE(b, e)) != 0) : \
73 (assert (!"BITSET_TEST_RANGE: bit range crosses word boundary"), 0))
74 #define BITSET_SET_RANGE(x, b, e) \
75 (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
76 ((x)[BITSET_BITWORD(b)] |= BITSET_RANGE(b, e)) : \
77 (assert (!"BITSET_SET_RANGE: bit range crosses word boundary"), 0))
78 #define BITSET_CLEAR_RANGE(x, b, e) \
79 (BITSET_BITWORD(b) == BITSET_BITWORD(e) ? \
80 ((x)[BITSET_BITWORD(b)] &= ~BITSET_RANGE(b, e)) : \
81 (assert (!"BITSET_CLEAR_RANGE: bit range crosses word boundary"), 0))
82
83 /* Get first bit set in a bitset.
84 */
85 static inline int
__bitset_ffs(const BITSET_WORD * x,int n)86 __bitset_ffs(const BITSET_WORD *x, int n)
87 {
88 int i;
89
90 for (i = 0; i < n; i++) {
91 if (x[i])
92 return ffs(x[i]) + BITSET_WORDBITS * i;
93 }
94
95 return 0;
96 }
97
98 /* Get the last bit set in a bitset.
99 */
100 static inline int
__bitset_last_bit(const BITSET_WORD * x,int n)101 __bitset_last_bit(const BITSET_WORD *x, int n)
102 {
103 for (int i = n - 1; i >= 0; i--) {
104 if (x[i])
105 return util_last_bit(x[i]) + BITSET_WORDBITS * i;
106 }
107
108 return 0;
109 }
110
111 #define BITSET_FFS(x) __bitset_ffs(x, ARRAY_SIZE(x))
112 #define BITSET_LAST_BIT(x, size) __bitset_last_bit(x, size)
113
114 static inline unsigned
__bitset_next_set(unsigned i,BITSET_WORD * tmp,const BITSET_WORD * set,unsigned size)115 __bitset_next_set(unsigned i, BITSET_WORD *tmp,
116 const BITSET_WORD *set, unsigned size)
117 {
118 unsigned bit, word;
119
120 /* NOTE: The initial conditions for this function are very specific. At
121 * the start of the loop, the tmp variable must be set to *set and the
122 * initial i value set to 0. This way, if there is a bit set in the first
123 * word, we ignore the i-value and just grab that bit (so 0 is ok, even
124 * though 0 may be returned). If the first word is 0, then the value of
125 * `word` will be 0 and we will go on to look at the second word.
126 */
127 word = BITSET_BITWORD(i);
128 while (*tmp == 0) {
129 word++;
130
131 if (word >= BITSET_WORDS(size))
132 return size;
133
134 *tmp = set[word];
135 }
136
137 /* Find the next set bit in the non-zero word */
138 bit = ffs(*tmp) - 1;
139
140 /* Unset the bit */
141 *tmp &= ~(1ull << bit);
142
143 return word * BITSET_WORDBITS + bit;
144 }
145
146 /**
147 * Iterates over each set bit in a set
148 *
149 * @param __i iteration variable, bit number
150 * @param __set the bitset to iterate (will not be modified)
151 * @param __size number of bits in the set to consider
152 */
153 #define BITSET_FOREACH_SET(__i, __set, __size) \
154 for (BITSET_WORD __tmp = *(__set), *__foo = &__tmp; __foo != NULL; __foo = NULL) \
155 for (__i = 0; \
156 (__i = __bitset_next_set(__i, &__tmp, __set, __size)) < __size;)
157
158 static inline void
__bitset_next_range(unsigned * start,unsigned * end,const BITSET_WORD * set,unsigned size)159 __bitset_next_range(unsigned *start, unsigned *end, const BITSET_WORD *set,
160 unsigned size)
161 {
162 /* To find the next start, start searching from end. In the first iteration
163 * it will be at 0, in every subsequent iteration it will be at the first
164 * 0-bit after the range.
165 */
166 unsigned word = BITSET_BITWORD(*end);
167 BITSET_WORD tmp = set[word] & ~(BITSET_BIT(*end) - 1);
168 while (!tmp) {
169 word++;
170 if (word >= BITSET_WORDS(size)) {
171 *start = *end = size;
172 return;
173 }
174 tmp = set[word];
175 }
176
177 *start = word * BITSET_WORDBITS + ffs(tmp) - 1;
178
179 /* Now do the opposite to find end. Here we can start at start + 1, because
180 * we know that the bit at start is 1 and we're searching for the first
181 * 0-bit.
182 */
183 word = BITSET_BITWORD(*start + 1);
184 tmp = set[word] | (BITSET_BIT(*start + 1) - 1);
185 while (~tmp == 0) {
186 word++;
187 if (word >= BITSET_WORDS(size)) {
188 *end = size;
189 return;
190 }
191 tmp = set[word];
192 }
193
194 /* Cap "end" at "size" in case there are extra bits past "size" set in the
195 * word. This is only necessary for "end" because we terminate the loop if
196 * "start" goes past "size".
197 */
198 *end = MIN2(word * BITSET_WORDBITS + ffs(~tmp) - 1, size);
199 }
200
201 /**
202 * Iterates over each contiguous range of set bits in a set
203 *
204 * @param __start the first 1 bit of the current range
205 * @param __end the bit after the last 1 bit of the current range
206 * @param __set the bitset to iterate (will not be modified)
207 * @param __size number of bits in the set to consider
208 */
209 #define BITSET_FOREACH_RANGE(__start, __end, __set, __size) \
210 for (__start = 0, __end = 0, \
211 __bitset_next_range(&__start, &__end, __set, __size); \
212 __start < __size; \
213 __bitset_next_range(&__start, &__end, __set, __size))
214
215
216 #ifdef __cplusplus
217
218 /**
219 * Simple C++ wrapper of a bitset type of static size, with value semantics
220 * and basic bitwise arithmetic operators. The operators defined below are
221 * expected to have the same semantics as the same operator applied to other
222 * fundamental integer types. T is the name of the struct to instantiate
223 * it as, and N is the number of bits in the bitset.
224 */
225 #define DECLARE_BITSET_T(T, N) struct T { \
226 EXPLICIT_CONVERSION \
227 operator bool() const \
228 { \
229 for (unsigned i = 0; i < BITSET_WORDS(N); i++) \
230 if (words[i]) \
231 return true; \
232 return false; \
233 } \
234 \
235 T & \
236 operator=(int x) \
237 { \
238 const T c = {{ (BITSET_WORD)x }}; \
239 return *this = c; \
240 } \
241 \
242 friend bool \
243 operator==(const T &b, const T &c) \
244 { \
245 return BITSET_EQUAL(b.words, c.words); \
246 } \
247 \
248 friend bool \
249 operator!=(const T &b, const T &c) \
250 { \
251 return !(b == c); \
252 } \
253 \
254 friend bool \
255 operator==(const T &b, int x) \
256 { \
257 const T c = {{ (BITSET_WORD)x }}; \
258 return b == c; \
259 } \
260 \
261 friend bool \
262 operator!=(const T &b, int x) \
263 { \
264 return !(b == x); \
265 } \
266 \
267 friend T \
268 operator~(const T &b) \
269 { \
270 T c; \
271 for (unsigned i = 0; i < BITSET_WORDS(N); i++) \
272 c.words[i] = ~b.words[i]; \
273 return c; \
274 } \
275 \
276 T & \
277 operator|=(const T &b) \
278 { \
279 for (unsigned i = 0; i < BITSET_WORDS(N); i++) \
280 words[i] |= b.words[i]; \
281 return *this; \
282 } \
283 \
284 friend T \
285 operator|(const T &b, const T &c) \
286 { \
287 T d = b; \
288 d |= c; \
289 return d; \
290 } \
291 \
292 T & \
293 operator&=(const T &b) \
294 { \
295 for (unsigned i = 0; i < BITSET_WORDS(N); i++) \
296 words[i] &= b.words[i]; \
297 return *this; \
298 } \
299 \
300 friend T \
301 operator&(const T &b, const T &c) \
302 { \
303 T d = b; \
304 d &= c; \
305 return d; \
306 } \
307 \
308 bool \
309 test(unsigned i) const \
310 { \
311 return BITSET_TEST(words, i); \
312 } \
313 \
314 T & \
315 set(unsigned i) \
316 { \
317 BITSET_SET(words, i); \
318 return *this; \
319 } \
320 \
321 T & \
322 clear(unsigned i) \
323 { \
324 BITSET_CLEAR(words, i); \
325 return *this; \
326 } \
327 \
328 BITSET_WORD words[BITSET_WORDS(N)]; \
329 }
330
331 #endif
332
333 #endif
334