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->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         guint32 i, count;
 206         gsize d;
 207
 208         count = 0;
 209         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 210                 d = set->data [i];
 211 #ifdef __GNUC__
 212                 if (sizeof (gsize) == sizeof (unsigned int))
 213                         count += __builtin_popcount (d);
 214                 else
 215                         count += __builtin_popcountll (d);
 216 #else
 217                 while (d) {
 218                         count ++;
 219                         d &= (d - 1);
 220                 }
 221 #endif
 222         }
 223         return count;
 224 }
 225 #else
 226 guint32
 227 mono_bitset_count (const MonoBitSet *set) {
 228         static const guint32 table [] = {
 229                 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
 230         };
 231         guint32 i, count, val;
 232
 233         count = 0;
 234         for (i = 0; i < set->size / BITS_PER_CHUNK;+i) {
 235                 if (set->data [i]) {
 236                         val = set->data [i];
 237                         val = (val & table [0]) ((val >> 1) & table [0]);
 238                         val = (val & table [1]) ((val >> 2) & table [1]);
 239                         val = (val & table [2]) ((val >> 4) & table [2]);
 240                         val = (val & table [3]) ((val >> 8) & table [3]);
 241                         val = (val & table [4]) ((val >> 16) & table [4]);
 242                         count += val;
 243                 }
 244         }
 245         return count;
 246 }
 247
 248 #endif
 249
 250 #if 0
 251 const static int
 252 bitstart_mask [] = {
 253         0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8,
 254         0xfffffff0, 0xffffffe0, 0xffffffc0, 0xffffff80,
 255         0xffffff00, 0xfffffe00, 0xfffffc00, 0xfffff800,
 256         0xfffff000, 0xffffe000, 0xffffc000, 0xffff8000,
 257         0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
 258         0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
 259         0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
 260         0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
 261         0x00000000
 262 };
 263
 264 #define my_g_bit_nth_lsf(m,n) (ffs((m) & bitstart_mask [(n)+1])-1)
 265 #define my_g_bit_nth_lsf_nomask(m) (ffs((m))-1)
 266
 267 #else
 268
 269 static inline gint
 270 my_g_bit_nth_lsf (gsize mask, gint nth_bit)
 271 {
 272         nth_bit ++;
 273         mask >>= nth_bit;
 274
 275         if ((mask == 0) || (nth_bit == BITS_PER_CHUNK))
 276                 return -1;
 277
 278 #if defined(__native_client__) && (defined(__i386__) || defined(__x86_64))
 279 #define USE_X86_32BIT_INSTRUCTIONS 1
 280 #endif
 281
 282 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
 283  {
 284          int r;
 285          /* This depends on mask != 0 */
 286          __asm__("bsfl %1,%0\n\t"
 287                          : "=r" (r) : "g" (mask));
 288          return nth_bit + r;
 289  }
 290 #elif defined(__x86_64) && defined(__GNUC__)
 291  {
 292         guint64 r;
 293
 294         __asm__("bsfq %1,%0\n\t"
 295                         : "=r" (r) : "rm" (mask));
 296         return nth_bit + r;
 297  }
 298 #else
 299         while (! (mask & 0x1)) {
 300                 mask >>= 1;
 301                 nth_bit ++;
 302         }
 303
 304         return nth_bit;
 305 #endif
 306 }
 307
 308 static inline gint
 309 my_g_bit_nth_lsf_nomask (gsize mask)
 310 {
 311         /* Mask is expected to be != 0 */
 312 #if (defined(__i386__) && defined(__GNUC__)) || defined(USE_X86_32BIT_INSTRUCTIONS)
 313         int r;
 314
 315         __asm__("bsfl %1,%0\n\t"
 316                         : "=r" (r) : "rm" (mask));
 317         return r;
 318 #elif defined(__x86_64) && defined(__GNUC__)
 319         guint64 r;
 320
 321         __asm__("bsfq %1,%0\n\t"
 322                         : "=r" (r) : "rm" (mask));
 323         return r;
 324 #else
 325         int nth_bit = 0;
 326
 327         while (! (mask & 0x1)) {
 328                 mask >>= 1;
 329                 nth_bit ++;
 330         }
 331
 332         return nth_bit;
 333 #endif
 334 }
 335
 336 #endif
 337
 338 static inline int
 339 my_g_bit_nth_msf (gsize mask,
 340                gint   nth_bit)
 341 {
 342         int i;
 343
 344         if (nth_bit == 0)
 345                 return -1;
 346
 347         mask <<= BITS_PER_CHUNK - nth_bit;
 348
 349         i = BITS_PER_CHUNK;
 350         while ((i > 0) && !(mask >> (BITS_PER_CHUNK - 8))) {
 351                 mask <<= 8;
 352                 i -= 8;
 353         }
 354         if (mask == 0)
 355                 return -1;
 356
 357         do {
 358                 i--;
 359                 if (mask & ((gsize)1 << (BITS_PER_CHUNK - 1)))
 360                         return i - (BITS_PER_CHUNK - nth_bit);
 361                 mask <<= 1;
 362     }
 363         while (mask);
 364
 365         return -1;
 366 }
 367
 368 static int
 369 find_first_unset (gsize mask, gint nth_bit)
 370 {
 371         do {
 372                 nth_bit++;
 373                 if (!(mask & ((gsize)1 << nth_bit))) {
 374                         if (nth_bit == BITS_PER_CHUNK)
 375                                 /* On 64 bit platforms, 1 << 64 == 1 */
 376                                 return -1;
 377                         else
 378                                 return nth_bit;
 379                 }
 380         } while (nth_bit < BITS_PER_CHUNK);
 381         return -1;
 382 }
 383
 384 /**
 385  * mono_bitset_find_start:
 386  * \param set bitset ptr
 387  * Equivalent to <code>mono_bitset_find_first (set, -1)</code> 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  * \param set bitset ptr
 404  * \param pos pos to search after (not including)
 405  * \returns position of first set bit after \p pos. If \p pos < 0, begin search from
 406  * start. Return \c -1 if no bit set is found.
 407  */
 408 int
 409 mono_bitset_find_first (const MonoBitSet *set, gint pos) {
 410         int j;
 411         int bit;
 412         int result, i;
 413
 414         if (pos < 0) {
 415                 j = 0;
 416                 bit = -1;
 417         } else {
 418                 j = pos / BITS_PER_CHUNK;
 419                 bit = pos % BITS_PER_CHUNK;
 420                 g_assert (pos < set->size);
 421         }
 422         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 423
 424         if (set->data [j]) {
 425                 result = my_g_bit_nth_lsf (set->data [j], bit);
 426                 if (result != -1)
 427                         return result + j * BITS_PER_CHUNK;
 428         }
 429         for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
 430                 if (set->data [i])
 431                         return my_g_bit_nth_lsf (set->data [i], -1) + i * BITS_PER_CHUNK;
 432         }
 433         return -1;
 434 }
 435
 436 /**
 437  * mono_bitset_find_last:
 438  * \param set bitset ptr
 439  * \param pos pos to search before (not including)
 440  * \returns position of last set bit before \p pos. If \p pos < 0 search is
 441  * started from the end. Returns \c -1 if no set bit is found.
 442  */
 443 int
 444 mono_bitset_find_last (const MonoBitSet *set, gint pos) {
 445         int j, bit, result, i;
 446
 447         if (pos < 0)
 448                 pos = set->size - 1;
 449
 450         j = pos / BITS_PER_CHUNK;
 451         bit = pos % BITS_PER_CHUNK;
 452
 453         g_return_val_if_fail (pos < set->size, -1);
 454
 455         if (set->data [j]) {
 456                 result = my_g_bit_nth_msf (set->data [j], bit);
 457                 if (result != -1)
 458                         return result + j * BITS_PER_CHUNK;
 459         }
 460         for (i = --j; i >= 0; --i) {
 461                 if (set->data [i])
 462                         return my_g_bit_nth_msf (set->data [i], BITS_PER_CHUNK) + i * BITS_PER_CHUNK;
 463         }
 464         return -1;
 465 }
 466
 467 /**
 468  * mono_bitset_find_first_unset:
 469  * \param set bitset ptr
 470  * \param pos pos to search after (not including)
 471  * \returns position of first unset bit after \p pos. If \p pos < 0 begin search from
 472  * start. Return \c -1 if no bit set is found.
 473  */
 474 int
 475 mono_bitset_find_first_unset (const MonoBitSet *set, gint pos) {
 476         int j;
 477         int bit;
 478         int result, i;
 479
 480         if (pos < 0) {
 481                 j = 0;
 482                 bit = -1;
 483         } else {
 484                 j = pos / BITS_PER_CHUNK;
 485                 bit = pos % BITS_PER_CHUNK;
 486                 g_return_val_if_fail (pos < set->size, -1);
 487         }
 488         /*g_print ("find first from %d (j: %d, bit: %d)\n", pos, j, bit);*/
 489
 490         if (set->data [j] != -1) {
 491                 result = find_first_unset (set->data [j], bit);
 492                 if (result != -1)
 493                         return result + j * BITS_PER_CHUNK;
 494         }
 495         for (i = ++j; i < set->size / BITS_PER_CHUNK; ++i) {
 496                 if (set->data [i] != -1) {
 497                         return find_first_unset (set->data [i], -1) + i * BITS_PER_CHUNK;
 498                 }
 499         }
 500         return -1;
 501 }
 502
 503 /**
 504  * mono_bitset_clone:
 505  * \param set bitset ptr to clone
 506  * \param new_size number of bits the cloned bitset can hold
 507  * \returns a cloned bitset of size \p new_size. \c MONO_BITSET_DONT_FREE
 508  * unset in cloned bitset. If \p new_size is 0, the cloned object is just
 509  * as big.
 510  */
 511 MonoBitSet*
 512 mono_bitset_clone (const MonoBitSet *set, guint32 new_size) {
 513         MonoBitSet *result;
 514
 515         if (!new_size)
 516                 new_size = set->size;
 517         result = mono_bitset_new (new_size, set->flags);
 518         result->flags &= ~MONO_BITSET_DONT_FREE;
 519         memcpy (result->data, set->data, set->size / 8);
 520         return result;
 521 }
 522
 523 /**
 524  * mono_bitset_copyto:
 525  * \param src bitset ptr to copy from
 526  * \param dest bitset ptr to copy to
 527  *
 528  * Copy one bitset to another.
 529  */
 530 void
 531 mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
 532         g_assert (dest->size <= src->size);
 533
 534         memcpy (&dest->data, &src->data, dest->size / 8);
 535 }
 536
 537 /**
 538  * mono_bitset_union:
 539  * \param dest bitset ptr to hold union
 540  * \param src bitset ptr to copy
 541  *
 542  * Make union of one bitset and another.
 543  */
 544 void
 545 mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
 546         int i, size;
 547
 548         g_assert (src->size <= dest->size);
 549
 550         size = dest->size / BITS_PER_CHUNK;
 551         for (i = 0; i < size; ++i)
 552                 dest->data [i] |= src->data [i];
 553 }
 554
 555 /**
 556  * mono_bitset_intersection:
 557  * \param dest bitset ptr to hold intersection
 558  * \param src bitset ptr to copy
 559  *
 560  * Make intersection of one bitset and another.
 561  */
 562 void
 563 mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
 564         int i, size;
 565
 566         g_assert (src->size <= dest->size);
 567
 568         size = dest->size / BITS_PER_CHUNK;
 569         for (i = 0; i < size; ++i)
 570                 dest->data [i] &= src->data [i];
 571 }
 572
 573 /**
 574  * mono_bitset_intersection_2:
 575  * \param dest bitset ptr to hold intersection
 576  * \param src1 first bitset
 577  * \param src2 second bitset
 578  *
 579  * Make intersection of two bitsets
 580  */
 581 void
 582 mono_bitset_intersection_2 (MonoBitSet *dest, const MonoBitSet *src1, const MonoBitSet *src2) {
 583         int i, size;
 584
 585         g_assert (src1->size <= dest->size);
 586         g_assert (src2->size <= dest->size);
 587
 588         size = dest->size / BITS_PER_CHUNK;
 589         for (i = 0; i < size; ++i)
 590                 dest->data [i] = src1->data [i] & src2->data [i];
 591 }
 592
 593 /**
 594  * mono_bitset_sub:
 595  * \param dest bitset ptr to hold bitset - src
 596  * \param src bitset ptr to copy
 597  *
 598  * Unset all bits in \p dest that are set in \p src.
 599  */
 600 void
 601 mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
 602         int i, size;
 603
 604         g_assert (src->size <= dest->size);
 605
 606         size = src->size / BITS_PER_CHUNK;
 607         for (i = 0; i < size; ++i)
 608                 dest->data [i] &= ~src->data [i];
 609 }
 610
 611 /**
 612  * mono_bitset_equal:
 613  * \param src bitset ptr
 614  * \param src1 bitset ptr
 615  * \returns TRUE if their size are the same and the same bits are set in
 616  * both bitsets.
 617  */
 618 gboolean
 619 mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1) {
 620         int i;
 621         if (src->size != src1->size)
 622                 return FALSE;
 623
 624         for (i = 0; i < src->size / BITS_PER_CHUNK; ++i)
 625                 if (src->data [i] != src1->data [i])
 626                         return FALSE;
 627         return TRUE;
 628 }
 629
 630 /**
 631  * mono_bitset_foreach:
 632  * \param set bitset ptr
 633  * \param func Function to call for every set bit
 634  * \param data pass this as second arg to func
 635  * Calls \p func for every bit set in bitset. Argument 1 is the number of
 636  * the bit set, argument 2 is data
 637  */
 638 void
 639 mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data)
 640 {
 641         int i, j;
 642         for (i = 0; i < set->size / BITS_PER_CHUNK; ++i) {
 643                 if (set->data [i]) {
 644                         for (j = 0; j < BITS_PER_CHUNK; ++j)
 645                                 if (set->data [i] & ((gsize)1 << j))
 646                                         func (j + i * BITS_PER_CHUNK, data);
 647                 }
 648         }
 649 }
 650
 651 #ifdef TEST_BITSET
 652
 653 /*
 654  * Compile with:
 655  * gcc -g -Wall -DTEST_BITSET -o monobitset monobitset.c `pkg-config --cflags --libs glib-2.0`
 656  */
 657 int
 658 main() {
 659         MonoBitSet *set1, *set2, *set3, *set4;
 660         int error = 1;
 661         int count, i;
 662
 663         set1 = mono_bitset_new (60, 0);
 664         set4 = mono_bitset_new (60, 0);
 665
 666         if (mono_bitset_count (set1) != 0)
 667                 return error;
 668         error++;
 669
 670         mono_bitset_set (set1, 33);
 671         if (mono_bitset_count (set1) != 1)
 672                 return error;
 673         error++;
 674
 675         /* g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0)); */
 676
 677         if (mono_bitset_find_first (set1, 0) != 33)
 678                 return error;
 679         error++;
 680
 681         if (mono_bitset_find_first (set1, 33) != -1)
 682                 return error;
 683         error++;
 684
 685         /* test 5 */
 686         if (mono_bitset_find_first (set1, -100) != 33)
 687                 return error;
 688         error++;
 689
 690         if (mono_bitset_find_last (set1, -1) != 33)
 691                 return error;
 692         error++;
 693
 694         if (mono_bitset_find_last (set1, 33) != -1)
 695                 return error;
 696         error++;
 697
 698         if (mono_bitset_find_last (set1, -100) != 33)
 699                 return error;
 700         error++;
 701
 702         if (mono_bitset_find_last (set1, 34) != 33)
 703                 return error;
 704         error++;
 705
 706         /* test 10 */
 707         if (!mono_bitset_test (set1, 33))
 708                 return error;
 709         error++;
 710
 711         if (mono_bitset_test (set1, 32) || mono_bitset_test (set1, 34))
 712                 return error;
 713         error++;
 714
 715         set2 = mono_bitset_clone (set1, 0);
 716         if (mono_bitset_count (set2) != 1)
 717                 return error;
 718         error++;
 719
 720         mono_bitset_invert (set2);
 721         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 1))
 722                 return error;
 723         error++;
 724
 725         mono_bitset_clear (set2, 10);
 726         if (mono_bitset_count (set2) != (mono_bitset_size (set2) - 2))
 727                 return error;
 728         error++;
 729
 730         /* test 15 */
 731         set3 = mono_bitset_clone (set2, 0);
 732         mono_bitset_union (set3, set1);
 733         if (mono_bitset_count (set3) != (mono_bitset_size (set3) - 1))
 734                 return error;
 735         error++;
 736
 737         mono_bitset_clear_all (set2);
 738         if (mono_bitset_count (set2) != 0)
 739                 return error;
 740         error++;
 741
 742         mono_bitset_invert (set2);
 743         if (mono_bitset_count (set2) != mono_bitset_size (set2))
 744                 return error;
 745         error++;
 746
 747         mono_bitset_set (set4, 0);
 748         mono_bitset_set (set4, 1);
 749         mono_bitset_set (set4, 10);
 750         if (mono_bitset_count (set4) != 3)
 751                 return error;
 752         error++;
 753
 754         count = 0;
 755         for (i = mono_bitset_find_first (set4, -1); i != -1; i = mono_bitset_find_first (set4, i)) {
 756                 count ++;
 757                 switch (count) {
 758                 case 1:
 759                   if (i != 0)
 760                     return error;
 761                   break;
 762                 case 2:
 763                   if (i != 1)
 764                     return error;
 765                   break;
 766                 case 3:
 767                   if (i != 10)
 768                     return error;
 769                   break;
 770                 }
 771                 /* g_print ("count got: %d at %d\n", count, i); */
 772         }
 773         if (count != 3)
 774                 return error;
 775         error++;
 776
 777         if (mono_bitset_find_first (set4, -1) != 0)
 778                 return error;
 779         error++;
 780
 781         /* 20 */
 782         mono_bitset_set (set4, 31);
 783         if (mono_bitset_find_first (set4, 10) != 31)
 784                 return error;
 785         error++;
 786
 787         mono_bitset_free (set1);
 788
 789         set1 = mono_bitset_new (200, 0);
 790         mono_bitset_set (set1, 0);
 791         mono_bitset_set (set1, 1);
 792         mono_bitset_set (set1, 10);
 793         mono_bitset_set (set1, 31);
 794         mono_bitset_set (set1, 150);
 795
 796         mono_bitset_free (set1);
 797         mono_bitset_free (set2);
 798         mono_bitset_free (set3);
 799         mono_bitset_free (set4);
 800
 801         g_print ("total tests passed: %d\n", error - 1);
 802
 803         return 0;
 804 }
 805
 806 #endif