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