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];
 237
 238                 /*
 239                  * Find the next bit set in the unit.
 240                  * Mind that this function returns 0, if the unit is -1 and
 241                  * counts the bits from 1 on.
 242                  */
 243                 unsigned long next_in_this_unit =
 244                         _bitset_inside_ntz_value((set ? curr_unit : ~curr_unit) & ~in_unit_mask);
 245
 246                 /* If there is a bit set in the current unit, exit. */
 247                 if(next_in_this_unit < BS_UNIT_SIZE_BITS)
 248                         return next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS;
 249
 250                 /* Else search for set bits in the next units. */
 251                 else {
 252                         unsigned long i;
 253                         for(i = unit_number + 1; i < bs->units; ++i) {
 254                                 unsigned long data = bs->data[i];
 255                                 unsigned long first_set =
 256                                         _bitset_inside_ntz_value(set ? data : ~data);
 257
 258                                 if(first_set < BS_UNIT_SIZE_BITS)
 259                                         return first_set + i * BS_UNIT_SIZE_BITS;
 260                         }
 261                 }
 262         }
 263
 264         return -1;
 265 }
 266
 267 #define bitset_next_clear(bs,pos) _bitset_next((bs), (pos), 0)
 268 #define bitset_next_set(bs,pos) _bitset_next((bs), (pos), 1)
 269
 270 /**
 271  * Convenience macro for bitset iteration.
 272  * @param bitset The bitset.
 273  * @param elm A unsigned long variable.
 274  */
 275 #define bitset_foreach(bitset,elm) \
 276   for(elm = bitset_next_set(bitset,0); elm != -1; elm = bitset_next_set(bitset,elm+1))
 277
 278
 279 #define bitset_foreach_clear(bitset,elm) \
 280   for(elm = bitset_next_clear(bitset,0); elm != -1; elm = bitset_next_clear(bitset,elm+1))
 281
 282 /**
 283  * Count the bits set.
 284  * This can also be seen as the cardinality of the set.
 285  * @param bs The bitset.
 286  * @return The number of bits set in the bitset.
 287  */
 288 static INLINE unsigned long bitset_popcnt(const bitset_t *bs)
 289 {
 290         unsigned long i, pop = 0;
 291         unsigned long *unit;
 292
 293         for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit)
 294                 pop += _bitset_inside_pop(unit);
 295
 296         return pop;
 297 }
 298
 299 /**
 300  * Clear the bitset.
 301  * This sets all bits to zero.
 302  * @param bs The bitset.
 303  */
 304 static INLINE void bitset_clear_all(bitset_t *bs)
 305 {
 306         memset(bs->data, 0, BS_UNIT_SIZE * bs->units);
 307 }
 308
 309 /**
 310  * Set the bitset.
 311  * This sets all bits to one.
 312  * @param bs The bitset.
 313  */
 314 static INLINE void bitset_set_all(bitset_t *bs)
 315 {
 316         //TODO is this correct (last unit)?
 317         //TODO is -1 correct == all bits equal 1
 318         memset(bs->data, -1, BS_UNIT_SIZE * bs->units);
 319 }
 320
 321 /**
 322  * Check, if one bitset is contained by another.
 323  * That is, each bit set in lhs is also set in rhs.
 324  * @param lhs A bitset.
 325  * @param rhs Another bitset.
 326  * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
 327  */
 328 static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
 329 {
 330         unsigned long n = lhs->units < rhs->units ? lhs->units : rhs->units;
 331         unsigned long i;
 332
 333         for(i = 0; i < n; ++i) {
 334                 unsigned long lu = lhs->data[i];
 335                 unsigned long ru = rhs->data[i];
 336
 337                 if((lu | ru) & ~ru)
 338                         return 0;
 339         }
 340
 341         /*
 342          * If the left hand sinde is a larger bitset than rhs,
 343          * we have to check, that all extra bits in lhs are 0
 344          */
 345         if(lhs->units > n) {
 346                 for(i = n; i < lhs->units; ++i) {
 347                         if(lhs->data[i] != 0)
 348                                 return 0;
 349                 }
 350         }
 351
 352         return 1;
 353 }
 354
 355 /**
 356  * Print a bitset to a stream.
 357  * The bitset is printed as a comma seperated list of bits set.
 358  * @param file The stream.
 359  * @param bs The bitset.
 360  */
 361 static INLINE void bitset_fprint(FILE *file, const bitset_t *bs)
 362 {
 363         const char *prefix = "";
 364         int i;
 365
 366         putc('[', file);
 367         for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) {
 368                 fprintf(file, "%s%u", prefix, i);
 369                 prefix = ",";
 370         }
 371         putc(']', file);
 372 }
 373
 374 static INLINE void bitset_debug_fprint(FILE *file, const bitset_t *bs)
 375 {
 376         unsigned long i;
 377
 378         fprintf(file, "%lu:", bs->units);
 379         for(i = 0; i < bs->units; ++i)
 380                 fprintf(file, " %0lx", bs->data[i]);
 381 }
 382
 383 /*
 384  * Here, the binary operations follow.
 385  * And, Or, And Not, Xor are available.
 386  */
 387 #define BINARY_OP(op) \
 388 static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \
 389 { \
 390         unsigned long i; \
 391         unsigned long n = tgt->units > src->units ? src->units : tgt->units; \
 392         for(i = 0; i < n; i += _BITSET_BINOP_UNITS_INC) \
 393                 _bitset_inside_binop_ ## op(&tgt->data[i], &src->data[i]); \
 394         if(n < tgt->units) \
 395                 _bitset_clear_rest(&tgt->data[i], tgt->units - i); \
 396         return tgt; \
 397 }
 398
 399 /*
 400  * Define the clear rest macro for the and, since it is the only case,
 401  * were non existed (treated as 0) units in the src must be handled.
 402  * For all other operations holds: x Op 0 = x for Op in { Andnot, Or, Xor }
 403  *
 404  * For and, each bitset implementer has to provide the macro
 405  * _bitset_clear_units(data, n), which clears n units from the pointer
 406  * data on.
 407  */
 408 #define _bitset_clear_rest(data,n) _bitset_inside_clear_units(data, n)
 409 BINARY_OP(and)
 410 #undef _bitset_clear_rest
 411 #define _bitset_clear_rest(data,n)
 412
 413 BINARY_OP(andnot)
 414 BINARY_OP(or)
 415 BINARY_OP(xor)
 416
 417 #endif