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)
  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         for (i = 0; i < n-1; ++i) {
 201                 bitset[i] = ~0u;
 202         }
 203         bitset[i] = rbitset_last_mask_(size);
 204 }
 205
 206 /**
 207  * Clear a bit at position pos.
 208  *
 209  * @param bitset  the bitset
 210  * @param pos     the position of the bit to be clear
 211  */
 212 static inline void rbitset_clear(unsigned *bitset, unsigned pos)
 213 {
 214         BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
 215 }
 216
 217 /**
 218  * Clear all bits in a given bitset.
 219  *
 220  * @param bitset  the bitset
 221  * @param size    number of bits in the bitset
 222  */
 223 static inline void rbitset_clear_all(unsigned *bitset, unsigned size)
 224 {
 225         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 226         memset(bitset, 0, size_bytes);
 227 }
 228
 229 /**
 230  * Flip all bits in a given bitset.
 231  *
 232  * @param bitset  the bitset
 233  * @param size    number of bits in the bitset
 234  */
 235 static inline void rbitset_flip_all(unsigned *bitset, unsigned size)
 236 {
 237         unsigned pos;
 238         unsigned n    = BITSET_SIZE_ELEMS(size);
 239         for (pos = 0; pos < n-1; ++pos) {
 240                 bitset[pos] ^= ~0u;
 241         }
 242         bitset[pos] ^= rbitset_last_mask_(size);
 243 }
 244
 245 /**
 246  * Check if a bit is set at position pos.
 247  *
 248  * @param bitset  the bitset
 249  * @param pos     the position of the bit to check
 250  */
 251 static inline bool rbitset_is_set(const unsigned *bitset, unsigned pos)
 252 {
 253         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
 254 }
 255
 256 /**
 257  * Calculate the number of set bits (number of elements).
 258  *
 259  * @param bitset  the bitset
 260  * @param size    size of the bitset in bits
 261  */
 262 static inline unsigned rbitset_popcount(const unsigned *bitset, unsigned size)
 263 {
 264         unsigned i;
 265         unsigned n   = BITSET_SIZE_ELEMS(size);
 266         unsigned res = 0;
 267
 268         for (i = 0; i < n; ++i) {
 269                 res += popcount(bitset[i]);
 270         }
 271
 272         return res;
 273 }
 274
 275 /**
 276  * Returns the position of the next bit starting from (and including)
 277  * a given position.
 278  *
 279  * @param bitset  a bitset
 280  * @param pos     the first position to check
 281  * @param set     if 0 search for unset bit, else for set bit
 282  *
 283  * @return the first position where a matched bit was found
 284  *
 285  * @note Does NOT check the size of the bitset, so ensure that a bit
 286  *       will be found or use a sentinel bit!
 287  */
 288 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos,
 289                                     bool set)
 290 {
 291         unsigned p;
 292         unsigned elem_pos = pos / BITS_PER_ELEM;
 293         unsigned bit_pos = pos % BITS_PER_ELEM;
 294
 295         unsigned elem = bitset[elem_pos];
 296         unsigned mask = set ? 0 : ~0u;
 297
 298         /*
 299          * Mask out the bits smaller than pos in the current unit.
 300          * We are only interested in bits set higher than pos.
 301          */
 302         unsigned in_elem_mask = (1 << bit_pos) - 1;
 303
 304         elem ^= mask;
 305         p = ntz(elem & ~in_elem_mask);
 306
 307         /* If there is a bit set in the current elem, exit. */
 308         if (p < BITS_PER_ELEM) {
 309                 return elem_pos * BITS_PER_ELEM + p;
 310         }
 311
 312         /* Else search for set bits in the next units. */
 313         for (;;) {
 314                 elem_pos++;
 315                 elem = bitset[elem_pos] ^ mask;
 316
 317                 p = ntz(elem);
 318                 if (p < BITS_PER_ELEM) {
 319                         return elem_pos * BITS_PER_ELEM + p;
 320                 }
 321         }
 322 }
 323
 324 /**
 325  * Returns the position of the next bit starting from (and including)
 326  * a given position.
 327  *
 328  * @param bitset  a bitset
 329  * @param pos     the first position to check
 330  * @param last    first position that is not checked anymore
 331  * @param set     if 0 search for unset bit, else for set bit
 332  *
 333  * @return the first position where a matched bit was found.
 334  *         (unsigned)-1 if no bit was found.
 335  */
 336 static inline unsigned rbitset_next_max(const unsigned *bitset, unsigned pos,
 337                                         unsigned last, bool set)
 338 {
 339         unsigned p;
 340         unsigned elem_pos = pos / BITS_PER_ELEM;
 341         unsigned bit_pos  = pos % BITS_PER_ELEM;
 342
 343         unsigned elem = bitset[elem_pos];
 344         unsigned mask = set ? 0 : ~0u;
 345         unsigned res  = (unsigned)-1;
 346
 347         /*
 348          * Mask out the bits smaller than pos in the current unit.
 349          * We are only interested in bits set higher than pos.
 350          */
 351         unsigned in_elem_mask = (1 << bit_pos) - 1;
 352
 353         assert(pos < last);
 354
 355         elem ^= mask;
 356         p = ntz(elem & ~in_elem_mask);
 357
 358         /* If there is a bit set in the current elem, exit. */
 359         if (p < BITS_PER_ELEM) {
 360                 res = elem_pos * BITS_PER_ELEM + p;
 361         } else {
 362                 unsigned n = BITSET_SIZE_ELEMS(last);
 363                 /* Else search for set bits in the next units. */
 364                 for (elem_pos++; elem_pos < n; elem_pos++) {
 365                         elem = bitset[elem_pos] ^ mask;
 366
 367                         p = ntz(elem);
 368                         if (p < BITS_PER_ELEM) {
 369                                 res = elem_pos * BITS_PER_ELEM + p;
 370                                 break;
 371                         }
 372                 }
 373         }
 374         if (res >= last)
 375                 res = (unsigned)-1;
 376
 377         return res;
 378 }
 379
 380 /**
 381  * Inplace Intersection of two sets.
 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_and(unsigned *dst, const unsigned *src, unsigned size)
 388 {
 389         unsigned i, n = BITSET_SIZE_ELEMS(size);
 390
 391         for (i = 0; i < n; ++i) {
 392                 dst[i] &= src[i];
 393         }
 394 }
 395
 396 /**
 397  * Inplace Union of two sets.
 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_or(unsigned *dst, const unsigned *src, unsigned size)
 404 {
 405         unsigned i, n = BITSET_SIZE_ELEMS(size);
 406
 407         for (i = 0; i < n; ++i) {
 408                 dst[i] |= src[i];
 409         }
 410 }
 411
 412 /**
 413  * Remove all bits in src from dst.
 414  *
 415  * @param dst   the destination bitset and first operand
 416  * @param src   the second bitset
 417  * @param size  size of both bitsets in bits
 418  */
 419 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
 420 {
 421         unsigned i, n = BITSET_SIZE_ELEMS(size);
 422
 423         for (i = 0; i < n; ++i) {
 424                 dst[i] &= ~src[i];
 425         }
 426 }
 427
 428 /**
 429  * Xor of two bitsets.
 430  *
 431  * @param dst   the destination bitset and first operand
 432  * @param src   the second bitset
 433  * @param size  size of both bitsets in bits
 434  */
 435 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
 436 {
 437         unsigned i, n = BITSET_SIZE_ELEMS(size);
 438
 439         for (i = 0; i < n; ++i) {
 440                 dst[i] ^= src[i];
 441         }
 442 }
 443
 444 /**
 445  * Set bits in a range to zero or one
 446  * @param bitset   the bitset
 447  * @param from     first bit to set
 448  * @param to       last bit (the first bit which is not set anymore)
 449  * @param val      wether to set to 1 or 0
 450  */
 451 static inline void rbitset_set_range(unsigned *bitset, unsigned from,
 452                                      unsigned to, bool val)
 453 {
 454         /*
 455          * A small example (for cleaning bits in the same unit).
 456          * from   = 7
 457          * to     = 19
 458          * do_set = 0
 459          * result:         xxxxxxx000000000000xxxxxxxxxxxxx
 460          * from_unit_mask: 00000001111111111111111111111111
 461          * to_unit_mask:   11111111111111111110000000000000
 462          * scale:          01234567890123456789012345678901
 463          *                           1         2         3
 464          */
 465
 466         unsigned from_bit       = from % BITS_PER_ELEM;
 467         unsigned from_pos       = from / BITS_PER_ELEM;
 468         unsigned from_unit_mask = ~((1 << from_bit) - 1);
 469
 470         unsigned to_bit         = to % BITS_PER_ELEM;
 471         unsigned to_pos         = to / BITS_PER_ELEM;
 472         unsigned to_unit_mask   = (1 << to_bit) - 1;
 473
 474         assert(from < to);
 475
 476         /* do we want to set the bits in the range? */
 477         if (val) {
 478                 if (from_pos == to_pos) {
 479                         BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
 480                 } else {
 481                         unsigned i;
 482                         BITSET_ELEM(bitset, from_pos) |= from_unit_mask;
 483                         BITSET_ELEM(bitset, to_pos)   |= to_unit_mask;
 484                         for (i = from_pos + 1; i < to_pos; ++i)
 485                                 BITSET_ELEM(bitset, i) = ~0u;
 486                 }
 487         } else {
 488                 /* ... or clear them? */
 489                 if (from_pos == to_pos) {
 490                         BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
 491                 } else {
 492                         unsigned i;
 493                         BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask;
 494                         BITSET_ELEM(bitset, to_pos)   &= ~to_unit_mask;
 495                         for (i = from_pos + 1; i < to_pos; ++i)
 496                                 BITSET_ELEM(bitset, i) = 0;
 497                 }
 498         }
 499 }
 500
 501 /**
 502  * Returns 1 of two bitsets are equal.
 503  *
 504  * @param bitset1  the first bitset
 505  * @param bitset2  the second bitset
 506  * @param size     size of both bitsets in bits
 507  */
 508 static inline bool rbitsets_equal(const unsigned *bitset1,
 509                                   const unsigned *bitset2, unsigned size)
 510 {
 511         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 512         return memcmp(bitset1, bitset2, size_bytes) == 0;
 513 }
 514
 515 /**
 516  * Tests wether 2 bitsets wether at least 1 bit is set in both.
 517  *
 518  * @param bitset1  the first bitset
 519  * @param bitset2  the second bitset
 520  * @param size     size of both bitsets in bits
 521  */
 522 static inline bool rbitsets_have_common(const unsigned *bitset1,
 523                                         const unsigned *bitset2, unsigned size)
 524 {
 525         unsigned i;
 526         unsigned n = BITSET_SIZE_ELEMS(size);
 527
 528         for (i = 0; i < n; ++i) {
 529                 if ((bitset1[i] & bitset2[i]) != 0)
 530                         return true;
 531         }
 532         return false;
 533 }
 534
 535 /**
 536  * Tests wether all bits set in bitset1 are also set in bitset2.
 537  *
 538  * @param bitset1  the first bitset
 539  * @param bitset2  the second bitset
 540  * @param size     size of both bitsets in bits
 541  */
 542 static inline bool rbitset_contains(const unsigned *bitset1,
 543                                     const unsigned *bitset2, unsigned size)
 544 {
 545         unsigned i;
 546         unsigned n = BITSET_SIZE_ELEMS(size);
 547
 548         for (i = 0; i < n; ++i) {
 549                 if ((bitset1[i] & bitset2[i]) != bitset1[i])
 550                         return false;
 551         }
 552         return true;
 553 }
 554
 555 /**
 556  * Treat the bitset as a number and subtract 1.
 557  * @param  bitset  the bitset.
 558  * @return size    size of the bitset in bits
 559  */
 560 static inline void rbitset_minus1(unsigned *bitset, unsigned size)
 561 {
 562         unsigned i;
 563         unsigned n         = BITSET_SIZE_ELEMS(size);
 564         unsigned last_mask = rbitset_last_mask_(size);
 565
 566         for (i = 0; i < n; ++i) {
 567                 unsigned mask       = i == n-1 ? last_mask : ~0u;
 568                 unsigned val        = bitset[i] & mask;
 569                 unsigned val_minus1 = val - 1;
 570                 bitset[i] = val_minus1 & mask;
 571
 572                 if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0)
 573                         break;
 574         }
 575 }
 576
 577 /**
 578  * Copy a raw bitset into another.
 579  *
 580  * @param dst   the destination set
 581  * @param src   the source set
 582  * @param size  size of both bitsets in bits
 583  */
 584 static inline void rbitset_copy(unsigned *dst, const unsigned *src,
 585                                 unsigned size)
 586 {
 587         memcpy(dst, src, BITSET_SIZE_BYTES(size));
 588 }
 589
 590 static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
 591                                      unsigned size)
 592 {
 593         unsigned n         = BITSET_SIZE_ELEMS(size);
 594         unsigned last_mask = rbitset_last_mask_(size);
 595
 596         memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8));
 597         dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask);
 598 }
 599
 600 #endif