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

   1 /*
   2  * Copyright (C) 1995-2008 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  * @version $Id$
  26  */
  27 #ifndef FIRM_ADT_BITSET_H
  28 #define FIRM_ADT_BITSET_H
  29
  30 #include <stdlib.h>
  31 #include <stdio.h>
  32 #include <assert.h>
  33 #include <string.h>
  34
  35 #include "xmalloc.h"
  36 #include "bitfiddle.h"
  37 #include "raw_bitset.h"
  38
  39 typedef struct bitset_t {
  40         unsigned 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(unsigned 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, unsigned 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                                              unsigned 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(unsigned 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 unsigned 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, unsigned 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, unsigned 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, unsigned 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, unsigned 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 /**
 188  * Find the next unset bit from a given bit.
 189  * @note Note that if pos is unset, pos is returned.
 190  * @param bs The bitset.
 191  * @param pos The bit from which to search for the next set bit.
 192  * @return The next set bit from pos on, or (unsigned)-1, if no unset bit was
 193  * found after pos.
 194  */
 195 static inline unsigned bitset_next_clear(const bitset_t *bs, unsigned pos)
 196 {
 197         if (pos >= bs->size)
 198                 return (unsigned)-1;
 199         return rbitset_next_max(bs->data, pos, bs->size, false);
 200 }
 201
 202 /**
 203  * Find the next set bit from a given bit.
 204  * @note Note that if pos is set, pos is returned.
 205  * @param bs The bitset.
 206  * @param pos The bit from which to search for the next set bit.
 207  * @return The next set bit from pos on, or (unsigned)-1, if no set bit was
 208  * found after pos.
 209  */
 210 static inline unsigned bitset_next_set(const bitset_t *bs, unsigned pos)
 211 {
 212         if (pos >= bs->size)
 213                 return (unsigned)-1;
 214         return rbitset_next_max(bs->data, pos, bs->size, true);
 215 }
 216
 217 /**
 218  * Convenience macro for bitset iteration.
 219  * @param bitset The bitset.
 220  * @param elm A unsigned long variable.
 221  */
 222 #define bitset_foreach(bitset,elm) \
 223         for(elm = bitset_next_set(bitset,0); elm != (unsigned) -1; elm = bitset_next_set(bitset,elm+1))
 224
 225
 226 #define bitset_foreach_clear(bitset,elm) \
 227         for(elm = bitset_next_clear(bitset,0); elm != (unsigned) -1; elm = bitset_next_clear(bitset,elm+1))
 228
 229 /**
 230  * Count the bits set.
 231  * This can also be seen as the cardinality of the set.
 232  * @param bs The bitset.
 233  * @return The number of bits set in the bitset.
 234  */
 235 static inline unsigned bitset_popcount(const bitset_t *bs)
 236 {
 237         return rbitset_popcount(bs->data, bs->size);
 238 }
 239
 240 /**
 241  * Clear the bitset.
 242  * This sets all bits to zero.
 243  * @param bs The bitset.
 244  */
 245 static inline void bitset_clear_all(bitset_t *bs)
 246 {
 247         rbitset_clear_all(bs->data, bs->size);
 248 }
 249
 250 /**
 251  * Set the bitset.
 252  * This sets all bits to one.
 253  * @param bs The bitset.
 254  */
 255 static inline void bitset_set_all(bitset_t *bs)
 256 {
 257         rbitset_set_all(bs->data, bs->size);
 258 }
 259
 260 /**
 261  * Check, if one bitset is contained by another.
 262  * That is, each bit set in lhs is also set in rhs.
 263  * @param lhs A bitset.
 264  * @param rhs Another bitset.
 265  * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
 266  */
 267 static inline bool bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
 268 {
 269         assert(lhs->size == rhs->size);
 270         return rbitset_contains(lhs->data, rhs->data, lhs->size);
 271 }
 272
 273 /**
 274  * Treat the bitset as a number and subtract 1.
 275  * @param bs The bitset.
 276  * @return The same bitset.
 277  */
 278 static inline void bitset_minus1(bitset_t *bs)
 279 {
 280         rbitset_minus1(bs->data, bs->size);
 281 }
 282
 283 /**
 284  * Check if two bitsets intersect.
 285  * @param a The first bitset.
 286  * @param b The second bitset.
 287  * @return 1 if they have a bit in common, 0 if not.
 288  */
 289 static inline bool bitset_intersect(const bitset_t *a, const bitset_t *b)
 290 {
 291         assert(a->size == b->size);
 292         return rbitsets_have_common(a->data, b->data, a->size);
 293 }
 294
 295 /**
 296  * set or clear all bits in the range [from;to[.
 297  * @param a      The bitset.
 298  * @param from   The first index to set to one.
 299  * @param to     The last index plus one to set to one.
 300  * @param do_set If 1 the bits are set, if 0, they are cleared.
 301  */
 302 static inline void bitset_mod_range(bitset_t *a, unsigned from, unsigned to,
 303                                     bool do_set)
 304 {
 305         if (from == to)
 306             return;
 307
 308         if (to < from) {
 309                 unsigned tmp = from;
 310                 from = to;
 311                 to = tmp;
 312         }
 313
 314         if (to > a->size)
 315                 to = a->size;
 316
 317         rbitset_set_range(a->data, from, to, do_set);
 318 }
 319
 320 #define bitset_set_range(bs, from, to)   bitset_mod_range((bs), (from), (to), 1)
 321 #define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
 322
 323 /**
 324  * Check, if a bitset is empty.
 325  * @param a The bitset.
 326  * @return 1, if the bitset is empty, 0 if not.
 327  */
 328 static inline bool bitset_is_empty(const bitset_t *bs)
 329 {
 330         return rbitset_is_empty(bs->data, bs->size);
 331 }
 332
 333 /**
 334  * Print a bitset to a stream.
 335  * The bitset is printed as a comma separated list of bits set.
 336  * @param file The stream.
 337  * @param bs The bitset.
 338  */
 339 static inline void bitset_fprint(FILE *file, const bitset_t *bs)
 340 {
 341         const char *prefix = "";
 342         int i;
 343
 344         putc('{', file);
 345         for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) {
 346                 fprintf(file, "%s%d", prefix, i);
 347                 prefix = ",";
 348         }
 349         putc('}', file);
 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_and(bitset_t *tgt, const bitset_t *src)
 359 {
 360         assert(tgt->size == src->size);
 361         rbitset_and(tgt->data, src->data, src->size);
 362 }
 363
 364 /**
 365  * Perform tgt = tgt & ~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_andnot(bitset_t *tgt, const bitset_t *src)
 371 {
 372         assert(tgt->size == src->size);
 373         rbitset_andnot(tgt->data, src->data, src->size);
 374 }
 375
 376 /**
 377  * Perform Union, tgt = tgt u 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_or(bitset_t *tgt, const bitset_t *src)
 383 {
 384         assert(tgt->size == src->size);
 385         rbitset_or(tgt->data, src->data, src->size);
 386 }
 387
 388 /**
 389  * Perform tgt = tgt ^ src operation.
 390  * @param tgt  The target bitset.
 391  * @param src  The source bitset.
 392  * @return the tgt set.
 393  */
 394 static inline void bitset_xor(bitset_t *tgt, const bitset_t *src)
 395 {
 396         assert(tgt->size == src->size);
 397         rbitset_xor(tgt->data, src->data, src->size);
 398 }
 399
 400 /**
 401  * Copy a raw bitset into an bitset.
 402  */
 403 static inline void rbitset_copy_to_bitset(const unsigned *rbitset,
 404                                           bitset_t *bitset)
 405 {
 406         rbitset_copy(bitset->data, rbitset, bitset->size);
 407 }
 408
 409 #endif