mono/utils/monobitset.c

   1 /**
   2  * \file
   3  */
   4
   5 #include <glib.h>
   6 #include <string.h>
   7
   8 #include "monobitset.h"
   9 #include "config.h"
  10
  11 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
  12
  13 /*
  14  * mono_bitset_alloc_size:
  15  * @max_size: The number of bits you want to hold
  16  * @flags: unused
  17  *
  18  * Return the number of bytes required to hold the bitset.
  19  * Useful to allocate it on the stack or with mempool.
  20  * Use with mono_bitset_mem_new ().
  21  */
  22 guint32
  23 mono_bitset_alloc_size (guint32 max_size, guint32 flags) {
  24         guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
  25
  26         return sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY);
  27 }
  28
  29 /*
  30  * mono_bitset_new:
  31  * @max_size: The numer of bits you want to hold
  32  * @flags: bitfield of flags
  33  *
  34  * Return a bitset of size max_size. It must be freed using
  35  * mono_bitset_free.
  36  */
  37 MonoBitSet *
  38 mono_bitset_new (guint32 max_size, guint32 flags) {
  39         guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
  40         MonoBitSet *result;
  41
  42         result = (MonoBitSet *) g_malloc0 (sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY));
  43         result->size = real_size * BITS_PER_CHUNK;
  44         result->flags = flags;
  45         return result;
  46 }
  47
  48 /*
  49  * mono_bitset_mem_new:
  50  * @mem: The location the bitset is stored
  51  * @max_size: The number of bits you want to hold
  52  * @flags: bitfield of flags
  53  *
  54  * Return mem, which is now a initialized bitset of size max_size. It is
  55  * not freed even if called with mono_bitset_free. mem must be at least
  56  * as big as mono_bitset_alloc_size returns for the same max_size.
  57  */
  58 MonoBitSet *
  59 mono_bitset_mem_new (gpointer mem, guint32 max_size, guint32 flags) {
  60         guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
  61         MonoBitSet *result = (MonoBitSet *) mem;
  62
  63         result->size = real_size * BITS_PER_CHUNK;
  64         result->flags = flags | MONO_BITSET_DONT_FREE;
  65         return result;
  66 }
  67
  68 /*
  69  * mono_bitset_free:
  70  * @set: bitset ptr to free
  71  *
  72  * Free bitset unless flags have MONO_BITSET_DONT_FREE set. Does not
  73  * free anything if flag MONO_BITSET_DONT_FREE is set or bitset was
  74  * made with mono_bitset_mem_new.
  75  */
  76 void
  77 mono_bitset_free (MonoBitSet *set) {
  78         if (!(set->flags & MONO_BITSET_DONT_FREE))
  79                 g_free (set);
  80 }
  81
  82 /*
  83  * mono_bitset_set:
  84  * @set: bitset ptr
  85  * @pos: set bit at this pos
  86  *
  87  * Set bit at pos @pos, counting from 0.
  88  */
  89 void
  90 mono_bitset_set (MonoBitSet *set, guint32 pos) {
  91         int j = pos / BITS_PER_CHUNK;
  92         int bit = pos % BITS_PER_CHUNK;
  93
  94         g_assert (pos < set->size);
  95
  96         set->data [j] |= (gsize)1 << bit;
  97 }
  98
  99 /*
 100  * mono_bitset_test:
 101  * @set: bitset ptr
 102  * @pos: test bit at this pos
 103  *
 104  * Test bit at pos @pos, counting from 0.
 105  * Returns a value != 0 if set, 0 otherwise.
 106  */
 107 int
 108 mono_bitset_test (const MonoBitSet *set, guint32 pos) {
 109         int j = pos / BITS_PER_CHUNK;
 110         int bit = pos % BITS_PER_CHUNK;
 111
 112         g_return_val_if_fail (pos < set->size, 0);
 113
 114         return (set->data [j] & ((gsize)1 << bit)) > 0;
 115 }
 116
 117 /*
 118  * mono_bitset_test_bulk:
 119  * @set: bitset ptr
 120  * @pos: test bit at this pos
 121  *
 122  * Return 32/64 bits from the bitset, starting from @pos, which must be
 123  * divisible with 32/64.
 124  */
 125 gsize
 126 mono_bitset_test_bulk (const MonoBitSet *set, guint32 pos) {
 127         int j = pos / BITS_PER_CHUNK;
 128
 129         if (pos >= set->size)
 130                 return 0;
 131         else
 132                 return set->data [j];
 133 }
 134
 135 /*
 136  * mono_bitset_clear:
 137  * @set: bitset ptr
 138  * @pos: unset bit at this pos
 139  *
 140  * Unset bit at pos 'pos', counting from 0.
 141  */
 142 void
 143 mono_bitset_clear (MonoBitSet *set, guint32 pos) {
 144         int j = pos / BITS_PER_CHUNK;
 145         int bit = pos % BITS_PER_CHUNK;
 146
 147         g_assert (pos < set->size);
 148
 149         set->data [j] &= ~((gsize)1 << bit);
 150 }
 151
 152 /*
 153  * mono_bitset_clear_all:
 154  * @set: bitset ptr
 155  *
 156  * Unset all bits.
 157  */
 158 void
 159 mono_bitset_clear_all (MonoBitSet *set) {
 160         memset (set->data, 0, set->size / 8);
 161 }
 162
 163 /*
 164  * mono_bitset_set_all:
 165  * @set: bitset ptr
 166  *
 167  * Set all bits.
 168  */
 169 void
 170 mono_bitset_set_all (MonoBitSet *set) {
 171         memset (set->data, -1, set->size / 8);
 172 }
 173
 174 /*
 175  * mono_bitset_invert:
 176  * @set: bitset ptr
 177  *
 178  * Flip all bits.
 179  */
 180 void
 181 mono_bitset_invert (MonoBitSet *set) {
 182         int i;
 183         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i)
 184                 set->data [i] = ~set->data [i];
 185 }
 186
 187 /*
 188  * mono_bitset_size:
 189  * @set: bitset ptr
 190  *
 191  * Returns the number of bits this bitset can hold.
 192  */
 193 guint32
 194 mono_bitset_size (const MonoBitSet *set) {
 195         return set->size;
 196 }
 197
 198 /*
 199  * should test wich version is faster.
 200  */
 201 #if 1
 202
 203 /*
 204  * mono_bitset_count:
 205  * @set: bitset ptr
 206  *
 207  * return number of bits that is set.
 208  */
 209 guint32
 210 mono_bitset_count (const MonoBitSet *set) {
 211         guint32 i, count;
 212         gsize d;
 213
 214         count = 0;
 215         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 216                 d = set->data [i];
 217 #ifdef __GNUC__
 218                 if (sizeof (gsize) == sizeof (unsigned int))
 219                         count += __builtin_popcount (d);
 220                 else
 221                         count += __builtin_popcountll (d);
 222 #else
 223                 while (d) {
 224                         count ++;
 225                         d &= (d - 1);
 226                 }
 227 #endif
 228         }
 229         return count;
 230 }
 231 #else
 232 guint32
 233 mono_bitset_count (const MonoBitSet *set) {
 234         static const guint32 table [] = {
 235                 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
 236         };
 237         guint32 i, count, val;
 238
 239         count = 0;
 240         for (i = 0; i < set->size / BITS_PER_CHUNK;+i) {
 241                 if (set->data [i]) {
 242                         val = set->data [i];
 243                         val = (val & table [0]) ((val >> 1) & table [0]);
 244                         val = (val & table [1]) ((val >> 2) & table [1]);
 245                         val = (val & table [2]) ((val >> 4) & table [2]);
 246                         val = (val & table [3]) ((val >> 8) & table [3]);
 247                         val = (val & table [4]) ((val >> 16) & table [4]);
 248                         count += val;
 249                 }
 250         }
 251         return count;
 252 }
 253
 254 #endif
 255
 256 #if 0
 257 const static int
 258 bitstart_mask [] = {
 259         0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8,
 260         0xfffffff0, 0xffffffe0, 0xffffffc0, 0xffffff80,
 261         0xffffff00, 0xfffffe00, 0xfffffc00, 0xfffff800,
 262         0xfffff000, 0xffffe000, 0xffffc000, 0xffff8000,
 263         0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
 264         0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
 265         0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
 266         0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
 267         0x00000000
 268 };
 269
 270 #define my_g_bit_nth_lsf(m,n) (ffs((m) & bitstart_mask [(n)+1])-1)
 271 #define my_g_bit_nth_lsf_nomask(m) (ffs((m))-1)
 272
 273 #else
 274
 275 static inline gint
 276 my_g_bit_nth_lsf (gsize mask, gint nth_bit)
 277 {
 278         nth_bit ++;
 279         mask >>= nth_bit;
 280
 281         if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
 282                 return -1;
 283
 284 #if defined(__native_client__) && (defined(__i386__) || defined(__x86_64))
 285 #define USE_X86_32BIT_INSTRUCTIONS 1
 286 #endif
 287
 288 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
 289  {
 290          int r;
 291          /* This depends on mask != 0 */
 292          __asm__("bsfl %1,%0\n\t"
 293                          : "=r" (r) : "g" (mask));
 294          return nth_bit + r;
 295  }
 296 #elif defined(__x86_64) && defined(__GNUC__)
 297  {
 298         guint64 r;
 299
 300         __asm__("bsfq %1,%0\n\t"
 301                         : "=r" (r) : "rm" (mask));
 302         return nth_bit + r;
 303  }
 304 #else
 305         while (! (mask & 0x1)) {
 306                 mask >>= 1;
 307                 nth_bit ++;
 308         }
 309
 310         return nth_bit;
 311 #endif
 312 }
 313
 314 static inline gint
 315 my_g_bit_nth_lsf_nomask (gsize mask)
 316 {
 317         /* Mask is expected to be != 0 */
 318 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
 319         int r;
 320
 321         __asm__("bsfl %1,%0\n\t"
 322                         : "=r" (r) : "rm" (mask));
 323         return r;
 324 #elif defined(__x86_64) && defined(__GNUC__)
 325         guint64 r;
 326
 327         __asm__("bsfq %1,%0\n\t"
 328                         : "=r" (r) : "rm" (mask));
 329         return r;
 330 #else
 331         int nth_bit = 0;
 332
 333         while (! (mask & 0x1)) {
 334                 mask >>= 1;
 335                 nth_bit ++;
 336         }
 337
 338         return nth_bit;
 339 #endif
 340 }
 341
 342 #endif
 343
 344 static inline int
 345 my_g_bit_nth_msf (gsize mask,
 346                gint   nth_bit)
 347 {
 348         int i;
 349
 350         if (nth_bit == 0)
 351                 return -1;
 352
 353         mask <<= BITS_PER_CHUNK - nth_bit;
 354
 355         i = BITS_PER_CHUNK;
 356         while ((i > 0) && !(mask >> (BITS_PER_CHUNK - 8))) {
 357                 mask <<= 8;
 358                 i -= 8;
 359         }
 360         if (mask == 0)
 361                 return -1;
 362
 363         do {
 364                 i--;
 365                 if (mask & ((gsize)1 << (BITS_PER_CHUNK - 1)))
 366                         return i - (BITS_PER_CHUNK - nth_bit);
 367                 mask <<= 1;
 368     }
 369         while (mask);
 370
 371         return -1;
 372 }
 373
 374 static int
 375 find_first_unset (gsize mask, gint nth_bit)
 376 {
 377         do {
 378                 nth_bit++;
 379                 if (!(mask & ((gsize)1 << nth_bit))) {
 380                         if (nth_bit == BITS_PER_CHUNK)
 381                                 /* On 64 bit platforms, 1 << 64 == 1 */
 382                                 return -1;
 383                         else
 384                                 return nth_bit;
 385                 }
 386         } while (nth_bit < BITS_PER_CHUNK);
 387         return -1;
 388 }
 389
 390 /*
 391  * mono_bitset_find_start:
 392  * @set: bitset ptr
 393  *
 394  * Equivalent to mono_bitset_find_first (set, -1) but faster.
 395  */
 396 int
 397 mono_bitset_find_start   (const MonoBitSet *set)
 398 {
 399         int i;
 400
 401         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 402                 if (set->data [i])
 403                         return my_g_bit_nth_lsf_nomask (set->data [i]) + i * BITS_PER_CHUNK;
 404         }
 405         return -1;
 406 }
 407
 408 /*
 409  * mono_bitset_find_first:
 410  * @set: bitset ptr
 411  * @pos: pos to search _after_ (not including)
 412  *
 413  * Returns position of first set bit after @pos. If pos < 0 begin search from
 414  * start. Return -1 if no bit set is found.
 415  */
 416 int
 417 mono_bitset_find_first (const MonoBitSet *set, gint pos) {
 418         int j;
 419         int bit;
 420         int result, i;
 421
 422         if (pos < 0) {
 423                 j = 0;
 424                 bit = -1;
 425         } else {
 426                 j = pos / BITS_PER_CHUNK;
 427                 bit = pos % BITS_PER_CHUNK;
 428                 g_assert (pos < set->size);
 429         }
 430         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 431
 432         if (set->data [j]) {
 433                 result = my_g_bit_nth_lsf (set->data [j], bit);
 434                 if (result != -1)
 435                         return result + j * BITS_PER_CHUNK;
 436         }
 437         for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
 438                 if (set->data [i])
 439                         return my_g_bit_nth_lsf (set->data [i], -1) + i * BITS_PER_CHUNK;
 440         }
 441         return -1;
 442 }
 443
 444 /*
 445  * mono_bitset_find_last:
 446  * @set: bitset ptr
 447  * @pos: pos to search _before_ (not including)
 448  *
 449  * Returns position of last set bit before pos. If pos < 0 search is
 450  * started from the end. Returns -1 if no set bit is found.
 451  */
 452 int
 453 mono_bitset_find_last (const MonoBitSet *set, gint pos) {
 454         int j, bit, result, i;
 455
 456         if (pos < 0)
 457                 pos = set->size - 1;
 458
 459         j = pos / BITS_PER_CHUNK;
 460         bit = pos % BITS_PER_CHUNK;
 461
 462         g_return_val_if_fail (pos < set->size, -1);
 463
 464         if (set->data [j]) {
 465                 result = my_g_bit_nth_msf (set->data [j], bit);
 466                 if (result != -1)
 467                         return result + j * BITS_PER_CHUNK;
 468         }
 469         for (i = --j; i >= 0; --i) {
 470                 if (set->data [i])
 471                         return my_g_bit_nth_msf (set->data [i], BITS_PER_CHUNK) + i * BITS_PER_CHUNK;
 472         }
 473         return -1;
 474 }
 475
 476 /*
 477  * mono_bitset_find_first_unset:
 478  * @set: bitset ptr
 479  * @pos: pos to search _after_ (not including)
 480  *
 481  * Returns position of first unset bit after @pos. If pos < 0 begin search from
 482  * start. Return -1 if no bit set is found.
 483  */
 484 int
 485 mono_bitset_find_first_unset (const MonoBitSet *set, gint pos) {
 486         int j;
 487         int bit;
 488         int result, i;
 489
 490         if (pos < 0) {
 491                 j = 0;
 492                 bit = -1;
 493         } else {
 494                 j = pos / BITS_PER_CHUNK;
 495                 bit = pos % BITS_PER_CHUNK;
 496                 g_return_val_if_fail (pos < set->size, -1);
 497         }
 498         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 499
 500         if (set->data [j] != -1) {
 501                 result = find_first_unset (set->data [j], bit);
 502                 if (result != -1)
 503                         return result + j * BITS_PER_CHUNK;
 504         }
 505         for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
 506                 if (set->data [i] != -1) {
 507                         return find_first_unset (set->data [i], -1) + i * BITS_PER_CHUNK;
 508                 }
 509         }
 510         return -1;
 511 }
 512
 513 /*
 514  * mono_bitset_clone:
 515  * @set: bitset ptr to clone
 516  * @new_size: number of bits the cloned bitset can hold
 517  *
 518  * Return a cloned bitset of size new_size. MONO_BITSET_DONT_FREE
 519  * unset in cloned bitset. If new_size is 0, the cloned object is just
 520  * as big.
 521  */
 522 MonoBitSet*
 523 mono_bitset_clone (const MonoBitSet *set, guint32 new_size) {
 524         MonoBitSet *result;
 525
 526         if (!new_size)
 527                 new_size = set->size;
 528         result = mono_bitset_new (new_size, set->flags);
 529         result->flags &= ~MONO_BITSET_DONT_FREE;
 530         memcpy (result->data, set->data, set->size / 8);
 531         return result;
 532 }
 533
 534 /*
 535  * mono_bitset_copyto:
 536  * @src: bitset ptr to copy from
 537  * @dest: bitset ptr to copy to
 538  *
 539  * Copy one bitset to another.
 540  */
 541 void
 542 mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
 543         g_assert (dest->size <= src->size);
 544
 545         memcpy (&dest->data, &src->data, dest->size / 8);
 546 }
 547
 548 /*
 549  * mono_bitset_union:
 550  * @dest: bitset ptr to hold union
 551  * @src: bitset ptr to copy
 552  *
 553  * Make union of one bitset and another.
 554  */
 555 void
 556 mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
 557         int i, size;
 558
 559         g_assert (src->size <= dest->size);
 560
 561         size = dest->size / BITS_PER_CHUNK;
 562         for (i = 0; i < size; ++i)
 563                 dest->data [i] |= src->data [i];
 564 }
 565
 566 /*
 567  * mono_bitset_intersection:
 568  * @dest: bitset ptr to hold intersection
 569  * @src: bitset ptr to copy
 570  *
 571  * Make intersection of one bitset and another.
 572  */
 573 void
 574 mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
 575         int i, size;
 576
 577         g_assert (src->size <= dest->size);
 578
 579         size = dest->size / BITS_PER_CHUNK;
 580         for (i = 0; i < size; ++i)
 581                 dest->data [i] &= src->data [i];
 582 }
 583
 584 /*
 585  * mono_bitset_intersection_2:
 586  * @dest: bitset ptr to hold intersection
 587  * @src1: first bitset
 588  * @src2: second bitset
 589  *
 590  * Make intersection of two bitsets
 591  */
 592 void
 593 mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
 594         int i, size;
 595
 596         g_assert (src1->size <= dest->size);
 597         g_assert (src2->size <= dest->size);
 598
 599         size = dest->size / BITS_PER_CHUNK;
 600         for (i = 0; i < size; ++i)
 601                 dest->data [i] = src1->data [i] & src2->data [i];
 602 }
 603
 604 /*
 605  * mono_bitset_sub:
 606  * @dest: bitset ptr to hold bitset - src
 607  * @src: bitset ptr to copy
 608  *
 609  * Unset all bits in dest, which are set in src.
 610  */
 611 void
 612 mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
 613         int i, size;
 614
 615         g_assert (src->size <= dest->size);
 616
 617         size = src->size / BITS_PER_CHUNK;
 618         for (i = 0; i < size; ++i)
 619                 dest->data [i] &= ~src->data [i];
 620 }
 621
 622 /*
 623  * mono_bitset_equal:
 624  * @src: bitset ptr
 625  * @src1: bitset ptr
 626  *
 627  * return TRUE if their size are the same and the same bits are set in
 628  * both bitsets.
 629  */
 630 gboolean
 631 mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1) {
 632         int i;
 633         if (src->size != src1->size)
 634                 return FALSE;
 635
 636         for (i = 0; i < src->size / BITS_PER_CHUNK; ++i)
 637                 if (src->data [i] != src1->data [i])
 638                         return FALSE;
 639         return TRUE;
 640 }
 641
 642 /*
 643  * mono_bitset_foreach:
 644  * @set: bitset ptr
 645  * @func: Function to call for every set bit
 646  * @data: pass this as second arg to func
 647  *
 648  * Calls func for every bit set in bitset. Argument 1 is the number of
 649  * the bit set, argument 2 is data
 650  */
 651 void
 652 mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data)
 653 {
 654         int i, j;
 655         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 656                 if (set->data [i]) {
 657                         for (j = 0; j < BITS_PER_CHUNK; ++j)
 658                                 if (set->data [i] & ((gsize)1 << j))
 659                                         func (j + i * BITS_PER_CHUNK, data);
 660                 }
 661         }
 662 }
 663
 664 #ifdef TEST_BITSET
 665
 666 /*
 667  * Compile with:
 668  * gcc -g -Wall -DTEST_BITSET -o monobitset monobitset.c `pkg-config --cflags --libs glib-2.0`
 669  */
 670 int
 671 main() {
 672         MonoBitSet *set1, *set2, *set3, *set4;
 673         int error = 1;
 674         int count, i;
 675
 676         set1 = mono_bitset_new (60, 0);
 677         set4 = mono_bitset_new (60, 0);
 678
 679         if (mono_bitset_count (set1) != 0)
 680                 return error;
 681         error++;
 682
 683         mono_bitset_set (set1, 33);
 684         if (mono_bitset_count (set1) != 1)
 685                 return error;
 686         error++;
 687
 688         /* g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0)); */
 689
 690         if (mono_bitset_find_first (set1, 0) != 33)
 691                 return error;
 692         error++;
 693
 694         if (mono_bitset_find_first (set1, 33) != -1)
 695                 return error;
 696         error++;
 697
 698         /* test 5 */
 699         if (mono_bitset_find_first (set1, -100) != 33)
 700                 return error;
 701         error++;
 702
 703         if (mono_bitset_find_last (set1, -1) != 33)
 704                 return error;
 705         error++;
 706
 707         if (mono_bitset_find_last (set1, 33) != -1)
 708                 return error;
 709         error++;
 710
 711         if (mono_bitset_find_last (set1, -100) != 33)
 712                 return error;
 713         error++;
 714
 715         if (mono_bitset_find_last (set1, 34) != 33)
 716                 return error;
 717         error++;
 718
 719         /* test 10 */
 720         if (!mono_bitset_test (set1, 33))
 721                 return error;
 722         error++;
 723
 724         if (mono_bitset_test (set1, 32) || mono_bitset_test (set1, 34))
 725                 return error;
 726         error++;
 727
 728         set2 = mono_bitset_clone (set1, 0);
 729         if (mono_bitset_count (set2) != 1)
 730                 return error;
 731         error++;
 732
 733         mono_bitset_invert (set2);
 734         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 1))
 735                 return error;
 736         error++;
 737
 738         mono_bitset_clear (set2, 10);
 739         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 2))
 740                 return error;
 741         error++;
 742
 743         /* test 15 */
 744         set3 = mono_bitset_clone (set2, 0);
 745         mono_bitset_union (set3, set1);
 746         if (mono_bitset_count (set3) != (mono_bitset_size (set3) - 1))
 747                 return error;
 748         error++;
 749
 750         mono_bitset_clear_all (set2);
 751         if (mono_bitset_count (set2) != 0)
 752                 return error;
 753         error++;
 754
 755         mono_bitset_invert (set2);
 756         if (mono_bitset_count (set2) != mono_bitset_size (set2))
 757                 return error;
 758         error++;
 759
 760         mono_bitset_set (set4, 0);
 761         mono_bitset_set (set4, 1);
 762         mono_bitset_set (set4, 10);
 763         if (mono_bitset_count (set4) != 3)
 764                 return error;
 765         error++;
 766
 767         count = 0;
 768         for (i = mono_bitset_find_first (set4, -1); i != -1; i = mono_bitset_find_first (set4, i)) {
 769                 count ++;
 770                 switch (count) {
 771                 case 1:
 772                   if (i != 0)
 773                     return error;
 774                   break;
 775                 case 2:
 776                   if (i != 1)
 777                     return error;
 778                   break;
 779                 case 3:
 780                   if (i != 10)
 781                     return error;
 782                   break;
 783                 }
 784                 /* g_print ("count got: %d at %d\n", count, i); */
 785         }
 786         if (count != 3)
 787                 return error;
 788         error++;
 789
 790         if (mono_bitset_find_first (set4, -1) != 0)
 791                 return error;
 792         error++;
 793
 794         /* 20 */
 795         mono_bitset_set (set4, 31);
 796         if (mono_bitset_find_first (set4, 10) != 31)
 797                 return error;
 798         error++;
 799
 800         mono_bitset_free (set1);
 801
 802         set1 = mono_bitset_new (200, 0);
 803         mono_bitset_set (set1, 0);
 804         mono_bitset_set (set1, 1);
 805         mono_bitset_set (set1, 10);
 806         mono_bitset_set (set1, 31);
 807         mono_bitset_set (set1, 150);
 808
 809         mono_bitset_free (set1);
 810         mono_bitset_free (set2);
 811         mono_bitset_free (set3);
 812         mono_bitset_free (set4);
 813
 814         g_print ("total tests passed: %d\n", error - 1);
 815
 816         return 0;
 817 }
 818
 819 #endif