#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
+ * @max_size: The number of bits you want to hold
* @flags: unused
*
* Return the number of bytes required to hold the bitset.
guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
MonoBitSet *result;
- result = g_malloc0 (sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY));
+ result = (MonoBitSet *) g_malloc0 (sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY));
result->size = real_size * BITS_PER_CHUNK;
result->flags = flags;
return result;
MonoBitSet *
mono_bitset_mem_new (gpointer mem, guint32 max_size, guint32 flags) {
guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
- MonoBitSet *result = mem;
+ MonoBitSet *result = (MonoBitSet *) mem;
result->size = real_size * BITS_PER_CHUNK;
result->flags = flags | MONO_BITSET_DONT_FREE;
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 (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;
+#ifdef __GNUC__
+ if (sizeof (gsize) == sizeof (unsigned long))
+ count += __builtin_popcountl (d);
+ else
+ count += __builtin_popcount (d);
#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
+ while (d) {
+ count ++;
+ d &= (d - 1);
}
+#endif
}
return count;
}
if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
return -1;
-#if defined(__i386__) && defined(__GNUC__)
+#if defined(__native_client__) && (defined(__i386__) || defined(__x86_64))
+#define USE_X86_32BIT_INSTRUCTIONS 1
+#endif
+
+#if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
{
int r;
/* This depends on mask != 0 */
my_g_bit_nth_lsf_nomask (gsize mask)
{
/* Mask is expected to be != 0 */
-#if defined(__i386__) && defined(__GNUC__)
+#if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
int r;
__asm__("bsfl %1,%0\n\t"
}
static int
-find_first_unset (gulong mask, gint nth_bit)
+find_first_unset (gsize mask, gint nth_bit)
{
do {
nth_bit++;
*/
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 < src->size / BITS_PER_CHUNK; ++i)
+ size = src->size / BITS_PER_CHUNK;
+ for (i = 0; i < size; ++i)
dest->data [i] &= ~src->data [i];
}
}
#endif
-