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