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

   1 /**
   2  * Bitsets.
   3  */
   4
   5 #ifndef __FIRM_BITSET_H
   6 #define __FIRM_BITSET_H
   7
   8 #include <stdlib.h>
   9 #include <stdio.h>
  10 #include <assert.h>
  11 #include <string.h>
  12
  13
  14 #define INLINE inline
  15
  16 #define BITSET_USE_STD
  17
  18 #include "bitset_std.h"
  19
  20 typedef struct _bitset_t {
  21         unsigned units;
  22         bitset_unit_t *data;
  23 } bitset_t;
  24
  25 #define BS_UNIT_SIZE sizeof(bitset_unit_t)
  26 #define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8)
  27 #define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1)
  28
  29
  30 /**
  31  * Units needed for a given highest bit.
  32  * @param highest_bit The highest bit that should be storable.
  33  * @return The number of units needed.
  34  */
  35 #define _bitset_units(highest_bit) (round_up2(highest_bit, BS_UNIT_SIZE_BITS) / BS_UNIT_SIZE_BITS)
  36
  37 /**
  38  * Compute the size in bytes needed for a bitset.
  39  * This also include the size for the bitset data structure.
  40  * @param highest_bit The highest bit that shall be storable.
  41  * @return The overall amount of bytes needed for that bitset.
  42  */
  43 #define _bitset_overall_size(highest_bit) \
  44         (sizeof(bitset_t) + _bitset_units(highest_bit) * BS_UNIT_SIZE)
  45
  46 /**
  47  * Initialize a bitset.
  48  * This functions should not be called.
  49  * @param area A pointer to memory reserved for the bitset.
  50  * @param units The number of units that are allocated for the bitset.
  51  * @return A pointer to the initialized bitset.
  52  */
  53 static INLINE bitset_t *_bitset_prepare(void *area, unsigned units)
  54 {
  55         bitset_t *ptr = area;
  56         ptr->units = units;
  57         ptr->data = (bitset_unit_t *) (ptr + 1);
  58         memset(ptr->data, 0, BS_UNIT_SIZE * units);
  59         return ptr;
  60 }
  61
  62 /**
  63  * Allocate a bitset on an obstack.
  64  * @param obst The obstack.
  65  * @param highest_bit The greatest bit that shall be stored in the set.
  66  * @return A pointer to an empty initialized bitset.
  67  */
  68 #define bitset_obstack_alloc(obst,highest_bit) \
  69   _bitset_prepare(obstack_alloc(obst, _bitset_overall_size(highest_bit)), _bitset_units(highest_bit))
  70
  71 /**
  72  * Allocate a bitset via malloc.
  73  * @param highest_bit The greatest bit that shall be stored in the set.
  74  * @return A pointer to an empty initialized bitset.
  75  */
  76 #define bitset_malloc(highest_bit) \
  77         _bitset_prepare(malloc(_bitset_overall_size(highest_bit)), _bitset_units(highest_bit))
  78
  79 /**
  80  * Free a bitset allocated with bitset_malloc().
  81  * @param bs The bitset.
  82  */
  83 #define bitset_free(bs) free(bs)
  84
  85 /**
  86  * Allocate a bitset on the stack via alloca.
  87  * @param highest_bit The greatest bit that shall be stored in the set.
  88  * @return A pointer to an empty initialized bitset.
  89  */
  90 #define bitset_alloca(highest_bit) \
  91         _bitset_prepare(alloca(_bitset_overall_size(highest_bit)), _bitset_units(highest_bit))
  92
  93 /**
  94  * Print a bitset to a stream.
  95  * The bitset is printed as a comma seperated list of bits set.
  96  * @param file The stream.
  97  * @param bs The bitset.
  98  */
  99 static INLINE void bitset_fprint(FILE *file, bitset_t *bs)
 100 {
 101         const char *prefix = "";
 102         int i;
 103         unsigned k = 0;
 104
 105         putc('[', file);
 106         for(i = 0; i < bs->units; i++) {
 107                 bitset_unit_t j;
 108                 bitset_unit_t unit = bs->data[i];
 109
 110 #if 0
 111                 printf("%s%08x", prefix, unit);
 112                 prefix=":";
 113                 continue;
 114 #endif
 115                 for(j = 1; j != 0; j <<= 1, k++) {
 116                         if(unit & j) {
 117                                 fprintf(file, "%s%u", prefix, k);
 118                                 prefix = ",";
 119                         }
 120                 }
 121         }
 122         putc(']', file);
 123 }
 124
 125 /**
 126  * Get the unit which contains a specific bit.
 127  * This function is internal.
 128  * @param bs The bitset.
 129  * @param bit The bit.
 130  * @return A pointer to the unit containing the bit.
 131  */
 132 static INLINE bitset_unit_t *_bitset_get_unit(const bitset_t *bs, unsigned bit)
 133 {
 134         assert(bit < bs->units * BS_UNIT_SIZE_BITS && "Bit too large");
 135         return bs->data + bit / BS_UNIT_SIZE_BITS;
 136 }
 137
 138 /**
 139  * Set a bit in the bitset.
 140  * @param bs The bitset.
 141  * @param bit The bit to set.
 142  */
 143 static INLINE void bitset_set(bitset_t *bs, unsigned bit)
 144 {
 145         bitset_unit_t *unit = _bitset_get_unit(bs, bit);
 146         _bitset_inside_set(unit, bit & BS_UNIT_MASK);
 147 }
 148
 149 /**
 150  * Clear a bit in the bitset.
 151  * @param bs The bitset.
 152  * @param bit The bit to clear.
 153  */
 154 static INLINE void bitset_clear(bitset_t *bs, unsigned bit)
 155 {
 156         bitset_unit_t *unit = _bitset_get_unit(bs, bit);
 157         _bitset_inside_clear(unit, bit & BS_UNIT_MASK);
 158 }
 159
 160 /**
 161  * Flip a bit in a bitset.
 162  * @param bs The bitset.
 163  * @param bit The bit to flip.
 164  */
 165 static INLINE void bitset_flip(bitset_t *bs, unsigned bit)
 166 {
 167         bitset_unit_t *unit = _bitset_get_unit(bs, bit);
 168         _bitset_inside_flip(unit, bit & BS_UNIT_MASK);
 169 }
 170
 171 /**
 172  * Find the smallest bit set in the bitset.
 173  * @param bs The bitset.
 174  * @return The smallest bit set in the bitset.
 175  */
 176 static INLINE unsigned bitset_min(bitset_t *bs)
 177 {
 178         unsigned i, ofs = 0;
 179         bitset_unit_t *unit;
 180
 181         for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit) {
 182                 unsigned pos = _bitset_inside_ntz(unit);
 183                 if(pos > 0)
 184                         return ofs + pos;
 185                 ofs += BS_UNIT_SIZE_BITS;
 186         }
 187
 188         return 0;
 189 }
 190
 191 /**
 192  * Find the greatest bit set in the bitset.
 193  * @param bs The bitset.
 194  * @return The greatest bit set in the bitset.
 195  */
 196 static INLINE unsigned bitset_max(bitset_t *bs)
 197 {
 198         unsigned i, max = 0, ofs = 0;
 199         bitset_unit_t *unit;
 200
 201         for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit) {
 202                 unsigned pos = _bitset_inside_nlz(unit);
 203                 if(pos > 0)
 204                         max = ofs + pos;
 205                 ofs += BS_UNIT_SIZE_BITS;
 206         }
 207
 208         return max;
 209 }
 210
 211 /**
 212  * Count the bits set.
 213  * This can also be seen as the cardinality of the set.
 214  * @param bs The bitset.
 215  * @return The number of bits set in the bitset.
 216  */
 217 static INLINE unsigned bitset_pop(bitset_t *bs)
 218 {
 219         unsigned i, pop = 0;
 220         bitset_unit_t *unit;
 221
 222         for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit)
 223                 pop += _bitset_inside_pop(unit);
 224
 225         return pop;
 226 }
 227
 228 /*
 229  * Here, the binary operations follow.
 230  * And, Or, And Not, Xor are available.
 231  */
 232
 233 #define BINARY_OP(op) \
 234 static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, bitset_t *src) \
 235 { \
 236         int i; \
 237         int n = tgt->units > src->units ? src->units : tgt->units; \
 238         bitset_unit_t *tgt_unit, *src_unit; \
 239         src_unit = src->data; \
 240         tgt_unit = tgt->data; \
 241         for(i = 0; i < n; ++i) \
 242                 _bitset_inside_ ## op(tgt_unit++, src_unit++); \
 243         return tgt; \
 244 }
 245
 246 BINARY_OP(and)
 247 BINARY_OP(andnot)
 248 BINARY_OP(or)
 249 BINARY_OP(xor)
 250
 251
 252 #endif