#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
*/
guint32
mono_bitset_count (const MonoBitSet *set) {
-#if SIZEOF_VOID_P == 8
- static const unsigned char table [16] = {
- 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
- };
-#endif
guint32 i, count;
gsize d;
/* there is probably some asm code that can do this much faster */
if (d) {
#if SIZEOF_VOID_P == 8
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
- count += table [d & 0xf]; d >>= 4;
+ /* 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);
static inline gint
my_g_bit_nth_lsf (gsize mask, gint nth_bit)
{
-#ifdef __i386__
- int cnt;
-#endif
-
nth_bit ++;
mask >>= nth_bit;
if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
return -1;
-#ifdef __i386__
- /* This depends on mask != 0 */
- __asm__("bsfl %1,%0\n\t"
- : "=r" (cnt) : "g" (mask));
- return nth_bit + cnt;
+#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;
my_g_bit_nth_lsf_nomask (gsize mask)
{
/* Mask is expected to be != 0 */
-#ifdef __i386__
+#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;
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
} 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);*/
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];
}
projects / mono.git / blobdiff