1 /*
2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
3 *
4 * This file is part of libFirm.
5 *
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.
10 *
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.
14 *
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
17 * PURPOSE.
18 */
19
20 /**
21 * @file
22 * @brief raw bitsets (low-level bitset operations)
23 * @date 15.10.2004
24 * @author Matthias Braun
25 *
26 * Raw bitsets are constructed from unsigned int arrays. Additional
27 * information like the size of the bitset or the used memory are not
28 * stored for (memory) efficiency reasons.
29 *
30 * These bitsets need less space than bitset_t and their representation
31 * as int arrays allows having constant bitsets in the ro data segment.
32 * They should for smaller bitset, whose length is known through other means
33 * (a typical usage case is a set of cpu registers)
34 *
35 * The bitset is built as an array of unsigned integers. The unused bits
36 * must be zero.
37 */
38 #ifndef FIRM_ADT_RAW_BITSET_H
39 #define FIRM_ADT_RAW_BITSET_H
40
41 #include <assert.h>
42 #include <stdbool.h>
43 #include "bitfiddle.h"
44 #include "obst.h"
45
46 #define BITS_PER_ELEM (sizeof(unsigned) * 8)
47 #define BITSET_SIZE_ELEMS(size_bits) ((size_bits+BITS_PER_ELEM-1)/BITS_PER_ELEM)
48 #define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits) * sizeof(unsigned))
49 #define BITSET_ELEM(bitset,pos) bitset[pos / BITS_PER_ELEM]
50
51 /**
52 * Allocate an empty raw bitset on the heap.
53 *
54 * @param size number of bits in the bitset
55 *
56 * @return the new bitset
57 */
rbitset_malloc(size_t size)58 static inline unsigned *rbitset_malloc(size_t size)
59 {
60 return XMALLOCNZ(unsigned, BITSET_SIZE_ELEMS(size));
61 }
62
63 /**
64 * Allocate an empty raw bitset on the stack.
65 *
66 * @param res will contain the newly allocated bitset
67 * @param size number of bits in the bitset
68 */
69 #define rbitset_alloca(res, size) \
70 do { \
71 size_t size_bytes = BITSET_SIZE_BYTES(size); \
72 res = (unsigned*)alloca(size_bytes); \
73 memset(res, 0, size_bytes); \
74 } while(0)
75
76 /**
77 * Allocate an empty raw bitset on an obstack.
78 *
79 * @param obst the obstack where the bitset is allocated on
80 * @param size number of bits in the bitset
81 *
82 * @return the new bitset
83 */
rbitset_obstack_alloc(struct obstack * obst,size_t size)84 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst,
85 size_t size)
86 {
87 return OALLOCNZ(obst, unsigned, BITSET_SIZE_ELEMS(size));
88 }
89
90 /**
91 * Duplicate a raw bitset on an obstack.
92 *
93 * @param obst the obstack where the bitset is allocated on
94 * @param old_bitset the bitset to be duplicated
95 * @param size number of bits in the bitset
96 *
97 * @return the new bitset
98 */
rbitset_duplicate_obstack_alloc(struct obstack * obst,const unsigned * old_bitset,size_t size)99 static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
100 const unsigned *old_bitset, size_t size)
101 {
102 size_t size_bytes = BITSET_SIZE_BYTES(size);
103 unsigned *res = OALLOCN(obst, unsigned, BITSET_SIZE_ELEMS(size));
104 memcpy(res, old_bitset, size_bytes);
105
106 return res;
107 }
108
109 /**
110 * Check if a bitset is empty, ie all bits cleared.
111 */
rbitset_is_empty(const unsigned * bitset,size_t size)112 static inline bool rbitset_is_empty(const unsigned *bitset, size_t size)
113 {
114 size_t i;
115 size_t n = BITSET_SIZE_ELEMS(size);
116
117 for (i = 0; i < n; ++i) {
118 if (bitset[i] != 0) {
119 return false;
120 }
121 }
122 return true;
123 }
124
125 /**
126 * Set a bit at position pos.
127 *
128 * @param bitset the bitset
129 * @param pos the position of the bit to be set
130 */
rbitset_set(unsigned * bitset,size_t pos)131 static inline void rbitset_set(unsigned *bitset, size_t pos)
132 {
133 BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
134 }
135
136 /**
137 * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero.
138 *
139 * @param bitset the bitset
140 * @param pos position of the bit to be flipped
141 */
rbitset_flip(unsigned * bitset,size_t pos)142 static inline void rbitset_flip(unsigned *bitset, size_t pos)
143 {
144 BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
145 }
146
rbitset_last_mask_(size_t size)147 static inline unsigned rbitset_last_mask_(size_t size)
148 {
149 size_t p;
150 if (size == 0)
151 return 0;
152 p = size % BITS_PER_ELEM;
153 return p == 0 ? ~0u : (1u << p)-1u;
154 }
155
156 /**
157 * Set all bits in a given bitset.
158 *
159 * @param bitset the bitset
160 * @param size number of bits in the bitset
161 */
rbitset_set_all(unsigned * bitset,size_t size)162 static inline void rbitset_set_all(unsigned *bitset, size_t size)
163 {
164 size_t i;
165 size_t n = BITSET_SIZE_ELEMS(size);
166
167 if (n == 0)
168 return;
169
170 for (i = 0; i < n-1; ++i) {
171 bitset[i] = ~0u;
172 }
173 bitset[i] = rbitset_last_mask_(size);
174 }
175
176 /**
177 * Clear a bit at position pos.
178 *
179 * @param bitset the bitset
180 * @param pos the position of the bit to be clear
181 */
rbitset_clear(unsigned * bitset,size_t pos)182 static inline void rbitset_clear(unsigned *bitset, size_t pos)
183 {
184 BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
185 }
186
187 /**
188 * Clear all bits in a given bitset.
189 *
190 * @param bitset the bitset
191 * @param size number of bits in the bitset
192 */
rbitset_clear_all(unsigned * bitset,size_t size)193 static inline void rbitset_clear_all(unsigned *bitset, size_t size)
194 {
195 size_t size_bytes = BITSET_SIZE_BYTES(size);
196 memset(bitset, 0, size_bytes);
197 }
198
199 /**
200 * Flip all bits in a given bitset.
201 *
202 * @param bitset the bitset
203 * @param size number of bits in the bitset
204 */
rbitset_flip_all(unsigned * bitset,size_t size)205 static inline void rbitset_flip_all(unsigned *bitset, size_t size)
206 {
207 size_t pos;
208 size_t n = BITSET_SIZE_ELEMS(size);
209
210 if (n == 0)
211 return;
212
213 for (pos = 0; pos < n-1; ++pos) {
214 bitset[pos] ^= ~0u;
215 }
216 bitset[pos] ^= rbitset_last_mask_(size);
217 }
218
219 /**
220 * Check if a bit is set at position pos.
221 *
222 * @param bitset the bitset
223 * @param pos the position of the bit to check
224 */
rbitset_is_set(const unsigned * bitset,size_t pos)225 static inline bool rbitset_is_set(const unsigned *bitset, size_t pos)
226 {
227 return (BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM))) != 0;
228 }
229
230 /**
231 * Calculate the number of set bits (number of elements).
232 *
233 * @param bitset the bitset
234 * @param size size of the bitset in bits
235 */
rbitset_popcount(const unsigned * bitset,size_t size)236 static inline size_t rbitset_popcount(const unsigned *bitset, size_t size)
237 {
238 size_t i, n = BITSET_SIZE_ELEMS(size);
239 size_t res = 0;
240
241 for (i = 0; i < n; ++i) {
242 res += popcount(bitset[i]);
243 }
244
245 return res;
246 }
247
248 /**
249 * Returns the position of the next bit starting from (and including)
250 * a given position.
251 *
252 * @param bitset a bitset
253 * @param pos the first position to check
254 * @param set if 0 search for unset bit, else for set bit
255 *
256 * @return the first position where a matched bit was found
257 *
258 * @note Does NOT check the size of the bitset, so ensure that a bit
259 * will be found or use a sentinel bit!
260 */
rbitset_next(const unsigned * bitset,size_t pos,bool set)261 static inline size_t rbitset_next(const unsigned *bitset, size_t pos,
262 bool set)
263 {
264 unsigned p;
265 size_t elem_pos = pos / BITS_PER_ELEM;
266 size_t bit_pos = pos % BITS_PER_ELEM;
267
268 unsigned elem = bitset[elem_pos];
269 unsigned mask = set ? 0 : ~0u;
270
271 /*
272 * Mask out the bits smaller than pos in the current unit.
273 * We are only interested in bits set higher than pos.
274 */
275 unsigned in_elem_mask = (1 << bit_pos) - 1;
276
277 elem ^= mask;
278 p = ntz(elem & ~in_elem_mask);
279
280 /* If there is a bit set in the current elem, exit. */
281 if (p < BITS_PER_ELEM) {
282 return elem_pos * BITS_PER_ELEM + p;
283 }
284
285 /* Else search for set bits in the next units. */
286 for (;;) {
287 elem_pos++;
288 elem = bitset[elem_pos] ^ mask;
289
290 p = ntz(elem);
291 if (p < BITS_PER_ELEM) {
292 return elem_pos * BITS_PER_ELEM + p;
293 }
294 }
295 }
296
297 /**
298 * Returns the position of the next bit starting from (and including)
299 * a given position.
300 *
301 * @param bitset a bitset
302 * @param pos the first position to check
303 * @param last first position that is not checked anymore
304 * @param set if 0 search for unset bit, else for set bit
305 *
306 * @return the first position where a matched bit was found.
307 * (size_t)-1 if no bit was found.
308 */
rbitset_next_max(const unsigned * bitset,size_t pos,size_t last,bool set)309 static inline size_t rbitset_next_max(const unsigned *bitset, size_t pos,
310 size_t last, bool set)
311 {
312 size_t p;
313 size_t elem_pos = pos / BITS_PER_ELEM;
314 size_t bit_pos = pos % BITS_PER_ELEM;
315
316 unsigned elem = bitset[elem_pos];
317 unsigned mask = set ? 0u : ~0u;
318 size_t res = (size_t)-1;
319
320 /*
321 * Mask out the bits smaller than pos in the current unit.
322 * We are only interested in bits set higher than pos.
323 */
324 unsigned in_elem_mask = (1u << bit_pos) - 1;
325
326 assert(pos < last);
327
328 elem ^= mask;
329 p = ntz(elem & ~in_elem_mask);
330
331 /* If there is a bit set in the current elem, exit. */
332 if (p < BITS_PER_ELEM) {
333 res = elem_pos * BITS_PER_ELEM + p;
334 } else {
335 size_t n = BITSET_SIZE_ELEMS(last);
336 /* Else search for set bits in the next units. */
337 for (elem_pos++; elem_pos < n; elem_pos++) {
338 elem = bitset[elem_pos] ^ mask;
339
340 p = ntz(elem);
341 if (p < BITS_PER_ELEM) {
342 res = elem_pos * BITS_PER_ELEM + p;
343 break;
344 }
345 }
346 }
347 if (res >= last)
348 res = (size_t)-1;
349
350 return res;
351 }
352
353 /**
354 * Inplace Intersection of two sets.
355 *
356 * @param dst the destination bitset and first operand
357 * @param src the second bitset
358 * @param size size of both bitsets in bits
359 */
rbitset_and(unsigned * dst,const unsigned * src,size_t size)360 static inline void rbitset_and(unsigned *dst, const unsigned *src, size_t size)
361 {
362 size_t i, n = BITSET_SIZE_ELEMS(size);
363
364 for (i = 0; i < n; ++i) {
365 dst[i] &= src[i];
366 }
367 }
368
369 /**
370 * Inplace Union of two sets.
371 *
372 * @param dst the destination bitset and first operand
373 * @param src the second bitset
374 * @param size size of both bitsets in bits
375 */
rbitset_or(unsigned * dst,const unsigned * src,size_t size)376 static inline void rbitset_or(unsigned *dst, const unsigned *src, size_t size)
377 {
378 size_t i, n = BITSET_SIZE_ELEMS(size);
379
380 for (i = 0; i < n; ++i) {
381 dst[i] |= src[i];
382 }
383 }
384
385 /**
386 * Remove all bits in src from dst.
387 *
388 * @param dst the destination bitset and first operand
389 * @param src the second bitset
390 * @param size size of both bitsets in bits
391 */
rbitset_andnot(unsigned * dst,const unsigned * src,size_t size)392 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, size_t size)
393 {
394 size_t i, n = BITSET_SIZE_ELEMS(size);
395
396 for (i = 0; i < n; ++i) {
397 dst[i] &= ~src[i];
398 }
399 }
400
401 /**
402 * Xor of two bitsets.
403 *
404 * @param dst the destination bitset and first operand
405 * @param src the second bitset
406 * @param size size of both bitsets in bits
407 */
rbitset_xor(unsigned * dst,const unsigned * src,size_t size)408 static inline void rbitset_xor(unsigned *dst, const unsigned *src, size_t size)
409 {
410 size_t i, n = BITSET_SIZE_ELEMS(size);
411
412 for (i = 0; i < n; ++i) {
413 dst[i] ^= src[i];
414 }
415 }
416
417 /**
418 * Set bits in a range to zero or one
419 * @param bitset the bitset
420 * @param from first bit to set
421 * @param to last bit (the first bit which is not set anymore)
422 * @param val whether to set to 1 or 0
423 */
rbitset_set_range(unsigned * bitset,size_t from,size_t to,bool val)424 static inline void rbitset_set_range(unsigned *bitset, size_t from,
425 size_t to, bool val)
426 {
427 /*
428 * A small example (for cleaning bits in the same unit).
429 * from = 7
430 * to = 19
431 * do_set = 0
432 * result: xxxxxxx000000000000xxxxxxxxxxxxx
433 * from_unit_mask: 00000001111111111111111111111111
434 * to_unit_mask: 11111111111111111110000000000000
435 * scale: 01234567890123456789012345678901
436 * 1 2 3
437 */
438
439 size_t from_bit = from % BITS_PER_ELEM;
440 size_t from_pos = from / BITS_PER_ELEM;
441 unsigned from_unit_mask = ~((1 << from_bit) - 1);
442
443 size_t to_bit = to % BITS_PER_ELEM;
444 size_t to_pos = to / BITS_PER_ELEM;
445 unsigned to_unit_mask = (1 << to_bit) - 1;
446
447 assert(from < to);
448
449 /* do we want to set the bits in the range? */
450 if (val) {
451 if (from_pos == to_pos) {
452 BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
453 } else {
454 size_t i;
455 BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
456 BITSET_ELEM(bitset, to_pos) |= to_unit_mask;
457 for (i = from_pos + 1; i < to_pos; ++i)
458 BITSET_ELEM(bitset, i) = ~0u;
459 }
460 } else {
461 /* ... or clear them? */
462 if (from_pos == to_pos) {
463 BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
464 } else {
465 size_t i;
466 BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
467 BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask;
468 for (i = from_pos + 1; i < to_pos; ++i)
469 BITSET_ELEM(bitset, i) = 0;
470 }
471 }
472 }
473
474 /**
475 * Returns 1 of two bitsets are equal.
476 *
477 * @param bitset1 the first bitset
478 * @param bitset2 the second bitset
479 * @param size size of both bitsets in bits
480 */
rbitsets_equal(const unsigned * bitset1,const unsigned * bitset2,size_t size)481 static inline bool rbitsets_equal(const unsigned *bitset1,
482 const unsigned *bitset2, size_t size)
483 {
484 size_t size_bytes = BITSET_SIZE_BYTES(size);
485 return memcmp(bitset1, bitset2, size_bytes) == 0;
486 }
487
488 /**
489 * Tests whether 2 bitsets have at least one common set bit.
490 *
491 * @param bitset1 the first bitset
492 * @param bitset2 the second bitset
493 * @param size size of both bitsets in bits
494 */
rbitsets_have_common(const unsigned * bitset1,const unsigned * bitset2,size_t size)495 static inline bool rbitsets_have_common(const unsigned *bitset1,
496 const unsigned *bitset2, size_t size)
497 {
498 size_t i, n = BITSET_SIZE_ELEMS(size);
499
500 for (i = 0; i < n; ++i) {
501 if ((bitset1[i] & bitset2[i]) != 0)
502 return true;
503 }
504 return false;
505 }
506
507 /**
508 * Tests whether all bits set in bitset1 are also set in bitset2.
509 *
510 * @param bitset1 the first bitset
511 * @param bitset2 the second bitset
512 * @param size size of both bitsets in bits
513 */
rbitset_contains(const unsigned * bitset1,const unsigned * bitset2,size_t size)514 static inline bool rbitset_contains(const unsigned *bitset1,
515 const unsigned *bitset2, size_t size)
516 {
517 size_t i, n = BITSET_SIZE_ELEMS(size);
518
519 for (i = 0; i < n; ++i) {
520 if ((bitset1[i] & bitset2[i]) != bitset1[i])
521 return false;
522 }
523 return true;
524 }
525
526 /**
527 * Treat the bitset as a number and subtract 1.
528 * @param bitset the bitset.
529 * @return size size of the bitset in bits
530 */
rbitset_minus1(unsigned * bitset,size_t size)531 static inline void rbitset_minus1(unsigned *bitset, size_t size)
532 {
533 size_t i, n = BITSET_SIZE_ELEMS(size);
534 unsigned last_mask = rbitset_last_mask_(size);
535
536 for (i = 0; i < n; ++i) {
537 unsigned mask = i == n-1 ? last_mask : ~0u;
538 unsigned val = bitset[i] & mask;
539 unsigned val_minus1 = val - 1;
540 bitset[i] = val_minus1 & mask;
541
542 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
543 break;
544 }
545 }
546
547 /**
548 * Copy a raw bitset into another.
549 *
550 * @param dst the destination set
551 * @param src the source set
552 * @param size size of both bitsets in bits
553 */
rbitset_copy(unsigned * dst,const unsigned * src,size_t size)554 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
555 size_t size)
556 {
557 memcpy(dst, src, BITSET_SIZE_BYTES(size));
558 }
559
rbitset_copy_into(unsigned * dst,const unsigned * src,size_t size)560 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
561 size_t size)
562 {
563 size_t n = BITSET_SIZE_ELEMS(size);
564 unsigned last_mask = rbitset_last_mask_(size);
565
566 memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
567 dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);
568 }
569
570 #endif
571