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