+/**
+ * Clear the bitset.
+ * This sets all bits to zero.
+ * @param bs The bitset.
+ */
+static inline bitset_t *bitset_clear_all(bitset_t *bs)
+{
+ memset(BS_DATA(bs), 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(bs), -1, bs->units * BS_UNIT_SIZE);
+ return _bitset_mask_highest(bs);
+}
+
+/**
+ * Check, if one bitset is contained by another.
+ * That is, each bit set in lhs is also set in rhs.
+ * @param lhs A bitset.
+ * @param rhs Another bitset.
+ * @return 1, if all bits in lhs are also set in rhs, 0 otherwise.
+ */
+static inline int bitset_contains(const bitset_t *lhs, const bitset_t *rhs)
+{
+ bitset_pos_t n = lhs->units < rhs->units ? lhs->units : rhs->units;
+ bitset_pos_t i;
+
+ for(i = 0; i < n; ++i) {
+ bitset_unit_t lu = BS_DATA(lhs)[i];
+ bitset_unit_t ru = BS_DATA(rhs)[i];
+
+ if((lu | ru) & ~ru)
+ return 0;
+ }
+
+ /*
+ * If the left hand sinde is a larger bitset than rhs,
+ * we have to check, that all extra bits in lhs are 0
+ */
+ if(lhs->units > n) {
+ for(i = n; i < lhs->units; ++i) {
+ if(BS_DATA(lhs)[i] != 0)
+ return 0;
+ }
+ }
+
+ 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(bs)[i];
+ bitset_unit_t um1 = unit - 1;
+
+ BS_DATA(bs)[i] = um1;
+
+ if(((unit >> _SH) ^ (um1 >> _SH)) == 0)
+ break;
+ }
+#undef _SH
+}
+
+/**
+ * Check if two bitsets intersect.
+ * @param a The first bitset.
+ * @param b The second bitset.
+ * @return 1 if they have a bit in common, 0 if not.
+ */
+static inline int bitset_intersect(const bitset_t *a, const bitset_t *b)
+{
+ bitset_pos_t n = a->units < b->units ? a->units : b->units;
+ bitset_pos_t i;
+
+ for (i = 0; i < n; ++i)
+ if (BS_DATA(a)[i] & BS_DATA(b)[i])
+ return 1;
+
+ 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.
+ * @return 1, if the bitset is empty, 0 if not.
+ */
+static inline int bitset_is_empty(const bitset_t *a)
+{
+ bitset_pos_t i;
+ for (i = 0; i < a->units; ++i)
+ if (BS_DATA(a)[i] != 0)
+ return 0;
+ return 1;
+}
+
+/**
+ * Print a bitset to a stream.
+ * The bitset is printed as a comma separated list of bits set.
+ * @param file The stream.
+ * @param bs The bitset.
+ */
+static inline void bitset_fprint(FILE *file, const bitset_t *bs)
+{
+ const char *prefix = "";
+ int i;
+
+ putc('{', file);
+ for(i = bitset_next_set(bs, 0); i != -1; i = bitset_next_set(bs, i + 1)) {
+ fprintf(file, "%s%u", prefix, i);
+ prefix = ",";
+ }
+ putc('}', file);
+}
+
+static inline void bitset_debug_fprint(FILE *file, const bitset_t *bs)
+{
+ bitset_pos_t i;
+
+ fprintf(file, "%u:", bs->units);
+ for(i = 0; i < bs->units; ++i)
+ fprintf(file, " " BITSET_UNIT_FMT, BS_DATA(bs)[i]);
+}
+
+/**
+ * Perform tgt = tgt \ src operation.
+ * @param tgt The target bitset.
+ * @param src The source bitset.
+ * @return the tgt set.
+ */
+static inline bitset_t *bitset_andnot(bitset_t *tgt, const bitset_t *src);
+
+/**
+ * Perform Union, tgt = tgt u src operation.
+ * @param tgt The target bitset.
+ * @param src The source bitset.
+ * @return the tgt set.
+ */
+static inline bitset_t *bitset_or(bitset_t *tgt, const bitset_t *src);
+
+/**
+ * Perform tgt = tgt ^ ~src operation.
+ * @param tgt The target bitset.
+ * @param src The source bitset.
+ * @return the tgt set.
+ */
+static inline bitset_t *bitset_xor(bitset_t *tgt, const bitset_t *src);
+