X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fbitset.h;h=9ae16372b73ff483b755c33563e7b8fc9254636a;hb=25ea4567ce42388f59fdc45e11f278290fdd1353;hp=1f621680bd19d6819e5be8bda58cad2e9c802001;hpb=0f08af6110e629451b65376c720731385ea4b8f1;p=libfirm

diff --git a/ir/adt/bitset.h b/ir/adt/bitset.h
index 1f621680b..9ae16372b 100644
--- a/ir/adt/bitset.h
+++ b/ir/adt/bitset.h
@@ -16,6 +16,14 @@
 #include "firm_config.h"
 #include "bitfiddle.h"
 
+#ifdef _WIN32
+#include <malloc.h>
+#else
+#include <alloca.h>
+#endif
+
+typedef unsigned int bitset_pos_t;
+
 #include "bitset_std.h"
 
 /*
@@ -25,11 +33,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 +48,43 @@ 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)
+{
+	bitset_pos_t rest = bs->size & BS_UNIT_MASK;
+	if (rest)
+		bs->data[bs->units - 1] &= (1 << rest) - 1;
+	return bs;
+}
+
 /**
  * Get the capacity of the bitset in bits.
  * @param bs The bitset.
@@ -68,22 +92,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 bitset_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(xmalloc(_bitset_overall_size(sizeof(bitset_t), size)), size)
 
 /**
  * Free a bitset allocated with bitset_malloc().
@@ -93,11 +125,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 +139,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 +151,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 +162,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,12 +185,24 @@ 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);
 }
 
+/**
+ * Flip the whole bitset.
+ * @param bs The bitset.
+ */
+static INLINE void bitset_flip_all(bitset_t *bs)
+{
+	bitset_pos_t i;
+	for(i = 0; i < bs->units; i++)
+		_bitset_inside_flip_unit(&bs->data[i]);
+	_bitset_mask_highest(bs);
+}
+
 /**
  * Copy a bitset to another.
  * @param tgt The target bitset.
@@ -160,13 +211,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 +225,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 +245,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;
@@ -217,46 +268,51 @@ static INLINE unsigned long bitset_max(const bitset_t *bs)
  * @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;
+	bitset_pos_t res;
 
-	if(unit_number >= bs->units)
+	if(pos >= bs->size)
 		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];
+		bitset_unit_t curr_unit = bs->data[unit_number];
 
 		/*
 		 * 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.
 		 */
-		unsigned long next_in_this_unit =
+		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)
-			return next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS;
+		if (next_in_this_unit < BS_UNIT_SIZE_BITS) {
+			res = next_in_this_unit + unit_number * BS_UNIT_SIZE_BITS;
+			return res < bs->size ? res : -1;
+		}
 
 		/* 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_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;
+				if (first_set < BS_UNIT_SIZE_BITS) {
+					res = first_set + i * BS_UNIT_SIZE_BITS;
+					return res < bs->size ? res : -1;
+				}
 			}
 		}
 	}
@@ -285,10 +341,10 @@ static INLINE unsigned long _bitset_next(const bitset_t *bs,
  * @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);
@@ -301,9 +357,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->units * BS_UNIT_SIZE);
+  return _bitset_mask_highest(bs);
 }
 
 /**
@@ -315,12 +383,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;
@@ -340,6 +408,29 @@ static INLINE int bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
 	return 1;
 }
 
+/**
+ * Treat the bitset as a number and subtract 1.
+ * @param bs The bitset.
+ * @return The same bitset.
+ */
+static INLINE void bitset_minus1(bitset_t *bs)
+{
+#define _SH (sizeof(bitset_unit_t) * 8 - 1)
+
+  bitset_pos_t i;
+
+  for(i = 0; i < bs->units; ++i) {
+    bitset_unit_t unit = bs->data[i];
+    bitset_unit_t um1  = unit - 1;
+
+    bs->data[i] = um1;
+
+    if(((unit >> _SH) ^ (um1 >> _SH)) == 0)
+      break;
+  }
+#undef _SH
+}
+
 /**
  * Print a bitset to a stream.
  * The bitset is printed as a comma seperated list of bits set.
@@ -361,11 +452,11 @@ static INLINE void bitset_fprint(FILE *file, const bitset_t *bs)
 
 static INLINE void bitset_debug_fprint(FILE *file, const bitset_t *bs)
 {
-	unsigned long i;
+	bitset_pos_t i;
 
-	fprintf(file, "%lu:", 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]);
 }
 
 /*
@@ -375,13 +466,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) \
 { \
-	unsigned long i; \
-	unsigned long 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); \
 }
 
 /*