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  * @brief
  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 {
  93         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  94         unsigned *res = obstack_alloc(obst, size_bytes);
  95         memset(res, 0, size_bytes);
  96
  97         return res;
  98 }
  99
 100 /**
 101  * Allocate an empty raw bitset including the size on an obstack.
 102  * The size of this bitset can be accessed by bitset[-1].
 103  *
 104  * @param obst  the obstack where the bitset is allocated on
 105  * @param size  number of bits in the bitset
 106  *
 107  * @return the new bitset
 108  */
 109 static inline unsigned *rbitset_w_size_obstack_alloc(struct obstack *obst, 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
 133 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
 134                                           const unsigned *old_bitset,
 135                                           unsigned size)
 136 {
 137         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 138         unsigned *res = obstack_alloc(obst, size_bytes);
 139         memcpy(res, old_bitset, size_bytes);
 140
 141         return res;
 142 }
 143
 144 /**
 145  * Check if a bitset is empty, ie all bits cleared.
 146  */
 147 static inline int rbitset_is_empty(unsigned *bitset, unsigned size)
 148 {
 149         unsigned n = BITSET_SIZE_ELEMS(size);
 150         unsigned i;
 151         for (i = 0; i < n; ++i) {
 152                 if (bitset[i] != 0)
 153                         return 0;
 154         }
 155
 156         return 1;
 157 }
 158
 159 /**
 160  * Set a bit at position pos.
 161  *
 162  * @param bitset  the bitset
 163  * @param pos     the position of the bit to be set
 164  */
 165 static inline void rbitset_set(unsigned *bitset, unsigned pos)
 166 {
 167         BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
 168 }
 169
 170 /**
 171  * Set all bits in a given bitset.
 172  *
 173  * @param bitset  the bitset
 174  * @param size    number of bits in the bitset
 175  */
 176 static inline void rbitset_set_all(unsigned *bitset, unsigned size)
 177 {
 178         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 179         memset(bitset, ~0, size_bytes);
 180 }
 181
 182
 183 /**
 184  * Clear a bit at position pos.
 185  *
 186  * @param bitset  the bitset
 187  * @param pos     the position of the bit to be clear
 188  */
 189 static inline void rbitset_clear(unsigned *bitset, unsigned pos)
 190 {
 191         BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
 192 }
 193
 194 /**
 195  * Clear all bits in a given bitset.
 196  *
 197  * @param bitset  the bitset
 198  * @param size    number of bits in the bitset
 199  */
 200 static inline void rbitset_clear_all(unsigned *bitset, unsigned size)
 201 {
 202         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 203         memset(bitset, 0, size_bytes);
 204 }
 205
 206 /**
 207  * Check if a bit is set at position pos.
 208  *
 209  * @param bitset  the bitset
 210  * @param pos     the position of the bit to check
 211  */
 212 static inline int rbitset_is_set(const unsigned *bitset, unsigned pos)
 213 {
 214         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
 215 }
 216
 217 /**
 218  * Calculate the number of set bits (number of elements).
 219  *
 220  * @param bitset  the bitset
 221  * @param size    size of the bitset
 222  */
 223 static inline unsigned rbitset_popcnt(const unsigned *bitset, unsigned size)
 224 {
 225         unsigned pos;
 226         unsigned n = BITSET_SIZE_ELEMS(size);
 227         unsigned res = 0;
 228         const unsigned *elem = bitset;
 229
 230         for (pos = 0; pos < n; ++pos) {
 231                 res += _bitset_inside_pop(elem);
 232                 elem++;
 233         }
 234
 235         return res;
 236 }
 237
 238 /**
 239  * Returns the position of the next bit starting from (and including)
 240  * a given position.
 241  *
 242  * @param bitset  a bitset
 243  * @param pos     the first position to check
 244  * @param set     if 0 search for unset bit, else for set bit
 245  *
 246  * @return the first position where a matched bit was found
 247  *
 248  * @note Does NOT check the size of the bitset, so ensure that a bit
 249  *       will be found or use a sentinel bit!
 250  */
 251 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set)
 252 {
 253         unsigned p;
 254         unsigned elem_pos = pos / BITS_PER_ELEM;
 255         unsigned bit_pos = pos % BITS_PER_ELEM;
 256
 257         unsigned elem = bitset[elem_pos];
 258         unsigned mask = 0;
 259
 260         /*
 261          * Mask out the bits smaller than pos in the current unit.
 262          * We are only interested in bits set higher than pos.
 263          */
 264         unsigned in_elem_mask = (1 << bit_pos) - 1;
 265
 266         if (!set)
 267                 mask = ~mask;
 268         elem ^= mask;
 269         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 270
 271         /* If there is a bit set in the current elem, exit. */
 272         if (p < BITS_PER_ELEM) {
 273                 return elem_pos * BITS_PER_ELEM + p;
 274         }
 275
 276         /* Else search for set bits in the next units. */
 277         while (1) {
 278                 elem_pos++;
 279                 elem = bitset[elem_pos] ^ mask;
 280
 281                 p = _bitset_inside_ntz_value(elem);
 282                 if (p < BITS_PER_ELEM) {
 283                         return elem_pos * BITS_PER_ELEM + p;
 284                 }
 285         }
 286 }
 287
 288 /**
 289  * Inplace Intersection of two sets.
 290  *
 291  * @param dst   the destination bitset and first operand
 292  * @param src   the second bitset
 293  * @param size  size of both bitsets
 294  */
 295 static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size)
 296 {
 297         unsigned i, n = BITSET_SIZE_ELEMS(size);
 298
 299         for (i = 0; i < n; ++i) {
 300                 dst[i] &= src[i];
 301         }
 302 }
 303
 304 /**
 305  * Inplace Union of two sets.
 306  *
 307  * @param dst   the destination bitset and first operand
 308  * @param src   the second bitset
 309  * @param size  size of both bitsets
 310  */
 311 static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size)
 312 {
 313         unsigned i, n = BITSET_SIZE_ELEMS(size);
 314
 315         for (i = 0; i < n; ++i) {
 316                 dst[i] |= src[i];
 317         }
 318 }
 319
 320 /**
 321  * Remove all bits in src from dst.
 322  *
 323  * @param dst   the destination bitset and first operand
 324  * @param src   the second bitset
 325  * @param size  size of both bitsets
 326  */
 327 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
 328 {
 329         unsigned i, n = BITSET_SIZE_ELEMS(size);
 330
 331         for (i = 0; i < n; ++i) {
 332                 dst[i] &= ~src[i];
 333         }
 334 }
 335
 336 /**
 337  * Xor of two bitsets.
 338  *
 339  * @param dst   the destination bitset and first operand
 340  * @param src   the second bitset
 341  * @param size  size of both bitsets
 342  */
 343 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
 344 {
 345         unsigned i, n = BITSET_SIZE_ELEMS(size);
 346
 347         for (i = 0; i < n; ++i) {
 348                 dst[i] ^= src[i];
 349         }
 350 }
 351
 352 /**
 353  * Returns 1 of two bitsets are equal.
 354  *
 355  * @param bitset1  the first bitset
 356  * @param bitset2  the second bitset
 357  * @param size     size of both bitsets
 358  */
 359 static inline int rbitset_equal(const unsigned *bitset1,
 360                                 const unsigned *bitset2, size_t size)
 361 {
 362         return memcmp(bitset1, bitset2, BITSET_SIZE_BYTES(size)) == 0;
 363 }
 364
 365 /**
 366  * Tests wether 2 bitsets wether at least 1 bit is set in both.
 367  *
 368  * @param bitset1  the first bitset
 369  * @param bitset2  the second bitset
 370  * @param size     size of both bitsets
 371  */
 372 static inline int rbitsets_have_common(const unsigned *bitset1,
 373                                        const unsigned *bitset2, size_t size)
 374 {
 375         unsigned i;
 376         unsigned n = BITSET_SIZE_ELEMS(size);
 377
 378         for (i = 0; i < n; ++i) {
 379                 if ((bitset1[i] & bitset2[i]) != 0)
 380                         return 1;
 381         }
 382         return 0;
 383 }
 384
 385 /**
 386  * Copy a raw bitset into another.
 387  *
 388  * @param dst   the destination set
 389  * @param src   the source set
 390  * @param size  size of both bitsets
 391  */
 392 static inline void rbitset_copy(unsigned *dst, const unsigned *src, size_t size)
 393 {
 394         memcpy(dst, src, BITSET_SIZE_BYTES(size));
 395 }
 396
 397 /**
 398  * Copy a raw bitset into an bitset.
 399  *
 400  * @deprecated
 401  */
 402 static inline void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset)
 403 {
 404         // TODO optimize me (or remove me)
 405         unsigned i, n = bitset_size(bitset);
 406         for (i = 0; i < n; ++i) {
 407                 if (rbitset_is_set(rbitset, i))
 408                         bitset_set(bitset, i);
 409         }
 410 }
 411
 412 #endif /* FIRM_ADT_RAW_BITSET_H */