X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Futils%2Fmonobitset.c;h=e113260d4a8dde077d498fdea9fd6d3d1cb2b7a1;hb=e83f4a2ab3043d48fca236fa54ac411fc8bad549;hp=a39820c51aa5920f8d17ac83b5dcb909317396d0;hpb=234225d112c4b018b8d1796f4c06a15812137500;p=mono.git diff --git a/mono/utils/monobitset.c b/mono/utils/monobitset.c index a39820c51aa..e113260d4a8 100644 --- a/mono/utils/monobitset.c +++ b/mono/utils/monobitset.c @@ -4,23 +4,11 @@ #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: - * @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. @@ -31,7 +19,7 @@ guint32 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); } /* @@ -47,7 +35,7 @@ mono_bitset_new (guint32 max_size, guint32 flags) { 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; @@ -99,9 +87,9 @@ mono_bitset_set (MonoBitSet *set, guint32 pos) { 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; } /* @@ -119,7 +107,7 @@ mono_bitset_test (const MonoBitSet *set, guint32 pos) { g_return_val_if_fail (pos < set->size, 0); - return set->data [j] & (1 << bit); + return (set->data [j] & ((gsize)1 << bit)) > 0; } /* @@ -127,10 +115,10 @@ mono_bitset_test (const MonoBitSet *set, guint32 pos) { * @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; @@ -152,9 +140,9 @@ mono_bitset_clear (MonoBitSet *set, guint32 pos) { 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); } /* @@ -165,9 +153,7 @@ mono_bitset_clear (MonoBitSet *set, guint32 pos) { */ 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); } /* @@ -178,9 +164,7 @@ mono_bitset_clear_all (MonoBitSet *set) { */ 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); } /* @@ -220,26 +204,23 @@ mono_bitset_size (const MonoBitSet *set) { */ 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) { - /* 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]; + d = set->data [i]; +#ifdef __GNUC__ + if (sizeof (gsize) == sizeof (unsigned long)) + count += __builtin_popcountl (d); + else + count += __builtin_popcount (d); +#else + while (d) { + count ++; + d &= (d - 1); } +#endif } return count; } @@ -286,41 +267,121 @@ bitstart_mask [] = { #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(__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 */ + __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 } -#define my_g_bit_nth_lsf_nomask(m) (my_g_bit_nth_lsf((m),-1)) + +static inline gint +my_g_bit_nth_lsf_nomask (gsize mask) +{ + /* Mask is expected to be != 0 */ +#if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS) + 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 +} -#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, +#endif + +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: @@ -360,7 +421,7 @@ mono_bitset_find_first (const MonoBitSet *set, gint pos) { } 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);*/ @@ -403,7 +464,44 @@ mono_bitset_find_last (const MonoBitSet *set, gint pos) { } 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; } @@ -438,12 +536,9 @@ mono_bitset_clone (const MonoBitSet *set, guint32 new_size) { */ 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); } /* @@ -455,11 +550,12 @@ mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) { */ 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]; } @@ -472,12 +568,33 @@ mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) { */ void mono_bitset_intersection (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) - 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]; +} + +/* + * 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_assert (src1->size <= dest->size); + g_assert (src2->size <= dest->size); + + size = dest->size / BITS_PER_CHUNK; + for (i = 0; i < size; ++i) + dest->data [i] = src1->data [i] & src2->data [i]; } /* @@ -489,11 +606,12 @@ mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) { */ 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]; } @@ -533,7 +651,7 @@ mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data) 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); } } @@ -695,4 +813,3 @@ main() { } #endif -