4 #include "monobitset.h"
7 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
10 * mono_bitset_alloc_size:
11 * @max_size: The number of bits you want to hold
14 * Return the number of bytes required to hold the bitset.
15 * Useful to allocate it on the stack or with mempool.
16 * Use with mono_bitset_mem_new ().
19 mono_bitset_alloc_size (guint32 max_size, guint32 flags) {
20 guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
22 return sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY);
27 * @max_size: The numer of bits you want to hold
28 * @flags: bitfield of flags
30 * Return a bitset of size max_size. It must be freed using
34 mono_bitset_new (guint32 max_size, guint32 flags) {
35 guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
38 result = g_malloc0 (sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY));
39 result->size = real_size * BITS_PER_CHUNK;
40 result->flags = flags;
45 * mono_bitset_mem_new:
46 * @mem: The location the bitset is stored
47 * @max_size: The number of bits you want to hold
48 * @flags: bitfield of flags
50 * Return mem, which is now a initialized bitset of size max_size. It is
51 * not freed even if called with mono_bitset_free. mem must be at least
52 * as big as mono_bitset_alloc_size returns for the same max_size.
55 mono_bitset_mem_new (gpointer mem, guint32 max_size, guint32 flags) {
56 guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
57 MonoBitSet *result = mem;
59 result->size = real_size * BITS_PER_CHUNK;
60 result->flags = flags | MONO_BITSET_DONT_FREE;
66 * @set: bitset ptr to free
68 * Free bitset unless flags have MONO_BITSET_DONT_FREE set. Does not
69 * free anything if flag MONO_BITSET_DONT_FREE is set or bitset was
70 * made with mono_bitset_mem_new.
73 mono_bitset_free (MonoBitSet *set) {
74 if (!(set->flags & MONO_BITSET_DONT_FREE))
81 * @pos: set bit at this pos
83 * Set bit at pos @pos, counting from 0.
86 mono_bitset_set (MonoBitSet *set, guint32 pos) {
87 int j = pos / BITS_PER_CHUNK;
88 int bit = pos % BITS_PER_CHUNK;
90 g_assert (pos < set->size);
92 set->data [j] |= (gsize)1 << bit;
98 * @pos: test bit at this pos
100 * Test bit at pos @pos, counting from 0.
101 * Returns a value != 0 if set, 0 otherwise.
104 mono_bitset_test (const MonoBitSet *set, guint32 pos) {
105 int j = pos / BITS_PER_CHUNK;
106 int bit = pos % BITS_PER_CHUNK;
108 g_return_val_if_fail (pos < set->size, 0);
110 return (set->data [j] & ((gsize)1 << bit)) > 0;
114 * mono_bitset_test_bulk:
116 * @pos: test bit at this pos
118 * Return 32/64 bits from the bitset, starting from @pos, which must be
119 * divisible with 32/64.
122 mono_bitset_test_bulk (const MonoBitSet *set, guint32 pos) {
123 int j = pos / BITS_PER_CHUNK;
125 if (pos >= set->size)
128 return set->data [j];
134 * @pos: unset bit at this pos
136 * Unset bit at pos 'pos', counting from 0.
139 mono_bitset_clear (MonoBitSet *set, guint32 pos) {
140 int j = pos / BITS_PER_CHUNK;
141 int bit = pos % BITS_PER_CHUNK;
143 g_assert (pos < set->size);
145 set->data [j] &= ~((gsize)1 << bit);
149 * mono_bitset_clear_all:
155 mono_bitset_clear_all (MonoBitSet *set) {
156 memset (set->data, 0, set->size / 8);
160 * mono_bitset_set_all:
166 mono_bitset_set_all (MonoBitSet *set) {
167 memset (set->data, -1, set->size / 8);
171 * mono_bitset_invert:
177 mono_bitset_invert (MonoBitSet *set) {
179 for (i = 0; i < set->size / BITS_PER_CHUNK; ++i)
180 set->data [i] = ~set->data [i];
187 * Returns the number of bits this bitset can hold.
190 mono_bitset_size (const MonoBitSet *set) {
195 * should test wich version is faster.
203 * return number of bits that is set.
206 mono_bitset_count (const MonoBitSet *set) {
211 for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
213 /* there is probably some asm code that can do this much faster */
215 #if SIZEOF_VOID_P == 8
216 /* http://www.jjj.de/bitwizardry/bitwizardrypage.html */
217 d -= (d>>1) & 0x5555555555555555;
218 d = ((d>>2) & 0x3333333333333333) + (d & 0x3333333333333333);
219 d = ((d>>4) + d) & 0x0f0f0f0f0f0f0f0f;
220 d *= 0x0101010101010101;
223 /* http://aggregate.org/MAGIC/ */
224 d -= ((d >> 1) & 0x55555555);
225 d = (((d >> 2) & 0x33333333) + (d & 0x33333333));
226 d = (((d >> 4) + d) & 0x0f0f0f0f);
229 count += (d & 0x0000003f);
237 mono_bitset_count (const MonoBitSet *set) {
238 static const guint32 table [] = {
239 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
241 guint32 i, count, val;
244 for (i = 0; i < set->size / BITS_PER_CHUNK;+i) {
247 val = (val & table [0]) ((val >> 1) & table [0]);
248 val = (val & table [1]) ((val >> 2) & table [1]);
249 val = (val & table [2]) ((val >> 4) & table [2]);
250 val = (val & table [3]) ((val >> 8) & table [3]);
251 val = (val & table [4]) ((val >> 16) & table [4]);
263 0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8,
264 0xfffffff0, 0xffffffe0, 0xffffffc0, 0xffffff80,
265 0xffffff00, 0xfffffe00, 0xfffffc00, 0xfffff800,
266 0xfffff000, 0xffffe000, 0xffffc000, 0xffff8000,
267 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
268 0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
269 0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
270 0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
274 #define my_g_bit_nth_lsf(m,n) (ffs((m) & bitstart_mask [(n)+1])-1)
275 #define my_g_bit_nth_lsf_nomask(m) (ffs((m))-1)
280 my_g_bit_nth_lsf (gsize mask, gint nth_bit)
285 if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
288 #if defined(__native_client__) && (defined(__i386__) || defined(__x86_64))
289 #define USE_X86_32BIT_INSTRUCTIONS 1
292 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
295 /* This depends on mask != 0 */
296 __asm__("bsfl %1,%0\n\t"
297 : "=r" (r) : "g" (mask));
300 #elif defined(__x86_64) && defined(__GNUC__)
304 __asm__("bsfq %1,%0\n\t"
305 : "=r" (r) : "rm" (mask));
309 while (! (mask & 0x1)) {
319 my_g_bit_nth_lsf_nomask (gsize mask)
321 /* Mask is expected to be != 0 */
322 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
325 __asm__("bsfl %1,%0\n\t"
326 : "=r" (r) : "rm" (mask));
328 #elif defined(__x86_64) && defined(__GNUC__)
331 __asm__("bsfq %1,%0\n\t"
332 : "=r" (r) : "rm" (mask));
337 while (! (mask & 0x1)) {
349 my_g_bit_nth_msf (gsize mask,
357 mask <<= BITS_PER_CHUNK - nth_bit;
360 while ((i > 0) && !(mask >> (BITS_PER_CHUNK - 8))) {
369 if (mask & ((gsize)1 << (BITS_PER_CHUNK - 1)))
370 return i - (BITS_PER_CHUNK - nth_bit);
379 find_first_unset (gsize mask, gint nth_bit)
383 if (!(mask & ((gsize)1 << nth_bit))) {
384 if (nth_bit == BITS_PER_CHUNK)
385 /* On 64 bit platforms, 1 << 64 == 1 */
390 } while (nth_bit < BITS_PER_CHUNK);
395 * mono_bitset_find_start:
398 * Equivalent to mono_bitset_find_first (set, -1) but faster.
401 mono_bitset_find_start (const MonoBitSet *set)
405 for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
407 return my_g_bit_nth_lsf_nomask (set->data [i]) + i * BITS_PER_CHUNK;
413 * mono_bitset_find_first:
415 * @pos: pos to search _after_ (not including)
417 * Returns position of first set bit after @pos. If pos < 0 begin search from
418 * start. Return -1 if no bit set is found.
421 mono_bitset_find_first (const MonoBitSet *set, gint pos) {
430 j = pos / BITS_PER_CHUNK;
431 bit = pos % BITS_PER_CHUNK;
432 g_assert (pos < set->size);
434 /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
437 result = my_g_bit_nth_lsf (set->data [j], bit);
439 return result + j * BITS_PER_CHUNK;
441 for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
443 return my_g_bit_nth_lsf (set->data [i], -1) + i * BITS_PER_CHUNK;
449 * mono_bitset_find_last:
451 * @pos: pos to search _before_ (not including)
453 * Returns position of last set bit before pos. If pos < 0 search is
454 * started from the end. Returns -1 if no set bit is found.
457 mono_bitset_find_last (const MonoBitSet *set, gint pos) {
458 int j, bit, result, i;
463 j = pos / BITS_PER_CHUNK;
464 bit = pos % BITS_PER_CHUNK;
466 g_return_val_if_fail (pos < set->size, -1);
469 result = my_g_bit_nth_msf (set->data [j], bit);
471 return result + j * BITS_PER_CHUNK;
473 for (i = --j; i >= 0; --i) {
475 return my_g_bit_nth_msf (set->data [i], BITS_PER_CHUNK) + i * BITS_PER_CHUNK;
481 * mono_bitset_find_first_unset:
483 * @pos: pos to search _after_ (not including)
485 * Returns position of first unset bit after @pos. If pos < 0 begin search from
486 * start. Return -1 if no bit set is found.
489 mono_bitset_find_first_unset (const MonoBitSet *set, gint pos) {
498 j = pos / BITS_PER_CHUNK;
499 bit = pos % BITS_PER_CHUNK;
500 g_return_val_if_fail (pos < set->size, -1);
502 /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
504 if (set->data [j] != -1) {
505 result = find_first_unset (set->data [j], bit);
507 return result + j * BITS_PER_CHUNK;
509 for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
510 if (set->data [i] != -1) {
511 return find_first_unset (set->data [i], -1) + i * BITS_PER_CHUNK;
519 * @set: bitset ptr to clone
520 * @new_size: number of bits the cloned bitset can hold
522 * Return a cloned bitset of size new_size. MONO_BITSET_DONT_FREE
523 * unset in cloned bitset. If new_size is 0, the cloned object is just
527 mono_bitset_clone (const MonoBitSet *set, guint32 new_size) {
531 new_size = set->size;
532 result = mono_bitset_new (new_size, set->flags);
533 result->flags &= ~MONO_BITSET_DONT_FREE;
534 memcpy (result->data, set->data, set->size / 8);
539 * mono_bitset_copyto:
540 * @src: bitset ptr to copy from
541 * @dest: bitset ptr to copy to
543 * Copy one bitset to another.
546 mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
547 g_assert (dest->size <= src->size);
549 memcpy (&dest->data, &src->data, dest->size / 8);
554 * @dest: bitset ptr to hold union
555 * @src: bitset ptr to copy
557 * Make union of one bitset and another.
560 mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
563 g_assert (src->size <= dest->size);
565 size = dest->size / BITS_PER_CHUNK;
566 for (i = 0; i < size; ++i)
567 dest->data [i] |= src->data [i];
571 * mono_bitset_intersection:
572 * @dest: bitset ptr to hold intersection
573 * @src: bitset ptr to copy
575 * Make intersection of one bitset and another.
578 mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
581 g_assert (src->size <= dest->size);
583 size = dest->size / BITS_PER_CHUNK;
584 for (i = 0; i < size; ++i)
585 dest->data [i] &= src->data [i];
589 * mono_bitset_intersection_2:
590 * @dest: bitset ptr to hold intersection
591 * @src1: first bitset
592 * @src2: second bitset
594 * Make intersection of two bitsets
597 mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
600 g_assert (src1->size <= dest->size);
601 g_assert (src2->size <= dest->size);
603 size = dest->size / BITS_PER_CHUNK;
604 for (i = 0; i < size; ++i)
605 dest->data [i] = src1->data [i] & src2->data [i];
610 * @dest: bitset ptr to hold bitset - src
611 * @src: bitset ptr to copy
613 * Unset all bits in dest, which are set in src.
616 mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
619 g_assert (src->size <= dest->size);
621 size = src->size / BITS_PER_CHUNK;
622 for (i = 0; i < size; ++i)
623 dest->data [i] &= ~src->data [i];
631 * return TRUE if their size are the same and the same bits are set in
635 mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1) {
637 if (src->size != src1->size)
640 for (i = 0; i < src->size / BITS_PER_CHUNK; ++i)
641 if (src->data [i] != src1->data [i])
647 * mono_bitset_foreach:
649 * @func: Function to call for every set bit
650 * @data: pass this as second arg to func
652 * Calls func for every bit set in bitset. Argument 1 is the number of
653 * the bit set, argument 2 is data
656 mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data)
659 for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
661 for (j = 0; j < BITS_PER_CHUNK; ++j)
662 if (set->data [i] & ((gsize)1 << j))
663 func (j + i * BITS_PER_CHUNK, data);
672 * gcc -g -Wall -DTEST_BITSET -o monobitset monobitset.c `pkg-config --cflags --libs glib-2.0`
676 MonoBitSet *set1, *set2, *set3, *set4;
680 set1 = mono_bitset_new (60, 0);
681 set4 = mono_bitset_new (60, 0);
683 if (mono_bitset_count (set1) != 0)
687 mono_bitset_set (set1, 33);
688 if (mono_bitset_count (set1) != 1)
692 /* g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0)); */
694 if (mono_bitset_find_first (set1, 0) != 33)
698 if (mono_bitset_find_first (set1, 33) != -1)
703 if (mono_bitset_find_first (set1, -100) != 33)
707 if (mono_bitset_find_last (set1, -1) != 33)
711 if (mono_bitset_find_last (set1, 33) != -1)
715 if (mono_bitset_find_last (set1, -100) != 33)
719 if (mono_bitset_find_last (set1, 34) != 33)
724 if (!mono_bitset_test (set1, 33))
728 if (mono_bitset_test (set1, 32) || mono_bitset_test (set1, 34))
732 set2 = mono_bitset_clone (set1, 0);
733 if (mono_bitset_count (set2) != 1)
737 mono_bitset_invert (set2);
738 if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 1))
742 mono_bitset_clear (set2, 10);
743 if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 2))
748 set3 = mono_bitset_clone (set2, 0);
749 mono_bitset_union (set3, set1);
750 if (mono_bitset_count (set3) != (mono_bitset_size (set3) - 1))
754 mono_bitset_clear_all (set2);
755 if (mono_bitset_count (set2) != 0)
759 mono_bitset_invert (set2);
760 if (mono_bitset_count (set2) != mono_bitset_size (set2))
764 mono_bitset_set (set4, 0);
765 mono_bitset_set (set4, 1);
766 mono_bitset_set (set4, 10);
767 if (mono_bitset_count (set4) != 3)
772 for (i = mono_bitset_find_first (set4, -1); i != -1; i = mono_bitset_find_first (set4, i)) {
788 /* g_print ("count got: %d at %d\n", count, i); */
794 if (mono_bitset_find_first (set4, -1) != 0)
799 mono_bitset_set (set4, 31);
800 if (mono_bitset_find_first (set4, 10) != 31)
804 mono_bitset_free (set1);
806 set1 = mono_bitset_new (200, 0);
807 mono_bitset_set (set1, 0);
808 mono_bitset_set (set1, 1);
809 mono_bitset_set (set1, 10);
810 mono_bitset_set (set1, 31);
811 mono_bitset_set (set1, 150);
813 mono_bitset_free (set1);
814 mono_bitset_free (set2);
815 mono_bitset_free (set3);
816 mono_bitset_free (set4);
818 g_print ("total tests passed: %d\n", error - 1);