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