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

   1 /**
   2  * @file bitset.h
   3  * @date 15.10.2004
   4  * @author Matthias Braun
   5  * @brief helper functions for working with raw bitsets
   6  * @summary
   7  *     Raw bitsets are constructed from int arrays. Additional information
   8  *     like the size of the bitset or the used memory aren't saved for
   9  *     efficiency reasons.
  10  *
  11  *     These bitsets need less space than bitset_t and their representation
  12  *     as int arrays allows having constant bitsets in the ro data segment.
  13  *     They should for smaller bitset, whose length is known through other means
  14  *     (a typical usage case is a set of cpu registers)
  15  *
  16  *     The bitset is built as an array of unsigned integers. It is assumed that
  17  *     exactly 32 bits may be put into each element of the array. If there are
  18  *     remaining bits, then they should be 0
  19  */
  20 #ifndef __FIRM_RAW_BITSET_H
  21 #define __FIRM_RAW_BITSET_H
  22
  23 #include <assert.h>
  24 #include "bitset.h"
  25 #include "bitset_std.h"
  26 #include "obst.h"
  27
  28 #define BITS_PER_ELEM                   32
  29 #define BITSET_SIZE_ELEMS(size_bits)    ((size_bits)/32 + 1)
  30 #define BITSET_SIZE_BYTES(size_bits)    (BITSET_SIZE_ELEMS(size_bits)*4)
  31 #define BITSET_ELEM(bitset,pos)         bitset[pos / 32]
  32
  33 static INLINE unsigned *rbitset_alloca(unsigned size)
  34 {
  35         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  36         unsigned *res = alloca(size_bytes);
  37         memset(res, 0, size_bytes);
  38
  39         return res;
  40 }
  41
  42 static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size)
  43 {
  44         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  45         unsigned *res = obstack_alloc(obst, size_bytes);
  46         memset(res, 0, size_bytes);
  47
  48         return res;
  49 }
  50
  51 static INLINE
  52 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
  53                                                   const unsigned *old_bitset,
  54                                           unsigned size)
  55 {
  56         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  57         unsigned *res = obstack_alloc(obst, size_bytes);
  58         memcpy(res, old_bitset, size_bytes);
  59
  60         return res;
  61 }
  62
  63 static INLINE void rbitset_set(unsigned *bitset, unsigned pos)
  64 {
  65         BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
  66 }
  67
  68 static INLINE void rbitset_clear(unsigned *bitset, unsigned pos)
  69 {
  70         BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
  71 }
  72
  73 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos)
  74 {
  75         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
  76 }
  77
  78 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size)
  79 {
  80         unsigned pos;
  81         unsigned n = BITSET_SIZE_ELEMS(size);
  82         unsigned res = 0;
  83         const unsigned *elem = bitset;
  84
  85         for(pos = 0; pos < n; ++pos) {
  86                 res += _bitset_inside_pop(elem);
  87                 elem++;
  88         }
  89
  90         return res;
  91 }
  92
  93 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set)
  94 {
  95         unsigned p;
  96         unsigned elem_pos = pos / BITS_PER_ELEM;
  97         unsigned bit_pos = pos % BITS_PER_ELEM;
  98
  99         unsigned elem = bitset[elem_pos];
 100
 101         /*
 102          * Mask out the bits smaller than pos in the current unit.
 103          * We are only interested in bits set higher than pos.
 104          */
 105         unsigned in_elem_mask = (1 << bit_pos) - 1;
 106
 107         if(!set)
 108                 elem = ~elem;
 109         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 110
 111         /* If there is a bit set in the current elem, exit. */
 112         if(p < BITS_PER_ELEM) {
 113                 return elem_pos * BITS_PER_ELEM + p;
 114         }
 115
 116         /* Else search for set bits in the next units. */
 117         while(1) {
 118                 elem_pos++;
 119                 elem = bitset[elem_pos];
 120                 if(!set)
 121                         elem = ~elem;
 122
 123                 p = _bitset_inside_ntz_value(elem);
 124                 if(p < BITS_PER_ELEM) {
 125                         return elem_pos * BITS_PER_ELEM + p;
 126                 }
 127         }
 128
 129         assert(0);
 130         return 0xdeadbeef;
 131 }
 132
 133 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
 134                                unsigned size)
 135 {
 136         unsigned i = 0;
 137         unsigned n = BITSET_SIZE_ELEMS(size);
 138
 139         for(i = 0; i < n; ++i) {
 140                 bitset1[i] &= bitset2[i];
 141         }
 142 }
 143
 144 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
 145                               unsigned size)
 146 {
 147         unsigned i = 0;
 148         unsigned n = BITSET_SIZE_ELEMS(size);
 149
 150         for(i = 0; i < n; ++i) {
 151                 bitset1[i] |= bitset2[i];
 152         }
 153 }
 154
 155 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
 156                                   unsigned size)
 157 {
 158         unsigned i = 0;
 159         unsigned n = BITSET_SIZE_ELEMS(size);
 160
 161         for(i = 0; i < n; ++i) {
 162                 bitset1[i] &= ~bitset2[i];
 163         }
 164 }
 165
 166 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
 167                                unsigned size)
 168 {
 169         unsigned i = 0;
 170         unsigned n = BITSET_SIZE_ELEMS(size);
 171
 172         for(i = 0; i < n; ++i) {
 173                 bitset1[i] ^= bitset2[i];
 174         }
 175 }
 176
 177 /** @deprecated */
 178 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset)
 179 {
 180         // TODO optimize me (or remove me)
 181         unsigned i;
 182         unsigned n = bitset_size(bitset);
 183         for(i = 0; i < n; ++i) {
 184                 if(rbitset_is_set(rbitset, i))
 185                         bitset_set(bitset, i);
 186         }
 187 }
 188
 189 #endif