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

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