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