mono/utils/monobitset.c

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