/*
- * 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.
*
* @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
#include "bitset.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 { \
* 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);
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)
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));
}
* 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++;
}
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.
*/
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);
}
}
projects / libfirm / blobdiff