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