/*
- * 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.
*
static INLINE bitset_t *_bitset_prepare(void *area, bitset_pos_t size)
{
bitset_t *ptr = area;
- memset(area, 0, BS_TOTAL_SIZE(size));
+ memset(ptr, 0, BS_TOTAL_SIZE(size));
ptr->units = BS_UNITS(size);
ptr->size = size;
return ptr;
return _bitset_mask_highest(tgt);
}
-/**
- * Find the smallest bit set in the bitset.
- * @param bs The bitset.
- * @return The smallest bit set in the bitset.
- */
-static INLINE bitset_pos_t bitset_min(const bitset_t *bs)
-{
- bitset_pos_t i, ofs = 0;
-
- for(i = 0; i < bs->units; ++i) {
- bitset_unit_t *unit = &BS_DATA(bs)[i];
- bitset_pos_t pos = _bitset_inside_ntz(unit);
- if(pos > 0)
- return ofs + pos;
- ofs += BS_UNIT_SIZE_BITS;
- }
-
- return 0;
-}
-
-/**
- * Find the greatest bit set in the bitset.
- * @param bs The bitset.
- * @return The greatest bit set in the bitset.
- */
-static INLINE bitset_pos_t bitset_max(const bitset_t *bs)
-{
- bitset_pos_t i, max = 0, ofs = 0;
-
- for(i = 0; i < bs->units; ++i) {
- bitset_unit_t *unit = &BS_DATA(bs)[i];
- bitset_pos_t pos = _bitset_inside_nlz(unit);
- if(pos > 0)
- max = ofs + pos;
- ofs += BS_UNIT_SIZE_BITS;
- }
-
- return max;
-}
-
/**
* Find the next set bit from a given bit.
* @note Note that if pos is set, pos is returned.
/* If there is a bit set in the current unit, exit. */
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;
+ return res < bs->size ? res : (bitset_pos_t) -1;
}
/* Else search for set bits in the next units. */
if (first_set < BS_UNIT_SIZE_BITS) {
res = first_set + i * BS_UNIT_SIZE_BITS;
- return res < bs->size ? res : -1;
+ return res < bs->size ? res : (bitset_pos_t) -1;
}
}
}
* @param elm A unsigned long variable.
*/
#define bitset_foreach(bitset,elm) \
- for(elm = bitset_next_set(bitset,0); elm != -1; elm = bitset_next_set(bitset,elm+1))
+ for(elm = bitset_next_set(bitset,0); elm != (bitset_pos_t) -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))
+ for(elm = bitset_next_clear(bitset,0); elm != (bitset_pos_t) -1; elm = bitset_next_clear(bitset,elm+1))
/**
* Count the bits set.
return 0;
}
+/**
+ * set or clear all bits in the range [from;to[.
+ * @param a The bitset.
+ * @param from The first index to set to one.
+ * @param to The last index plus one to set to one.
+ * @param do_set If 1 the bits are set, if 0, they are cleared.
+ */
+static INLINE void bitset_mod_range(bitset_t *a, bitset_pos_t from, bitset_pos_t to, int do_set)
+{
+ bitset_pos_t from_unit, to_unit, i;
+ bitset_unit_t from_unit_mask, to_unit_mask;
+
+ if (from == to)
+ return;
+
+ if (to < from) {
+ bitset_pos_t tmp = from;
+ from = to;
+ to = tmp;
+ }
+
+ if (to > a->size)
+ to = a->size;
+
+ /*
+ * A small example (for cleaning bits in the same unit).
+ * from = 7
+ * to = 19
+ * do_set = 0
+ * result: xxxxxxx000000000000xxxxxxxxxxxxx
+ * from_unit_mask: 00000001111111111111111111111111
+ * to_unit_mask: 11111111111111111110000000000000
+ * scale: 01234567890123456789012345678901
+ * 1 2 3
+ */
+
+ from_unit = from / BS_UNIT_SIZE_BITS;
+ from_unit_mask = ~((1 << from) - 1);
+ from = from & BS_UNIT_MASK;
+
+ to_unit = to / BS_UNIT_SIZE_BITS;
+ to_unit_mask = (1 << to) - 1;
+ to = to & BS_UNIT_MASK;
+
+ /* do we want to set the bits in the range? */
+ if (do_set) {
+ /* If from and to are in the same unit: */
+ if (from_unit == to_unit)
+ BS_DATA(a)[from_unit] |= from_unit_mask & to_unit_mask;
+
+ /* Else, we have to treat the from and to units seperately */
+ else {
+ BS_DATA(a)[from_unit] |= from_unit_mask;
+ BS_DATA(a)[to_unit] |= to_unit_mask;
+ for (i = from_unit + 1; i < to_unit; i++)
+ BS_DATA(a)[i] = BITSET_UNIT_ALL_ONE;
+ }
+ }
+
+ /* ... or clear them? */
+ else {
+ if (from_unit == to_unit)
+ BS_DATA(a)[from_unit] &= ~(from_unit_mask & to_unit_mask);
+
+ else {
+ BS_DATA(a)[from_unit] &= ~from_unit_mask;
+ BS_DATA(a)[to_unit] &= ~to_unit_mask;
+ for (i = from_unit + 1; i < to_unit; i++)
+ BS_DATA(a)[i] = 0;
+ }
+ }
+}
+
+#define bitset_set_range(bs, from, to) bitset_mod_range((bs), (from), (to), 1)
+#define bitset_clear_range(bs, from, to) bitset_mod_range((bs), (from), (to), 0)
+
/**
* Check, if a bitset is empty.
* @param a The bitset.
#define _bitset_clear_rest(data,n) _bitset_inside_clear_units(data, n)
BINARY_OP(and)
#undef _bitset_clear_rest
-#define _bitset_clear_rest(data,n)
+#define _bitset_clear_rest(data,n) do { } while(0)
BINARY_OP(andnot)
BINARY_OP(or)