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         size_t p;
 308         size_t elem_pos = pos / BITS_PER_ELEM;
 309         size_t bit_pos  = pos % BITS_PER_ELEM;
 310
 311         unsigned elem = bitset[elem_pos];
 312         unsigned mask = set ? 0u : ~0u;
 313         size_t res  = (size_t)-1;
 314
 315         /*
 316          * Mask out the bits smaller than pos in the current unit.
 317          * We are only interested in bits set higher than pos.
 318          */
 319         unsigned in_elem_mask = (1u << bit_pos) - 1;
 320
 321         assert(pos < last);
 322
 323         elem ^= mask;
 324         p = ntz(elem & ~in_elem_mask);
 325
 326         /* If there is a bit set in the current elem, exit. */
 327         if (p < BITS_PER_ELEM) {
 328                 res = elem_pos * BITS_PER_ELEM + p;
 329         } else {
 330                 size_t n = BITSET_SIZE_ELEMS(last);
 331                 /* Else search for set bits in the next units. */
 332                 for (elem_pos++; elem_pos < n; elem_pos++) {
 333                         elem = bitset[elem_pos] ^ mask;
 334
 335                         p = ntz(elem);
 336                         if (p < BITS_PER_ELEM) {
 337                                 res = elem_pos * BITS_PER_ELEM + p;
 338                                 break;
 339                         }
 340                 }
 341         }
 342         if (res >= last)
 343                 res = (size_t)-1;
 344
 345         return res;
 346 }
 347
 348 /**
 349  * Inplace Intersection of two sets.
 350  *
 351  * @param dst   the destination bitset and first operand
 352  * @param src   the second bitset
 353  * @param size  size of both bitsets in bits
 354  */
 355 static inline void rbitset_and(unsigned *dst, const unsigned *src, size_t size)
 356 {
 357         size_t i, n = BITSET_SIZE_ELEMS(size);
 358
 359         for (i = 0; i < n; ++i) {
 360                 dst[i] &= src[i];
 361         }
 362 }
 363
 364 /**
 365  * Inplace Union of two sets.
 366  *
 367  * @param dst   the destination bitset and first operand
 368  * @param src   the second bitset
 369  * @param size  size of both bitsets in bits
 370  */
 371 static inline void rbitset_or(unsigned *dst, const unsigned *src, size_t size)
 372 {
 373         size_t i, n = BITSET_SIZE_ELEMS(size);
 374
 375         for (i = 0; i < n; ++i) {
 376                 dst[i] |= src[i];
 377         }
 378 }
 379
 380 /**
 381  * Remove all bits in src from dst.
 382  *
 383  * @param dst   the destination bitset and first operand
 384  * @param src   the second bitset
 385  * @param size  size of both bitsets in bits
 386  */
 387 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, size_t size)
 388 {
 389         size_t i, n = BITSET_SIZE_ELEMS(size);
 390
 391         for (i = 0; i < n; ++i) {
 392                 dst[i] &= ~src[i];
 393         }
 394 }
 395
 396 /**
 397  * Xor of two bitsets.
 398  *
 399  * @param dst   the destination bitset and first operand
 400  * @param src   the second bitset
 401  * @param size  size of both bitsets in bits
 402  */
 403 static inline void rbitset_xor(unsigned *dst, const unsigned *src, size_t size)
 404 {
 405         size_t i, n = BITSET_SIZE_ELEMS(size);
 406
 407         for (i = 0; i < n; ++i) {
 408                 dst[i] ^= src[i];
 409         }
 410 }
 411
 412 /**
 413  * Set bits in a range to zero or one
 414  * @param bitset   the bitset
 415  * @param from     first bit to set
 416  * @param to       last bit (the first bit which is not set anymore)
 417  * @param val      whether to set to 1 or 0
 418  */
 419 static inline void rbitset_set_range(unsigned *bitset, size_t from,
 420                                      size_t to, bool val)
 421 {
 422         /*
 423          * A small example (for cleaning bits in the same unit).
 424          * from   = 7
 425          * to     = 19
 426          * do_set = 0
 427          * result:         xxxxxxx000000000000xxxxxxxxxxxxx
 428          * from_unit_mask: 00000001111111111111111111111111
 429          * to_unit_mask:   11111111111111111110000000000000
 430          * scale:          01234567890123456789012345678901
 431          *                           1         2         3
 432          */
 433
 434         size_t from_bit         = from % BITS_PER_ELEM;
 435         size_t from_pos         = from / BITS_PER_ELEM;
 436         unsigned from_unit_mask = ~((1 << from_bit) - 1);
 437
 438         size_t to_bit         = to % BITS_PER_ELEM;
 439         size_t to_pos         = to / BITS_PER_ELEM;
 440         unsigned to_unit_mask = (1 << to_bit) - 1;
 441
 442         assert(from < to);
 443
 444         /* do we want to set the bits in the range? */
 445         if (val) {
 446                 if (from_pos == to_pos) {
 447                         BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
 448                 } else {
 449                         size_t i;
 450                         BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
 451                         BITSET_ELEM(bitset, to_pos)   |= to_unit_mask;
 452                         for (i = from_pos + 1; i < to_pos; ++i)
 453                                 BITSET_ELEM(bitset, i) = ~0u;
 454                 }
 455         } else {
 456                 /* ... or clear them? */
 457                 if (from_pos == to_pos) {
 458                         BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
 459                 } else {
 460                         size_t i;
 461                         BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
 462                         BITSET_ELEM(bitset, to_pos)   &= ~to_unit_mask;
 463                         for (i = from_pos + 1; i < to_pos; ++i)
 464                                 BITSET_ELEM(bitset, i) = 0;
 465                 }
 466         }
 467 }
 468
 469 /**
 470  * Returns 1 of two bitsets are equal.
 471  *
 472  * @param bitset1  the first bitset
 473  * @param bitset2  the second bitset
 474  * @param size     size of both bitsets in bits
 475  */
 476 static inline bool rbitsets_equal(const unsigned *bitset1,
 477                                   const unsigned *bitset2, size_t size)
 478 {
 479         size_t size_bytes = BITSET_SIZE_BYTES(size);
 480         return memcmp(bitset1, bitset2, size_bytes) == 0;
 481 }
 482
 483 /**
 484  * Tests whether 2 bitsets have at least one common set bit.
 485  *
 486  * @param bitset1  the first bitset
 487  * @param bitset2  the second bitset
 488  * @param size     size of both bitsets in bits
 489  */
 490 static inline bool rbitsets_have_common(const unsigned *bitset1,
 491                                         const unsigned *bitset2, size_t size)
 492 {
 493         size_t i, n = BITSET_SIZE_ELEMS(size);
 494
 495         for (i = 0; i < n; ++i) {
 496                 if ((bitset1[i] & bitset2[i]) != 0)
 497                         return true;
 498         }
 499         return false;
 500 }
 501
 502 /**
 503  * Tests whether all bits set in bitset1 are also set in bitset2.
 504  *
 505  * @param bitset1  the first bitset
 506  * @param bitset2  the second bitset
 507  * @param size     size of both bitsets in bits
 508  */
 509 static inline bool rbitset_contains(const unsigned *bitset1,
 510                                     const unsigned *bitset2, size_t size)
 511 {
 512         size_t i, n = BITSET_SIZE_ELEMS(size);
 513
 514         for (i = 0; i < n; ++i) {
 515                 if ((bitset1[i] & bitset2[i]) != bitset1[i])
 516                         return false;
 517         }
 518         return true;
 519 }
 520
 521 /**
 522  * Treat the bitset as a number and subtract 1.
 523  * @param  bitset  the bitset.
 524  * @return size    size of the bitset in bits
 525  */
 526 static inline void rbitset_minus1(unsigned *bitset, size_t size)
 527 {
 528         size_t i, n        = BITSET_SIZE_ELEMS(size);
 529         unsigned last_mask = rbitset_last_mask_(size);
 530
 531         for (i = 0; i < n; ++i) {
 532                 unsigned mask       = i == n-1 ? last_mask : ~0u;
 533                 unsigned val        = bitset[i] & mask;
 534                 unsigned val_minus1 = val - 1;
 535                 bitset[i] = val_minus1 & mask;
 536
 537                 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
 538                         break;
 539         }
 540 }
 541
 542 /**
 543  * Copy a raw bitset into another.
 544  *
 545  * @param dst   the destination set
 546  * @param src   the source set
 547  * @param size  size of both bitsets in bits
 548  */
 549 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
 550                                 size_t size)
 551 {
 552         memcpy(dst, src, BITSET_SIZE_BYTES(size));
 553 }
 554
 555 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
 556                                      size_t size)
 557 {
 558         size_t n           = BITSET_SIZE_ELEMS(size);
 559         unsigned last_mask = rbitset_last_mask_(size);
 560
 561         memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
 562         dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);
 563 }
 564
 565 #endif