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