X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=include%2Flibfirm%2Fadt%2Fraw_bitset.h;h=f6fddd9f74fd227081928aff6b4fc44a82a0b4c2;hb=fa5ab873b17e738215efcdc1cfe08fdfe4103bf9;hp=3a5bfd683aa42cbf25d20cc06c6abfd7302f51a9;hpb=435253f3a8766fec2ac2adf559bb10cfcb5d36f4;p=libfirm diff --git a/include/libfirm/adt/raw_bitset.h b/include/libfirm/adt/raw_bitset.h index 3a5bfd683..f6fddd9f7 100644 --- a/include/libfirm/adt/raw_bitset.h +++ b/include/libfirm/adt/raw_bitset.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -24,8 +24,8 @@ * @author Matthias Braun * @version $Id$ * @summary - * Raw bitsets are constructed from int arrays. Additional information - * like the size of the bitset or the used memory aren't saved for + * 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. * * These bitsets need less space than bitset_t and their representation @@ -42,19 +42,36 @@ #include #include "bitset.h" -#include "bitset_std.h" #include "obst.h" -#define BITS_PER_ELEM 32 -#define BITSET_SIZE_ELEMS(size_bits) ((size_bits)/32 + 1) -#define BITSET_SIZE_BYTES(size_bits) (BITSET_SIZE_ELEMS(size_bits)*4) -#define BITSET_ELEM(bitset,pos) bitset[pos / 32] +/** 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] + +/** + * Allocate an empty raw bitset on the heap. + * + * @param size number of bits in the bitset + * + * @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; +} /** * Allocate an empty raw bitset on the stack. * * @param res will contain the newly allocated bitset - * @param size element size of the bitset + * @param size number of bits in the bitset */ #define rbitset_alloca(res, size) \ do { \ @@ -67,11 +84,12 @@ do { \ * Allocate an empty raw bitset on an obstack. * * @param obst the obstack where the bitset is allocated on - * @param size element size of the bitset + * @param size number of bits in the bitset * * @return the new bitset */ -static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size) { +static inline unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned size) +{ unsigned size_bytes = BITSET_SIZE_BYTES(size); unsigned *res = obstack_alloc(obst, size_bytes); memset(res, 0, size_bytes); @@ -79,16 +97,39 @@ static INLINE unsigned *rbitset_obstack_alloc(struct obstack *obst, unsigned siz return res; } +/** + * 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. * * @param obst the obstack where the bitset is allocated on * @param old_bitset the bitset to be duplicated - * @param size element size of the bitset + * @param size number of bits in the bitset * * @return the new bitset */ -static INLINE +static inline unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst, const unsigned *old_bitset, unsigned size) @@ -100,33 +141,75 @@ unsigned *rbitset_duplicate_obstack_alloc(struct obstack *obst, return res; } +/** + * Check if a bitset is empty, ie all bits cleared. + */ +static inline int rbitset_is_empty(unsigned *bitset, unsigned size) +{ + unsigned size_bytes = BITSET_SIZE_ELEMS(size); + unsigned i; + for (i = 0; i < size_bytes; ++i) + if (bitset[i] != 0) + return 0; + + return 1; +} + /** * Set a bit at position pos. * * @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, unsigned pos) +{ BITSET_ELEM(bitset,pos) |= 1 << (pos % BITS_PER_ELEM); } +/** + * 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) +{ + unsigned size_bytes = BITSET_SIZE_BYTES(size); + memset(bitset, ~0, size_bytes); +} + + /** * Clear a bit at position pos. * * @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, unsigned pos) +{ BITSET_ELEM(bitset, pos) &= ~(1 << (pos % BITS_PER_ELEM)); } +/** + * Clear all bits in a given bitset. + * + * @param bitset the bitset + * @param size number of bits in the bitset + */ +static inline void rbitset_clear_all(unsigned *bitset, unsigned size) +{ + unsigned size_bytes = BITSET_SIZE_BYTES(size); + memset(bitset, 0, size_bytes); +} + /** * 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 int rbitset_is_set(const unsigned *bitset, unsigned pos) +{ return BITSET_ELEM(bitset, pos) & (1 << (pos % BITS_PER_ELEM)); } @@ -134,14 +217,16 @@ static INLINE int rbitset_is_set(const unsigned *bitset, unsigned pos) { * Calculate the number of set bits (number of elements). * * @param bitset the bitset + * @param size size of the bitset */ -static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) { +static inline unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) +{ unsigned pos; unsigned n = BITSET_SIZE_ELEMS(size); unsigned res = 0; const unsigned *elem = bitset; - for(pos = 0; pos < n; ++pos) { + for (pos = 0; pos < n; ++pos) { res += _bitset_inside_pop(elem); elem++; } @@ -149,12 +234,27 @@ static INLINE unsigned rbitset_popcnt(const unsigned *bitset, unsigned size) { return res; } -static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int set) { +/** + * 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 set if 0 search for unset bit, else for set bit + * + * @return the first position where a matched bit was found + * + * @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) +{ unsigned p; unsigned elem_pos = pos / BITS_PER_ELEM; unsigned bit_pos = pos % BITS_PER_ELEM; unsigned elem = bitset[elem_pos]; + unsigned mask = 0; /* * Mask out the bits smaller than pos in the current unit. @@ -162,94 +262,148 @@ static INLINE unsigned rbitset_next(const unsigned *bitset, unsigned pos, int se */ unsigned in_elem_mask = (1 << bit_pos) - 1; - if(!set) - elem = ~elem; + if (!set) + mask = ~mask; + elem ^= mask; p = _bitset_inside_ntz_value(elem & ~in_elem_mask); /* If there is a bit set in the current elem, exit. */ - if(p < BITS_PER_ELEM) { + if (p < BITS_PER_ELEM) { return elem_pos * BITS_PER_ELEM + p; } /* Else search for set bits in the next units. */ - while(1) { + while (1) { elem_pos++; - elem = bitset[elem_pos]; - if(!set) - elem = ~elem; + elem = bitset[elem_pos] ^ mask; p = _bitset_inside_ntz_value(elem); - if(p < BITS_PER_ELEM) { + if (p < BITS_PER_ELEM) { return elem_pos * BITS_PER_ELEM + p; } } - - assert(0); - return 0xdeadbeef; } /** * Inplace Intersection of two sets. + * + * @param dst the destination bitset and first operand + * @param src the second bitset + * @param size size of both bitsets */ -static INLINE void rbitset_and(unsigned *bitset1, const unsigned *bitset2, - unsigned size) +static inline void rbitset_and(unsigned *dst, const unsigned *src, unsigned size) { unsigned i, n = BITSET_SIZE_ELEMS(size); - for(i = 0; i < n; ++i) { - bitset1[i] &= bitset2[i]; + for (i = 0; i < n; ++i) { + dst[i] &= src[i]; } } /** * Inplace Union of two sets. + * + * @param dst the destination bitset and first operand + * @param src the second bitset + * @param size size of both bitsets */ -static INLINE void rbitset_or(unsigned *bitset1, const unsigned *bitset2, - unsigned size) +static inline void rbitset_or(unsigned *dst, const unsigned *src, unsigned size) { unsigned i, n = BITSET_SIZE_ELEMS(size); - for(i = 0; i < n; ++i) { - bitset1[i] |= bitset2[i]; + for (i = 0; i < n; ++i) { + dst[i] |= src[i]; } } /** - * Remove all bits in bitset2 from bitset 1. + * Remove all bits in src from dst. + * + * @param dst the destination bitset and first operand + * @param src the second bitset + * @param size size of both bitsets */ -static INLINE void rbitset_andnot(unsigned *bitset1, const unsigned *bitset2, - unsigned size) +static inline void rbitset_andnot(unsigned *dst, const unsigned *src, unsigned size) { unsigned i, n = BITSET_SIZE_ELEMS(size); - for(i = 0; i < n; ++i) { - bitset1[i] &= ~bitset2[i]; + for (i = 0; i < n; ++i) { + dst[i] &= ~src[i]; } } /** * Xor of two bitsets. + * + * @param dst the destination bitset and first operand + * @param src the second bitset + * @param size size of both bitsets */ -static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2, - unsigned size) +static inline void rbitset_xor(unsigned *dst, const unsigned *src, unsigned size) { unsigned i, n = BITSET_SIZE_ELEMS(size); - for(i = 0; i < n; ++i) { - bitset1[i] ^= bitset2[i]; + for (i = 0; i < n; ++i) { + dst[i] ^= src[i]; } } +/** + * Returns 1 of two bitsets are equal. + * + * @param bitset1 the first bitset + * @param bitset2 the second bitset + * @param size size of both bitsets + */ +static inline int rbitset_equal(const unsigned *bitset1, + const unsigned *bitset2, size_t size) +{ + return memcmp(bitset1, bitset2, BITSET_SIZE_BYTES(size)) == 0; +} + +/** + * Tests wether 2 bitsets wether at least 1 bit is set in both. + * + * @param bitset1 the first bitset + * @param bitset2 the second bitset + * @param size size of both bitsets + */ +static inline int rbitsets_have_common(const unsigned *bitset1, + const unsigned *bitset2, size_t size) +{ + unsigned i; + unsigned n = BITSET_SIZE_ELEMS(size); + + for (i = 0; i < n; ++i) { + if ((bitset1[i] & bitset2[i]) != 0) + return 1; + } + return 0; +} + +/** + * Copy a raw bitset into another. + * + * @param dst the destination set + * @param src the source set + * @param size size of both bitsets + */ +static inline void rbitset_copy(unsigned *dst, const unsigned *src, size_t size) +{ + memcpy(dst, src, BITSET_SIZE_BYTES(size)); +} + /** * Copy a raw bitset into an bitset. * * @deprecated */ -static INLINE void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) { +static inline void rbitset_copy_to_bitset(const unsigned *rbitset, bitset_t *bitset) +{ // TODO optimize me (or remove me) unsigned i, n = bitset_size(bitset); - for(i = 0; i < n; ++i) { - if(rbitset_is_set(rbitset, i)) + for (i = 0; i < n; ++i) { + if (rbitset_is_set(rbitset, i)) bitset_set(bitset, i); } }