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