X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=include%2Flibfirm%2Fadt%2Fraw_bitset.h;h=1426b137a08a6b6131bbe77e694abbc803b92fbb;hb=fc906bb2542111be7aa6cfd082f86a84d43f03b4;hp=ca4761bdb837a4fdb055021a6d218c8db5580396;hpb=99d90ebc8ef32273dac2d27b9aa9e30ebd6c2c80;p=libfirm

diff --git a/include/libfirm/adt/raw_bitset.h b/include/libfirm/adt/raw_bitset.h
index ca4761bdb..1426b137a 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
@@ -44,16 +44,34 @@
 #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 { \
@@ -66,7 +84,7 @@ 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
  */
@@ -78,12 +96,34 @@ 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
  */
@@ -99,6 +139,16 @@ 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 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.
  *
@@ -119,6 +169,17 @@ 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.
  *
@@ -239,6 +300,18 @@ static INLINE void rbitset_xor(unsigned *bitset1, const unsigned *bitset2,
 	}
 }
 
+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.
  *