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  * \param max_size The number of bits you want to hold
  16  * \param flags unused
  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.
  20  */
  21 guint32
  22 mono_bitset_alloc_size (guint32 max_size, guint32 flags) {
  23         guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
  24
  25         return sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY);
  26 }
  27
  28 /**
  29  * mono_bitset_new:
  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.
  34  */
  35 MonoBitSet *
  36 mono_bitset_new (guint32 max_size, guint32 flags) {
  37         guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
  38         MonoBitSet *result;
  39
  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;
  43         return result;
  44 }
  45
  46 /**
  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
  51  *
  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.
  55  */
  56 MonoBitSet *
  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;
  60
  61         result->size = real_size * BITS_PER_CHUNK;
  62         result->flags = flags | MONO_BITSET_DONT_FREE;
  63         return result;
  64 }
  65
  66 /*
  67  * mono_bitset_free:
  68  * \param set bitset ptr to free
  69  *
  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.
  73  */
  74 void
  75 mono_bitset_free (MonoBitSet *set) {
  76         if (set && !(set->flags & MONO_BITSET_DONT_FREE))
  77                 g_free (set);
  78 }
  79
  80 /**
  81  * mono_bitset_set:
  82  * \param set bitset ptr
  83  * \param pos set bit at this pos
  84  *
  85  * Set bit at \p pos, counting from 0.
  86  */
  87 void
  88 mono_bitset_set (MonoBitSet *set, guint32 pos) {
  89         int j = pos / BITS_PER_CHUNK;
  90         int bit = pos % BITS_PER_CHUNK;
  91
  92         g_assert (pos < set->size);
  93
  94         set->data [j] |= (gsize)1 << bit;
  95 }
  96
  97 /**
  98  * mono_bitset_test:
  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.
 103  */
 104 int
 105 mono_bitset_test (const MonoBitSet *set, guint32 pos) {
 106         int j = pos / BITS_PER_CHUNK;
 107         int bit = pos % BITS_PER_CHUNK;
 108
 109         g_return_val_if_fail (pos < set->size, 0);
 110
 111         return (set->data [j] & ((gsize)1 << bit)) > 0;
 112 }
 113
 114 /**
 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.
 120  */
 121 gsize
 122 mono_bitset_test_bulk (const MonoBitSet *set, guint32 pos) {
 123         int j = pos / BITS_PER_CHUNK;
 124
 125         if (pos >= set->size)
 126                 return 0;
 127         else
 128                 return set->data [j];
 129 }
 130
 131 /**
 132  * mono_bitset_clear:
 133  * \param set bitset ptr
 134  * \param pos unset bit at this pos
 135  *
 136  * Unset bit at \p pos, counting from 0.
 137  */
 138 void
 139 mono_bitset_clear (MonoBitSet *set, guint32 pos) {
 140         int j = pos / BITS_PER_CHUNK;
 141         int bit = pos % BITS_PER_CHUNK;
 142
 143         g_assert (pos < set->size);
 144
 145         set->data [j] &= ~((gsize)1 << bit);
 146 }
 147
 148 /**
 149  * mono_bitset_clear_all:
 150  * \param set bitset ptr
 151  *
 152  * Unset all bits.
 153  */
 154 void
 155 mono_bitset_clear_all (MonoBitSet *set) {
 156         memset (set->data, 0, set->size / 8);
 157 }
 158
 159 /**
 160  * mono_bitset_set_all:
 161  * \param set bitset ptr
 162  *
 163  * Set all bits.
 164  */
 165 void
 166 mono_bitset_set_all (MonoBitSet *set) {
 167         memset (set->data, -1, set->size / 8);
 168 }
 169
 170 /**
 171  * mono_bitset_invert:
 172  * \param set bitset ptr
 173  *
 174  * Flip all bits.
 175  */
 176 void
 177 mono_bitset_invert (MonoBitSet *set) {
 178         int i;
 179         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i)
 180                 set->data [i] = ~set->data [i];
 181 }
 182
 183 /**
 184  * mono_bitset_size:
 185  * \param set bitset ptr
 186  * \returns the number of bits this bitset can hold.
 187  */
 188 guint32
 189 mono_bitset_size (const MonoBitSet *set) {
 190         return set->size;
 191 }
 192
 193 /*
 194  * should test wich version is faster.
 195  */
 196 #if 1
 197
 198 /**
 199  * mono_bitset_count:
 200  * \param set bitset ptr
 201  * \returns number of bits that are set.
 202  */
 203 guint32
 204 mono_bitset_count (const MonoBitSet *set)
 205 {
 206         guint32 i, count;
 207         gsize d;
 208
 209         count = 0;
 210         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 211                 d = set->data [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);
 217                 else
 218                         count += __builtin_popcountll (d);
 219 #else
 220                 while (d) {
 221                         count ++;
 222                         d &= (d - 1);
 223                 }
 224 #endif
 225         }
 226         return count;
 227 }
 228 #else
 229 guint32
 230 mono_bitset_count (const MonoBitSet *set) {
 231         static const guint32 table [] = {
 232                 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
 233         };
 234         guint32 i, count, val;
 235
 236         count = 0;
 237         for (i = 0; i < set->size / BITS_PER_CHUNK;+i) {
 238                 if (set->data [i]) {
 239                         val = set->data [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]);
 245                         count += val;
 246                 }
 247         }
 248         return count;
 249 }
 250
 251 #endif
 252
 253 #if 0
 254 const static int
 255 bitstart_mask [] = {
 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,
 264         0x00000000
 265 };
 266
 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)
 269
 270 #else
 271
 272 static gint
 273 my_g_bit_nth_lsf (gsize mask, gint nth_bit)
 274 {
 275         nth_bit ++;
 276         mask >>= nth_bit;
 277
 278         if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
 279                 return -1;
 280
 281 #if (defined(__i386__) && defined(__GNUC__))
 282  {
 283          int r;
 284          /* This depends on mask != 0 */
 285          __asm__("bsfl %1,%0\n\t"
 286                          : "=r" (r) : "g" (mask));
 287          return nth_bit + r;
 288  }
 289 #elif defined(__x86_64) && defined(__GNUC__)
 290  {
 291         guint64 r;
 292
 293         __asm__("bsfq %1,%0\n\t"
 294                         : "=r" (r) : "rm" (mask));
 295         return nth_bit + r;
 296  }
 297 #else
 298         while (! (mask & 0x1)) {
 299                 mask >>= 1;
 300                 nth_bit ++;
 301         }
 302
 303         return nth_bit;
 304 #endif
 305 }
 306
 307 static gint
 308 my_g_bit_nth_lsf_nomask (gsize mask)
 309 {
 310         /* Mask is expected to be != 0 */
 311 #if (defined(__i386__) && defined(__GNUC__))
 312         int r;
 313
 314         __asm__("bsfl %1,%0\n\t"
 315                         : "=r" (r) : "rm" (mask));
 316         return r;
 317 #elif defined(__x86_64) && defined(__GNUC__)
 318         guint64 r;
 319
 320         __asm__("bsfq %1,%0\n\t"
 321                         : "=r" (r) : "rm" (mask));
 322         return r;
 323 #else
 324         int nth_bit = 0;
 325
 326         while (! (mask & 0x1)) {
 327                 mask >>= 1;
 328                 nth_bit ++;
 329         }
 330
 331         return nth_bit;
 332 #endif
 333 }
 334
 335 #endif
 336
 337 static int
 338 my_g_bit_nth_msf (gsize mask,
 339                gint   nth_bit)
 340 {
 341         int i;
 342
 343         if (nth_bit == 0)
 344                 return -1;
 345
 346         mask <<= BITS_PER_CHUNK - nth_bit;
 347
 348         i = BITS_PER_CHUNK;
 349         while ((i > 0) && !(mask >> (BITS_PER_CHUNK - 8))) {
 350                 mask <<= 8;
 351                 i -= 8;
 352         }
 353         if (mask == 0)
 354                 return -1;
 355
 356         do {
 357                 i--;
 358                 if (mask & ((gsize)1 << (BITS_PER_CHUNK - 1)))
 359                         return i - (BITS_PER_CHUNK - nth_bit);
 360                 mask <<= 1;
 361     }
 362         while (mask);
 363
 364         return -1;
 365 }
 366
 367 static int
 368 find_first_unset (gsize mask, gint nth_bit)
 369 {
 370         do {
 371                 nth_bit++;
 372                 if (!(mask & ((gsize)1 << nth_bit))) {
 373                         if (nth_bit == BITS_PER_CHUNK)
 374                                 /* On 64 bit platforms, 1 << 64 == 1 */
 375                                 return -1;
 376                         else
 377                                 return nth_bit;
 378                 }
 379         } while (nth_bit < BITS_PER_CHUNK);
 380         return -1;
 381 }
 382
 383 /**
 384  * mono_bitset_find_start:
 385  * \param set bitset ptr
 386  * Equivalent to <code>mono_bitset_find_first (set, -1)</code> but faster.
 387  */
 388 int
 389 mono_bitset_find_start   (const MonoBitSet *set)
 390 {
 391         int i;
 392
 393         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 394                 if (set->data [i])
 395                         return my_g_bit_nth_lsf_nomask (set->data [i]) + i * BITS_PER_CHUNK;
 396         }
 397         return -1;
 398 }
 399
 400 /**
 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.
 406  */
 407 int
 408 mono_bitset_find_first (const MonoBitSet *set, gint pos) {
 409         int j;
 410         int bit;
 411         int result, i;
 412
 413         if (pos < 0) {
 414                 j = 0;
 415                 bit = -1;
 416         } else {
 417                 j = pos / BITS_PER_CHUNK;
 418                 bit = pos % BITS_PER_CHUNK;
 419                 g_assert (pos < set->size);
 420         }
 421         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 422
 423         if (set->data [j]) {
 424                 result = my_g_bit_nth_lsf (set->data [j], bit);
 425                 if (result != -1)
 426                         return result + j * BITS_PER_CHUNK;
 427         }
 428         for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
 429                 if (set->data [i])
 430                         return my_g_bit_nth_lsf (set->data [i], -1) + i * BITS_PER_CHUNK;
 431         }
 432         return -1;
 433 }
 434
 435 /**
 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.
 441  */
 442 int
 443 mono_bitset_find_last (const MonoBitSet *set, gint pos) {
 444         int j, bit, result, i;
 445
 446         if (pos < 0)
 447                 pos = set->size - 1;
 448
 449         j = pos / BITS_PER_CHUNK;
 450         bit = pos % BITS_PER_CHUNK;
 451
 452         g_return_val_if_fail (pos < set->size, -1);
 453
 454         if (set->data [j]) {
 455                 result = my_g_bit_nth_msf (set->data [j], bit);
 456                 if (result != -1)
 457                         return result + j * BITS_PER_CHUNK;
 458         }
 459         for (i = --j; i >= 0; --i) {
 460                 if (set->data [i])
 461                         return my_g_bit_nth_msf (set->data [i], BITS_PER_CHUNK) + i * BITS_PER_CHUNK;
 462         }
 463         return -1;
 464 }
 465
 466 /**
 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.
 472  */
 473 int
 474 mono_bitset_find_first_unset (const MonoBitSet *set, gint pos) {
 475         int j;
 476         int bit;
 477         int result, i;
 478
 479         if (pos < 0) {
 480                 j = 0;
 481                 bit = -1;
 482         } else {
 483                 j = pos / BITS_PER_CHUNK;
 484                 bit = pos % BITS_PER_CHUNK;
 485                 g_return_val_if_fail (pos < set->size, -1);
 486         }
 487         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 488
 489         if (set->data [j] != -1) {
 490                 result = find_first_unset (set->data [j], bit);
 491                 if (result != -1)
 492                         return result + j * BITS_PER_CHUNK;
 493         }
 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;
 497                 }
 498         }
 499         return -1;
 500 }
 501
 502 /**
 503  * mono_bitset_clone:
 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
 508  * as big.
 509  */
 510 MonoBitSet*
 511 mono_bitset_clone (const MonoBitSet *set, guint32 new_size) {
 512         MonoBitSet *result;
 513
 514         if (!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);
 519         return result;
 520 }
 521
 522 /**
 523  * mono_bitset_copyto:
 524  * \param src bitset ptr to copy from
 525  * \param dest bitset ptr to copy to
 526  *
 527  * Copy one bitset to another.
 528  */
 529 void
 530 mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
 531         g_assert (dest->size <= src->size);
 532
 533         memcpy (&dest->data, &src->data, dest->size / 8);
 534 }
 535
 536 /**
 537  * mono_bitset_union:
 538  * \param dest bitset ptr to hold union
 539  * \param src bitset ptr to copy
 540  *
 541  * Make union of one bitset and another.
 542  */
 543 void
 544 mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
 545         int i, size;
 546
 547         g_assert (src->size <= dest->size);
 548
 549         size = dest->size / BITS_PER_CHUNK;
 550         for (i = 0; i < size; ++i)
 551                 dest->data [i] |= src->data [i];
 552 }
 553
 554 /**
 555  * mono_bitset_intersection:
 556  * \param dest bitset ptr to hold intersection
 557  * \param src bitset ptr to copy
 558  *
 559  * Make intersection of one bitset and another.
 560  */
 561 void
 562 mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
 563         int i, size;
 564
 565         g_assert (src->size <= dest->size);
 566
 567         size = dest->size / BITS_PER_CHUNK;
 568         for (i = 0; i < size; ++i)
 569                 dest->data [i] &= src->data [i];
 570 }
 571
 572 /**
 573  * mono_bitset_intersection_2:
 574  * \param dest bitset ptr to hold intersection
 575  * \param src1 first bitset
 576  * \param src2 second bitset
 577  *
 578  * Make intersection of two bitsets
 579  */
 580 void
 581 mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
 582         int i, size;
 583
 584         g_assert (src1->size <= dest->size);
 585         g_assert (src2->size <= dest->size);
 586
 587         size = dest->size / BITS_PER_CHUNK;
 588         for (i = 0; i < size; ++i)
 589                 dest->data [i] = src1->data [i] & src2->data [i];
 590 }
 591
 592 /**
 593  * mono_bitset_sub:
 594  * \param dest bitset ptr to hold bitset - src
 595  * \param src bitset ptr to copy
 596  *
 597  * Unset all bits in \p dest that are set in \p src.
 598  */
 599 void
 600 mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
 601         int i, size;
 602
 603         g_assert (src->size <= dest->size);
 604
 605         size = src->size / BITS_PER_CHUNK;
 606         for (i = 0; i < size; ++i)
 607                 dest->data [i] &= ~src->data [i];
 608 }
 609
 610 /**
 611  * mono_bitset_equal:
 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
 615  * both bitsets.
 616  */
 617 gboolean
 618 mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1) {
 619         int i;
 620         if (src->size != src1->size)
 621                 return FALSE;
 622
 623         for (i = 0; i < src->size / BITS_PER_CHUNK; ++i)
 624                 if (src->data [i] != src1->data [i])
 625                         return FALSE;
 626         return TRUE;
 627 }
 628
 629 /**
 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
 636  */
 637 void
 638 mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data)
 639 {
 640         int i, j;
 641         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 642                 if (set->data [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);
 646                 }
 647         }
 648 }
 649
 650 gboolean
 651 mono_bitset_test_safe (const MonoBitSet *set, guint32 pos)
 652 {
 653         return set && set->size > pos && mono_bitset_test (set, pos);
 654 }
 655
 656 #ifdef TEST_BITSET
 657
 658 /*
 659  * Compile with:
 660  * gcc -g -Wall -DTEST_BITSET -o monobitset monobitset.c `pkg-config --cflags --libs glib-2.0`
 661  */
 662 int
 663 main() {
 664         MonoBitSet *set1, *set2, *set3, *set4;
 665         int error = 1;
 666         int count, i;
 667
 668         set1 = mono_bitset_new (60, 0);
 669         set4 = mono_bitset_new (60, 0);
 670
 671         if (mono_bitset_count (set1) != 0)
 672                 return error;
 673         error++;
 674
 675         mono_bitset_set (set1, 33);
 676         if (mono_bitset_count (set1) != 1)
 677                 return error;
 678         error++;
 679
 680         /* g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0)); */
 681
 682         if (mono_bitset_find_first (set1, 0) != 33)
 683                 return error;
 684         error++;
 685
 686         if (mono_bitset_find_first (set1, 33) != -1)
 687                 return error;
 688         error++;
 689
 690         /* test 5 */
 691         if (mono_bitset_find_first (set1, -100) != 33)
 692                 return error;
 693         error++;
 694
 695         if (mono_bitset_find_last (set1, -1) != 33)
 696                 return error;
 697         error++;
 698
 699         if (mono_bitset_find_last (set1, 33) != -1)
 700                 return error;
 701         error++;
 702
 703         if (mono_bitset_find_last (set1, -100) != 33)
 704                 return error;
 705         error++;
 706
 707         if (mono_bitset_find_last (set1, 34) != 33)
 708                 return error;
 709         error++;
 710
 711         /* test 10 */
 712         if (!mono_bitset_test (set1, 33))
 713                 return error;
 714         error++;
 715
 716         if (mono_bitset_test (set1, 32) || mono_bitset_test (set1, 34))
 717                 return error;
 718         error++;
 719
 720         set2 = mono_bitset_clone (set1, 0);
 721         if (mono_bitset_count (set2) != 1)
 722                 return error;
 723         error++;
 724
 725         mono_bitset_invert (set2);
 726         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 1))
 727                 return error;
 728         error++;
 729
 730         mono_bitset_clear (set2, 10);
 731         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 2))
 732                 return error;
 733         error++;
 734
 735         /* test 15 */
 736         set3 = mono_bitset_clone (set2, 0);
 737         mono_bitset_union (set3, set1);
 738         if (mono_bitset_count (set3) != (mono_bitset_size (set3) - 1))
 739                 return error;
 740         error++;
 741
 742         mono_bitset_clear_all (set2);
 743         if (mono_bitset_count (set2) != 0)
 744                 return error;
 745         error++;
 746
 747         mono_bitset_invert (set2);
 748         if (mono_bitset_count (set2) != mono_bitset_size (set2))
 749                 return error;
 750         error++;
 751
 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)
 756                 return error;
 757         error++;
 758
 759         count = 0;
 760         for (i = mono_bitset_find_first (set4, -1); i != -1; i = mono_bitset_find_first (set4, i)) {
 761                 count ++;
 762                 switch (count) {
 763                 case 1:
 764                   if (i != 0)
 765                     return error;
 766                   break;
 767                 case 2:
 768                   if (i != 1)
 769                     return error;
 770                   break;
 771                 case 3:
 772                   if (i != 10)
 773                     return error;
 774                   break;
 775                 }
 776                 /* g_print ("count got: %d at %d\n", count, i); */
 777         }
 778         if (count != 3)
 779                 return error;
 780         error++;
 781
 782         if (mono_bitset_find_first (set4, -1) != 0)
 783                 return error;
 784         error++;
 785
 786         /* 20 */
 787         mono_bitset_set (set4, 31);
 788         if (mono_bitset_find_first (set4, 10) != 31)
 789                 return error;
 790         error++;
 791
 792         mono_bitset_free (set1);
 793
 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);
 800
 801         mono_bitset_free (set1);
 802         mono_bitset_free (set2);
 803         mono_bitset_free (set3);
 804         mono_bitset_free (set4);
 805
 806         g_print ("total tests passed: %d\n", error - 1);
 807
 808         return 0;
 809 }
 810
 811 #endif