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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   convenience layer over raw_bitsets (stores number of bits
   9  *          with the bitfield)
  10  * @author  Matthias Braun
  11  */
  12 #ifndef FIRM_ADT_BITSET_H
  13 #define FIRM_ADT_BITSET_H
  14
  15 #include <stdlib.h>
  16 #include <stdio.h>
  17 #include <assert.h>
  18 #include <string.h>
  19 #include "irprintf.h"
  20
  21 #include "xmalloc.h"
  22 #include "bitfiddle.h"
  23 #include "raw_bitset.h"
  24
  25 typedef struct bitset_t {
  26         size_t size;       /**< size of the bitset in bits */
  27         unsigned data[1];  /**< data (should be declared data[] but this is only
  28                                 allowed in C99) */
  29 } bitset_t;
  30
  31 /**
  32  * return the number of bytes a bitset would need
  33  */
  34 static inline size_t bitset_total_size(size_t n_bits)
  35 {
  36         return sizeof(bitset_t) - sizeof(((bitset_t*)0)->data)
  37                 + BITSET_SIZE_BYTES(n_bits);
  38 }
  39
  40 /**
  41  * initialize a bitset for bitsize size (bitset should point to memory
  42  * with a size calculated by bitset_total_size)
  43  */
  44 static inline bitset_t *bitset_init(void *memory, size_t size)
  45 {
  46         bitset_t *result = (bitset_t*) memory;
  47         result->size = size;
  48         rbitset_clear_all(result->data, size);
  49         return result;
  50 }
  51
  52 /**
  53  * Allocate a bitset on an obstack.
  54  * @param obst The obstack.
  55  * @param size The greatest bit that shall be stored in the set.
  56  * @return A pointer to an empty initialized bitset.
  57  */
  58 static inline bitset_t *bitset_obstack_alloc(struct obstack *obst,
  59                                              size_t n_bits)
  60 {
  61         size_t size   = bitset_total_size(n_bits);
  62         void  *memory = obstack_alloc(obst, size);
  63         return bitset_init(memory, n_bits);
  64 }
  65
  66 /**
  67  * Allocate a bitset via malloc.
  68  * @param size The greatest bit that shall be stored in the set.
  69  * @return A pointer to an empty initialized bitset.
  70  */
  71 static inline bitset_t *bitset_malloc(size_t n_bits)
  72 {
  73         size_t  size   = bitset_total_size(n_bits);
  74         void   *memory = xmalloc(size);
  75         return bitset_init(memory, n_bits);
  76 }
  77
  78 /**
  79  * Free a bitset allocated with bitset_malloc().
  80  * @param bs The bitset.
  81  */
  82 static inline void bitset_free(bitset_t *bitset)
  83 {
  84         xfree(bitset);
  85 }
  86
  87 /**
  88  * Allocate a bitset on the stack via alloca.
  89  * @param size The greatest bit that shall be stored in the set.
  90  * @return A pointer to an empty initialized bitset.
  91  */
  92 #define bitset_alloca(size) \
  93         bitset_init(alloca(bitset_total_size(size)), (size))
  94
  95 /**
  96  * Get the size of the bitset in bits.
  97  * @note Note the difference between capacity and size.
  98  * @param bs The bitset.
  99  * @return The highest bit which can be set or cleared plus 1.
 100  */
 101 static inline size_t bitset_size(const bitset_t *bitset)
 102 {
 103         return bitset->size;
 104 }
 105
 106 /**
 107  * Set a bit in the bitset.
 108  * @param bs The bitset.
 109  * @param bit The bit to set.
 110  */
 111 static inline void bitset_set(bitset_t *bs, size_t bit)
 112 {
 113         assert(bit < bs->size);
 114         rbitset_set(bs->data, bit);
 115 }
 116
 117 /**
 118  * Clear a bit in the bitset.
 119  * @param bs The bitset.
 120  * @param bit The bit to clear.
 121  */
 122 static inline void bitset_clear(bitset_t *bs, size_t bit)
 123 {
 124         assert(bit < bs->size);
 125         rbitset_clear(bs->data, bit);
 126 }
 127
 128 /**
 129  * Check, if a bit is set.
 130  * @param bs The bitset.
 131  * @param bit The bit to check for.
 132  * @return 1, if the bit was set, 0 if not.
 133  */
 134 static inline bool bitset_is_set(const bitset_t *bs, size_t bit)
 135 {
 136         assert(bit < bs->size);
 137         return rbitset_is_set(bs->data, bit);
 138 }
 139
 140 /**
 141  * Flip a bit in a bitset.
 142  * @param bs The bitset.
 143  * @param bit The bit to flip.
 144  */
 145 static inline void bitset_flip(bitset_t *bs, size_t bit)
 146 {
 147         assert(bit < bs->size);
 148         rbitset_flip(bs->data, bit);
 149 }
 150
 151 /**
 152  * Flip the whole bitset.
 153  * @param bs The bitset.
 154  */
 155 static inline void bitset_flip_all(bitset_t *bs)
 156 {
 157         rbitset_flip_all(bs->data, bs->size);
 158 }
 159
 160 /**
 161  * Copy a bitset to another. Both bitset must be initialized and have the same
 162  * number of bits.
 163  * @param tgt The target bitset.
 164  * @param src The source bitset.
 165  * @return The target bitset.
 166  */
 167 static inline void bitset_copy(bitset_t *tgt, const bitset_t *src)
 168 {
 169         assert(tgt->size == src->size);
 170         rbitset_copy(tgt->data, src->data, src->size);
 171 }
 172
 173 static inline void bitset_copy_into(bitset_t *tgt, const bitset_t *src)
 174 {
 175         assert(tgt->size >= src->size);
 176         rbitset_copy_into(tgt->data, src->data, src->size);
 177 }
 178
 179 /**
 180  * Find the next unset bit from a given bit.
 181  * @note Note that if pos is unset, pos is returned.
 182  * @param bs The bitset.
 183  * @param pos The bit from which to search for the next set bit.
 184  * @return The next set bit from pos on, or (size_t)-1, if no unset bit was
 185  * found after pos.
 186  */
 187 static inline size_t bitset_next_clear(const bitset_t *bs, size_t pos)
 188 {
 189         return rbitset_next_max(bs->data, pos, bs->size, false);
 190 }
 191
 192 /**
 193  * Find the next set bit from a given bit.
 194  * @note Note that if pos is set, pos is returned.
 195  * @param bs The bitset.
 196  * @param pos The bit from which to search for the next set bit.
 197  * @return The next set bit from pos on, or (size_t)-1, if no set bit was
 198  * found after pos.
 199  */
 200 static inline size_t bitset_next_set(const bitset_t *bs, size_t pos)
 201 {
 202         return rbitset_next_max(bs->data, pos, bs->size, true);
 203 }
 204
 205 /**
 206  * Convenience macro for bitset iteration.
 207  * @param bitset The bitset.
 208  * @param elm A size_t variable.
 209  */
 210 #define bitset_foreach(bitset, elm) \
 211         for (size_t elm = 0; (elm = bitset_next_set((bitset), elm)) != (size_t)-1; ++elm)
 212
 213
 214 #define bitset_foreach_clear(bitset, elm) \
 215         for (size_t elm = 0; (elm = bitset_next_clear((bitset), elm)) != (size_t)-1; ++elm)
 216
 217 /**
 218  * Count the bits set.
 219  * This can also be seen as the cardinality of the set.
 220  * @param bs The bitset.
 221  * @return The number of bits set in the bitset.
 222  */
 223 static inline size_t bitset_popcount(const bitset_t *bs)
 224 {
 225         return rbitset_popcount(bs->data, bs->size);
 226 }
 227
 228 /**
 229  * Clear the bitset.
 230  * This sets all bits to zero.
 231  * @param bs The bitset.
 232  */
 233 static inline void bitset_clear_all(bitset_t *bs)
 234 {
 235         rbitset_clear_all(bs->data, bs->size);
 236 }
 237
 238 /**
 239  * Set the bitset.
 240  * This sets all bits to one.
 241  * @param bs The bitset.
 242  */
 243 static inline void bitset_set_all(bitset_t *bs)
 244 {
 245         rbitset_set_all(bs->data, bs->size);
 246 }
 247
 248 /**
 249  * Check, if one bitset is contained by another.
 250  * That is, each bit set in lhs is also set in rhs.
 251  * @param lhs A bitset.
 252  * @param rhs Another bitset.
 253  * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
 254  */
 255 static inline bool bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
 256 {
 257         assert(lhs->size == rhs->size);
 258         return rbitset_contains(lhs->data, rhs->data, lhs->size);
 259 }
 260
 261 /**
 262  * Treat the bitset as a number and subtract 1.
 263  * @param bs The bitset.
 264  * @return The same bitset.
 265  */
 266 static inline void bitset_minus1(bitset_t *bs)
 267 {
 268         rbitset_minus1(bs->data, bs->size);
 269 }
 270
 271 /**
 272  * Check if two bitsets intersect.
 273  * @param a The first bitset.
 274  * @param b The second bitset.
 275  * @return 1 if they have a bit in common, 0 if not.
 276  */
 277 static inline bool bitset_intersect(const bitset_t *a, const bitset_t *b)
 278 {
 279         assert(a->size == b->size);
 280         return rbitsets_have_common(a->data, b->data, a->size);
 281 }
 282
 283 /**
 284  * set or clear all bits in the range [from;to[.
 285  * @param a      The bitset.
 286  * @param from   The first index to set to one.
 287  * @param to     The last index plus one to set to one.
 288  * @param do_set If 1 the bits are set, if 0, they are cleared.
 289  */
 290 static inline void bitset_mod_range(bitset_t *a, size_t from, size_t to,
 291                                     bool do_set)
 292 {
 293         if (from == to)
 294             return;
 295
 296         if (to < from) {
 297                 size_t tmp = from;
 298                 from = to;
 299                 to = tmp;
 300         }
 301
 302         if (to > a->size)
 303                 to = a->size;
 304
 305         rbitset_set_range(a->data, from, to, do_set);
 306 }
 307
 308 #define bitset_set_range(bs, from, to)   bitset_mod_range((bs), (from), (to), 1)
 309 #define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
 310
 311 /**
 312  * Check, if a bitset is empty.
 313  * @param a The bitset.
 314  * @return 1, if the bitset is empty, 0 if not.
 315  */
 316 static inline bool bitset_is_empty(const bitset_t *bs)
 317 {
 318         return rbitset_is_empty(bs->data, bs->size);
 319 }
 320
 321 /**
 322  * Print a bitset to a stream.
 323  * The bitset is printed as a comma separated list of bits set.
 324  * @param file The stream.
 325  * @param bs The bitset.
 326  */
 327 static inline void bitset_fprint(FILE *file, const bitset_t *bs)
 328 {
 329         const char *prefix = "";
 330         size_t i;
 331
 332         putc('{', file);
 333         for(i = bitset_next_set(bs, 0); i != (size_t)-1; i = bitset_next_set(bs, i + 1)) {
 334                 ir_fprintf(file, "%s%zu", prefix, i);
 335                 prefix = ",";
 336         }
 337         putc('}', file);
 338 }
 339
 340 /**
 341  * Perform tgt = tgt & src operation.
 342  * @param tgt  The target bitset.
 343  * @param src  The source bitset.
 344  * @return the tgt set.
 345  */
 346 static inline void bitset_and(bitset_t *tgt, const bitset_t *src)
 347 {
 348         assert(tgt->size == src->size);
 349         rbitset_and(tgt->data, src->data, src->size);
 350 }
 351
 352 /**
 353  * Perform tgt = tgt & ~src operation.
 354  * @param tgt  The target bitset.
 355  * @param src  The source bitset.
 356  * @return the tgt set.
 357  */
 358 static inline void bitset_andnot(bitset_t *tgt, const bitset_t *src)
 359 {
 360         assert(tgt->size == src->size);
 361         rbitset_andnot(tgt->data, src->data, src->size);
 362 }
 363
 364 /**
 365  * Perform Union, tgt = tgt u src operation.
 366  * @param tgt  The target bitset.
 367  * @param src  The source bitset.
 368  * @return the tgt set.
 369  */
 370 static inline void bitset_or(bitset_t *tgt, const bitset_t *src)
 371 {
 372         assert(tgt->size == src->size);
 373         rbitset_or(tgt->data, src->data, src->size);
 374 }
 375
 376 /**
 377  * Perform tgt = tgt ^ src operation.
 378  * @param tgt  The target bitset.
 379  * @param src  The source bitset.
 380  * @return the tgt set.
 381  */
 382 static inline void bitset_xor(bitset_t *tgt, const bitset_t *src)
 383 {
 384         assert(tgt->size == src->size);
 385         rbitset_xor(tgt->data, src->data, src->size);
 386 }
 387
 388 /**
 389  * Copy a raw bitset into an bitset.
 390  */
 391 static inline void rbitset_copy_to_bitset(const unsigned *rbitset,
 392                                           bitset_t *bitset)
 393 {
 394         rbitset_copy(bitset->data, rbitset, bitset->size);
 395 }
 396
 397 #endif