X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fraw_bitset.h;h=e5056c44242294837ff811fe70a2aa7b11d09a35;hb=3e889332cb054e5cee1a12bba6dd0209121100cf;hp=9c6c1871fd247d91310b38691ff7d10ce475aa2b;hpb=45fc5c69b556a288c3df6058b58ad99b2d865ac5;p=libfirm diff --git a/ir/adt/raw_bitset.h b/ir/adt/raw_bitset.h index 9c6c1871f..e5056c442 100644 --- a/ir/adt/raw_bitset.h +++ b/ir/adt/raw_bitset.h @@ -19,38 +19,35 @@ /** * @file - * @brief helper functions for working with raw bitsets + * @brief raw bitsets (low-level bitset operations) * @date 15.10.2004 * @author Matthias Braun * @version $Id$ - * @brief - * Raw bitsets are constructed from unsigned int arrays. Additional information - * like the size of the bitset or the used memory are not stored for - * efficiency reasons. + * + * Raw bitsets are constructed from unsigned int arrays. Additional + * information like the size of the bitset or the used memory are not + * stored for (memory) efficiency reasons. * * These bitsets need less space than bitset_t and their representation * as int arrays allows having constant bitsets in the ro data segment. * They should for smaller bitset, whose length is known through other means * (a typical usage case is a set of cpu registers) * - * The bitset is built as an array of unsigned integers. It is assumed that - * exactly 32 bits may be put into each element of the array. If there are - * remaining bits, then they should be 0 + * The bitset is built as an array of unsigned integers. The unused bits + * must be zero. */ #ifndef FIRM_ADT_RAW_BITSET_H #define FIRM_ADT_RAW_BITSET_H #include -#include "bitset.h" +#include +#include "bitfiddle.h" #include "obst.h" -/** The base type for raw bitsets. */ -typedef unsigned int rawbs_base_t; - -#define BITS_PER_ELEM (sizeof(rawbs_base_t) * 8) -#define BITSET_SIZE_ELEMS(size_bits) ((size_bits)/BITS_PER_ELEM + 1) -#define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits) * sizeof(rawbs_base_t)) -#define BITSET_ELEM(bitset,pos) bitset[pos / BITS_PER_ELEM] +#define BITS_PER_ELEM (sizeof(unsigned) * 8) +#define BITSET_SIZE_ELEMS(size_bits) ((size_bits+BITS_PER_ELEM-1)/BITS_PER_ELEM) +#define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits) * sizeof(unsigned)) +#define BITSET_ELEM(bitset,pos) bitset[pos / BITS_PER_ELEM] /** * Allocate an empty raw bitset on the heap. @@ -59,12 +56,9 @@ typedef unsigned int rawbs_base_t; * * @return the new bitset */ -static inline unsigned *rbitset_malloc(unsigned size) { - unsigned size_bytes = BITSET_SIZE_BYTES(size); - unsigned *res = xmalloc(size_bytes); - memset(res, 0, size_bytes); - - return res; +static inline unsigned *rbitset_malloc(size_t size) +{ + return XMALLOCNZ(unsigned, BITSET_SIZE_ELEMS(size)); } /** @@ -75,8 +69,8 @@ static inline unsigned *rbitset_malloc(unsigned size) { */ #define rbitset_alloca(res, size) \ do { \ - unsigned size_bytes = BITSET_SIZE_BYTES(size); \ - res = alloca(size_bytes); \ + size_t size_bytes = BITSET_SIZE_BYTES(size); \ + res = (unsigned*)alloca(size_bytes); \ memset(res, 0, size_bytes); \ } while(0) @@ -88,38 +82,12 @@ do { \ * * @return the new bitset */ -static inline unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size) +static inline unsigned *rbitset_obstack_alloc(struct obstack *obst, + size_t size) { - unsigned size_bytes = BITSET_SIZE_BYTES(size); - unsigned *res = obstack_alloc(obst, size_bytes); - memset(res, 0, size_bytes); - - return res; + return OALLOCNZ(obst, unsigned, BITSET_SIZE_ELEMS(size)); } -/** - * Allocate an empty raw bitset including the size on an obstack. - * The size of this bitset can be accessed by bitset[-1]. - * - * @param obst the obstack where the bitset is allocated on - * @param size number of bits in the bitset - * - * @return the new bitset - */ -static inline unsigned *rbitset_w_size_obstack_alloc(struct obstack *obst, unsigned size) -{ - unsigned size_bytes = BITSET_SIZE_BYTES(size); - unsigned *res = obstack_alloc(obst, size_bytes + sizeof(unsigned)); - *res = size; - ++res; - memset(res, 0, size_bytes); - - return res; -} - -/** Return the size of a bitset allocated with a *_w_size_* function */ -#define rbitset_size(set) (set)[-1] - /** * Duplicate a raw bitset on an obstack. * @@ -130,10 +98,10 @@ static inline unsigned *rbitset_w_size_obstack_alloc(struct obstack *obst, unsig * @return the new bitset */ static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst, - const unsigned *old_bitset, unsigned size) + const unsigned *old_bitset, size_t size) { - unsigned size_bytes = BITSET_SIZE_BYTES(size); - unsigned *res = obstack_alloc(obst, size_bytes); + size_t size_bytes = BITSET_SIZE_BYTES(size); + unsigned *res = OALLOCN(obst, unsigned, BITSET_SIZE_ELEMS(size)); memcpy(res, old_bitset, size_bytes); return res; @@ -142,16 +110,17 @@ static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst, /** * Check if a bitset is empty, ie all bits cleared. */ -static inline int rbitset_is_empty(unsigned *bitset, unsigned size) +static inline bool rbitset_is_empty(const unsigned *bitset, size_t size) { - unsigned n = BITSET_SIZE_ELEMS(size); - unsigned i; + size_t i; + size_t n = BITSET_SIZE_ELEMS(size); + for (i = 0; i < n; ++i) { - if (bitset[i] != 0) - return 0; + if (bitset[i] != 0) { + return false; + } } - - return 1; + return true; } /** @@ -160,23 +129,50 @@ static inline int rbitset_is_empty(unsigned *bitset, unsigned size) * @param bitset the bitset * @param pos the position of the bit to be set */ -static inline void rbitset_set(unsigned *bitset, unsigned pos) +static inline void rbitset_set(unsigned *bitset, size_t pos) { BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM); } +/** + * Flip a bit at position pos. A zero bit becomes one, a one bit becomes zero. + * + * @param bitset the bitset + * @param pos position of the bit to be flipped + */ +static inline void rbitset_flip(unsigned *bitset, size_t pos) +{ + BITSET_ELEM(bitset, pos) ^= 1 << (pos % BITS_PER_ELEM); +} + +static inline unsigned rbitset_last_mask_(size_t size) +{ + size_t p; + if (size == 0) + return 0; + p = size % BITS_PER_ELEM; + return p == 0 ? ~0u : (1u << p)-1u; +} + /** * Set all bits in a given bitset. * * @param bitset the bitset * @param size number of bits in the bitset */ -static inline void rbitset_set_all(unsigned *bitset, unsigned size) +static inline void rbitset_set_all(unsigned *bitset, size_t size) { - unsigned size_bytes = BITSET_SIZE_BYTES(size); - memset(bitset, ~0, size_bytes); -} + size_t i; + size_t n = BITSET_SIZE_ELEMS(size); + + if (n == 0) + return; + for (i = 0; i < n-1; ++i) { + bitset[i] = ~0u; + } + bitset[i] = rbitset_last_mask_(size); +} /** * Clear a bit at position pos. @@ -184,7 +180,7 @@ static inline void rbitset_set_all(unsigned *bitset, unsigned size) * @param bitset the bitset * @param pos the position of the bit to be clear */ -static inline void rbitset_clear(unsigned *bitset, unsigned pos) +static inline void rbitset_clear(unsigned *bitset, size_t pos) { BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM)); } @@ -195,39 +191,56 @@ static inline void rbitset_clear(unsigned *bitset, unsigned pos) * @param bitset the bitset * @param size number of bits in the bitset */ -static inline void rbitset_clear_all(unsigned *bitset, unsigned size) +static inline void rbitset_clear_all(unsigned *bitset, size_t size) { - unsigned size_bytes = BITSET_SIZE_BYTES(size); + size_t size_bytes = BITSET_SIZE_BYTES(size); memset(bitset, 0, size_bytes); } +/** + * Flip all bits in a given bitset. + * + * @param bitset the bitset + * @param size number of bits in the bitset + */ +static inline void rbitset_flip_all(unsigned *bitset, size_t size) +{ + size_t pos; + size_t n = BITSET_SIZE_ELEMS(size); + + if (n == 0) + return; + + for (pos = 0; pos < n-1; ++pos) { + bitset[pos] ^= ~0u; + } + bitset[pos] ^= rbitset_last_mask_(size); +} + /** * Check if a bit is set at position pos. * * @param bitset the bitset * @param pos the position of the bit to check */ -static inline int rbitset_is_set(const unsigned *bitset, unsigned pos) +static inline bool rbitset_is_set(const unsigned *bitset, size_t pos) { - return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM)); + return (BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM))) != 0; } /** * Calculate the number of set bits (number of elements). * * @param bitset the bitset - * @param size size of the bitset + * @param size size of the bitset in bits */ -static inline unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) +static inline size_t rbitset_popcount(const unsigned *bitset, size_t size) { - unsigned pos; - unsigned n = BITSET_SIZE_ELEMS(size); - unsigned res = 0; - const unsigned *elem = bitset; - - for (pos = 0; pos < n; ++pos) { - res += _bitset_inside_pop(elem); - elem++; + size_t i, n = BITSET_SIZE_ELEMS(size); + size_t res = 0; + + for (i = 0; i < n; ++i) { + res += popcount(bitset[i]); } return res; @@ -246,14 +259,15 @@ static inline unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) * @note Does NOT check the size of the bitset, so ensure that a bit * will be found or use a sentinel bit! */ -static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) +static inline size_t rbitset_next(const unsigned *bitset, size_t pos, + bool set) { unsigned p; - unsigned elem_pos = pos / BITS_PER_ELEM; - unsigned bit_pos = pos % BITS_PER_ELEM; + size_t elem_pos = pos / BITS_PER_ELEM; + size_t bit_pos = pos % BITS_PER_ELEM; unsigned elem = bitset[elem_pos]; - unsigned mask = 0; + unsigned mask = set ? 0 : ~0u; /* * Mask out the bits smaller than pos in the current unit. @@ -261,10 +275,8 @@ static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos, int se */ unsigned in_elem_mask = (1 << bit_pos) - 1; - if (!set) - mask = ~mask; elem ^= mask; - p = _bitset_inside_ntz_value(elem & ~in_elem_mask); + p = ntz(elem & ~in_elem_mask); /* If there is a bit set in the current elem, exit. */ if (p < BITS_PER_ELEM) { @@ -276,23 +288,79 @@ static inline unsigned rbitset_next(const unsigned *bitset, unsigned pos, int se elem_pos++; elem = bitset[elem_pos] ^ mask; - p = _bitset_inside_ntz_value(elem); + p = ntz(elem); if (p < BITS_PER_ELEM) { return elem_pos * BITS_PER_ELEM + p; } } } +/** + * Returns the position of the next bit starting from (and including) + * a given position. + * + * @param bitset a bitset + * @param pos the first position to check + * @param last first position that is not checked anymore + * @param set if 0 search for unset bit, else for set bit + * + * @return the first position where a matched bit was found. + * (size_t)-1 if no bit was found. + */ +static inline size_t rbitset_next_max(const unsigned *bitset, size_t pos, + size_t last, bool set) +{ + size_t p; + size_t elem_pos = pos / BITS_PER_ELEM; + size_t bit_pos = pos % BITS_PER_ELEM; + + unsigned elem = bitset[elem_pos]; + unsigned mask = set ? 0u : ~0u; + size_t res = (size_t)-1; + + /* + * Mask out the bits smaller than pos in the current unit. + * We are only interested in bits set higher than pos. + */ + unsigned in_elem_mask = (1u << bit_pos) - 1; + + assert(pos < last); + + elem ^= mask; + p = ntz(elem & ~in_elem_mask); + + /* If there is a bit set in the current elem, exit. */ + if (p < BITS_PER_ELEM) { + res = elem_pos * BITS_PER_ELEM + p; + } else { + size_t n = BITSET_SIZE_ELEMS(last); + /* Else search for set bits in the next units. */ + for (elem_pos++; elem_pos < n; elem_pos++) { + elem = bitset[elem_pos] ^ mask; + + p = ntz(elem); + if (p < BITS_PER_ELEM) { + res = elem_pos * BITS_PER_ELEM + p; + break; + } + } + } + if (res >= last) + res = (size_t)-1; + + return res; +} + /** * Inplace Intersection of two sets. * * @param dst the destination bitset and first operand * @param src the second bitset - * @param size size of both bitsets + * @param size size of both bitsets in bits */ -static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size) +static inline void rbitset_and(unsigned *dst, const unsigned *src, size_t size) { - unsigned i, n = BITSET_SIZE_ELEMS(size); + size_t i, n = BITSET_SIZE_ELEMS(size); for (i = 0; i < n; ++i) { dst[i] &= src[i]; @@ -304,11 +372,11 @@ static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size * * @param dst the destination bitset and first operand * @param src the second bitset - * @param size size of both bitsets + * @param size size of both bitsets in bits */ -static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size) +static inline void rbitset_or(unsigned *dst, const unsigned *src, size_t size) { - unsigned i, n = BITSET_SIZE_ELEMS(size); + size_t i, n = BITSET_SIZE_ELEMS(size); for (i = 0; i < n; ++i) { dst[i] |= src[i]; @@ -320,11 +388,11 @@ static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size) * * @param dst the destination bitset and first operand * @param src the second bitset - * @param size size of both bitsets + * @param size size of both bitsets in bits */ -static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size) +static inline void rbitset_andnot(unsigned *dst, const unsigned *src, size_t size) { - unsigned i, n = BITSET_SIZE_ELEMS(size); + size_t i, n = BITSET_SIZE_ELEMS(size); for (i = 0; i < n; ++i) { dst[i] &= ~src[i]; @@ -336,28 +404,86 @@ static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned s * * @param dst the destination bitset and first operand * @param src the second bitset - * @param size size of both bitsets + * @param size size of both bitsets in bits */ -static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size) +static inline void rbitset_xor(unsigned *dst, const unsigned *src, size_t size) { - unsigned i, n = BITSET_SIZE_ELEMS(size); + size_t i, n = BITSET_SIZE_ELEMS(size); for (i = 0; i < n; ++i) { dst[i] ^= src[i]; } } +/** + * Set bits in a range to zero or one + * @param bitset the bitset + * @param from first bit to set + * @param to last bit (the first bit which is not set anymore) + * @param val wether to set to 1 or 0 + */ +static inline void rbitset_set_range(unsigned *bitset, size_t from, + size_t to, bool val) +{ + /* + * A small example (for cleaning bits in the same unit). + * from = 7 + * to = 19 + * do_set = 0 + * result: xxxxxxx000000000000xxxxxxxxxxxxx + * from_unit_mask: 00000001111111111111111111111111 + * to_unit_mask: 11111111111111111110000000000000 + * scale: 01234567890123456789012345678901 + * 1 2 3 + */ + + size_t from_bit = from % BITS_PER_ELEM; + size_t from_pos = from / BITS_PER_ELEM; + unsigned from_unit_mask = ~((1 << from_bit) - 1); + + size_t to_bit = to % BITS_PER_ELEM; + size_t to_pos = to / BITS_PER_ELEM; + unsigned to_unit_mask = (1 << to_bit) - 1; + + assert(from < to); + + /* do we want to set the bits in the range? */ + if (val) { + if (from_pos == to_pos) { + BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask; + } else { + size_t i; + BITSET_ELEM(bitset, from_pos) |= from_unit_mask; + BITSET_ELEM(bitset, to_pos) |= to_unit_mask; + for (i = from_pos + 1; i < to_pos; ++i) + BITSET_ELEM(bitset, i) = ~0u; + } + } else { + /* ... or clear them? */ + if (from_pos == to_pos) { + BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask); + } else { + size_t i; + BITSET_ELEM(bitset, from_pos) &= ~from_unit_mask; + BITSET_ELEM(bitset, to_pos) &= ~to_unit_mask; + for (i = from_pos + 1; i < to_pos; ++i) + BITSET_ELEM(bitset, i) = 0; + } + } +} + /** * Returns 1 of two bitsets are equal. * * @param bitset1 the first bitset * @param bitset2 the second bitset - * @param size size of both bitsets + * @param size size of both bitsets in bits */ -static inline int rbitset_equal(const unsigned *bitset1, - const unsigned *bitset2, size_t size) +static inline bool rbitsets_equal(const unsigned *bitset1, + const unsigned *bitset2, size_t size) { - return memcmp(bitset1, bitset2, BITSET_SIZE_BYTES(size)) == 0; + size_t size_bytes = BITSET_SIZE_BYTES(size); + return memcmp(bitset1, bitset2, size_bytes) == 0; } /** @@ -365,46 +491,81 @@ static inline int rbitset_equal(const unsigned *bitset1, * * @param bitset1 the first bitset * @param bitset2 the second bitset - * @param size size of both bitsets + * @param size size of both bitsets in bits */ -static inline int rbitsets_have_common(const unsigned *bitset1, - const unsigned *bitset2, size_t size) +static inline bool rbitsets_have_common(const unsigned *bitset1, + const unsigned *bitset2, size_t size) { - unsigned i; - unsigned n = BITSET_SIZE_ELEMS(size); + size_t i, n = BITSET_SIZE_ELEMS(size); for (i = 0; i < n; ++i) { if ((bitset1[i] & bitset2[i]) != 0) - return 1; + return true; } - return 0; + return false; } /** - * Copy a raw bitset into another. + * Tests wether all bits set in bitset1 are also set in bitset2. * - * @param dst the destination set - * @param src the source set - * @param size size of both bitsets + * @param bitset1 the first bitset + * @param bitset2 the second bitset + * @param size size of both bitsets in bits */ -static inline void rbitset_copy(unsigned *dst, const unsigned *src, size_t size) +static inline bool rbitset_contains(const unsigned *bitset1, + const unsigned *bitset2, size_t size) { - memcpy(dst, src, BITSET_SIZE_BYTES(size)); + size_t i, n = BITSET_SIZE_ELEMS(size); + + for (i = 0; i < n; ++i) { + if ((bitset1[i] & bitset2[i]) != bitset1[i]) + return false; + } + return true; } /** - * Copy a raw bitset into an bitset. - * - * @deprecated + * Treat the bitset as a number and subtract 1. + * @param bitset the bitset. + * @return size size of the bitset in bits */ -static inline void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) +static inline void rbitset_minus1(unsigned *bitset, size_t size) { - // TODO optimize me (or remove me) - unsigned i, n = bitset_size(bitset); + size_t i, n = BITSET_SIZE_ELEMS(size); + unsigned last_mask = rbitset_last_mask_(size); + for (i = 0; i < n; ++i) { - if (rbitset_is_set(rbitset, i)) - bitset_set(bitset, i); + unsigned mask = i == n-1 ? last_mask : ~0u; + unsigned val = bitset[i] & mask; + unsigned val_minus1 = val - 1; + bitset[i] = val_minus1 & mask; + + if (((val >> (BITS_PER_ELEM-1)) ^ (val_minus1 >> (BITS_PER_ELEM-1))) == 0) + break; } } -#endif /* FIRM_ADT_RAW_BITSET_H */ +/** + * Copy a raw bitset into another. + * + * @param dst the destination set + * @param src the source set + * @param size size of both bitsets in bits + */ +static inline void rbitset_copy(unsigned *dst, const unsigned *src, + size_t size) +{ + memcpy(dst, src, BITSET_SIZE_BYTES(size)); +} + +static inline void rbitset_copy_into(unsigned *dst, const unsigned *src, + size_t size) +{ + size_t n = BITSET_SIZE_ELEMS(size); + unsigned last_mask = rbitset_last_mask_(size); + + memcpy(dst, src, (n-1) * (BITS_PER_ELEM/8)); + dst[n-1] = (src[n-1] & last_mask) | (dst[n-1] & ~last_mask); +} + +#endif