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