nsz Git - libfirm/blob - include/libfirm/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   helper functions for working with raw bitsets
  23  * @date    15.10.2004
  24  * @author  Matthias Braun
  25  * @version $Id$
  26  * @summary
  27  *     Raw bitsets are constructed from unsigned int arrays. Additional information
  28  *     like the size of the bitset or the used memory are not stored for
  29  *     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. It is assumed that
  37  *     exactly 32 bits may be put into each element of the array. If there are
  38  *     remaining bits, then they should be 0
  39  */
  40 #ifndef FIRM_ADT_RAW_BITSET_H
  41 #define FIRM_ADT_RAW_BITSET_H
  42
  43 #include <assert.h>
  44 #include "bitset.h"
  45 #include "obst.h"
  46
  47 /** The base type for raw bitsets. */
  48 typedef unsigned int  rawbs_base_t;
  49
  50 #define BITS_PER_ELEM                   (sizeof(rawbs_base_t) * 8)
  51 #define BITSET_SIZE_ELEMS(size_bits)    ((size_bits)/BITS_PER_ELEM + 1)
  52 #define BITSET_SIZE_BYTES(size_bits)    (BITSET_SIZE_ELEMS(size_bits) * sizeof(rawbs_base_t))
  53 #define BITSET_ELEM(bitset,pos)         bitset[pos / BITS_PER_ELEM]
  54
  55 /**
  56  * Allocate an empty raw bitset on the heap.
  57  *
  58  * @param size  number of bits in the bitset
  59  *
  60  * @return the new bitset
  61  */
  62 static inline unsigned *rbitset_malloc(unsigned size) {
  63         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  64         unsigned *res = xmalloc(size_bytes);
  65         memset(res, 0, size_bytes);
  66
  67         return res;
  68 }
  69
  70 /**
  71  * Allocate an empty raw bitset on the stack.
  72  *
  73  * @param res   will contain the newly allocated bitset
  74  * @param size  number of bits in the bitset
  75  */
  76 #define rbitset_alloca(res, size) \
  77 do { \
  78         unsigned size_bytes = BITSET_SIZE_BYTES(size); \
  79         res = alloca(size_bytes); \
  80         memset(res, 0, size_bytes); \
  81 } while(0)
  82
  83 /**
  84  * Allocate an empty raw bitset on an obstack.
  85  *
  86  * @param obst  the obstack where the bitset is allocated on
  87  * @param size  number of bits in the bitset
  88  *
  89  * @return the new bitset
  90  */
  91 static inline unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size) {
  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, unsigned size) {
 109         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 110         unsigned *res = obstack_alloc(obst, size_bytes + sizeof(unsigned));
 111         *res = size;
 112         ++res;
 113         memset(res, 0, size_bytes);
 114
 115         return res;
 116 }
 117
 118 /** Return the size of a bitset allocated with a *_w_size_* function */
 119 #define rbitset_size(set)       (set)[-1]
 120
 121 /**
 122  * Duplicate a raw bitset on an obstack.
 123  *
 124  * @param obst       the obstack where the bitset is allocated on
 125  * @param old_bitset the bitset to be duplicated
 126  * @param size       number of bits in the bitset
 127  *
 128  * @return the new bitset
 129  */
 130 static inline
 131 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
 132                                           const unsigned *old_bitset,
 133                                           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 int rbitset_is_empty(unsigned *bitset, unsigned size) {
 146         unsigned i, size_bytes = BITSET_SIZE_BYTES(size);
 147         for (i = 0; i < size_bytes; ++i)
 148                 if (bitset[i]) return 0;
 149         return 1;
 150 }
 151
 152 /**
 153  * Set a bit at position pos.
 154  *
 155  * @param bitset  the bitset
 156  * @param pos     the position of the bit to be set
 157  */
 158 static inline void rbitset_set(unsigned *bitset, unsigned pos) {
 159         BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
 160 }
 161
 162 /**
 163  * Set all bits in a given bitset.
 164  *
 165  * @param bitset  the bitset
 166  * @param size    number of bits in the bitset
 167  */
 168 static inline void rbitset_set_all(unsigned *bitset, unsigned size) {
 169         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 170         memset(bitset, ~0, size_bytes);
 171 }
 172
 173
 174 /**
 175  * Clear a bit at position pos.
 176  *
 177  * @param bitset  the bitset
 178  * @param pos     the position of the bit to be clear
 179  */
 180 static inline void rbitset_clear(unsigned *bitset, unsigned pos) {
 181         BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
 182 }
 183
 184 /**
 185  * Clear all bits in a given bitset.
 186  *
 187  * @param bitset  the bitset
 188  * @param size    number of bits in the bitset
 189  */
 190 static inline void rbitset_clear_all(unsigned *bitset, unsigned size) {
 191         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 192         memset(bitset, 0, size_bytes);
 193 }
 194
 195 /**
 196  * Check if a bit is set at position pos.
 197  *
 198  * @param bitset  the bitset
 199  * @param pos     the position of the bit to check
 200  */
 201 static inline int rbitset_is_set(const unsigned *bitset, unsigned pos) {
 202         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
 203 }
 204
 205 /**
 206  * Calculate the number of set bits (number of elements).
 207  *
 208  * @param bitset  the bitset
 209  * @param size    size of the bitset
 210  */
 211 static inline unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) {
 212         unsigned pos;
 213         unsigned n = BITSET_SIZE_ELEMS(size);
 214         unsigned res = 0;
 215         const unsigned *elem = bitset;
 216
 217         for (pos = 0; pos < n; ++pos) {
 218                 res += _bitset_inside_pop(elem);
 219                 elem++;
 220         }
 221
 222         return res;
 223 }
 224
 225 /**
 226  * Returns the position of the next bit starting from (and including)
 227  * a given position.
 228  *
 229  * @param bitset  a bitset
 230  * @param pos     the first position to check
 231  * @param set     if 0 search for unset bit, else for set bit
 232  *
 233  * @return the first position where a matched bit was found
 234  *
 235  * @note Does NOT check the size of the bitset, so ensure that a bit
 236  *       will be found or use a sentinel bit!
 237  */
 238 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) {
 239         unsigned p;
 240         unsigned elem_pos = pos / BITS_PER_ELEM;
 241         unsigned bit_pos = pos % BITS_PER_ELEM;
 242
 243         unsigned elem = bitset[elem_pos];
 244         unsigned mask = 0;
 245
 246         /*
 247          * Mask out the bits smaller than pos in the current unit.
 248          * We are only interested in bits set higher than pos.
 249          */
 250         unsigned in_elem_mask = (1 << bit_pos) - 1;
 251
 252         if (!set)
 253                 mask = ~mask;
 254         elem ^= mask;
 255         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 256
 257         /* If there is a bit set in the current elem, exit. */
 258         if (p < BITS_PER_ELEM) {
 259                 return elem_pos * BITS_PER_ELEM + p;
 260         }
 261
 262         /* Else search for set bits in the next units. */
 263         while (1) {
 264                 elem_pos++;
 265                 elem = bitset[elem_pos] ^ mask;
 266
 267                 p = _bitset_inside_ntz_value(elem);
 268                 if (p < BITS_PER_ELEM) {
 269                         return elem_pos * BITS_PER_ELEM + p;
 270                 }
 271         }
 272 }
 273
 274 /**
 275  * Inplace Intersection of two sets.
 276  *
 277  * @param dst   the destination bitset and first operand
 278  * @param src   the second bitset
 279  * @param size  size of both bitsets
 280  */
 281 static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size)
 282 {
 283         unsigned i, n = BITSET_SIZE_ELEMS(size);
 284
 285         for (i = 0; i < n; ++i) {
 286                 dst[i] &= src[i];
 287         }
 288 }
 289
 290 /**
 291  * Inplace Union of two sets.
 292  *
 293  * @param dst   the destination bitset and first operand
 294  * @param src   the second bitset
 295  * @param size  size of both bitsets
 296  */
 297 static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size)
 298 {
 299         unsigned i, n = BITSET_SIZE_ELEMS(size);
 300
 301         for (i = 0; i < n; ++i) {
 302                 dst[i] |= src[i];
 303         }
 304 }
 305
 306 /**
 307  * Remove all bits in src from dst.
 308  *
 309  * @param dst   the destination bitset and first operand
 310  * @param src   the second bitset
 311  * @param size  size of both bitsets
 312  */
 313 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
 314 {
 315         unsigned i, n = BITSET_SIZE_ELEMS(size);
 316
 317         for (i = 0; i < n; ++i) {
 318                 dst[i] &= ~src[i];
 319         }
 320 }
 321
 322 /**
 323  * Xor of two bitsets.
 324  *
 325  * @param dst   the destination bitset and first operand
 326  * @param src   the second bitset
 327  * @param size  size of both bitsets
 328  */
 329 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
 330 {
 331         unsigned i, n = BITSET_SIZE_ELEMS(size);
 332
 333         for (i = 0; i < n; ++i) {
 334                 dst[i] ^= src[i];
 335         }
 336 }
 337
 338 /**
 339  * Returns 1 of two bitsets are equal.
 340  *
 341  * @param bitset1  the first bitset
 342  * @param bitset2  the second bitset
 343  * @param size     size of both bitsets
 344  */
 345 static inline int rbitset_equal(const unsigned *bitset1,
 346                                 const unsigned *bitset2, size_t size)
 347 {
 348         return memcmp(bitset1, bitset2, BITSET_SIZE_BYTES(size)) == 0;
 349 }
 350
 351 /**
 352  * Tests wether 2 bitsets wether at least 1 bit is set in both.
 353  *
 354  * @param bitset1  the first bitset
 355  * @param bitset2  the second bitset
 356  * @param size     size of both bitsets
 357  */
 358 static inline int rbitsets_have_common(const unsigned *bitset1,
 359                                        const unsigned *bitset2, size_t size)
 360 {
 361         unsigned i;
 362         unsigned n = BITSET_SIZE_ELEMS(size);
 363
 364         for (i = 0; i < n; ++i) {
 365                 if ((bitset1[i] & bitset2[i]) != 0)
 366                         return 1;
 367         }
 368         return 0;
 369 }
 370
 371 /**
 372  * Copy a raw bitset into another.
 373  *
 374  * @param dst   the destination set
 375  * @param src   the source set
 376  * @param size  size of both bitsets
 377  */
 378 static inline void rbitset_copy(unsigned *dst, const unsigned *src, size_t size)
 379 {
 380         memcpy(dst, src, BITSET_SIZE_BYTES(size));
 381 }
 382
 383 /**
 384  * Copy a raw bitset into an bitset.
 385  *
 386  * @deprecated
 387  */
 388 static inline void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) {
 389         // TODO optimize me (or remove me)
 390         unsigned i, n = bitset_size(bitset);
 391         for (i = 0; i < n; ++i) {
 392                 if (rbitset_is_set(rbitset, i))
 393                         bitset_set(bitset, i);
 394         }
 395 }
 396
 397 #endif /* FIRM_ADT_RAW_BITSET_H */