nsz Git - libfirm/blob - ir/adt/raw_bitset.h

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