X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fbitset.h;h=62f44f9a5116357b7a059c63df6e008574a96376;hb=e788b4026fcd2d87cf70cd6b117f415399e7883e;hp=0a7ad4bc2e08c85b1060cedf45af9301bf3a90be;hpb=d0da4b10666196a66db30e84b9c19428490bf802;p=libfirm

diff --git a/ir/adt/bitset.h b/ir/adt/bitset.h
index 0a7ad4bc2..62f44f9a5 100644
--- a/ir/adt/bitset.h
+++ b/ir/adt/bitset.h
@@ -16,6 +16,8 @@
 #include "firm_config.h"
 #include "bitfiddle.h"
 
+typedef unsigned int bitset_pos_t;
+
 #include "bitset_std.h"
 
 /*
@@ -25,11 +27,12 @@
 */
 
 typedef struct _bitset_t {
-	unsigned long units;
-	unsigned long *data;
+	bitset_pos_t units;
+  bitset_pos_t size;
+	bitset_unit_t *data;
 } bitset_t;
 
-#define BS_UNIT_SIZE sizeof(unsigned long)
+#define BS_UNIT_SIZE sizeof(bitset_unit_t)
 #define BS_UNIT_SIZE_BITS (BS_UNIT_SIZE * 8)
 #define BS_UNIT_MASK (BS_UNIT_SIZE_BITS - 1)
 
@@ -39,28 +42,41 @@ typedef struct _bitset_t {
  *
  * Note that this function needs three macros which must be provided by the
  * bitfield implementor:
- * - _bitset_overall_size(highest_bit) The overall size that must be
+ * - _bitset_overall_size(size) The overall size that must be
  *   allocated for the bitfield in bytes.
- * - _bitset_units(highest_bit) The number of units that will be
+ * - _bitset_units(size) The number of units that will be
  *   present in the bitfield for a given highest bit.
- * - _bitset_data_ptr(data, highest_bit) This produces as pointer to the
+ * - _bitset_data_ptr(data, size) This produces as pointer to the
  *   first unit in the allocated memory area. The main reason for this
  *   macro is, that some bitset implementors want control over memory
  *   alignment.
  *
  * @param area A pointer to memory reserved for the bitset.
- * @param units The number of units that are allocated for the bitset.
+ * @param size The size of the bitset in bits.
  * @return A pointer to the initialized bitset.
  */
-static INLINE bitset_t *_bitset_prepare(void *area, unsigned long highest_bit)
+static INLINE bitset_t *_bitset_prepare(void *area, bitset_pos_t size)
 {
 	bitset_t *ptr = area;
-	memset(area, 0, _bitset_overall_size(sizeof(bitset_t), highest_bit));
-	ptr->units = _bitset_units(highest_bit);
-	ptr->data = _bitset_data_ptr(area, sizeof(bitset_t), highest_bit);
+	memset(area, 0, _bitset_overall_size(sizeof(bitset_t), size));
+	ptr->units = _bitset_units(size);
+  ptr->size = size;
+	ptr->data = _bitset_data_ptr(area, sizeof(bitset_t), size);
 	return ptr;
 }
 
+/**
+ * Mask out all bits, which are only there, because the number
+ * of bits in the set didn't match a unit size boundary.
+ * @param bs The bitset.
+ * @return The masked bitset.
+ */
+static INLINE bitset_t *_bitset_mask_highest(bitset_t *bs)
+{
+  bs->data[bs->units - 1] &= (bs->size & BS_UNIT_MASK) - 1;
+  return bs;
+}
+
 /**
  * Get the capacity of the bitset in bits.
  * @param bs The bitset.
@@ -68,22 +84,30 @@ static INLINE bitset_t *_bitset_prepare(void *area, unsigned long highest_bit)
  */
 #define bitset_capacity(bs) ((bs)->units * BS_UNIT_SIZE_BITS)
 
+/**
+ * Get the size of the bitset in bits.
+ * @note Note the difference between capacity and size.
+ * @param bs The bitset.
+ * @return The highest bit which can be set or cleared plus 1.
+ */
+#define bistet_size(bs)  ((bs)->size)
+
 /**
  * Allocate a bitset on an obstack.
  * @param obst The obstack.
- * @param highest_bit The greatest bit that shall be stored in the set.
+ * @param size The greatest bit that shall be stored in the set.
  * @return A pointer to an empty initialized bitset.
  */
-#define bitset_obstack_alloc(obst,highest_bit) \
-  _bitset_prepare(obstack_alloc(obst, _bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit)
+#define bitset_obstack_alloc(obst,size) \
+  _bitset_prepare(obstack_alloc(obst, _bitset_overall_size(sizeof(bitset_t), size)), size)
 
 /**
  * Allocate a bitset via malloc.
- * @param highest_bit The greatest bit that shall be stored in the set.
+ * @param size The greatest bit that shall be stored in the set.
  * @return A pointer to an empty initialized bitset.
  */
-#define bitset_malloc(highest_bit) \
-	_bitset_prepare(malloc(_bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit)
+#define bitset_malloc(size) \
+	_bitset_prepare(malloc(_bitset_overall_size(sizeof(bitset_t), size)), size)
 
 /**
  * Free a bitset allocated with bitset_malloc().
@@ -93,11 +117,11 @@ static INLINE bitset_t *_bitset_prepare(void *area, unsigned long highest_bit)
 
 /**
  * Allocate a bitset on the stack via alloca.
- * @param highest_bit The greatest bit that shall be stored in the set.
+ * @param size The greatest bit that shall be stored in the set.
  * @return A pointer to an empty initialized bitset.
  */
-#define bitset_alloca(highest_bit) \
-	_bitset_prepare(alloca(_bitset_overall_size(sizeof(bitset_t), highest_bit)), highest_bit)
+#define bitset_alloca(size) \
+	_bitset_prepare(alloca(_bitset_overall_size(sizeof(bitset_t), size)), size)
 
 
 /**
@@ -107,9 +131,10 @@ static INLINE bitset_t *_bitset_prepare(void *area, unsigned long highest_bit)
  * @param bit The bit.
  * @return A pointer to the unit containing the bit.
  */
-static INLINE unsigned long *_bitset_get_unit(const bitset_t *bs, unsigned long bit)
+static INLINE bitset_unit_t *_bitset_get_unit(const bitset_t *bs, bitset_pos_t bit)
 {
-	assert(bit < bs->units * BS_UNIT_SIZE_BITS && "Bit too large");
+	/* assert(bit < bs->units * BS_UNIT_SIZE_BITS && "Bit too large"); */
+  assert(bit <= bs->size && "Bit to large");
 	return bs->data + bit / BS_UNIT_SIZE_BITS;
 }
 
@@ -118,9 +143,9 @@ static INLINE unsigned long *_bitset_get_unit(const bitset_t *bs, unsigned long
  * @param bs The bitset.
  * @param bit The bit to set.
  */
-static INLINE void bitset_set(bitset_t *bs, unsigned long bit)
+static INLINE void bitset_set(bitset_t *bs, bitset_pos_t bit)
 {
-	unsigned long *unit = _bitset_get_unit(bs, bit);
+	bitset_unit_t *unit = _bitset_get_unit(bs, bit);
 	_bitset_inside_set(unit, bit & BS_UNIT_MASK);
 }
 
@@ -129,15 +154,21 @@ static INLINE void bitset_set(bitset_t *bs, unsigned long bit)
  * @param bs The bitset.
  * @param bit The bit to clear.
  */
-static INLINE void bitset_clear(bitset_t *bs, unsigned long bit)
+static INLINE void bitset_clear(bitset_t *bs, bitset_pos_t bit)
 {
-	unsigned long *unit = _bitset_get_unit(bs, bit);
+	bitset_unit_t *unit = _bitset_get_unit(bs, bit);
 	_bitset_inside_clear(unit, bit & BS_UNIT_MASK);
 }
 
-static INLINE int bitset_is_set(const bitset_t *bs, unsigned long bit)
+/**
+ * Check, if a bit is set.
+ * @param bs The bitset.
+ * @param bit The bit to check for.
+ * @return 1, if the bit was set, 0 if not.
+ */
+static INLINE int bitset_is_set(const bitset_t *bs, bitset_pos_t bit)
 {
-	unsigned long *unit = _bitset_get_unit(bs, bit);
+	bitset_unit_t *unit = _bitset_get_unit(bs, bit);
 	return _bitset_inside_is_set(unit, bit & BS_UNIT_MASK);
 }
 
@@ -146,9 +177,9 @@ static INLINE int bitset_is_set(const bitset_t *bs, unsigned long bit)
  * @param bs The bitset.
  * @param bit The bit to flip.
  */
-static INLINE void bitset_flip(bitset_t *bs, unsigned long bit)
+static INLINE void bitset_flip(bitset_t *bs, bitset_pos_t bit)
 {
-	unsigned long *unit = _bitset_get_unit(bs, bit);
+	bitset_unit_t *unit = _bitset_get_unit(bs, bit);
 	_bitset_inside_flip(unit, bit & BS_UNIT_MASK);
 }
 
@@ -160,13 +191,13 @@ static INLINE void bitset_flip(bitset_t *bs, unsigned long bit)
  */
 static INLINE bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src)
 {
-	unsigned long tu = tgt->units;
-	unsigned long su = src->units;
-	unsigned long min_units = tu < su ? tu : su;
+	bitset_pos_t tu = tgt->units;
+	bitset_pos_t su = src->units;
+	bitset_pos_t min_units = tu < su ? tu : su;
 	memcpy(tgt->data, src->data, min_units * BS_UNIT_SIZE);
 	if(tu > min_units)
 		memset(tgt->data + min_units, 0, BS_UNIT_SIZE * (tu - min_units));
-	return tgt;
+	return _bitset_mask_highest(tgt);
 }
 
 /**
@@ -174,13 +205,13 @@ static INLINE bitset_t *bitset_copy(bitset_t *tgt, const bitset_t *src)
  * @param bs The bitset.
  * @return The smallest bit set in the bitset.
  */
-static INLINE unsigned long bitset_min(const bitset_t *bs)
+static INLINE bitset_pos_t bitset_min(const bitset_t *bs)
 {
-	unsigned long i, ofs = 0;
+	bitset_pos_t i, ofs = 0;
 
 	for(i = 0; i < bs->units; ++i) {
-		unsigned long *unit = &bs->data[i];
-		unsigned long pos = _bitset_inside_ntz(unit);
+		bitset_unit_t *unit = &bs->data[i];
+		bitset_pos_t pos = _bitset_inside_ntz(unit);
 		if(pos > 0)
 			return ofs + pos;
 		ofs += BS_UNIT_SIZE_BITS;
@@ -194,13 +225,13 @@ static INLINE unsigned long bitset_min(const bitset_t *bs)
  * @param bs The bitset.
  * @return The greatest bit set in the bitset.
  */
-static INLINE unsigned long bitset_max(const bitset_t *bs)
+static INLINE bitset_pos_t bitset_max(const bitset_t *bs)
 {
-	unsigned long i, max = 0, ofs = 0;
+	bitset_pos_t i, max = 0, ofs = 0;
 
 	for(i = 0; i < bs->units; ++i) {
-		unsigned long *unit = &bs->data[i];
-		unsigned long pos = _bitset_inside_nlz(unit);
+		bitset_unit_t *unit = &bs->data[i];
+		bitset_pos_t pos = _bitset_inside_nlz(unit);
 		if(pos > 0)
 			max = ofs + pos;
 		ofs += BS_UNIT_SIZE_BITS;
@@ -214,30 +245,35 @@ static INLINE unsigned long bitset_max(const bitset_t *bs)
  * @note Note that if pos is set, pos is returned.
  * @param bs The bitset.
  * @param pos The bit from which to search for the next set bit.
+ * @param set if 1, serach for set bits, else for unset bits
  * @return The next set bit from pos on, or -1, if no set bit was found
  * after pos.
  */
-static INLINE unsigned long _bitset_next(const bitset_t *bs,
-		unsigned long pos, int set)
+static INLINE bitset_pos_t _bitset_next(const bitset_t *bs,
+		bitset_pos_t pos, int set)
 {
-	unsigned long unit_number = pos / BS_UNIT_SIZE_BITS;
+	bitset_pos_t unit_number = pos / BS_UNIT_SIZE_BITS;
 
 	if(unit_number >= bs->units)
 		return -1;
 
 	{
-		unsigned long bit_in_unit = pos & BS_UNIT_MASK;
-		unsigned long in_unit_mask = (1 << bit_in_unit) - 1;
+		bitset_pos_t bit_in_unit = pos & BS_UNIT_MASK;
+		bitset_pos_t in_unit_mask = (1 << bit_in_unit) - 1;
 
 		/*
 		 * Mask out the bits smaller than pos in the current unit.
 		 * We are only interested in bits set higher than pos.
 		 */
-		unsigned long curr_unit = bs->data[unit_number] & ~in_unit_mask;
+		bitset_unit_t curr_unit = bs->data[unit_number];
 
-		/* Find the next bit set in the unit. */
-		unsigned long next_in_this_unit
-			= _bitset_inside_ntz_value(set ? curr_unit : ~curr_unit);
+		/*
+		 * Find the next bit set in the unit.
+		 * Mind that this function returns 0, if the unit is -1 and
+		 * counts the bits from 1 on.
+		 */
+		bitset_pos_t next_in_this_unit =
+			_bitset_inside_ntz_value((set ? curr_unit : ~curr_unit) & ~in_unit_mask);
 
 		/* If there is a bit set in the current unit, exit. */
 		if(next_in_this_unit < BS_UNIT_SIZE_BITS)
@@ -245,10 +281,12 @@ static INLINE unsigned long _bitset_next(const bitset_t *bs,
 
 		/* Else search for set bits in the next units. */
 		else {
-			unsigned long i;
+			bitset_pos_t i;
 			for(i = unit_number + 1; i < bs->units; ++i) {
-				unsigned long data = bs->data[i];
-				unsigned long first_set = _bitset_inside_ntz_value(set ? data : ~data);
+				bitset_unit_t data = bs->data[i];
+				bitset_pos_t first_set =
+					_bitset_inside_ntz_value(set ? data : ~data);
+
 				if(first_set < BS_UNIT_SIZE_BITS)
 					return first_set + i * BS_UNIT_SIZE_BITS;
 			}
@@ -269,16 +307,20 @@ static INLINE unsigned long _bitset_next(const bitset_t *bs,
 #define bitset_foreach(bitset,elm) \
   for(elm = bitset_next_set(bitset,0); elm != -1; elm = bitset_next_set(bitset,elm+1))
 
+
+#define bitset_foreach_clear(bitset,elm) \
+  for(elm = bitset_next_clear(bitset,0); elm != -1; elm = bitset_next_clear(bitset,elm+1))
+
 /**
  * Count the bits set.
  * This can also be seen as the cardinality of the set.
  * @param bs The bitset.
  * @return The number of bits set in the bitset.
  */
-static INLINE unsigned long bitset_popcnt(const bitset_t *bs)
+static INLINE bitset_pos_t bitset_popcnt(const bitset_t *bs)
 {
-	unsigned long i, pop = 0;
-	unsigned long *unit;
+	bitset_pos_t i, pop = 0;
+	bitset_unit_t *unit;
 
 	for(i = 0, unit = bs->data; i < bs->units; ++i, ++unit)
 		pop += _bitset_inside_pop(unit);
@@ -291,9 +333,21 @@ static INLINE unsigned long bitset_popcnt(const bitset_t *bs)
  * This sets all bits to zero.
  * @param bs The bitset.
  */
-static INLINE void bitset_clear_all(bitset_t *bs)
+static INLINE bitset_t *bitset_clear_all(bitset_t *bs)
 {
 	memset(bs->data, 0, BS_UNIT_SIZE * bs->units);
+  return bs;
+}
+
+/**
+ * Set the bitset.
+ * This sets all bits to one.
+ * @param bs The bitset.
+ */
+static INLINE bitset_t *bitset_set_all(bitset_t *bs)
+{
+	memset(bs->data, -1, BS_UNIT_SIZE * bs->units);
+  return bs;
 }
 
 /**
@@ -305,12 +359,12 @@ static INLINE void bitset_clear_all(bitset_t *bs)
  */
 static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
 {
-	unsigned long n = lhs->units < rhs->units ? lhs->units : rhs->units;
-	unsigned long i;
+	bitset_pos_t n = lhs->units < rhs->units ? lhs->units : rhs->units;
+	bitset_pos_t i;
 
 	for(i = 0; i < n; ++i) {
-		unsigned long lu = lhs->data[i];
-		unsigned long ru = rhs->data[i];
+		bitset_unit_t lu = lhs->data[i];
+		bitset_unit_t ru = rhs->data[i];
 
 		if((lu | ru) & ~ru)
 			return 0;
@@ -351,11 +405,11 @@ static INLINE void bitset_fprint(FILE *file, const bitset_t *bs)
 
 static INLINE void bitset_debug_fprint(FILE *file, const bitset_t *bs)
 {
-	int i;
+	bitset_pos_t i;
 
-	fprintf(file, "%d:", bs->units);
+	fprintf(file, "%u:", bs->units);
 	for(i = 0; i < bs->units; ++i)
-		fprintf(file, " %0lx", bs->data[i]);
+		fprintf(file, " " BITSET_UNIT_FMT, bs->data[i]);
 }
 
 /*
@@ -365,13 +419,13 @@ static INLINE void bitset_debug_fprint(FILE *file, const bitset_t *bs)
 #define BINARY_OP(op) \
 static INLINE bitset_t *bitset_ ## op(bitset_t *tgt, const bitset_t *src) \
 { \
-	int i; \
-	int n = tgt->units > src->units ? src->units : tgt->units; \
+	bitset_pos_t i; \
+	bitset_pos_t n = tgt->units > src->units ? src->units : tgt->units; \
 	for(i = 0; i < n; i += _BITSET_BINOP_UNITS_INC) \
 		_bitset_inside_binop_ ## op(&tgt->data[i], &src->data[i]); \
 	if(n < tgt->units) \
 		_bitset_clear_rest(&tgt->data[i], tgt->units - i); \
-	return tgt; \
+	return _bitset_mask_highest(tgt); \
 }
 
 /*