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