8 #include "monobitset.h"
11 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
14 * mono_bitset_alloc_size:
15 * \param max_size The number of bits you want to hold
17 * \returns the number of bytes required to hold the bitset.
18 * Useful to allocate it on the stack or with mempool.
19 * Use with \c mono_bitset_mem_new.
22 mono_bitset_alloc_size (guint32 max_size
, guint32 flags
) {
23 guint32 real_size
= (max_size
+ BITS_PER_CHUNK
- 1) / BITS_PER_CHUNK
;
25 return sizeof (MonoBitSet
) + sizeof (gsize
) * (real_size
- MONO_ZERO_LEN_ARRAY
);
30 * \param max_size The numer of bits you want to hold
31 * \param flags bitfield of flags
32 * \returns a bitset of size \p max_size. It must be freed using
33 * \c mono_bitset_free.
36 mono_bitset_new (guint32 max_size
, guint32 flags
) {
37 guint32 real_size
= (max_size
+ BITS_PER_CHUNK
- 1) / BITS_PER_CHUNK
;
40 result
= (MonoBitSet
*) g_malloc0 (sizeof (MonoBitSet
) + sizeof (gsize
) * (real_size
- MONO_ZERO_LEN_ARRAY
));
41 result
->size
= real_size
* BITS_PER_CHUNK
;
42 result
->flags
= flags
;
47 * mono_bitset_mem_new:
48 * \param mem The location the bitset is stored
49 * \param max_size The number of bits you want to hold
50 * \param flags bitfield of flags
52 * Return \p mem, which is now a initialized bitset of size \p max_size. It is
53 * not freed even if called with \c mono_bitset_free. \p mem must be at least
54 * as big as \c mono_bitset_alloc_size returns for the same \p max_size.
57 mono_bitset_mem_new (gpointer mem
, guint32 max_size
, guint32 flags
) {
58 guint32 real_size
= (max_size
+ BITS_PER_CHUNK
- 1) / BITS_PER_CHUNK
;
59 MonoBitSet
*result
= (MonoBitSet
*) mem
;
61 result
->size
= real_size
* BITS_PER_CHUNK
;
62 result
->flags
= flags
| MONO_BITSET_DONT_FREE
;
68 * \param set bitset ptr to free
70 * Free bitset unless flags have \c MONO_BITSET_DONT_FREE set. Does not
71 * free anything if flag \c MONO_BITSET_DONT_FREE is set or bitset was
72 * made with \c mono_bitset_mem_new.
75 mono_bitset_free (MonoBitSet
*set
) {
76 if (set
&& !(set
->flags
& MONO_BITSET_DONT_FREE
))
82 * \param set bitset ptr
83 * \param pos set bit at this pos
85 * Set bit at \p pos, counting from 0.
88 mono_bitset_set (MonoBitSet
*set
, guint32 pos
) {
89 int j
= pos
/ BITS_PER_CHUNK
;
90 int bit
= pos
% BITS_PER_CHUNK
;
92 g_assert (pos
< set
->size
);
94 set
->data
[j
] |= (gsize
)1 << bit
;
99 * \param set bitset ptr
100 * \param pos test bit at this pos
101 * Test bit at \p pos, counting from 0.
102 * \returns a nonzero value if set, 0 otherwise.
105 mono_bitset_test (const MonoBitSet
*set
, guint32 pos
) {
106 int j
= pos
/ BITS_PER_CHUNK
;
107 int bit
= pos
% BITS_PER_CHUNK
;
109 g_return_val_if_fail (pos
< set
->size
, 0);
111 return (set
->data
[j
] & ((gsize
)1 << bit
)) > 0;
115 * mono_bitset_test_bulk:
116 * \param set bitset ptr
117 * \param pos test bit at this pos
118 * \returns 32/64 bits from the bitset, starting from \p 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
];
133 * \param set bitset ptr
134 * \param pos unset bit at this pos
136 * Unset bit at \p 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:
150 * \param set bitset ptr
155 mono_bitset_clear_all (MonoBitSet
*set
) {
156 memset (set
->data
, 0, set
->size
/ 8);
160 * mono_bitset_set_all:
161 * \param set bitset ptr
166 mono_bitset_set_all (MonoBitSet
*set
) {
167 memset (set
->data
, -1, set
->size
/ 8);
171 * mono_bitset_invert:
172 * \param set bitset ptr
177 mono_bitset_invert (MonoBitSet
*set
) {
179 for (i
= 0; i
< set
->size
/ BITS_PER_CHUNK
; ++i
)
180 set
->data
[i
] = ~set
->data
[i
];
185 * \param set bitset ptr
186 * \returns the number of bits this bitset can hold.
189 mono_bitset_size (const MonoBitSet
*set
) {
194 * should test wich version is faster.
200 * \param set bitset ptr
201 * \returns number of bits that are set.
204 mono_bitset_count (const MonoBitSet
*set
)
210 for (i
= 0; i
< set
->size
/ BITS_PER_CHUNK
; ++i
) {
212 #if defined (__GNUC__) && !defined (HOST_WIN32)
213 // The builtins do work on Win32, but can cause a not worthwhile runtime dependency.
214 // See https://github.com/mono/mono/pull/14248.
215 if (sizeof (gsize
) == sizeof (unsigned int))
216 count
+= __builtin_popcount (d
);
218 count
+= __builtin_popcountll (d
);
230 mono_bitset_count (const MonoBitSet
*set
) {
231 static const guint32 table
[] = {
232 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
234 guint32 i
, count
, val
;
237 for (i
= 0; i
< set
->size
/ BITS_PER_CHUNK
;+i
) {
240 val
= (val
& table
[0]) ((val
>> 1) & table
[0]);
241 val
= (val
& table
[1]) ((val
>> 2) & table
[1]);
242 val
= (val
& table
[2]) ((val
>> 4) & table
[2]);
243 val
= (val
& table
[3]) ((val
>> 8) & table
[3]);
244 val
= (val
& table
[4]) ((val
>> 16) & table
[4]);
256 0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8,
257 0xfffffff0, 0xffffffe0, 0xffffffc0, 0xffffff80,
258 0xffffff00, 0xfffffe00, 0xfffffc00, 0xfffff800,
259 0xfffff000, 0xffffe000, 0xffffc000, 0xffff8000,
260 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
261 0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
262 0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
263 0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
267 #define my_g_bit_nth_lsf(m,n) (ffs((m) & bitstart_mask [(n)+1])-1)
268 #define my_g_bit_nth_lsf_nomask(m) (ffs((m))-1)
273 my_g_bit_nth_lsf (gsize mask
, gint nth_bit
)
278 if ((mask
== 0) || (nth_bit
== BITS_PER_CHUNK
))
281 #if (defined(__i386__) && defined(__GNUC__))
284 /* This depends on mask != 0 */
285 __asm__("bsfl %1,%0\n\t"
286 : "=r" (r
) : "g" (mask
));
289 #elif defined(__x86_64) && defined(__GNUC__)
293 __asm__("bsfq %1,%0\n\t"
294 : "=r" (r
) : "rm" (mask
));
298 while (! (mask
& 0x1)) {
308 my_g_bit_nth_lsf_nomask (gsize mask
)
310 /* Mask is expected to be != 0 */
311 #if (defined(__i386__) && defined(__GNUC__))
314 __asm__("bsfl %1,%0\n\t"
315 : "=r" (r
) : "rm" (mask
));
317 #elif defined(__x86_64) && defined(__GNUC__)
320 __asm__("bsfq %1,%0\n\t"
321 : "=r" (r
) : "rm" (mask
));
326 while (! (mask
& 0x1)) {
338 my_g_bit_nth_msf (gsize mask
,
346 mask
<<= BITS_PER_CHUNK
- nth_bit
;
349 while ((i
> 0) && !(mask
>> (BITS_PER_CHUNK
- 8))) {
358 if (mask
& ((gsize
)1 << (BITS_PER_CHUNK
- 1)))
359 return i
- (BITS_PER_CHUNK
- nth_bit
);
368 find_first_unset (gsize mask
, gint nth_bit
)
372 if (!(mask
& ((gsize
)1 << nth_bit
))) {
373 if (nth_bit
== BITS_PER_CHUNK
)
374 /* On 64 bit platforms, 1 << 64 == 1 */
379 } while (nth_bit
< BITS_PER_CHUNK
);
384 * mono_bitset_find_start:
385 * \param set bitset ptr
386 * Equivalent to <code>mono_bitset_find_first (set, -1)</code> but faster.
389 mono_bitset_find_start (const MonoBitSet
*set
)
393 for (i
= 0; i
< set
->size
/ BITS_PER_CHUNK
; ++i
) {
395 return my_g_bit_nth_lsf_nomask (set
->data
[i
]) + i
* BITS_PER_CHUNK
;
401 * mono_bitset_find_first:
402 * \param set bitset ptr
403 * \param pos pos to search after (not including)
404 * \returns position of first set bit after \p pos. If \p pos < 0, begin search from
405 * start. Return \c -1 if no bit set is found.
408 mono_bitset_find_first (const MonoBitSet
*set
, gint pos
) {
417 j
= pos
/ BITS_PER_CHUNK
;
418 bit
= pos
% BITS_PER_CHUNK
;
419 g_assert (pos
< set
->size
);
421 /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
424 result
= my_g_bit_nth_lsf (set
->data
[j
], bit
);
426 return result
+ j
* BITS_PER_CHUNK
;
428 for (i
= ++j
; i
< set
->size
/ BITS_PER_CHUNK
; ++i
) {
430 return my_g_bit_nth_lsf (set
->data
[i
], -1) + i
* BITS_PER_CHUNK
;
436 * mono_bitset_find_last:
437 * \param set bitset ptr
438 * \param pos pos to search before (not including)
439 * \returns position of last set bit before \p pos. If \p pos < 0 search is
440 * started from the end. Returns \c -1 if no set bit is found.
443 mono_bitset_find_last (const MonoBitSet
*set
, gint pos
) {
444 int j
, bit
, result
, i
;
449 j
= pos
/ BITS_PER_CHUNK
;
450 bit
= pos
% BITS_PER_CHUNK
;
452 g_return_val_if_fail (pos
< set
->size
, -1);
455 result
= my_g_bit_nth_msf (set
->data
[j
], bit
);
457 return result
+ j
* BITS_PER_CHUNK
;
459 for (i
= --j
; i
>= 0; --i
) {
461 return my_g_bit_nth_msf (set
->data
[i
], BITS_PER_CHUNK
) + i
* BITS_PER_CHUNK
;
467 * mono_bitset_find_first_unset:
468 * \param set bitset ptr
469 * \param pos pos to search after (not including)
470 * \returns position of first unset bit after \p pos. If \p pos < 0 begin search from
471 * start. Return \c -1 if no bit set is found.
474 mono_bitset_find_first_unset (const MonoBitSet
*set
, gint pos
) {
483 j
= pos
/ BITS_PER_CHUNK
;
484 bit
= pos
% BITS_PER_CHUNK
;
485 g_return_val_if_fail (pos
< set
->size
, -1);
487 /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
489 if (set
->data
[j
] != -1) {
490 result
= find_first_unset (set
->data
[j
], bit
);
492 return result
+ j
* BITS_PER_CHUNK
;
494 for (i
= ++j
; i
< set
->size
/ BITS_PER_CHUNK
; ++i
) {
495 if (set
->data
[i
] != -1) {
496 return find_first_unset (set
->data
[i
], -1) + i
* BITS_PER_CHUNK
;
504 * \param set bitset ptr to clone
505 * \param new_size number of bits the cloned bitset can hold
506 * \returns a cloned bitset of size \p new_size. \c MONO_BITSET_DONT_FREE
507 * unset in cloned bitset. If \p new_size is 0, the cloned object is just
511 mono_bitset_clone (const MonoBitSet
*set
, guint32 new_size
) {
515 new_size
= set
->size
;
516 result
= mono_bitset_new (new_size
, set
->flags
);
517 result
->flags
&= ~MONO_BITSET_DONT_FREE
;
518 memcpy (result
->data
, set
->data
, set
->size
/ 8);
523 * mono_bitset_copyto:
524 * \param src bitset ptr to copy from
525 * \param dest bitset ptr to copy to
527 * Copy one bitset to another.
530 mono_bitset_copyto (const MonoBitSet
*src
, MonoBitSet
*dest
) {
531 g_assert (dest
->size
<= src
->size
);
533 memcpy (&dest
->data
, &src
->data
, dest
->size
/ 8);
538 * \param dest bitset ptr to hold union
539 * \param src bitset ptr to copy
541 * Make union of one bitset and another.
544 mono_bitset_union (MonoBitSet
*dest
, const MonoBitSet
*src
) {
547 g_assert (src
->size
<= dest
->size
);
549 size
= dest
->size
/ BITS_PER_CHUNK
;
550 for (i
= 0; i
< size
; ++i
)
551 dest
->data
[i
] |= src
->data
[i
];
555 * mono_bitset_intersection:
556 * \param dest bitset ptr to hold intersection
557 * \param src bitset ptr to copy
559 * Make intersection of one bitset and another.
562 mono_bitset_intersection (MonoBitSet
*dest
, const MonoBitSet
*src
) {
565 g_assert (src
->size
<= dest
->size
);
567 size
= dest
->size
/ BITS_PER_CHUNK
;
568 for (i
= 0; i
< size
; ++i
)
569 dest
->data
[i
] &= src
->data
[i
];
573 * mono_bitset_intersection_2:
574 * \param dest bitset ptr to hold intersection
575 * \param src1 first bitset
576 * \param src2 second bitset
578 * Make intersection of two bitsets
581 mono_bitset_intersection_2 (MonoBitSet
*dest
, const MonoBitSet
*src1
, const MonoBitSet
*src2
) {
584 g_assert (src1
->size
<= dest
->size
);
585 g_assert (src2
->size
<= dest
->size
);
587 size
= dest
->size
/ BITS_PER_CHUNK
;
588 for (i
= 0; i
< size
; ++i
)
589 dest
->data
[i
] = src1
->data
[i
] & src2
->data
[i
];
594 * \param dest bitset ptr to hold bitset - src
595 * \param src bitset ptr to copy
597 * Unset all bits in \p dest that are set in \p src.
600 mono_bitset_sub (MonoBitSet
*dest
, const MonoBitSet
*src
) {
603 g_assert (src
->size
<= dest
->size
);
605 size
= src
->size
/ BITS_PER_CHUNK
;
606 for (i
= 0; i
< size
; ++i
)
607 dest
->data
[i
] &= ~src
->data
[i
];
612 * \param src bitset ptr
613 * \param src1 bitset ptr
614 * \returns TRUE if their size are the same and the same bits are set in
618 mono_bitset_equal (const MonoBitSet
*src
, const MonoBitSet
*src1
) {
620 if (src
->size
!= src1
->size
)
623 for (i
= 0; i
< src
->size
/ BITS_PER_CHUNK
; ++i
)
624 if (src
->data
[i
] != src1
->data
[i
])
630 * mono_bitset_foreach:
631 * \param set bitset ptr
632 * \param func Function to call for every set bit
633 * \param data pass this as second arg to func
634 * Calls \p func for every bit set in bitset. Argument 1 is the number of
635 * the bit set, argument 2 is data
638 mono_bitset_foreach (MonoBitSet
*set
, MonoBitSetFunc func
, gpointer data
)
641 for (i
= 0; i
< set
->size
/ BITS_PER_CHUNK
; ++i
) {
643 for (j
= 0; j
< BITS_PER_CHUNK
; ++j
)
644 if (set
->data
[i
] & ((gsize
)1 << j
))
645 func (j
+ i
* BITS_PER_CHUNK
, data
);
651 mono_bitset_test_safe (const MonoBitSet
*set
, guint32 pos
)
653 return set
&& set
->size
> pos
&& mono_bitset_test (set
, pos
);
660 * gcc -g -Wall -DTEST_BITSET -o monobitset monobitset.c `pkg-config --cflags --libs glib-2.0`
664 MonoBitSet
*set1
, *set2
, *set3
, *set4
;
668 set1
= mono_bitset_new (60, 0);
669 set4
= mono_bitset_new (60, 0);
671 if (mono_bitset_count (set1
) != 0)
675 mono_bitset_set (set1
, 33);
676 if (mono_bitset_count (set1
) != 1)
680 /* g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0)); */
682 if (mono_bitset_find_first (set1
, 0) != 33)
686 if (mono_bitset_find_first (set1
, 33) != -1)
691 if (mono_bitset_find_first (set1
, -100) != 33)
695 if (mono_bitset_find_last (set1
, -1) != 33)
699 if (mono_bitset_find_last (set1
, 33) != -1)
703 if (mono_bitset_find_last (set1
, -100) != 33)
707 if (mono_bitset_find_last (set1
, 34) != 33)
712 if (!mono_bitset_test (set1
, 33))
716 if (mono_bitset_test (set1
, 32) || mono_bitset_test (set1
, 34))
720 set2
= mono_bitset_clone (set1
, 0);
721 if (mono_bitset_count (set2
) != 1)
725 mono_bitset_invert (set2
);
726 if (mono_bitset_count (set2
) != (mono_bitset_size (set2
) - 1))
730 mono_bitset_clear (set2
, 10);
731 if (mono_bitset_count (set2
) != (mono_bitset_size (set2
) - 2))
736 set3
= mono_bitset_clone (set2
, 0);
737 mono_bitset_union (set3
, set1
);
738 if (mono_bitset_count (set3
) != (mono_bitset_size (set3
) - 1))
742 mono_bitset_clear_all (set2
);
743 if (mono_bitset_count (set2
) != 0)
747 mono_bitset_invert (set2
);
748 if (mono_bitset_count (set2
) != mono_bitset_size (set2
))
752 mono_bitset_set (set4
, 0);
753 mono_bitset_set (set4
, 1);
754 mono_bitset_set (set4
, 10);
755 if (mono_bitset_count (set4
) != 3)
760 for (i
= mono_bitset_find_first (set4
, -1); i
!= -1; i
= mono_bitset_find_first (set4
, i
)) {
776 /* g_print ("count got: %d at %d\n", count, i); */
782 if (mono_bitset_find_first (set4
, -1) != 0)
787 mono_bitset_set (set4
, 31);
788 if (mono_bitset_find_first (set4
, 10) != 31)
792 mono_bitset_free (set1
);
794 set1
= mono_bitset_new (200, 0);
795 mono_bitset_set (set1
, 0);
796 mono_bitset_set (set1
, 1);
797 mono_bitset_set (set1
, 10);
798 mono_bitset_set (set1
, 31);
799 mono_bitset_set (set1
, 150);
801 mono_bitset_free (set1
);
802 mono_bitset_free (set2
);
803 mono_bitset_free (set3
);
804 mono_bitset_free (set4
);
806 g_print ("total tests passed: %d\n", error
- 1);