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 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  */
  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  */
  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  */
 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  */
 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  */
 142 static inline void rbitset_flip(unsigned *bitset, size_t pos)
 143 {
 144         BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM);
 145 }
 146
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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
 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