#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 (8 * sizeof (guint32))
-
-struct MonoBitSet {
- guint32 size;
- guint32 flags;
- guint32 data [MONO_ZERO_LEN_ARRAY];
-};
+#define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
/*
* mono_bitset_alloc_size:
mono_bitset_alloc_size (guint32 max_size, guint32 flags) {
guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
- return sizeof (MonoBitSet) + sizeof (guint32) * (real_size - MONO_ZERO_LEN_ARRAY);
+ return sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY);
}
/*
guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
MonoBitSet *result;
- result = g_malloc0 (sizeof (MonoBitSet) + sizeof (guint32) * (real_size - MONO_ZERO_LEN_ARRAY));
+ result = g_malloc0 (sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY));
result->size = real_size * BITS_PER_CHUNK;
result->flags = flags;
return result;
int j = pos / BITS_PER_CHUNK;
int bit = pos % BITS_PER_CHUNK;
- g_return_if_fail (pos < set->size);
+ g_assert (pos < set->size);
- set->data [j] |= 1 << bit;
+ set->data [j] |= (gsize)1 << bit;
}
/*
g_return_val_if_fail (pos < set->size, 0);
- return set->data [j] & (1 << bit);
+ return (set->data [j] & ((gsize)1 << bit)) > 0;
}
/*
* @set: bitset ptr
* @pos: test bit at this pos
*
- * Return 32 bits from the bitset, starting from @pos, which must be divisible
- * with 32.
+ * Return 32/64 bits from the bitset, starting from @pos, which must be
+ * divisible with 32/64.
*/
-guint32
+gsize
mono_bitset_test_bulk (const MonoBitSet *set, guint32 pos) {
int j = pos / BITS_PER_CHUNK;
int j = pos / BITS_PER_CHUNK;
int bit = pos % BITS_PER_CHUNK;
- g_return_if_fail (pos < set->size);
+ g_assert (pos < set->size);
- set->data [j] &= ~(1 << bit);
+ set->data [j] &= ~((gsize)1 << bit);
}
/*
*/
void
mono_bitset_clear_all (MonoBitSet *set) {
- int i;
- for (i = 0; i < set->size / BITS_PER_CHUNK; ++i)
- set->data [i] = 0;
+ memset (set->data, 0, set->size / 8);
}
/*
*/
void
mono_bitset_set_all (MonoBitSet *set) {
- int i;
- for (i = 0; i < set->size / BITS_PER_CHUNK; ++i)
- set->data [i] = 0xffffffff;
+ memset (set->data, -1, set->size / 8);
}
/*
*/
guint32
mono_bitset_count (const MonoBitSet *set) {
- static const unsigned char table [16] = {
- 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
- };
guint32 i, count;
- const unsigned char *b;
+ gsize d;
count = 0;
for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
+ d = set->data [i];
/* there is probably some asm code that can do this much faster */
- if (set->data [i]) {
- b = (unsigned char*) (set->data + i);
- count += table [b [0] & 0xf];
- count += table [b [0] >> 4];
- count += table [b [1] & 0xf];
- count += table [b [1] >> 4];
- count += table [b [2] & 0xf];
- count += table [b [2] >> 4];
- count += table [b [3] & 0xf];
- count += table [b [3] >> 4];
+ if (d) {
+#if SIZEOF_VOID_P == 8
+ /* http://www.jjj.de/bitwizardry/bitwizardrypage.html */
+ d -= (d>>1) & 0x5555555555555555;
+ d = ((d>>2) & 0x3333333333333333) + (d & 0x3333333333333333);
+ d = ((d>>4) + d) & 0x0f0f0f0f0f0f0f0f;
+ d *= 0x0101010101010101;
+ count += d >> 56;
+#else
+ /* http://aggregate.org/MAGIC/ */
+ d -= ((d >> 1) & 0x55555555);
+ d = (((d >> 2) & 0x33333333) + (d & 0x33333333));
+ d = (((d >> 4) + d) & 0x0f0f0f0f);
+ d += (d >> 8);
+ d += (d >> 16);
+ count += (d & 0x0000003f);
+#endif
}
}
return count;
#define my_g_bit_nth_lsf_nomask(m) (ffs((m))-1)
#else
+
static inline gint
-my_g_bit_nth_lsf (guint32 mask, gint nth_bit)
+my_g_bit_nth_lsf (gsize mask, gint nth_bit)
{
- do {
- nth_bit++;
- if (mask & (1 << (gulong) nth_bit))
- return nth_bit;
- } while (nth_bit < 31);
- return -1;
+ nth_bit ++;
+ mask >>= nth_bit;
+
+ if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
+ return -1;
+
+#if defined(__i386__) && defined(__GNUC__)
+ {
+ int r;
+ /* This depends on mask != 0 */
+ __asm__("bsfl %1,%0\n\t"
+ : "=r" (r) : "g" (mask));
+ return nth_bit + r;
+ }
+#elif defined(__x86_64) && defined(__GNUC__)
+ {
+ guint64 r;
+
+ __asm__("bsfq %1,%0\n\t"
+ : "=r" (r) : "rm" (mask));
+ return nth_bit + r;
+ }
+#else
+ while (! (mask & 0x1)) {
+ mask >>= 1;
+ nth_bit ++;
+ }
+
+ return nth_bit;
+#endif
+}
+
+static inline gint
+my_g_bit_nth_lsf_nomask (gsize mask)
+{
+ /* Mask is expected to be != 0 */
+#if defined(__i386__) && defined(__GNUC__)
+ int r;
+
+ __asm__("bsfl %1,%0\n\t"
+ : "=r" (r) : "rm" (mask));
+ return r;
+#elif defined(__x86_64) && defined(__GNUC__)
+ guint64 r;
+
+ __asm__("bsfq %1,%0\n\t"
+ : "=r" (r) : "rm" (mask));
+ return r;
+#else
+ int nth_bit = 0;
+
+ while (! (mask & 0x1)) {
+ mask >>= 1;
+ nth_bit ++;
+ }
+
+ return nth_bit;
+#endif
}
-#define my_g_bit_nth_lsf_nomask(m) (my_g_bit_nth_lsf((m),-1))
+
#endif
-#if SIZEOF_VOID_P == 8 && GLIB_MAJOR_VERSION == 2 && GLIB_MINOR_VERSION < 4
-/*
- * There was a 64 bit bug in glib-2.2: g_bit_nth_msf (0, -1) would return 32,
- * causing infinite loops in dominator computation. So glib-2.4 is required.
- */
-my_g_bit_nth_msf (gulong mask,
+static inline int
+my_g_bit_nth_msf (gsize mask,
gint nth_bit)
{
- if (nth_bit < 0)
- nth_bit = GLIB_SIZEOF_LONG * 8;
- do
- {
- nth_bit--;
- if (mask & (1UL << nth_bit))
- return nth_bit;
+ int i;
+
+ if (nth_bit == 0)
+ return -1;
+
+ mask <<= BITS_PER_CHUNK - nth_bit;
+
+ i = BITS_PER_CHUNK;
+ while ((i > 0) && !(mask >> (BITS_PER_CHUNK - 8))) {
+ mask <<= 8;
+ i -= 8;
+ }
+ if (mask == 0)
+ return -1;
+
+ do {
+ i--;
+ if (mask & ((gsize)1 << (BITS_PER_CHUNK - 1)))
+ return i - (BITS_PER_CHUNK - nth_bit);
+ mask <<= 1;
}
- while (nth_bit > 0);
- return -1;
+ while (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;
}
-#else
-#define my_g_bit_nth_msf(mask,nth_bit) g_bit_nth_msf((mask),(nth_bit))
-#endif
/*
* mono_bitset_find_start:
} else {
j = pos / BITS_PER_CHUNK;
bit = pos % BITS_PER_CHUNK;
- g_return_val_if_fail (pos < set->size, -1);
+ g_assert (pos < set->size);
}
/*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
}
for (i = --j; i >= 0; --i) {
if (set->data [i])
- return my_g_bit_nth_msf (set->data [i], -1) + i * BITS_PER_CHUNK;
+ return my_g_bit_nth_msf (set->data [i], BITS_PER_CHUNK) + i * BITS_PER_CHUNK;
+ }
+ 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;
}
*/
void
mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
- int i;
-
- g_return_if_fail (dest->size <= src->size);
+ g_assert (dest->size <= src->size);
- for (i = 0; i < dest->size / BITS_PER_CHUNK; ++i)
- dest->data [i] = src->data [i];
+ memcpy (&dest->data, &src->data, dest->size / 8);
}
/*
*/
void
mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
- int i;
+ int i, size;
- g_return_if_fail (src->size <= dest->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);
+
+ size = dest->size / BITS_PER_CHUNK;
+ for (i = 0; i < size; ++i)
+ dest->data [i] &= src->data [i];
+}
+
+/*
+ * mono_bitset_intersection_2:
+ * @dest: bitset ptr to hold intersection
+ * @src1: first bitset
+ * @src2: second bitset
+ *
+ * Make intersection of two bitsets
+ */
+void
+mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
+ int i, size;
- g_return_if_fail (src->size <= dest->size);
+ g_assert (src1->size <= dest->size);
+ g_assert (src2->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] = src1->data [i] & src2->data [i];
}
/*
*/
void
mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
- int i;
+ int i, size;
- g_return_if_fail (src->size <= dest->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];
}
for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
if (set->data [i]) {
for (j = 0; j < BITS_PER_CHUNK; ++j)
- if (set->data [i] & (1 << j))
+ if (set->data [i] & ((gsize)1 << j))
func (j + i * BITS_PER_CHUNK, data);
}
}
projects / mono.git / blobdiff