mono/utils/monobitset.c

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