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 int arrays. Additional information
  28  *     like the size of the bitset or the used memory aren't saved 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  * Duplicate a raw bitset on an obstack.
  83  *
  84  * @param obst       the obstack where the bitset is allocated on
  85  * @param old_bitset the bitset to be duplicated
  86  * @param size       element size of the bitset
  87  *
  88  * @return the new bitset
  89  */
  90 static INLINE
  91 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
  92                                           const unsigned *old_bitset,
  93                                           unsigned size)
  94 {
  95         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  96         unsigned *res = obstack_alloc(obst, size_bytes);
  97         memcpy(res, old_bitset, size_bytes);
  98
  99         return res;
 100 }
 101
 102 /**
 103  * Set a bit at position pos.
 104  *
 105  * @param bitset  the bitset
 106  * @param pos     the position of the bit to be set
 107  */
 108 static INLINE void rbitset_set(unsigned *bitset, unsigned pos) {
 109         BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
 110 }
 111
 112 /**
 113  * Clear a bit at position pos.
 114  *
 115  * @param bitset  the bitset
 116  * @param pos     the position of the bit to be clear
 117  */
 118 static INLINE void rbitset_clear(unsigned *bitset, unsigned pos) {
 119         BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
 120 }
 121
 122 /**
 123  * Check if a bit is set at position pos.
 124  *
 125  * @param bitset  the bitset
 126  * @param pos     the position of the bit to check
 127  */
 128 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos) {
 129         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
 130 }
 131
 132 /**
 133  * Calculate the number of set bits (number of elements).
 134  *
 135  * @param bitset  the bitset
 136  */
 137 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) {
 138         unsigned pos;
 139         unsigned n = BITSET_SIZE_ELEMS(size);
 140         unsigned res = 0;
 141         const unsigned *elem = bitset;
 142
 143         for(pos = 0; pos < n; ++pos) {
 144                 res += _bitset_inside_pop(elem);
 145                 elem++;
 146         }
 147
 148         return res;
 149 }
 150
 151 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) {
 152         unsigned p;
 153         unsigned elem_pos = pos / BITS_PER_ELEM;
 154         unsigned bit_pos = pos % BITS_PER_ELEM;
 155
 156         unsigned elem = bitset[elem_pos];
 157
 158         /*
 159          * Mask out the bits smaller than pos in the current unit.
 160          * We are only interested in bits set higher than pos.
 161          */
 162         unsigned in_elem_mask = (1 << bit_pos) - 1;
 163
 164         if(!set)
 165                 elem = ~elem;
 166         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 167
 168         /* If there is a bit set in the current elem, exit. */
 169         if(p < BITS_PER_ELEM) {
 170                 return elem_pos * BITS_PER_ELEM + p;
 171         }
 172
 173         /* Else search for set bits in the next units. */
 174         while(1) {
 175                 elem_pos++;
 176                 elem = bitset[elem_pos];
 177                 if(!set)
 178                         elem = ~elem;
 179
 180                 p = _bitset_inside_ntz_value(elem);
 181                 if(p < BITS_PER_ELEM) {
 182                         return elem_pos * BITS_PER_ELEM + p;
 183                 }
 184         }
 185
 186         assert(0);
 187         return 0xdeadbeef;
 188 }
 189
 190 /**
 191  * Inplace Intersection of two sets.
 192  */
 193 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
 194                                unsigned size)
 195 {
 196         unsigned i, n = BITSET_SIZE_ELEMS(size);
 197
 198         for(i = 0; i < n; ++i) {
 199                 bitset1[i] &= bitset2[i];
 200         }
 201 }
 202
 203 /**
 204  * Inplace Union of two sets.
 205  */
 206 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
 207                               unsigned size)
 208 {
 209         unsigned i, n = BITSET_SIZE_ELEMS(size);
 210
 211         for(i = 0; i < n; ++i) {
 212                 bitset1[i] |= bitset2[i];
 213         }
 214 }
 215
 216 /**
 217  * Remove all bits in bitset2 from bitset 1.
 218  */
 219 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
 220                                   unsigned size)
 221 {
 222         unsigned i, n = BITSET_SIZE_ELEMS(size);
 223
 224         for(i = 0; i < n; ++i) {
 225                 bitset1[i] &= ~bitset2[i];
 226         }
 227 }
 228
 229 /**
 230  * Xor of two bitsets.
 231  */
 232 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
 233                                unsigned size)
 234 {
 235         unsigned i, n = BITSET_SIZE_ELEMS(size);
 236
 237         for(i = 0; i < n; ++i) {
 238                 bitset1[i] ^= bitset2[i];
 239         }
 240 }
 241
 242 /**
 243  * Copy a raw bitset into an bitset.
 244  *
 245  * @deprecated
 246  */
 247 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) {
 248         // TODO optimize me (or remove me)
 249         unsigned i, n = bitset_size(bitset);
 250         for(i = 0; i < n; ++i) {
 251                 if(rbitset_is_set(rbitset, i))
 252                         bitset_set(bitset, i);
 253         }
 254 }
 255
 256 #endif /* FIRM_ADT_RAW_BITSET_H */