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

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