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