2009-02-23 Mark Probst <mark.probst@gmail.com>

[mono.git] / mono / utils / monobitset.c

diff --git a/mono/utils/monobitset.c b/mono/utils/monobitset.c
index 4f378fb7c9cdf124611a0cc66723b628f0b46d79..d25f66ec0b81b2e4d9daf78cbc92b81cb3575c91 100644 (file)
--- a/mono/utils/monobitset.c
+++ b/mono/utils/monobitset.c
@@ -4,20 +4,8 @@
 #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
@@ -383,6 +371,22 @@ my_g_bit_nth_msf (gsize mask,
        return -1;
 }
 
+static int
+find_first_unset (gsize 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
@@ -469,6 +473,43 @@ mono_bitset_find_last (const MonoBitSet *set, gint pos) {
        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
@@ -513,11 +554,12 @@ mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
  */
 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];
 }
 
@@ -530,12 +572,13 @@ mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
  */
 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];
 }
 
 /*
@@ -548,12 +591,13 @@ mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
  */
 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];
 }
 
@@ -566,11 +610,12 @@ mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const Mono
  */
 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];
 }