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

   1 /*
   2  * Copyrigth (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 static INLINE unsigned *rbitset_alloca(unsigned size)
  54 {
  55         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  56         unsigned *res = alloca(size_bytes);
  57         memset(res, 0, size_bytes);
  58
  59         return res;
  60 }
  61
  62 static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size)
  63 {
  64         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  65         unsigned *res = obstack_alloc(obst, size_bytes);
  66         memset(res, 0, size_bytes);
  67
  68         return res;
  69 }
  70
  71 static INLINE
  72 unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst,
  73                                                   const unsigned *old_bitset,
  74                                           unsigned size)
  75 {
  76         unsigned size_bytes = BITSET_SIZE_BYTES(size);
  77         unsigned *res = obstack_alloc(obst, size_bytes);
  78         memcpy(res, old_bitset, size_bytes);
  79
  80         return res;
  81 }
  82
  83 static INLINE void rbitset_set(unsigned *bitset, unsigned pos)
  84 {
  85         BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM);
  86 }
  87
  88 static INLINE void rbitset_clear(unsigned *bitset, unsigned pos)
  89 {
  90         BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM));
  91 }
  92
  93 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos)
  94 {
  95         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
  96 }
  97
  98 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size)
  99 {
 100         unsigned pos;
 101         unsigned n = BITSET_SIZE_ELEMS(size);
 102         unsigned res = 0;
 103         const unsigned *elem = bitset;
 104
 105         for(pos = 0; pos < n; ++pos) {
 106                 res += _bitset_inside_pop(elem);
 107                 elem++;
 108         }
 109
 110         return res;
 111 }
 112
 113 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set)
 114 {
 115         unsigned p;
 116         unsigned elem_pos = pos / BITS_PER_ELEM;
 117         unsigned bit_pos = pos % BITS_PER_ELEM;
 118
 119         unsigned elem = bitset[elem_pos];
 120
 121         /*
 122          * Mask out the bits smaller than pos in the current unit.
 123          * We are only interested in bits set higher than pos.
 124          */
 125         unsigned in_elem_mask = (1 << bit_pos) - 1;
 126
 127         if(!set)
 128                 elem = ~elem;
 129         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 130
 131         /* If there is a bit set in the current elem, exit. */
 132         if(p < BITS_PER_ELEM) {
 133                 return elem_pos * BITS_PER_ELEM + p;
 134         }
 135
 136         /* Else search for set bits in the next units. */
 137         while(1) {
 138                 elem_pos++;
 139                 elem = bitset[elem_pos];
 140                 if(!set)
 141                         elem = ~elem;
 142
 143                 p = _bitset_inside_ntz_value(elem);
 144                 if(p < BITS_PER_ELEM) {
 145                         return elem_pos * BITS_PER_ELEM + p;
 146                 }
 147         }
 148
 149         assert(0);
 150         return 0xdeadbeef;
 151 }
 152
 153 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
 154                                unsigned size)
 155 {
 156         unsigned i = 0;
 157         unsigned n = BITSET_SIZE_ELEMS(size);
 158
 159         for(i = 0; i < n; ++i) {
 160                 bitset1[i] &= bitset2[i];
 161         }
 162 }
 163
 164 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
 165                               unsigned size)
 166 {
 167         unsigned i = 0;
 168         unsigned n = BITSET_SIZE_ELEMS(size);
 169
 170         for(i = 0; i < n; ++i) {
 171                 bitset1[i] |= bitset2[i];
 172         }
 173 }
 174
 175 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
 176                                   unsigned size)
 177 {
 178         unsigned i = 0;
 179         unsigned n = BITSET_SIZE_ELEMS(size);
 180
 181         for(i = 0; i < n; ++i) {
 182                 bitset1[i] &= ~bitset2[i];
 183         }
 184 }
 185
 186 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
 187                                unsigned size)
 188 {
 189         unsigned i = 0;
 190         unsigned n = BITSET_SIZE_ELEMS(size);
 191
 192         for(i = 0; i < n; ++i) {
 193                 bitset1[i] ^= bitset2[i];
 194         }
 195 }
 196
 197 /** @deprecated */
 198 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset)
 199 {
 200         // TODO optimize me (or remove me)
 201         unsigned i;
 202         unsigned n = bitset_size(bitset);
 203         for(i = 0; i < n; ++i) {
 204                 if(rbitset_is_set(rbitset, i))
 205                         bitset_set(bitset, i);
 206         }
 207 }
 208
 209 #endif