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