nsz Git - libfirm/blob - include/libfirm/adt/raw_bitset.h

   1 /*
   2  * Copyright (C) 1995-2007 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 #define BITS_PER_ELEM                   32
  48 #define BITSET_SIZE_ELEMS(size_bits)    ((size_bits)/32 + 1)
  49 #define BITSET_SIZE_BYTES(size_bits)    (BITSET_SIZE_ELEMS(size_bits)*4)
  50 #define BITSET_ELEM(bitset,pos)         bitset[pos / 32]
  51
  52 /**
  53  * Allocate an empty raw bitset on the stack.
  54  *
  55  * @param res   will contain the newly allocated bitset
  56  * @param size  element size of the bitset
  57  */
  58 #define rbitset_alloca(res, size) \
  59 do { \
  60         unsigned size_bytes = BITSET_SIZE_BYTES(size); \
  61         res = alloca(size_bytes); \
  62         memset(res, 0, size_bytes); \
  63 } while(0)
  64
  65 /**
  66  * Allocate an empty raw bitset on an obstack.
  67  *
  68  * @param obst  the obstack where the bitset is allocated on
  69  * @param size  element size of the bitset
  70  *
  71  * @return the new bitset
  72  */
  73 static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size) {
  74         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  75         unsigned *res = obstack_alloc(obst, size_bytes);
  76         memset(res, 0, size_bytes);
  77
  78         return res;
  79 }
  80
  81 /**
  82  * Allocate an empty raw bitset including the size on an obstack.
  83  * The size of this bitset can be accessed by bitset[-1].
  84  *
  85  * @param obst  the obstack where the bitset is allocated on
  86  * @param size  element size of the bitset
  87  *
  88  * @return the new bitset
  89  */
  90 static INLINE unsigned *rbitset_w_size_obstack_alloc(struct obstack *obst, unsigned size) {
  91         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  92         unsigned *res = obstack_alloc(obst, size_bytes + sizeof(unsigned));
  93         *res = size;
  94         ++res;
  95         memset(res, 0, size_bytes);
  96
  97         return res;
  98 }
  99
 100 /** Return the size of a bitset allocated with a *_w_size_* function */
 101 #define rbitset_size(set)       (set)[-1]
 102
 103 /**
 104  * Duplicate a raw bitset on an obstack.
 105  *
 106  * @param obst       the obstack where the bitset is allocated on
 107  * @param old_bitset the bitset to be duplicated
 108  * @param size       element size of the bitset
 109  *
 110  * @return the new bitset
 111  */
 112 static INLINE
 113 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
 114                                           const unsigned *old_bitset,
 115                                           unsigned size)
 116 {
 117         unsigned size_bytes = BITSET_SIZE_BYTES(size);
 118         unsigned *res = obstack_alloc(obst, size_bytes);
 119         memcpy(res, old_bitset, size_bytes);
 120
 121         return res;
 122 }
 123
 124 /**
 125  * Check if a bitset is empty, ie all bits cleared.
 126  */
 127 static INLINE int rbitset_is_empty(unsigned *bitset, unsigned size) {
 128         unsigned i, size_bytes = BITSET_SIZE_BYTES(size);
 129         for (i = 0; i < size_bytes; ++i)
 130                 if (bitset[i]) return 0;
 131         return 1;
 132 }
 133
 134 /**
 135  * Set a bit at position pos.
 136  *
 137  * @param bitset  the bitset
 138  * @param pos     the position of the bit to be set
 139  */
 140 static INLINE void rbitset_set(unsigned *bitset, unsigned pos) {
 141         BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
 142 }
 143
 144 /**
 145  * Clear a bit at position pos.
 146  *
 147  * @param bitset  the bitset
 148  * @param pos     the position of the bit to be clear
 149  */
 150 static INLINE void rbitset_clear(unsigned *bitset, unsigned pos) {
 151         BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
 152 }
 153
 154 /**
 155  * Check if a bit is set at position pos.
 156  *
 157  * @param bitset  the bitset
 158  * @param pos     the position of the bit to check
 159  */
 160 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos) {
 161         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
 162 }
 163
 164 /**
 165  * Calculate the number of set bits (number of elements).
 166  *
 167  * @param bitset  the bitset
 168  */
 169 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) {
 170         unsigned pos;
 171         unsigned n = BITSET_SIZE_ELEMS(size);
 172         unsigned res = 0;
 173         const unsigned *elem = bitset;
 174
 175         for(pos = 0; pos < n; ++pos) {
 176                 res += _bitset_inside_pop(elem);
 177                 elem++;
 178         }
 179
 180         return res;
 181 }
 182
 183 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) {
 184         unsigned p;
 185         unsigned elem_pos = pos / BITS_PER_ELEM;
 186         unsigned bit_pos = pos % BITS_PER_ELEM;
 187
 188         unsigned elem = bitset[elem_pos];
 189
 190         /*
 191          * Mask out the bits smaller than pos in the current unit.
 192          * We are only interested in bits set higher than pos.
 193          */
 194         unsigned in_elem_mask = (1 << bit_pos) - 1;
 195
 196         if(!set)
 197                 elem = ~elem;
 198         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 199
 200         /* If there is a bit set in the current elem, exit. */
 201         if(p < BITS_PER_ELEM) {
 202                 return elem_pos * BITS_PER_ELEM + p;
 203         }
 204
 205         /* Else search for set bits in the next units. */
 206         while(1) {
 207                 elem_pos++;
 208                 elem = bitset[elem_pos];
 209                 if(!set)
 210                         elem = ~elem;
 211
 212                 p = _bitset_inside_ntz_value(elem);
 213                 if(p < BITS_PER_ELEM) {
 214                         return elem_pos * BITS_PER_ELEM + p;
 215                 }
 216         }
 217
 218         assert(0);
 219         return 0xdeadbeef;
 220 }
 221
 222 /**
 223  * Inplace Intersection of two sets.
 224  */
 225 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
 226                                unsigned size)
 227 {
 228         unsigned i, n = BITSET_SIZE_ELEMS(size);
 229
 230         for(i = 0; i < n; ++i) {
 231                 bitset1[i] &= bitset2[i];
 232         }
 233 }
 234
 235 /**
 236  * Inplace Union of two sets.
 237  */
 238 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
 239                               unsigned size)
 240 {
 241         unsigned i, n = BITSET_SIZE_ELEMS(size);
 242
 243         for(i = 0; i < n; ++i) {
 244                 bitset1[i] |= bitset2[i];
 245         }
 246 }
 247
 248 /**
 249  * Remove all bits in bitset2 from bitset 1.
 250  */
 251 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
 252                                   unsigned size)
 253 {
 254         unsigned i, n = BITSET_SIZE_ELEMS(size);
 255
 256         for(i = 0; i < n; ++i) {
 257                 bitset1[i] &= ~bitset2[i];
 258         }
 259 }
 260
 261 /**
 262  * Xor of two bitsets.
 263  */
 264 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
 265                                unsigned size)
 266 {
 267         unsigned i, n = BITSET_SIZE_ELEMS(size);
 268
 269         for(i = 0; i < n; ++i) {
 270                 bitset1[i] ^= bitset2[i];
 271         }
 272 }
 273
 274 /**
 275  * Copy a raw bitset into an bitset.
 276  *
 277  * @deprecated
 278  */
 279 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) {
 280         // TODO optimize me (or remove me)
 281         unsigned i, n = bitset_size(bitset);
 282         for(i = 0; i < n; ++i) {
 283                 if(rbitset_is_set(rbitset, i))
 284                         bitset_set(bitset, i);
 285         }
 286 }
 287
 288 #endif /* FIRM_ADT_RAW_BITSET_H */