mono/utils/monobitset.c

   1 #include <glib.h>
   2 #include <string.h>
   3
   4 #include "monobitset.h"
   5 #include "config.h"
   6
   7 #define BITS_PER_CHUNK MONO_BITSET_BITS_PER_CHUNK
   8
   9 /*
  10  * mono_bitset_alloc_size:
  11  * @max_size: The number of bits you want to hold
  12  * @flags: unused
  13  *
  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 ().
  17  */
  18 guint32
  19 mono_bitset_alloc_size (guint32 max_size, guint32 flags) {
  20         guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
  21
  22         return sizeof (MonoBitSet) + sizeof (gsize) * (real_size - MONO_ZERO_LEN_ARRAY);
  23 }
  24
  25 /*
  26  * mono_bitset_new:
  27  * @max_size: The numer of bits you want to hold
  28  * @flags: bitfield of flags
  29  *
  30  * Return a bitset of size max_size. It must be freed using
  31  * mono_bitset_free.
  32  */
  33 MonoBitSet *
  34 mono_bitset_new (guint32 max_size, guint32 flags) {
  35         guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
  36         MonoBitSet *result;
  37
  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;
  41         return result;
  42 }
  43
  44 /*
  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
  49  *
  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.
  53  */
  54 MonoBitSet *
  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;
  58
  59         result->size = real_size * BITS_PER_CHUNK;
  60         result->flags = flags | MONO_BITSET_DONT_FREE;
  61         return result;
  62 }
  63
  64 /*
  65  * mono_bitset_free:
  66  * @set: bitset ptr to free
  67  *
  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.
  71  */
  72 void
  73 mono_bitset_free (MonoBitSet *set) {
  74         if (!(set->flags & MONO_BITSET_DONT_FREE))
  75                 g_free (set);
  76 }
  77
  78 /*
  79  * mono_bitset_set:
  80  * @set: bitset ptr
  81  * @pos: set bit at this pos
  82  *
  83  * Set bit at pos @pos, counting from 0.
  84  */
  85 void
  86 mono_bitset_set (MonoBitSet *set, guint32 pos) {
  87         int j = pos / BITS_PER_CHUNK;
  88         int bit = pos % BITS_PER_CHUNK;
  89
  90         g_assert (pos < set->size);
  91
  92         set->data [j] |= (gsize)1 << bit;
  93 }
  94
  95 /*
  96  * mono_bitset_test:
  97  * @set: bitset ptr
  98  * @pos: test bit at this pos
  99  *
 100  * Test bit at pos @pos, counting from 0.
 101  * Returns a value != 0 if set, 0 otherwise.
 102  */
 103 int
 104 mono_bitset_test (const MonoBitSet *set, guint32 pos) {
 105         int j = pos / BITS_PER_CHUNK;
 106         int bit = pos % BITS_PER_CHUNK;
 107
 108         g_return_val_if_fail (pos < set->size, 0);
 109
 110         return (set->data [j] & ((gsize)1 << bit)) > 0;
 111 }
 112
 113 /*
 114  * mono_bitset_test_bulk:
 115  * @set: bitset ptr
 116  * @pos: test bit at this pos
 117  *
 118  * Return 32/64 bits from the bitset, starting from @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  * @set: bitset ptr
 134  * @pos: unset bit at this pos
 135  *
 136  * Unset bit at pos '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  * @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  * @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  * @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  * @set: bitset ptr
 186  *
 187  * Returns the number of bits this bitset can hold.
 188  */
 189 guint32
 190 mono_bitset_size (const MonoBitSet *set) {
 191         return set->size;
 192 }
 193
 194 /*
 195  * should test wich version is faster.
 196  */
 197 #if 1
 198
 199 /*
 200  * mono_bitset_count:
 201  * @set: bitset ptr
 202  *
 203  * return number of bits that is set.
 204  */
 205 guint32
 206 mono_bitset_count (const MonoBitSet *set) {
 207         guint32 i, count;
 208         gsize d;
 209
 210         count = 0;
 211         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 212                 d = set->data [i];
 213 #ifdef __GNUC__
 214                 count += __builtin_popcount (d);
 215 #else
 216                 while (d) {
 217                         count ++;
 218                         d &= (d - 1);
 219                 }
 220 #endif
 221         }
 222         return count;
 223 }
 224 #else
 225 guint32
 226 mono_bitset_count (const MonoBitSet *set) {
 227         static const guint32 table [] = {
 228                 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
 229         };
 230         guint32 i, count, val;
 231
 232         count = 0;
 233         for (i = 0; i < set->size / BITS_PER_CHUNK;+i) {
 234                 if (set->data [i]) {
 235                         val = set->data [i];
 236                         val = (val & table [0]) ((val >> 1) & table [0]);
 237                         val = (val & table [1]) ((val >> 2) & table [1]);
 238                         val = (val & table [2]) ((val >> 4) & table [2]);
 239                         val = (val & table [3]) ((val >> 8) & table [3]);
 240                         val = (val & table [4]) ((val >> 16) & table [4]);
 241                         count += val;
 242                 }
 243         }
 244         return count;
 245 }
 246
 247 #endif
 248
 249 #if 0
 250 const static int
 251 bitstart_mask [] = {
 252         0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8,
 253         0xfffffff0, 0xffffffe0, 0xffffffc0, 0xffffff80,
 254         0xffffff00, 0xfffffe00, 0xfffffc00, 0xfffff800,
 255         0xfffff000, 0xffffe000, 0xffffc000, 0xffff8000,
 256         0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
 257         0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
 258         0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
 259         0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
 260         0x00000000
 261 };
 262
 263 #define my_g_bit_nth_lsf(m,n) (ffs((m) & bitstart_mask [(n)+1])-1)
 264 #define my_g_bit_nth_lsf_nomask(m) (ffs((m))-1)
 265
 266 #else
 267
 268 static inline gint
 269 my_g_bit_nth_lsf (gsize mask, gint nth_bit)
 270 {
 271         nth_bit ++;
 272         mask >>= nth_bit;
 273
 274         if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
 275                 return -1;
 276
 277 #if defined(__native_client__) && (defined(__i386__) || defined(__x86_64))
 278 #define USE_X86_32BIT_INSTRUCTIONS 1
 279 #endif
 280
 281 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
 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 inline gint
 308 my_g_bit_nth_lsf_nomask (gsize mask)
 309 {
 310         /* Mask is expected to be != 0 */
 311 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
 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 inline 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  * @set: bitset ptr
 386  *
 387  * Equivalent to mono_bitset_find_first (set, -1) but faster.
 388  */
 389 int
 390 mono_bitset_find_start   (const MonoBitSet *set)
 391 {
 392         int i;
 393
 394         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 395                 if (set->data [i])
 396                         return my_g_bit_nth_lsf_nomask (set->data [i]) + i * BITS_PER_CHUNK;
 397         }
 398         return -1;
 399 }
 400
 401 /*
 402  * mono_bitset_find_first:
 403  * @set: bitset ptr
 404  * @pos: pos to search _after_ (not including)
 405  *
 406  * Returns position of first set bit after @pos. If pos < 0 begin search from
 407  * start. Return -1 if no bit set is found.
 408  */
 409 int
 410 mono_bitset_find_first (const MonoBitSet *set, gint pos) {
 411         int j;
 412         int bit;
 413         int result, i;
 414
 415         if (pos < 0) {
 416                 j = 0;
 417                 bit = -1;
 418         } else {
 419                 j = pos / BITS_PER_CHUNK;
 420                 bit = pos % BITS_PER_CHUNK;
 421                 g_assert (pos < set->size);
 422         }
 423         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 424
 425         if (set->data [j]) {
 426                 result = my_g_bit_nth_lsf (set->data [j], bit);
 427                 if (result != -1)
 428                         return result + j * BITS_PER_CHUNK;
 429         }
 430         for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
 431                 if (set->data [i])
 432                         return my_g_bit_nth_lsf (set->data [i], -1) + i * BITS_PER_CHUNK;
 433         }
 434         return -1;
 435 }
 436
 437 /*
 438  * mono_bitset_find_last:
 439  * @set: bitset ptr
 440  * @pos: pos to search _before_ (not including)
 441  *
 442  * Returns position of last set bit before pos. If pos < 0 search is
 443  * started from the end. Returns -1 if no set bit is found.
 444  */
 445 int
 446 mono_bitset_find_last (const MonoBitSet *set, gint pos) {
 447         int j, bit, result, i;
 448
 449         if (pos < 0)
 450                 pos = set->size - 1;
 451
 452         j = pos / BITS_PER_CHUNK;
 453         bit = pos % BITS_PER_CHUNK;
 454
 455         g_return_val_if_fail (pos < set->size, -1);
 456
 457         if (set->data [j]) {
 458                 result = my_g_bit_nth_msf (set->data [j], bit);
 459                 if (result != -1)
 460                         return result + j * BITS_PER_CHUNK;
 461         }
 462         for (i = --j; i >= 0; --i) {
 463                 if (set->data [i])
 464                         return my_g_bit_nth_msf (set->data [i], BITS_PER_CHUNK) + i * BITS_PER_CHUNK;
 465         }
 466         return -1;
 467 }
 468
 469 /*
 470  * mono_bitset_find_first_unset:
 471  * @set: bitset ptr
 472  * @pos: pos to search _after_ (not including)
 473  *
 474  * Returns position of first unset bit after @pos. If pos < 0 begin search from
 475  * start. Return -1 if no bit set is found.
 476  */
 477 int
 478 mono_bitset_find_first_unset (const MonoBitSet *set, gint pos) {
 479         int j;
 480         int bit;
 481         int result, i;
 482
 483         if (pos < 0) {
 484                 j = 0;
 485                 bit = -1;
 486         } else {
 487                 j = pos / BITS_PER_CHUNK;
 488                 bit = pos % BITS_PER_CHUNK;
 489                 g_return_val_if_fail (pos < set->size, -1);
 490         }
 491         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 492
 493         if (set->data [j] != -1) {
 494                 result = find_first_unset (set->data [j], bit);
 495                 if (result != -1)
 496                         return result + j * BITS_PER_CHUNK;
 497         }
 498         for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
 499                 if (set->data [i] != -1) {
 500                         return find_first_unset (set->data [i], -1) + i * BITS_PER_CHUNK;
 501                 }
 502         }
 503         return -1;
 504 }
 505
 506 /*
 507  * mono_bitset_clone:
 508  * @set: bitset ptr to clone
 509  * @new_size: number of bits the cloned bitset can hold
 510  *
 511  * Return a cloned bitset of size new_size. MONO_BITSET_DONT_FREE
 512  * unset in cloned bitset. If new_size is 0, the cloned object is just
 513  * as big.
 514  */
 515 MonoBitSet*
 516 mono_bitset_clone (const MonoBitSet *set, guint32 new_size) {
 517         MonoBitSet *result;
 518
 519         if (!new_size)
 520                 new_size = set->size;
 521         result = mono_bitset_new (new_size, set->flags);
 522         result->flags &= ~MONO_BITSET_DONT_FREE;
 523         memcpy (result->data, set->data, set->size / 8);
 524         return result;
 525 }
 526
 527 /*
 528  * mono_bitset_copyto:
 529  * @src: bitset ptr to copy from
 530  * @dest: bitset ptr to copy to
 531  *
 532  * Copy one bitset to another.
 533  */
 534 void
 535 mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
 536         g_assert (dest->size <= src->size);
 537
 538         memcpy (&dest->data, &src->data, dest->size / 8);
 539 }
 540
 541 /*
 542  * mono_bitset_union:
 543  * @dest: bitset ptr to hold union
 544  * @src: bitset ptr to copy
 545  *
 546  * Make union of one bitset and another.
 547  */
 548 void
 549 mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
 550         int i, size;
 551
 552         g_assert (src->size <= dest->size);
 553
 554         size = dest->size / BITS_PER_CHUNK;
 555         for (i = 0; i < size; ++i)
 556                 dest->data [i] |= src->data [i];
 557 }
 558
 559 /*
 560  * mono_bitset_intersection:
 561  * @dest: bitset ptr to hold intersection
 562  * @src: bitset ptr to copy
 563  *
 564  * Make intersection of one bitset and another.
 565  */
 566 void
 567 mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
 568         int i, size;
 569
 570         g_assert (src->size <= dest->size);
 571
 572         size = dest->size / BITS_PER_CHUNK;
 573         for (i = 0; i < size; ++i)
 574                 dest->data [i] &= src->data [i];
 575 }
 576
 577 /*
 578  * mono_bitset_intersection_2:
 579  * @dest: bitset ptr to hold intersection
 580  * @src1: first bitset
 581  * @src2: second bitset
 582  *
 583  * Make intersection of two bitsets
 584  */
 585 void
 586 mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
 587         int i, size;
 588
 589         g_assert (src1->size <= dest->size);
 590         g_assert (src2->size <= dest->size);
 591
 592         size = dest->size / BITS_PER_CHUNK;
 593         for (i = 0; i < size; ++i)
 594                 dest->data [i] = src1->data [i] & src2->data [i];
 595 }
 596
 597 /*
 598  * mono_bitset_sub:
 599  * @dest: bitset ptr to hold bitset - src
 600  * @src: bitset ptr to copy
 601  *
 602  * Unset all bits in dest, which are set in src.
 603  */
 604 void
 605 mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
 606         int i, size;
 607
 608         g_assert (src->size <= dest->size);
 609
 610         size = src->size / BITS_PER_CHUNK;
 611         for (i = 0; i < size; ++i)
 612                 dest->data [i] &= ~src->data [i];
 613 }
 614
 615 /*
 616  * mono_bitset_equal:
 617  * @src: bitset ptr
 618  * @src1: bitset ptr
 619  *
 620  * return TRUE if their size are the same and the same bits are set in
 621  * both bitsets.
 622  */
 623 gboolean
 624 mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1) {
 625         int i;
 626         if (src->size != src1->size)
 627                 return FALSE;
 628
 629         for (i = 0; i < src->size / BITS_PER_CHUNK; ++i)
 630                 if (src->data [i] != src1->data [i])
 631                         return FALSE;
 632         return TRUE;
 633 }
 634
 635 /*
 636  * mono_bitset_foreach:
 637  * @set: bitset ptr
 638  * @func: Function to call for every set bit
 639  * @data: pass this as second arg to func
 640  *
 641  * Calls func for every bit set in bitset. Argument 1 is the number of
 642  * the bit set, argument 2 is data
 643  */
 644 void
 645 mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data)
 646 {
 647         int i, j;
 648         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 649                 if (set->data [i]) {
 650                         for (j = 0; j < BITS_PER_CHUNK; ++j)
 651                                 if (set->data [i] & ((gsize)1 << j))
 652                                         func (j + i * BITS_PER_CHUNK, data);
 653                 }
 654         }
 655 }
 656
 657 #ifdef TEST_BITSET
 658
 659 /*
 660  * Compile with:
 661  * gcc -g -Wall -DTEST_BITSET -o monobitset monobitset.c `pkg-config --cflags --libs glib-2.0`
 662  */
 663 int
 664 main() {
 665         MonoBitSet *set1, *set2, *set3, *set4;
 666         int error = 1;
 667         int count, i;
 668
 669         set1 = mono_bitset_new (60, 0);
 670         set4 = mono_bitset_new (60, 0);
 671
 672         if (mono_bitset_count (set1) != 0)
 673                 return error;
 674         error++;
 675
 676         mono_bitset_set (set1, 33);
 677         if (mono_bitset_count (set1) != 1)
 678                 return error;
 679         error++;
 680
 681         /* g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0)); */
 682
 683         if (mono_bitset_find_first (set1, 0) != 33)
 684                 return error;
 685         error++;
 686
 687         if (mono_bitset_find_first (set1, 33) != -1)
 688                 return error;
 689         error++;
 690
 691         /* test 5 */
 692         if (mono_bitset_find_first (set1, -100) != 33)
 693                 return error;
 694         error++;
 695
 696         if (mono_bitset_find_last (set1, -1) != 33)
 697                 return error;
 698         error++;
 699
 700         if (mono_bitset_find_last (set1, 33) != -1)
 701                 return error;
 702         error++;
 703
 704         if (mono_bitset_find_last (set1, -100) != 33)
 705                 return error;
 706         error++;
 707
 708         if (mono_bitset_find_last (set1, 34) != 33)
 709                 return error;
 710         error++;
 711
 712         /* test 10 */
 713         if (!mono_bitset_test (set1, 33))
 714                 return error;
 715         error++;
 716
 717         if (mono_bitset_test (set1, 32) || mono_bitset_test (set1, 34))
 718                 return error;
 719         error++;
 720
 721         set2 = mono_bitset_clone (set1, 0);
 722         if (mono_bitset_count (set2) != 1)
 723                 return error;
 724         error++;
 725
 726         mono_bitset_invert (set2);
 727         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 1))
 728                 return error;
 729         error++;
 730
 731         mono_bitset_clear (set2, 10);
 732         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 2))
 733                 return error;
 734         error++;
 735
 736         /* test 15 */
 737         set3 = mono_bitset_clone (set2, 0);
 738         mono_bitset_union (set3, set1);
 739         if (mono_bitset_count (set3) != (mono_bitset_size (set3) - 1))
 740                 return error;
 741         error++;
 742
 743         mono_bitset_clear_all (set2);
 744         if (mono_bitset_count (set2) != 0)
 745                 return error;
 746         error++;
 747
 748         mono_bitset_invert (set2);
 749         if (mono_bitset_count (set2) != mono_bitset_size (set2))
 750                 return error;
 751         error++;
 752
 753         mono_bitset_set (set4, 0);
 754         mono_bitset_set (set4, 1);
 755         mono_bitset_set (set4, 10);
 756         if (mono_bitset_count (set4) != 3)
 757                 return error;
 758         error++;
 759
 760         count = 0;
 761         for (i = mono_bitset_find_first (set4, -1); i != -1; i = mono_bitset_find_first (set4, i)) {
 762                 count ++;
 763                 switch (count) {
 764                 case 1:
 765                   if (i != 0)
 766                     return error;
 767                   break;
 768                 case 2:
 769                   if (i != 1)
 770                     return error;
 771                   break;
 772                 case 3:
 773                   if (i != 10)
 774                     return error;
 775                   break;
 776                 }
 777                 /* g_print ("count got: %d at %d\n", count, i); */
 778         }
 779         if (count != 3)
 780                 return error;
 781         error++;
 782
 783         if (mono_bitset_find_first (set4, -1) != 0)
 784                 return error;
 785         error++;
 786
 787         /* 20 */
 788         mono_bitset_set (set4, 31);
 789         if (mono_bitset_find_first (set4, 10) != 31)
 790                 return error;
 791         error++;
 792
 793         mono_bitset_free (set1);
 794
 795         set1 = mono_bitset_new (200, 0);
 796         mono_bitset_set (set1, 0);
 797         mono_bitset_set (set1, 1);
 798         mono_bitset_set (set1, 10);
 799         mono_bitset_set (set1, 31);
 800         mono_bitset_set (set1, 150);
 801
 802         mono_bitset_free (set1);
 803         mono_bitset_free (set2);
 804         mono_bitset_free (set3);
 805         mono_bitset_free (set4);
 806
 807         g_print ("total tests passed: %d\n", error - 1);
 808
 809         return 0;
 810 }
 811
 812 #endif