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