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

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