X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fbitset.h;h=9f01046aacd0b105691d2424c9bcad313b45de7c;hb=c79fe4adc914d8d867772053bedf449a4f85645d;hp=38e51ef5cf10ad5ab0c11b17530e5f10ace3bbc4;hpb=e9a76eb0a87762bac3446ed303884095ed1e573d;p=libfirm diff --git a/ir/adt/bitset.h b/ir/adt/bitset.h index 38e51ef5c..9f01046aa 100644 --- a/ir/adt/bitset.h +++ b/ir/adt/bitset.h @@ -1,116 +1,120 @@ -/** - * @file bitset.h - * @date 15.10.2004 - * @author Sebastian Hack - * @brief A bitset implementation. +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifndef __FIRM_BITSET_H -#define __FIRM_BITSET_H +/** + * @file + * @brief convenience layer over raw_bitsets (stores number of bits + * with the bitfield) + * @author Matthias Braun + * @version $Id$ + */ +#ifndef FIRM_ADT_BITSET_H +#define FIRM_ADT_BITSET_H #include #include #include #include -#include "firm_config.h" +#include "xmalloc.h" #include "bitfiddle.h" +#include "raw_bitset.h" -#include "bitset_std.h" - -/* -#if defined(__GNUC__) && defined(__i386__) -#include "bitset_ia32.h" -#endif -*/ - -typedef struct _bitset_t { - unsigned long units; - unsigned long *data; +typedef struct bitset_t { + unsigned size; /**< size of the bitset in bits */ + unsigned data[1]; /**< data (should be declared data[] but this is only + allowed in C99) */ } bitset_t; -#define BS_UNIT_SIZE sizeof(unsigned long) -#define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8) -#define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1) - /** - * Initialize a bitset. - * This functions should not be called. - * - * Note that this function needs three macros which must be provided by the - * bitfield implementor: - * - _bitset_overall_size(highest_bit) The overall size that must be - * allocated for the bitfield in bytes. - * - _bitset_units(highest_bit) The number of units that will be - * present in the bitfield for a given highest bit. - * - _bitset_data_ptr(data, highest_bit) This produces as pointer to the - * first unit in the allocated memory area. The main reason for this - * macro is, that some bitset implementors want control over memory - * alignment. - * - * @param area A pointer to memory reserved for the bitset. - * @param units The number of units that are allocated for the bitset. - * @return A pointer to the initialized bitset. + * return the number of bytes a bitset would need */ -static INLINE bitset_t *_bitset_prepare(void *area, unsigned long highest_bit) +static inline size_t bitset_total_size(unsigned n_bits) { - bitset_t *ptr = area; - memset(area, 0, _bitset_overall_size(sizeof(bitset_t), highest_bit)); - ptr->units = _bitset_units(highest_bit); - ptr->data = _bitset_data_ptr(area, sizeof(bitset_t), highest_bit); - return ptr; + return sizeof(bitset_t) - sizeof(((bitset_t*)0)->data) + + BITSET_SIZE_BYTES(n_bits); } /** - * Get the capacity of the bitset in bits. - * @param bs The bitset. - * @return The capacity in bits of the bitset. + * initialize a bitset for bitsize size (bitset should point to memory + * with a size calculated by bitset_total_size) */ -#define bitset_capacity(bs) ((bs)->units * BS_UNIT_SIZE_BITS) +static inline bitset_t *bitset_init(void *memory, unsigned size) +{ + bitset_t *result = (bitset_t*) memory; + result->size = size; + rbitset_clear_all(result->data, size); + return result; +} /** * Allocate a bitset on an obstack. * @param obst The obstack. - * @param highest_bit The greatest bit that shall be stored in the set. + * @param size The greatest bit that shall be stored in the set. * @return A pointer to an empty initialized bitset. */ -#define bitset_obstack_alloc(obst,highest_bit) \ - _bitset_prepare(obstack_alloc(obst, _bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit) +static inline bitset_t *bitset_obstack_alloc(struct obstack *obst, + unsigned n_bits) +{ + size_t size = bitset_total_size(n_bits); + void *memory = obstack_alloc(obst, size); + return bitset_init(memory, n_bits); +} /** * Allocate a bitset via malloc. - * @param highest_bit The greatest bit that shall be stored in the set. + * @param size The greatest bit that shall be stored in the set. * @return A pointer to an empty initialized bitset. */ -#define bitset_malloc(highest_bit) \ - _bitset_prepare(malloc(_bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit) +static inline bitset_t *bitset_malloc(unsigned n_bits) +{ + size_t size = bitset_total_size(n_bits); + void *memory = xmalloc(size); + return bitset_init(memory, n_bits); +} /** * Free a bitset allocated with bitset_malloc(). * @param bs The bitset. */ -#define bitset_free(bs) free(bs) +static inline void bitset_free(bitset_t *bitset) +{ + xfree(bitset); +} /** * Allocate a bitset on the stack via alloca. - * @param highest_bit The greatest bit that shall be stored in the set. + * @param size The greatest bit that shall be stored in the set. * @return A pointer to an empty initialized bitset. */ -#define bitset_alloca(highest_bit) \ - _bitset_prepare(alloca(_bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit) - +#define bitset_alloca(size) \ + bitset_init(alloca(bitset_total_size(size)), (size)) /** - * Get the unit which contains a specific bit. - * This function is internal. + * Get the size of the bitset in bits. + * @note Note the difference between capacity and size. * @param bs The bitset. - * @param bit The bit. - * @return A pointer to the unit containing the bit. + * @return The highest bit which can be set or cleared plus 1. */ -static INLINE unsigned long *_bitset_get_unit(const bitset_t *bs, unsigned long bit) +static inline unsigned bitset_size(const bitset_t *bitset) { - assert(bit < bs->units * BS_UNIT_SIZE_BITS && "Bit too large"); - return bs->data + bit / BS_UNIT_SIZE_BITS; + return bitset->size; } /** @@ -118,10 +122,10 @@ static INLINE unsigned long *_bitset_get_unit(const bitset_t *bs, unsigned long * @param bs The bitset. * @param bit The bit to set. */ -static INLINE void bitset_set(bitset_t *bs, unsigned long bit) +static inline void bitset_set(bitset_t *bs, unsigned bit) { - unsigned long *unit = _bitset_get_unit(bs, bit); - _bitset_inside_set(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + rbitset_set(bs->data, bit); } /** @@ -129,16 +133,22 @@ static INLINE void bitset_set(bitset_t *bs, unsigned long bit) * @param bs The bitset. * @param bit The bit to clear. */ -static INLINE void bitset_clear(bitset_t *bs, unsigned long bit) +static inline void bitset_clear(bitset_t *bs, unsigned bit) { - unsigned long *unit = _bitset_get_unit(bs, bit); - _bitset_inside_clear(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + rbitset_clear(bs->data, bit); } -static INLINE int bitset_is_set(const bitset_t *bs, unsigned long bit) +/** + * Check, if a bit is set. + * @param bs The bitset. + * @param bit The bit to check for. + * @return 1, if the bit was set, 0 if not. + */ +static inline bool bitset_is_set(const bitset_t *bs, unsigned bit) { - unsigned long *unit = _bitset_get_unit(bs, bit); - return _bitset_inside_is_set(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + return rbitset_is_set(bs->data, bit); } /** @@ -146,67 +156,47 @@ static INLINE int bitset_is_set(const bitset_t *bs, unsigned long bit) * @param bs The bitset. * @param bit The bit to flip. */ -static INLINE void bitset_flip(bitset_t *bs, unsigned long bit) +static inline void bitset_flip(bitset_t *bs, unsigned bit) { - unsigned long *unit = _bitset_get_unit(bs, bit); - _bitset_inside_flip(unit, bit & BS_UNIT_MASK); + assert(bit < bs->size); + rbitset_flip(bs->data, bit); } /** - * Copy a bitset to another. - * @param tgt The target bitset. - * @param src The source bitset. - * @return The target bitset. + * Flip the whole bitset. + * @param bs The bitset. */ -static INLINE bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src) +static inline void bitset_flip_all(bitset_t *bs) { - unsigned long tu = tgt->units; - unsigned long su = src->units; - unsigned long min_units = tu < su ? tu : su; - memcpy(tgt->data, src->data, min_units * BS_UNIT_SIZE); - if(tu > min_units) - memset(tgt->data + min_units, 0, BS_UNIT_SIZE * (tu - min_units)); - return tgt; + rbitset_flip_all(bs->data, bs->size); } /** - * Find the smallest bit set in the bitset. - * @param bs The bitset. - * @return The smallest bit set in the bitset. + * Copy a bitset to another. Both bitset must be initialized and have the same + * number of bits. + * @param tgt The target bitset. + * @param src The source bitset. + * @return The target bitset. */ -static INLINE unsigned long bitset_min(const bitset_t *bs) +static inline void bitset_copy(bitset_t *tgt, const bitset_t *src) { - unsigned long i, ofs = 0; - - for(i = 0; i < bs->units; ++i) { - unsigned long *unit = &bs->data[i]; - unsigned long pos = _bitset_inside_ntz(unit); - if(pos > 0) - return ofs + pos; - ofs += BS_UNIT_SIZE_BITS; - } - - return 0; + assert(tgt->size == src->size); + rbitset_copy(tgt->data, src->data, src->size); } /** - * Find the greatest bit set in the bitset. + * Find the next unset bit from a given bit. + * @note Note that if pos is unset, pos is returned. * @param bs The bitset. - * @return The greatest bit set in the bitset. + * @param pos The bit from which to search for the next set bit. + * @return The next set bit from pos on, or (unsigned)-1, if no unset bit was + * found after pos. */ -static INLINE unsigned long bitset_max(const bitset_t *bs) +static inline unsigned bitset_next_clear(const bitset_t *bs, unsigned pos) { - unsigned long i, max = 0, ofs = 0; - - for(i = 0; i < bs->units; ++i) { - unsigned long *unit = &bs->data[i]; - unsigned long pos = _bitset_inside_nlz(unit); - if(pos > 0) - max = ofs + pos; - ofs += BS_UNIT_SIZE_BITS; - } - - return max; + if (pos >= bs->size) + return (unsigned)-1; + return rbitset_next_max(bs->data, pos, bs->size, false); } /** @@ -214,54 +204,27 @@ static INLINE unsigned long bitset_max(const bitset_t *bs) * @note Note that if pos is set, pos is returned. * @param bs The bitset. * @param pos The bit from which to search for the next set bit. - * @return The next set bit from pos on, or -1, if no set bit was found - * after pos. + * @return The next set bit from pos on, or (unsigned)-1, if no set bit was + * found after pos. */ -static INLINE unsigned long _bitset_next(const bitset_t *bs, - unsigned long pos, int set) +static inline unsigned bitset_next_set(const bitset_t *bs, unsigned pos) { - unsigned long unit_number = pos / BS_UNIT_SIZE_BITS; - unsigned long bit_in_unit = pos & BS_UNIT_MASK; - unsigned long in_unit_mask = (1 << bit_in_unit) - 1; - - /* - * Mask out the bits smaller than pos in the current unit. - * We are only interested in bits set higher than pos. - */ - unsigned long curr_unit = bs->data[unit_number] & ~in_unit_mask; - - /* Find the next bit set in the unit. */ - unsigned long next_in_this_unit - = _bitset_inside_ntz_value(set ? curr_unit : ~curr_unit); - - /* If there is a bit set in the current unit, exit. */ - if(next_in_this_unit < BS_UNIT_SIZE_BITS) - return next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS; - - /* Else search for set bits in the next units. */ - else { - unsigned long i; - for(i = unit_number + 1; i < bs->units; ++i) { - unsigned long data = bs->data[i]; - unsigned long first_set = _bitset_inside_ntz_value(set ? data : ~data); - if(first_set < BS_UNIT_SIZE_BITS) - return first_set + i * BS_UNIT_SIZE_BITS; - } - } - - return -1; + if (pos >= bs->size) + return (unsigned)-1; + return rbitset_next_max(bs->data, pos, bs->size, true); } -#define bitset_next_clear(bs,pos) _bitset_next((bs), (pos), 0) -#define bitset_next_set(bs,pos) _bitset_next((bs), (pos), 1) - /** * Convenience macro for bitset iteration. * @param bitset The bitset. * @param elm A unsigned long variable. */ #define bitset_foreach(bitset,elm) \ - for(elm = bitset_next_set(bitset,0); elm != -1; elm = bitset_next_set(bitset,elm+1)) + for(elm = bitset_next_set(bitset,0); elm != (unsigned) -1; elm = bitset_next_set(bitset,elm+1)) + + +#define bitset_foreach_clear(bitset,elm) \ + for(elm = bitset_next_clear(bitset,0); elm != (unsigned) -1; elm = bitset_next_clear(bitset,elm+1)) /** * Count the bits set. @@ -269,15 +232,9 @@ static INLINE unsigned long _bitset_next(const bitset_t *bs, * @param bs The bitset. * @return The number of bits set in the bitset. */ -static INLINE unsigned long bitset_popcnt(const bitset_t *bs) +static inline unsigned bitset_popcount(const bitset_t *bs) { - unsigned long i, pop = 0; - unsigned long *unit; - - for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit) - pop += _bitset_inside_pop(unit); - - return pop; + return rbitset_popcount(bs->data, bs->size); } /** @@ -285,9 +242,19 @@ static INLINE unsigned long bitset_popcnt(const bitset_t *bs) * This sets all bits to zero. * @param bs The bitset. */ -static INLINE void bitset_clear_all(bitset_t *bs) +static inline void bitset_clear_all(bitset_t *bs) { - memset(bs->data, 0, BS_UNIT_SIZE * bs->units); + rbitset_clear_all(bs->data, bs->size); +} + +/** + * Set the bitset. + * This sets all bits to one. + * @param bs The bitset. + */ +static inline void bitset_set_all(bitset_t *bs) +{ + rbitset_set_all(bs->data, bs->size); } /** @@ -297,84 +264,146 @@ static INLINE void bitset_clear_all(bitset_t *bs) * @param rhs Another bitset. * @return 1, if all bits in lhs are also set in rhs, 0 otherwise. */ -static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs) +static inline bool bitset_contains(const bitset_t *lhs, const bitset_t *rhs) { - unsigned long n = lhs->units < rhs->units ? lhs->units : rhs->units; - unsigned long i; + assert(lhs->size == rhs->size); + return rbitset_contains(lhs->data, rhs->data, lhs->size); +} - for(i = 0; i < n; ++i) { - unsigned long lu = lhs->data[i]; - unsigned long ru = rhs->data[i]; +/** + * Treat the bitset as a number and subtract 1. + * @param bs The bitset. + * @return The same bitset. + */ +static inline void bitset_minus1(bitset_t *bs) +{ + rbitset_minus1(bs->data, bs->size); +} - if((lu | ru) & ~ru) - return 0; - } +/** + * Check if two bitsets intersect. + * @param a The first bitset. + * @param b The second bitset. + * @return 1 if they have a bit in common, 0 if not. + */ +static inline bool bitset_intersect(const bitset_t *a, const bitset_t *b) +{ + assert(a->size == b->size); + return rbitsets_have_common(a->data, b->data, a->size); +} + +/** + * set or clear all bits in the range [from;to[. + * @param a The bitset. + * @param from The first index to set to one. + * @param to The last index plus one to set to one. + * @param do_set If 1 the bits are set, if 0, they are cleared. + */ +static inline void bitset_mod_range(bitset_t *a, unsigned from, unsigned to, + bool do_set) +{ + if (from == to) + return; - /* - * If the left hand sinde is a larger bitset than rhs, - * we have to check, that all extra bits in lhs are 0 - */ - if(lhs->units > n) { - for(i = n; i < lhs->units; ++i) { - if(lhs->data[i] != 0) - return 0; - } + if (to < from) { + unsigned tmp = from; + from = to; + to = tmp; } - return 1; + if (to > a->size) + to = a->size; + + rbitset_set_range(a->data, from, to, do_set); +} + +#define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1) +#define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0) + +/** + * Check, if a bitset is empty. + * @param a The bitset. + * @return 1, if the bitset is empty, 0 if not. + */ +static inline bool bitset_is_empty(const bitset_t *bs) +{ + return rbitset_is_empty(bs->data, bs->size); } /** * Print a bitset to a stream. - * The bitset is printed as a comma seperated list of bits set. + * The bitset is printed as a comma separated list of bits set. * @param file The stream. * @param bs The bitset. */ -static INLINE void bitset_fprint(FILE *file, const bitset_t *bs) +static inline void bitset_fprint(FILE *file, const bitset_t *bs) { const char *prefix = ""; int i; - putc('[', file); + putc('{', file); for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) { - fprintf(file, "%s%u", prefix, i); + fprintf(file, "%s%d", prefix, i); prefix = ","; } - putc(']', file); + putc('}', file); } -/* - * Here, the binary operations follow. - * And, Or, And Not, Xor are available. - */ -#define BINARY_OP(op) \ -static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \ -{ \ - int i; \ - int n = tgt->units > src->units ? src->units : tgt->units; \ - for(i = 0; i < n; i += _BITSET_BINOP_UNITS_INC) \ - _bitset_inside_binop_ ## op(&tgt->data[i], &src->data[i]); \ - if(n < tgt->units) \ - _bitset_clear_rest(&tgt->data[i], tgt->units - i); \ - return tgt; \ +/** + * Perform tgt = tgt & src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_and(bitset_t *tgt, const bitset_t *src) +{ + assert(tgt->size == src->size); + rbitset_and(tgt->data, src->data, src->size); } -/* - * Define the clear rest macro for the and, since it is the only case, - * were non existed (treated as 0) units in the src must be handled. - * For all other operations holds: x Op 0 = x for Op in { Andnot, Or, Xor } - * - * For and, each bitset implementer has to provide the macro - * _bitset_clear_units(data, n), which clears n units from the pointer - * data on. - */ -#define _bitset_clear_rest(data,n) _bitset_inside_clear_units(data, n) -BINARY_OP(and) -#undef _bitset_clear_rest -#define _bitset_clear_rest(data,n) - -BINARY_OP(andnot) -BINARY_OP(or) -BINARY_OP(xor) +/** + * Perform tgt = tgt & ~src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_andnot(bitset_t *tgt, const bitset_t *src) +{ + assert(tgt->size == src->size); + rbitset_andnot(tgt->data, src->data, src->size); +} + +/** + * Perform Union, tgt = tgt u src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_or(bitset_t *tgt, const bitset_t *src) +{ + assert(tgt->size == src->size); + rbitset_or(tgt->data, src->data, src->size); +} + +/** + * Perform tgt = tgt ^ src operation. + * @param tgt The target bitset. + * @param src The source bitset. + * @return the tgt set. + */ +static inline void bitset_xor(bitset_t *tgt, const bitset_t *src) +{ + assert(tgt->size == src->size); + rbitset_xor(tgt->data, src->data, src->size); +} + +/** + * Copy a raw bitset into an bitset. + */ +static inline void rbitset_copy_to_bitset(const unsigned *rbitset, + bitset_t *bitset) +{ + rbitset_copy(bitset->data, rbitset, bitset->size); +} #endif