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