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 {
  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 size_bytes = BITSET_SIZE_ELEMS(size);
 150         unsigned i;
 151         for (i = 0; i < size_bytes; ++i)
 152                 if (bitset[i] != 0)
 153                         return 0;
 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_popcnt(const unsigned *bitset, unsigned size)
 223 {
 224         unsigned pos;
 225         unsigned n = BITSET_SIZE_ELEMS(size);
 226         unsigned res = 0;
 227         const unsigned *elem = bitset;
 228
 229         for (pos = 0; pos < n; ++pos) {
 230                 res += _bitset_inside_pop(elem);
 231                 elem++;
 232         }
 233
 234         return res;
 235 }
 236
 237 /**
 238  * Returns the position of the next bit starting from (and including)
 239  * a given position.
 240  *
 241  * @param bitset  a bitset
 242  * @param pos     the first position to check
 243  * @param set     if 0 search for unset bit, else for set bit
 244  *
 245  * @return the first position where a matched bit was found
 246  *
 247  * @note Does NOT check the size of the bitset, so ensure that a bit
 248  *       will be found or use a sentinel bit!
 249  */
 250 static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set)
 251 {
 252         unsigned p;
 253         unsigned elem_pos = pos / BITS_PER_ELEM;
 254         unsigned bit_pos = pos % BITS_PER_ELEM;
 255
 256         unsigned elem = bitset[elem_pos];
 257         unsigned mask = 0;
 258
 259         /*
 260          * Mask out the bits smaller than pos in the current unit.
 261          * We are only interested in bits set higher than pos.
 262          */
 263         unsigned in_elem_mask = (1 << bit_pos) - 1;
 264
 265         if (!set)
 266                 mask = ~mask;
 267         elem ^= mask;
 268         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 269
 270         /* If there is a bit set in the current elem, exit. */
 271         if (p < BITS_PER_ELEM) {
 272                 return elem_pos * BITS_PER_ELEM + p;
 273         }
 274
 275         /* Else search for set bits in the next units. */
 276         while (1) {
 277                 elem_pos++;
 278                 elem = bitset[elem_pos] ^ mask;
 279
 280                 p = _bitset_inside_ntz_value(elem);
 281                 if (p < BITS_PER_ELEM) {
 282                         return elem_pos * BITS_PER_ELEM + p;
 283                 }
 284         }
 285 }
 286
 287 /**
 288  * Inplace Intersection of two sets.
 289  *
 290  * @param dst   the destination bitset and first operand
 291  * @param src   the second bitset
 292  * @param size  size of both bitsets
 293  */
 294 static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size)
 295 {
 296         unsigned i, n = BITSET_SIZE_ELEMS(size);
 297
 298         for (i = 0; i < n; ++i) {
 299                 dst[i] &= src[i];
 300         }
 301 }
 302
 303 /**
 304  * Inplace Union of two sets.
 305  *
 306  * @param dst   the destination bitset and first operand
 307  * @param src   the second bitset
 308  * @param size  size of both bitsets
 309  */
 310 static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size)
 311 {
 312         unsigned i, n = BITSET_SIZE_ELEMS(size);
 313
 314         for (i = 0; i < n; ++i) {
 315                 dst[i] |= src[i];
 316         }
 317 }
 318
 319 /**
 320  * Remove all bits in src from dst.
 321  *
 322  * @param dst   the destination bitset and first operand
 323  * @param src   the second bitset
 324  * @param size  size of both bitsets
 325  */
 326 static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size)
 327 {
 328         unsigned i, n = BITSET_SIZE_ELEMS(size);
 329
 330         for (i = 0; i < n; ++i) {
 331                 dst[i] &= ~src[i];
 332         }
 333 }
 334
 335 /**
 336  * Xor of two bitsets.
 337  *
 338  * @param dst   the destination bitset and first operand
 339  * @param src   the second bitset
 340  * @param size  size of both bitsets
 341  */
 342 static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size)
 343 {
 344         unsigned i, n = BITSET_SIZE_ELEMS(size);
 345
 346         for (i = 0; i < n; ++i) {
 347                 dst[i] ^= src[i];
 348         }
 349 }
 350
 351 /**
 352  * Returns 1 of two bitsets are equal.
 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 rbitset_equal(const unsigned *bitset1,
 359                                 const unsigned *bitset2, size_t size)
 360 {
 361         return memcmp(bitset1, bitset2, BITSET_SIZE_BYTES(size)) == 0;
 362 }
 363
 364 /**
 365  * Tests wether 2 bitsets wether at least 1 bit is set in both.
 366  *
 367  * @param bitset1  the first bitset
 368  * @param bitset2  the second bitset
 369  * @param size     size of both bitsets
 370  */
 371 static inline int rbitsets_have_common(const unsigned *bitset1,
 372                                        const unsigned *bitset2, size_t size)
 373 {
 374         unsigned i;
 375         unsigned n = BITSET_SIZE_ELEMS(size);
 376
 377         for (i = 0; i < n; ++i) {
 378                 if ((bitset1[i] & bitset2[i]) != 0)
 379                         return 1;
 380         }
 381         return 0;
 382 }
 383
 384 /**
 385  * Copy a raw bitset into another.
 386  *
 387  * @param dst   the destination set
 388  * @param src   the source set
 389  * @param size  size of both bitsets
 390  */
 391 static inline void rbitset_copy(unsigned *dst, const unsigned *src, size_t size)
 392 {
 393         memcpy(dst, src, BITSET_SIZE_BYTES(size));
 394 }
 395
 396 /**
 397  * Copy a raw bitset into an bitset.
 398  *
 399  * @deprecated
 400  */
 401 static inline void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset)
 402 {
 403         // TODO optimize me (or remove me)
 404         unsigned i, n = bitset_size(bitset);
 405         for (i = 0; i < n; ++i) {
 406                 if (rbitset_is_set(rbitset, i))
 407                         bitset_set(bitset, i);
 408         }
 409 }
 410
 411 #endif /* FIRM_ADT_RAW_BITSET_H */