/*
- * 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.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
* @brief raw bitsets (low-level bitset operations)
* @date 15.10.2004
* @author Matthias Braun
- * @version $Id$
*
* Raw bitsets are constructed from unsigned int arrays. Additional
* information like the size of the bitset or the used memory are not
*
* @return the new bitset
*/
-static inline unsigned *rbitset_malloc(unsigned size)
+static inline unsigned *rbitset_malloc(size_t size)
{
- unsigned size_bytes = BITSET_SIZE_BYTES(size);
- unsigned *res = xmalloc(size_bytes);
- memset(res, 0, size_bytes);
-
- return res;
+ return XMALLOCNZ(unsigned, BITSET_SIZE_ELEMS(size));
}
/**
* Allocate an empty raw bitset on the stack.
*
- * @param res will contain the newly allocated bitset
* @param size number of bits in the bitset
*/
-#define rbitset_alloca(res, size) \
-do { \
- unsigned size_bytes = BITSET_SIZE_BYTES(size); \
- res = alloca(size_bytes); \
- memset(res, 0, size_bytes); \
-} while(0)
+#define rbitset_alloca(size) \
+ ((unsigned*)memset(alloca(BITSET_SIZE_BYTES(size)), 0, BITSET_SIZE_BYTES(size)))
/**
* Allocate an empty raw bitset on an obstack.
* @return the new bitset
*/
static inline unsigned *rbitset_obstack_alloc(struct obstack *obst,
- unsigned size)
+ 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.
*
* @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;
/**
* Check if a bitset is empty, ie all bits cleared.
*/
-static inline bool rbitset_is_empty(const unsigned *bitset, unsigned size)
+static inline bool rbitset_is_empty(const unsigned *bitset, size_t size)
{
- unsigned i;
- unsigned n = BITSET_SIZE_ELEMS(size);
+ size_t i;
+ size_t n = BITSET_SIZE_ELEMS(size);
for (i = 0; i < n; ++i) {
if (bitset[i] != 0) {
* @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);
}
* @param bitset the bitset
* @param pos position of the bit to be flipped
*/
-static inline void rbitset_flip(unsigned *bitset, unsigned pos)
+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_(unsigned size)
+static inline unsigned rbitset_last_mask_(size_t size)
{
- unsigned p;
+ size_t p;
if (size == 0)
return 0;
p = size % BITS_PER_ELEM;
* @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 i;
- unsigned n = BITSET_SIZE_ELEMS(size);
+ size_t i;
+ size_t n = BITSET_SIZE_ELEMS(size);
if (n == 0)
return;
* @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));
}
* @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);
}
* @param bitset the bitset
* @param size number of bits in the bitset
*/
-static inline void rbitset_flip_all(unsigned *bitset, unsigned size)
+static inline void rbitset_flip_all(unsigned *bitset, size_t size)
{
- unsigned pos;
- unsigned n = BITSET_SIZE_ELEMS(size);
+ size_t pos;
+ size_t n = BITSET_SIZE_ELEMS(size);
if (n == 0)
return;
* @param bitset the bitset
* @param pos the position of the bit to check
*/
-static inline bool 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;
}
/**
* @param bitset the bitset
* @param size size of the bitset in bits
*/
-static inline unsigned rbitset_popcount(const unsigned *bitset, unsigned size)
+static inline size_t rbitset_popcount(const unsigned *bitset, size_t size)
{
- unsigned i;
- unsigned n = BITSET_SIZE_ELEMS(size);
- unsigned res = 0;
+ size_t i, n = BITSET_SIZE_ELEMS(size);
+ size_t res = 0;
for (i = 0; i < n; ++i) {
res += popcount(bitset[i]);
* @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,
- bool 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 = set ? 0 : ~0u;
* @param set if 0 search for unset bit, else for set bit
*
* @return the first position where a matched bit was found.
- * (unsigned)-1 if no bit was found.
+ * (size_t)-1 if no bit was found.
*/
-static inline unsigned rbitset_next_max(const unsigned *bitset, unsigned pos,
- unsigned last, bool set)
+static inline size_t rbitset_next_max(const unsigned *bitset, size_t pos,
+ size_t last, bool set)
{
- unsigned p;
- unsigned elem_pos = pos / BITS_PER_ELEM;
- unsigned bit_pos = pos % BITS_PER_ELEM;
+ assert(pos <= last);
+ if (pos == last)
+ return (size_t)-1;
+
+ 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 ? 0 : ~0u;
- unsigned res = (unsigned)-1;
+ 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 = (1 << bit_pos) - 1;
-
- assert(pos < last);
+ unsigned in_elem_mask = (1u << bit_pos) - 1;
elem ^= mask;
p = ntz(elem & ~in_elem_mask);
if (p < BITS_PER_ELEM) {
res = elem_pos * BITS_PER_ELEM + p;
} else {
- unsigned n = BITSET_SIZE_ELEMS(last);
+ 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;
}
}
if (res >= last)
- res = (unsigned)-1;
+ res = (size_t)-1;
return res;
}
* @param src the second bitset
* @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];
* @param src the second bitset
* @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];
* @param src the second bitset
* @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];
* @param src the second bitset
* @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];
* @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
+ * @param val whether to set to 1 or 0
*/
-static inline void rbitset_set_range(unsigned *bitset, unsigned from,
- unsigned to, bool val)
+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).
* 1 2 3
*/
- unsigned from_bit = from % BITS_PER_ELEM;
- unsigned from_pos = from / BITS_PER_ELEM;
+ size_t from_bit = from % BITS_PER_ELEM;
+ size_t from_pos = from / BITS_PER_ELEM;
unsigned from_unit_mask = ~((1 << from_bit) - 1);
- unsigned to_bit = to % BITS_PER_ELEM;
- unsigned to_pos = to / BITS_PER_ELEM;
- unsigned to_unit_mask = (1 << to_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);
if (from_pos == to_pos) {
BITSET_ELEM(bitset, from_pos) |= from_unit_mask & to_unit_mask;
} else {
- unsigned i;
+ 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)
if (from_pos == to_pos) {
BITSET_ELEM(bitset, from_pos) &= ~(from_unit_mask & to_unit_mask);
} else {
- unsigned i;
+ 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)
* @param size size of both bitsets in bits
*/
static inline bool rbitsets_equal(const unsigned *bitset1,
- const unsigned *bitset2, unsigned size)
+ const unsigned *bitset2, size_t size)
{
- unsigned size_bytes = BITSET_SIZE_BYTES(size);
+ size_t size_bytes = BITSET_SIZE_BYTES(size);
return memcmp(bitset1, bitset2, size_bytes) == 0;
}
/**
- * Tests wether 2 bitsets wether at least 1 bit is set in both.
+ * Tests whether 2 bitsets have at least one common set bit.
*
* @param bitset1 the first bitset
* @param bitset2 the second bitset
* @param size size of both bitsets in bits
*/
static inline bool rbitsets_have_common(const unsigned *bitset1,
- const unsigned *bitset2, unsigned size)
+ 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)
}
/**
- * Tests wether all bits set in bitset1 are also set in bitset2.
+ * Tests whether all bits set in bitset1 are also set in bitset2.
*
* @param bitset1 the first bitset
* @param bitset2 the second bitset
* @param size size of both bitsets in bits
*/
static inline bool rbitset_contains(const unsigned *bitset1,
- const unsigned *bitset2, unsigned size)
+ 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]) != bitset1[i])
* @param bitset the bitset.
* @return size size of the bitset in bits
*/
-static inline void rbitset_minus1(unsigned *bitset, unsigned size)
+static inline void rbitset_minus1(unsigned *bitset, size_t size)
{
- unsigned i;
- unsigned n = BITSET_SIZE_ELEMS(size);
+ size_t i, n = BITSET_SIZE_ELEMS(size);
unsigned last_mask = rbitset_last_mask_(size);
for (i = 0; i < n; ++i) {
* @param size size of both bitsets in bits
*/
static inline void rbitset_copy(unsigned *dst, const unsigned *src,
- unsigned size)
+ size_t size)
{
memcpy(dst, src, BITSET_SIZE_BYTES(size));
}
static inline void rbitset_copy_into(unsigned *dst, const unsigned *src,
- unsigned size)
+ size_t size)
{
- unsigned n = BITSET_SIZE_ELEMS(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);
}
+/**
+ * Convenience macro for raw bitset iteration.
+ * @param bitset The bitset.
+ * @param size Size of the bitset.
+ * @param elm A size_t variable.
+ */
+#define rbitset_foreach(bitset, size, elm) \
+ for (size_t elm = 0; (elm = rbitset_next_max((bitset), elm, size, 1)) != (size_t)-1; ++elm)
+
+/**
+ * Convenience macro for raw bitset iteration.
+ * @param bitset The bitset.
+ * @param size Size of the bitset.
+ * @param elm A size_t variable.
+ */
+#define rbitset_foreach_clear(bitset, size, elm) \
+ for (size_t elm = 0; (elm = rbitset_next_max((bitset), elm, size, 0)) != (size_t)-1; ++elm)
+
#endif
projects / libfirm / blobdiff