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 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  element size of 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  element size of 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  element size of 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  element size of 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       element size of 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  * Check if a bit is set at position pos.
 174  *
 175  * @param bitset  the bitset
 176  * @param pos     the position of the bit to check
 177  */
 178 static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos) {
 179         return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM));
 180 }
 181
 182 /**
 183  * Calculate the number of set bits (number of elements).
 184  *
 185  * @param bitset  the bitset
 186  */
 187 static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) {
 188         unsigned pos;
 189         unsigned n = BITSET_SIZE_ELEMS(size);
 190         unsigned res = 0;
 191         const unsigned *elem = bitset;
 192
 193         for(pos = 0; pos < n; ++pos) {
 194                 res += _bitset_inside_pop(elem);
 195                 elem++;
 196         }
 197
 198         return res;
 199 }
 200
 201 static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) {
 202         unsigned p;
 203         unsigned elem_pos = pos / BITS_PER_ELEM;
 204         unsigned bit_pos = pos % BITS_PER_ELEM;
 205
 206         unsigned elem = bitset[elem_pos];
 207
 208         /*
 209          * Mask out the bits smaller than pos in the current unit.
 210          * We are only interested in bits set higher than pos.
 211          */
 212         unsigned in_elem_mask = (1 << bit_pos) - 1;
 213
 214         if(!set)
 215                 elem = ~elem;
 216         p = _bitset_inside_ntz_value(elem & ~in_elem_mask);
 217
 218         /* If there is a bit set in the current elem, exit. */
 219         if(p < BITS_PER_ELEM) {
 220                 return elem_pos * BITS_PER_ELEM + p;
 221         }
 222
 223         /* Else search for set bits in the next units. */
 224         while(1) {
 225                 elem_pos++;
 226                 elem = bitset[elem_pos];
 227                 if(!set)
 228                         elem = ~elem;
 229
 230                 p = _bitset_inside_ntz_value(elem);
 231                 if(p < BITS_PER_ELEM) {
 232                         return elem_pos * BITS_PER_ELEM + p;
 233                 }
 234         }
 235
 236         assert(0);
 237         return 0xdeadbeef;
 238 }
 239
 240 /**
 241  * Inplace Intersection of two sets.
 242  */
 243 static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2,
 244                                unsigned size)
 245 {
 246         unsigned i, n = BITSET_SIZE_ELEMS(size);
 247
 248         for(i = 0; i < n; ++i) {
 249                 bitset1[i] &= bitset2[i];
 250         }
 251 }
 252
 253 /**
 254  * Inplace Union of two sets.
 255  */
 256 static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2,
 257                               unsigned size)
 258 {
 259         unsigned i, n = BITSET_SIZE_ELEMS(size);
 260
 261         for(i = 0; i < n; ++i) {
 262                 bitset1[i] |= bitset2[i];
 263         }
 264 }
 265
 266 /**
 267  * Remove all bits in bitset2 from bitset 1.
 268  */
 269 static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2,
 270                                   unsigned size)
 271 {
 272         unsigned i, n = BITSET_SIZE_ELEMS(size);
 273
 274         for(i = 0; i < n; ++i) {
 275                 bitset1[i] &= ~bitset2[i];
 276         }
 277 }
 278
 279 /**
 280  * Xor of two bitsets.
 281  */
 282 static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
 283                                unsigned size)
 284 {
 285         unsigned i, n = BITSET_SIZE_ELEMS(size);
 286
 287         for(i = 0; i < n; ++i) {
 288                 bitset1[i] ^= bitset2[i];
 289         }
 290 }
 291
 292 /**
 293  * Copy a raw bitset into an bitset.
 294  *
 295  * @deprecated
 296  */
 297 static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) {
 298         // TODO optimize me (or remove me)
 299         unsigned i, n = bitset_size(bitset);
 300         for(i = 0; i < n; ++i) {
 301                 if(rbitset_is_set(rbitset, i))
 302                         bitset_set(bitset, i);
 303         }
 304 }
 305
 306 #endif /* FIRM_ADT_RAW_BITSET_H */