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 = (MonoBitSet *) 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 = (MonoBitSet *) 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) {
214 if (sizeof (gsize) == sizeof (unsigned long))
215 count += __builtin_popcountl (d);
217 count += __builtin_popcount (d);
229 mono_bitset_count (const MonoBitSet *set) {
230 static const guint32 table [] = {
231 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
233 guint32 i, count, val;
236 for (i = 0; i < set->size / BITS_PER_CHUNK;+i) {
239 val = (val & table [0]) ((val >> 1) & table [0]);
240 val = (val & table [1]) ((val >> 2) & table [1]);
241 val = (val & table [2]) ((val >> 4) & table [2]);
242 val = (val & table [3]) ((val >> 8) & table [3]);
243 val = (val & table [4]) ((val >> 16) & table [4]);
255 0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8,
256 0xfffffff0, 0xffffffe0, 0xffffffc0, 0xffffff80,
257 0xffffff00, 0xfffffe00, 0xfffffc00, 0xfffff800,
258 0xfffff000, 0xffffe000, 0xffffc000, 0xffff8000,
259 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
260 0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
261 0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
262 0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
266 #define my_g_bit_nth_lsf(m,n) (ffs((m) & bitstart_mask [(n)+1])-1)
267 #define my_g_bit_nth_lsf_nomask(m) (ffs((m))-1)
272 my_g_bit_nth_lsf (gsize mask, gint nth_bit)
277 if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
280 #if defined(__native_client__) && (defined(__i386__) || defined(__x86_64))
281 #define USE_X86_32BIT_INSTRUCTIONS 1
284 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
287 /* This depends on mask != 0 */
288 __asm__("bsfl %1,%0\n\t"
289 : "=r" (r) : "g" (mask));
292 #elif defined(__x86_64) && defined(__GNUC__)
296 __asm__("bsfq %1,%0\n\t"
297 : "=r" (r) : "rm" (mask));
301 while (! (mask & 0x1)) {
311 my_g_bit_nth_lsf_nomask (gsize mask)
313 /* Mask is expected to be != 0 */
314 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
317 __asm__("bsfl %1,%0\n\t"
318 : "=r" (r) : "rm" (mask));
320 #elif defined(__x86_64) && defined(__GNUC__)
323 __asm__("bsfq %1,%0\n\t"
324 : "=r" (r) : "rm" (mask));
329 while (! (mask & 0x1)) {
341 my_g_bit_nth_msf (gsize mask,
349 mask <<= BITS_PER_CHUNK - nth_bit;
352 while ((i > 0) && !(mask >> (BITS_PER_CHUNK - 8))) {
361 if (mask & ((gsize)1 << (BITS_PER_CHUNK - 1)))
362 return i - (BITS_PER_CHUNK - nth_bit);
371 find_first_unset (gsize mask, gint nth_bit)
375 if (!(mask & ((gsize)1 << nth_bit))) {
376 if (nth_bit == BITS_PER_CHUNK)
377 /* On 64 bit platforms, 1 << 64 == 1 */
382 } while (nth_bit < BITS_PER_CHUNK);
387 * mono_bitset_find_start:
390 * Equivalent to mono_bitset_find_first (set, -1) but faster.
393 mono_bitset_find_start (const MonoBitSet *set)
397 for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
399 return my_g_bit_nth_lsf_nomask (set->data [i]) + i * BITS_PER_CHUNK;
405 * mono_bitset_find_first:
407 * @pos: pos to search _after_ (not including)
409 * Returns position of first set bit after @pos. If pos < 0 begin search from
410 * start. Return -1 if no bit set is found.
413 mono_bitset_find_first (const MonoBitSet *set, gint pos) {
422 j = pos / BITS_PER_CHUNK;
423 bit = pos % BITS_PER_CHUNK;
424 g_assert (pos < set->size);
426 /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
429 result = my_g_bit_nth_lsf (set->data [j], bit);
431 return result + j * BITS_PER_CHUNK;
433 for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
435 return my_g_bit_nth_lsf (set->data [i], -1) + i * BITS_PER_CHUNK;
441 * mono_bitset_find_last:
443 * @pos: pos to search _before_ (not including)
445 * Returns position of last set bit before pos. If pos < 0 search is
446 * started from the end. Returns -1 if no set bit is found.
449 mono_bitset_find_last (const MonoBitSet *set, gint pos) {
450 int j, bit, result, i;
455 j = pos / BITS_PER_CHUNK;
456 bit = pos % BITS_PER_CHUNK;
458 g_return_val_if_fail (pos < set->size, -1);
461 result = my_g_bit_nth_msf (set->data [j], bit);
463 return result + j * BITS_PER_CHUNK;
465 for (i = --j; i >= 0; --i) {
467 return my_g_bit_nth_msf (set->data [i], BITS_PER_CHUNK) + i * BITS_PER_CHUNK;
473 * mono_bitset_find_first_unset:
475 * @pos: pos to search _after_ (not including)
477 * Returns position of first unset bit after @pos. If pos < 0 begin search from
478 * start. Return -1 if no bit set is found.
481 mono_bitset_find_first_unset (const MonoBitSet *set, gint pos) {
490 j = pos / BITS_PER_CHUNK;
491 bit = pos % BITS_PER_CHUNK;
492 g_return_val_if_fail (pos < set->size, -1);
494 /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
496 if (set->data [j] != -1) {
497 result = find_first_unset (set->data [j], bit);
499 return result + j * BITS_PER_CHUNK;
501 for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
502 if (set->data [i] != -1) {
503 return find_first_unset (set->data [i], -1) + i * BITS_PER_CHUNK;
511 * @set: bitset ptr to clone
512 * @new_size: number of bits the cloned bitset can hold
514 * Return a cloned bitset of size new_size. MONO_BITSET_DONT_FREE
515 * unset in cloned bitset. If new_size is 0, the cloned object is just
519 mono_bitset_clone (const MonoBitSet *set, guint32 new_size) {
523 new_size = set->size;
524 result = mono_bitset_new (new_size, set->flags);
525 result->flags &= ~MONO_BITSET_DONT_FREE;
526 memcpy (result->data, set->data, set->size / 8);
531 * mono_bitset_copyto:
532 * @src: bitset ptr to copy from
533 * @dest: bitset ptr to copy to
535 * Copy one bitset to another.
538 mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
539 g_assert (dest->size <= src->size);
541 memcpy (&dest->data, &src->data, dest->size / 8);
546 * @dest: bitset ptr to hold union
547 * @src: bitset ptr to copy
549 * Make union of one bitset and another.
552 mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
555 g_assert (src->size <= dest->size);
557 size = dest->size / BITS_PER_CHUNK;
558 for (i = 0; i < size; ++i)
559 dest->data [i] |= src->data [i];
563 * mono_bitset_intersection:
564 * @dest: bitset ptr to hold intersection
565 * @src: bitset ptr to copy
567 * Make intersection of one bitset and another.
570 mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
573 g_assert (src->size <= dest->size);
575 size = dest->size / BITS_PER_CHUNK;
576 for (i = 0; i < size; ++i)
577 dest->data [i] &= src->data [i];
581 * mono_bitset_intersection_2:
582 * @dest: bitset ptr to hold intersection
583 * @src1: first bitset
584 * @src2: second bitset
586 * Make intersection of two bitsets
589 mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
592 g_assert (src1->size <= dest->size);
593 g_assert (src2->size <= dest->size);
595 size = dest->size / BITS_PER_CHUNK;
596 for (i = 0; i < size; ++i)
597 dest->data [i] = src1->data [i] & src2->data [i];
602 * @dest: bitset ptr to hold bitset - src
603 * @src: bitset ptr to copy
605 * Unset all bits in dest, which are set in src.
608 mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
611 g_assert (src->size <= dest->size);
613 size = src->size / BITS_PER_CHUNK;
614 for (i = 0; i < size; ++i)
615 dest->data [i] &= ~src->data [i];
623 * return TRUE if their size are the same and the same bits are set in
627 mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1) {
629 if (src->size != src1->size)
632 for (i = 0; i < src->size / BITS_PER_CHUNK; ++i)
633 if (src->data [i] != src1->data [i])
639 * mono_bitset_foreach:
641 * @func: Function to call for every set bit
642 * @data: pass this as second arg to func
644 * Calls func for every bit set in bitset. Argument 1 is the number of
645 * the bit set, argument 2 is data
648 mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data)
651 for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
653 for (j = 0; j < BITS_PER_CHUNK; ++j)
654 if (set->data [i] & ((gsize)1 << j))
655 func (j + i * BITS_PER_CHUNK, data);
664 * gcc -g -Wall -DTEST_BITSET -o monobitset monobitset.c `pkg-config --cflags --libs glib-2.0`
668 MonoBitSet *set1, *set2, *set3, *set4;
672 set1 = mono_bitset_new (60, 0);
673 set4 = mono_bitset_new (60, 0);
675 if (mono_bitset_count (set1) != 0)
679 mono_bitset_set (set1, 33);
680 if (mono_bitset_count (set1) != 1)
684 /* g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0)); */
686 if (mono_bitset_find_first (set1, 0) != 33)
690 if (mono_bitset_find_first (set1, 33) != -1)
695 if (mono_bitset_find_first (set1, -100) != 33)
699 if (mono_bitset_find_last (set1, -1) != 33)
703 if (mono_bitset_find_last (set1, 33) != -1)
707 if (mono_bitset_find_last (set1, -100) != 33)
711 if (mono_bitset_find_last (set1, 34) != 33)
716 if (!mono_bitset_test (set1, 33))
720 if (mono_bitset_test (set1, 32) || mono_bitset_test (set1, 34))
724 set2 = mono_bitset_clone (set1, 0);
725 if (mono_bitset_count (set2) != 1)
729 mono_bitset_invert (set2);
730 if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 1))
734 mono_bitset_clear (set2, 10);
735 if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 2))
740 set3 = mono_bitset_clone (set2, 0);
741 mono_bitset_union (set3, set1);
742 if (mono_bitset_count (set3) != (mono_bitset_size (set3) - 1))
746 mono_bitset_clear_all (set2);
747 if (mono_bitset_count (set2) != 0)
751 mono_bitset_invert (set2);
752 if (mono_bitset_count (set2) != mono_bitset_size (set2))
756 mono_bitset_set (set4, 0);
757 mono_bitset_set (set4, 1);
758 mono_bitset_set (set4, 10);
759 if (mono_bitset_count (set4) != 3)
764 for (i = mono_bitset_find_first (set4, -1); i != -1; i = mono_bitset_find_first (set4, i)) {
780 /* g_print ("count got: %d at %d\n", count, i); */
786 if (mono_bitset_find_first (set4, -1) != 0)
791 mono_bitset_set (set4, 31);
792 if (mono_bitset_find_first (set4, 10) != 31)
796 mono_bitset_free (set1);
798 set1 = mono_bitset_new (200, 0);
799 mono_bitset_set (set1, 0);
800 mono_bitset_set (set1, 1);
801 mono_bitset_set (set1, 10);
802 mono_bitset_set (set1, 31);
803 mono_bitset_set (set1, 150);
805 mono_bitset_free (set1);
806 mono_bitset_free (set2);
807 mono_bitset_free (set3);
808 mono_bitset_free (set4);
810 g_print ("total tests passed: %d\n", error - 1);