#include "monobitset.h"
#include "config.h"
-#ifdef __GNUC__
-#define MONO_ZERO_LEN_ARRAY 0
-#else
-#define MONO_ZERO_LEN_ARRAY 1
-#endif
-
#define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
-struct MonoBitSet {
- gsize size;
- gsize flags;
- gsize data [MONO_ZERO_LEN_ARRAY];
-};
-
/*
* mono_bitset_alloc_size:
* @max_size: The numer of bits you want to hold
return -1;
}
+static int
+find_first_unset (gulong mask, gint nth_bit)
+{
+ do {
+ nth_bit++;
+ if (!(mask & ((gsize)1 << nth_bit))) {
+ if (nth_bit == BITS_PER_CHUNK)
+ /* On 64 bit platforms, 1 << 64 == 1 */
+ return -1;
+ else
+ return nth_bit;
+ }
+ } while (nth_bit < BITS_PER_CHUNK);
+ return -1;
+}
+
/*
* mono_bitset_find_start:
* @set: bitset ptr
return -1;
}
+/*
+ * mono_bitset_find_first_unset:
+ * @set: bitset ptr
+ * @pos: pos to search _after_ (not including)
+ *
+ * Returns position of first unset bit after @pos. If pos < 0 begin search from
+ * start. Return -1 if no bit set is found.
+ */
+int
+mono_bitset_find_first_unset (const MonoBitSet *set, gint pos) {
+ int j;
+ int bit;
+ int result, i;
+
+ if (pos < 0) {
+ j = 0;
+ bit = -1;
+ } else {
+ j = pos / BITS_PER_CHUNK;
+ bit = pos % BITS_PER_CHUNK;
+ g_return_val_if_fail (pos < set->size, -1);
+ }
+ /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
+
+ if (set->data [j] != -1) {
+ result = find_first_unset (set->data [j], bit);
+ if (result != -1)
+ return result + j * BITS_PER_CHUNK;
+ }
+ for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
+ if (set->data [i] != -1) {
+ return find_first_unset (set->data [i], -1) + i * BITS_PER_CHUNK;
+ }
+ }
+ return -1;
+}
+
/*
* mono_bitset_clone:
* @set: bitset ptr to clone
*/
void
mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
- int i;
+ int i, size;
g_assert (src->size <= dest->size);
- for (i = 0; i < dest->size / BITS_PER_CHUNK; ++i)
+ size = dest->size / BITS_PER_CHUNK;
+ for (i = 0; i < size; ++i)
dest->data [i] |= src->data [i];
}
*/
void
mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
- int i;
+ int i, size;
g_assert (src->size <= dest->size);
- for (i = 0; i < dest->size / BITS_PER_CHUNK; ++i)
- dest->data [i] = dest->data [i] & src->data [i];
+ size = dest->size / BITS_PER_CHUNK;
+ for (i = 0; i < size; ++i)
+ dest->data [i] &= src->data [i];
}
/*
*/
void
mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
- int i;
+ int i, size;
g_assert (src1->size <= dest->size);
g_assert (src2->size <= dest->size);
- for (i = 0; i < dest->size / BITS_PER_CHUNK; ++i)
+ size = dest->size / BITS_PER_CHUNK;
+ for (i = 0; i < size; ++i)
dest->data [i] = src1->data [i] & src2->data [i];
}
*/
void
mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
- int i;
+ int i, size;
g_assert (src->size <= dest->size);
- for (i = 0; i < dest->size / BITS_PER_CHUNK; ++i)
+ size = src->size / BITS_PER_CHUNK;
+ for (i = 0; i < size; ++i)
dest->data [i] &= ~src->data [i];
}