/*
- * 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 <assert.h>
#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 { \
* 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
*/
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
*/
return res;
}
+/**
+ * Check if a bitset is empty, ie all bits cleared.
+ */
+static INLINE int rbitset_is_empty(unsigned *bitset, unsigned size) {
+ unsigned i, size_bytes = BITSET_SIZE_BYTES(size);
+ for (i = 0; i < size_bytes; ++i)
+ if (bitset[i]) return 0;
+ return 1;
+}
+
/**
* Set a bit at position 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.
*
}
}
+static INLINE int rbitset_equal(const unsigned *bitset1,
+ const unsigned *bitset2, size_t size)
+{
+ unsigned i, n = BITSET_SIZE_ELEMS(size);
+
+ for(i = 0; i < n; ++i) {
+ if(bitset1[i] != bitset2[i])
+ return 0;
+ }
+ return 1;
+}
+
/**
* Copy a raw bitset into an bitset.
*