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