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

   1 /**
   2  * @file bitset.h
   3  * @date 15.10.2004
   4  * @author Sebastian Hack
   5  * @brief A bitset implementation.
   6  */
   7
   8 #ifndef __FIRM_BITSET_H
   9 #define __FIRM_BITSET_H
  10
  11 #include <stdlib.h>
  12 #include <stdio.h>
  13 #include <assert.h>
  14 #include <string.h>
  15
  16 #include "config.h"
  17 #include "bitfiddle.h"
  18
  19 #include "bitset_std.h"
  20
  21 /* #if defined(__GNUC__) && defined(__i386__) */
  22 #if 0
  23 #include "bitset_ia32.h"
  24 #endif
  25
  26 typedef struct _bitset_t {
  27         unsigned long units;
  28         unsigned long *data;
  29 } bitset_t;
  30
  31 #define BS_UNIT_SIZE sizeof(unsigned long)
  32 #define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8)
  33 #define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1)
  34
  35 /**
  36  * Initialize a bitset.
  37  * This functions should not be called.
  38  *
  39  * Note that this function needs three macros which must be provided by the
  40  * bitfield implementor:
  41  * - _bitset_overall_size(highest_bit) The overall size that must be
  42  *   allocated for the bitfield in bytes.
  43  * - _bitset_units(highest_bit) The number of units that will be
  44  *   present in the bitfield for a given highest bit.
  45  * - _bitset_data_ptr(data, highest_bit) This produces as pointer to the
  46  *   first unit in the allocated memory area. The main reason for this
  47  *   macro is, that some bitset implementors want control over memory
  48  *   alignment.
  49  *
  50  * @param area A pointer to memory reserved for the bitset.
  51  * @param units The number of units that are allocated for the bitset.
  52  * @return A pointer to the initialized bitset.
  53  */
  54 static INLINE bitset_t *_bitset_prepare(void *area, unsigned long highest_bit)
  55 {
  56         bitset_t *ptr = area;
  57         memset(area, 0, _bitset_overall_size(sizeof(bitset_t), highest_bit));
  58         ptr->units = _bitset_units(highest_bit);
  59         ptr->data = _bitset_data_ptr(area, sizeof(bitset_t), highest_bit);
  60         return ptr;
  61 }
  62
  63 /**
  64  * Get the capacity of the bitset in bits.
  65  * @param bs The bitset.
  66  * @return The capacity in bits of the bitset.
  67  */
  68 #define bitset_capacity(bs) ((bs)->units * BS_UNIT_SIZE_BITS)
  69
  70 /**
  71  * Allocate a bitset on an obstack.
  72  * @param obst The obstack.
  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_obstack_alloc(obst,highest_bit) \
  77   _bitset_prepare(obstack_alloc(obst, _bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit)
  78
  79 /**
  80  * Allocate a bitset via malloc.
  81  * @param highest_bit The greatest bit that shall be stored in the set.
  82  * @return A pointer to an empty initialized bitset.
  83  */
  84 #define bitset_malloc(highest_bit) \
  85         _bitset_prepare(malloc(_bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit)
  86
  87 /**
  88  * Free a bitset allocated with bitset_malloc().
  89  * @param bs The bitset.
  90  */
  91 #define bitset_free(bs) free(bs)
  92
  93 /**
  94  * Allocate a bitset on the stack via alloca.
  95  * @param highest_bit The greatest bit that shall be stored in the set.
  96  * @return A pointer to an empty initialized bitset.
  97  */
  98 #define bitset_alloca(highest_bit) \
  99         _bitset_prepare(alloca(_bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit)
 100
 101
 102 /**
 103  * Get the unit which contains a specific bit.
 104  * This function is internal.
 105  * @param bs The bitset.
 106  * @param bit The bit.
 107  * @return A pointer to the unit containing the bit.
 108  */
 109 static INLINE unsigned long *_bitset_get_unit(const bitset_t *bs, unsigned long bit)
 110 {
 111         assert(bit < bs->units * BS_UNIT_SIZE_BITS && "Bit too large");
 112         return bs->data + bit / BS_UNIT_SIZE_BITS;
 113 }
 114
 115 /**
 116  * Set a bit in the bitset.
 117  * @param bs The bitset.
 118  * @param bit The bit to set.
 119  */
 120 static INLINE void bitset_set(bitset_t *bs, unsigned long bit)
 121 {
 122         unsigned long *unit = _bitset_get_unit(bs, bit);
 123         _bitset_inside_set(unit, bit & BS_UNIT_MASK);
 124 }
 125
 126 /**
 127  * Clear a bit in the bitset.
 128  * @param bs The bitset.
 129  * @param bit The bit to clear.
 130  */
 131 static INLINE void bitset_clear(bitset_t *bs, unsigned long bit)
 132 {
 133         unsigned long *unit = _bitset_get_unit(bs, bit);
 134         _bitset_inside_clear(unit, bit & BS_UNIT_MASK);
 135 }
 136
 137 static INLINE int bitset_is_set(const bitset_t *bs, unsigned long bit)
 138 {
 139         unsigned long *unit = _bitset_get_unit(bs, bit);
 140         return _bitset_inside_is_set(unit, bit & BS_UNIT_MASK);
 141 }
 142
 143 /**
 144  * Flip a bit in a bitset.
 145  * @param bs The bitset.
 146  * @param bit The bit to flip.
 147  */
 148 static INLINE void bitset_flip(bitset_t *bs, unsigned long bit)
 149 {
 150         unsigned long *unit = _bitset_get_unit(bs, bit);
 151         _bitset_inside_flip(unit, bit & BS_UNIT_MASK);
 152 }
 153
 154 /**
 155  * Copy a bitset to another.
 156  * @param tgt The target bitset.
 157  * @param src The source bitset.
 158  * @return The target bitset.
 159  */
 160 static INLINE bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src)
 161 {
 162         unsigned long tu = tgt->units;
 163         unsigned long su = src->units;
 164         unsigned long min_units = tu < su ? tu : su;
 165         memcpy(tgt->data, src->data, min_units * BS_UNIT_SIZE);
 166         if(tu > min_units)
 167                 memset(tgt->data + min_units, 0, BS_UNIT_SIZE * (tu - min_units));
 168         return tgt;
 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 long bitset_min(const bitset_t *bs)
 177 {
 178         unsigned long i, ofs = 0;
 179
 180         for(i = 0; i < bs->units; ++i) {
 181                 unsigned long *unit = &bs->data[i];
 182                 unsigned long 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 long bitset_max(const bitset_t *bs)
 197 {
 198         unsigned long i, max = 0, ofs = 0;
 199
 200         for(i = 0; i < bs->units; ++i) {
 201                 unsigned long *unit = &bs->data[i];
 202                 unsigned long 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  * Find the next set bit from a given bit.
 213  * @note Note that if pos is set, pos is returned.
 214  * @param bs The bitset.
 215  * @param pos The bit from which to search for the next set bit.
 216  * @return The next set bit from pos on, or -1, if no set bit was found
 217  * after pos.
 218  */
 219 static INLINE unsigned long _bitset_next(const bitset_t *bs,
 220                 unsigned long pos, int set)
 221 {
 222         unsigned long unit_number = pos / BS_UNIT_SIZE_BITS;
 223         unsigned long bit_in_unit = pos & BS_UNIT_MASK;
 224         unsigned long in_unit_mask = (1 << bit_in_unit) - 1;
 225
 226         /*
 227          * Mask out the bits smaller than pos in the current unit.
 228          * We are only interested in bits set higher than pos.
 229          */
 230         unsigned long curr_unit = bs->data[unit_number] & ~in_unit_mask;
 231
 232         /* Find the next bit set in the unit. */
 233         unsigned long next_in_this_unit
 234                 = _bitset_inside_ntz_value(set ? curr_unit : ~curr_unit);
 235
 236         /* If there is a bit set in the current unit, exit. */
 237         if(next_in_this_unit < BS_UNIT_SIZE_BITS)
 238                 return next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS;
 239
 240         /* Else search for set bits in the next units. */
 241         else {
 242                 unsigned long i;
 243                 for(i = unit_number + 1; i < bs->units; ++i) {
 244                         unsigned long data = bs->data[i];
 245                         unsigned long first_set = _bitset_inside_ntz_value(set ? data : ~data);
 246                         if(first_set < BS_UNIT_SIZE_BITS)
 247                                 return first_set + i * BS_UNIT_SIZE_BITS;
 248                 }
 249         }
 250
 251         return -1;
 252 }
 253
 254 #define bitset_next_clear(bs,pos) _bitset_next((bs), (pos), 0)
 255 #define bitset_next_set(bs,pos) _bitset_next((bs), (pos), 1)
 256
 257 /**
 258  * Convenience macro for bitset iteration.
 259  * @param bitset The bitset.
 260  * @param elm A unsigned long variable.
 261  */
 262 #define bitset_foreach(bitset,elm) \
 263   for(elm = bitset_next_set(bitset,0); elm != -1; elm = bitset_next_set(bitset,elm+1))
 264
 265 /**
 266  * Count the bits set.
 267  * This can also be seen as the cardinality of the set.
 268  * @param bs The bitset.
 269  * @return The number of bits set in the bitset.
 270  */
 271 static INLINE unsigned long bitset_popcnt(const bitset_t *bs)
 272 {
 273         unsigned long i, pop = 0;
 274         unsigned long *unit;
 275
 276         for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit)
 277                 pop += _bitset_inside_pop(unit);
 278
 279         return pop;
 280 }
 281
 282 /**
 283  * Clear the bitset.
 284  * This sets all bits to zero.
 285  * @param bs The bitset.
 286  */
 287 static INLINE void bitset_clear_all(bitset_t *bs)
 288 {
 289         memset(bs->data, 0, BS_UNIT_SIZE * bs->units);
 290 }
 291
 292 /**
 293  * Check, if one bitset is contained by another.
 294  * That is, each bit set in lhs is also set in rhs.
 295  * @param lhs A bitset.
 296  * @param rhs Another bitset.
 297  * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
 298  */
 299 static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
 300 {
 301         unsigned long n = lhs->units < rhs->units ? lhs->units : rhs->units;
 302         unsigned long i;
 303
 304         for(i = 0; i < n; ++i) {
 305                 unsigned long lu = lhs->data[i];
 306                 unsigned long ru = rhs->data[i];
 307
 308                 if((lu | ru) & ~ru)
 309                         return 0;
 310         }
 311
 312         /*
 313          * If the left hand sinde is a larger bitset than rhs,
 314          * we have to check, that all extra bits in lhs are 0
 315          */
 316         if(lhs->units > n) {
 317                 for(i = n; i < lhs->units; ++i) {
 318                         if(lhs->data[i] != 0)
 319                                 return 0;
 320                 }
 321         }
 322
 323         return 1;
 324 }
 325
 326 /**
 327  * Print a bitset to a stream.
 328  * The bitset is printed as a comma seperated list of bits set.
 329  * @param file The stream.
 330  * @param bs The bitset.
 331  */
 332 static INLINE void bitset_fprint(FILE *file, const bitset_t *bs)
 333 {
 334         const char *prefix = "";
 335         int i;
 336
 337         putc('[', file);
 338         for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) {
 339                 fprintf(file, "%s%u", prefix, i);
 340                 prefix = ",";
 341         }
 342         putc(']', file);
 343 }
 344
 345 /*
 346  * Here, the binary operations follow.
 347  * And, Or, And Not, Xor are available.
 348  */
 349
 350 #define BINARY_OP(op) \
 351 static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \
 352 { \
 353         int i; \
 354         int n = tgt->units > src->units ? src->units : tgt->units; \
 355         for(i = 0; i < n; i += _BITSET_BINOP_UNITS_INC) \
 356                 _bitset_inside_binop_ ## op(&tgt->data[i], &src->data[i]); \
 357         for(i = n; i < tgt->units; i += _BITSET_BINOP_UNITS_INC) \
 358                 _bitset_inside_binop_with_zero_ ## op(&tgt->data[i]); \
 359         return tgt; \
 360 }
 361
 362 BINARY_OP(and)
 363 BINARY_OP(andnot)
 364 BINARY_OP(or)
 365 BINARY_OP(xor)
 366
 367 #endif