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