1 /* Variable array bitsets. 2 3 Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc. 4 5 Contributed by Michael Hayes (m.hayes (at) elec.canterbury.ac.nz). 6 7 This program is free software: you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation, either version 3 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 19 20 #include <config.h> 21 22 #include "vbitset.h" 23 24 #include <stdlib.h> 25 #include <string.h> 26 27 /* This file implements variable size bitsets stored as a variable 28 length array of words. Any unused bits in the last word must be 29 zero. 30 31 Note that binary or ternary operations assume that each bitset operand 32 has the same size. 33 */ 34 35 static void vbitset_unused_clear (bitset); 36 37 static void vbitset_set (bitset, bitset_bindex); 38 static void vbitset_reset (bitset, bitset_bindex); 39 static bool vbitset_test (bitset, bitset_bindex); 40 static bitset_bindex vbitset_list (bitset, bitset_bindex *, 41 bitset_bindex, bitset_bindex *); 42 static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *, 43 bitset_bindex, bitset_bindex *); 44 45 #define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) 46 #define VBITSET_WORDS(X) ((X)->b.cdata) 47 #define VBITSET_SIZE(X) ((X)->b.csize) 48 #define VBITSET_ASIZE(X) ((X)->v.size) 49 50 #undef min 51 #undef max 52 #define min(a, b) ((a) > (b) ? (b) : (a)) 53 #define max(a, b) ((a) > (b) ? (a) : (b)) 54 55 static bitset_bindex 56 vbitset_resize (bitset src, bitset_bindex n_bits) 57 { 58 bitset_windex oldsize; 59 bitset_windex newsize; 60 61 if (n_bits == BITSET_NBITS_ (src)) 62 return n_bits; 63 64 oldsize = VBITSET_SIZE (src); 65 newsize = VBITSET_N_WORDS (n_bits); 66 67 if (oldsize < newsize) 68 { 69 bitset_windex size; 70 71 /* The bitset needs to grow. If we already have enough memory 72 allocated, then just zero what we need. */ 73 if (newsize > VBITSET_ASIZE (src)) 74 { 75 /* We need to allocate more memory. When oldsize is 76 non-zero this means that we are changing the size, so 77 grow the bitset 25% larger than requested to reduce 78 number of reallocations. */ 79 80 if (oldsize == 0) 81 size = newsize; 82 else 83 size = newsize + newsize / 4; 84 85 VBITSET_WORDS (src) 86 = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word)); 87 VBITSET_ASIZE (src) = size; 88 } 89 90 memset (VBITSET_WORDS (src) + oldsize, 0, 91 (newsize - oldsize) * sizeof (bitset_word)); 92 VBITSET_SIZE (src) = newsize; 93 } 94 else 95 { 96 /* The bitset needs to shrink. There's no point deallocating 97 the memory unless it is shrinking by a reasonable amount. */ 98 if ((oldsize - newsize) >= oldsize / 2) 99 { 100 VBITSET_WORDS (src) 101 = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word)); 102 VBITSET_ASIZE (src) = newsize; 103 } 104 105 /* Need to prune any excess bits. FIXME. */ 106 107 VBITSET_SIZE (src) = newsize; 108 } 109 110 BITSET_NBITS_ (src) = n_bits; 111 return n_bits; 112 } 113 114 115 /* Set bit BITNO in bitset DST. */ 116 static void 117 vbitset_set (dst, bitno) 118 bitset dst; 119 bitset_bindex bitno; 120 { 121 bitset_windex windex = bitno / BITSET_WORD_BITS; 122 123 /* Perhaps we should abort. The user should explicitly call 124 bitset_resize since this will not catch the case when we set a 125 bit larger than the current size but smaller than the allocated 126 size. */ 127 vbitset_resize (dst, bitno); 128 129 dst->b.cdata[windex - dst->b.cindex] |= 130 (bitset_word) 1 << (bitno % BITSET_WORD_BITS); 131 } 132 133 134 /* Reset bit BITNO in bitset DST. */ 135 static void 136 vbitset_reset (dst, bitno) 137 bitset dst ATTRIBUTE_UNUSED; 138 bitset_bindex bitno ATTRIBUTE_UNUSED; 139 { 140 /* We must be accessing outside the cache so the bit is 141 zero anyway. */ 142 } 143 144 145 /* Test bit BITNO in bitset SRC. */ 146 static bool 147 vbitset_test (src, bitno) 148 bitset src ATTRIBUTE_UNUSED; 149 bitset_bindex bitno ATTRIBUTE_UNUSED; 150 { 151 /* We must be accessing outside the cache so the bit is 152 zero anyway. */ 153 return 0; 154 } 155 156 157 /* Find list of up to NUM bits set in BSET in reverse order, starting 158 from and including NEXT and store in array LIST. Return with 159 actual number of bits found and with *NEXT indicating where search 160 stopped. */ 161 static bitset_bindex 162 vbitset_list_reverse (src, list, num, next) 163 bitset src; 164 bitset_bindex *list; 165 bitset_bindex num; 166 bitset_bindex *next; 167 { 168 bitset_bindex bitno; 169 bitset_bindex rbitno; 170 bitset_bindex count; 171 bitset_windex windex; 172 unsigned int bitcnt; 173 bitset_bindex bitoff; 174 bitset_word *srcp = VBITSET_WORDS (src); 175 bitset_bindex n_bits = BITSET_SIZE_ (src); 176 177 rbitno = *next; 178 179 /* If num is 1, we could speed things up with a binary search 180 of the word of interest. */ 181 182 if (rbitno >= n_bits) 183 return 0; 184 185 count = 0; 186 187 bitno = n_bits - (rbitno + 1); 188 189 windex = bitno / BITSET_WORD_BITS; 190 bitcnt = bitno % BITSET_WORD_BITS; 191 bitoff = windex * BITSET_WORD_BITS; 192 193 do 194 { 195 bitset_word word; 196 197 word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); 198 for (; word; bitcnt--) 199 { 200 if (word & BITSET_MSB) 201 { 202 list[count++] = bitoff + bitcnt; 203 if (count >= num) 204 { 205 *next = n_bits - (bitoff + bitcnt); 206 return count; 207 } 208 } 209 word <<= 1; 210 } 211 bitoff -= BITSET_WORD_BITS; 212 bitcnt = BITSET_WORD_BITS - 1; 213 } 214 while (windex--); 215 216 *next = n_bits - (bitoff + 1); 217 return count; 218 } 219 220 221 /* Find list of up to NUM bits set in BSET starting from and including 222 *NEXT and store in array LIST. Return with actual number of bits 223 found and with *NEXT indicating where search stopped. */ 224 static bitset_bindex 225 vbitset_list (src, list, num, next) 226 bitset src; 227 bitset_bindex *list; 228 bitset_bindex num; 229 bitset_bindex *next; 230 { 231 bitset_bindex bitno; 232 bitset_bindex count; 233 bitset_windex windex; 234 bitset_bindex bitoff; 235 bitset_windex size = VBITSET_SIZE (src); 236 bitset_word *srcp = VBITSET_WORDS (src); 237 bitset_word word; 238 239 bitno = *next; 240 241 count = 0; 242 if (!bitno) 243 { 244 /* Many bitsets are zero, so make this common case fast. */ 245 for (windex = 0; windex < size && !srcp[windex]; windex++) 246 continue; 247 if (windex >= size) 248 return 0; 249 250 /* If num is 1, we could speed things up with a binary search 251 of the current word. */ 252 253 bitoff = windex * BITSET_WORD_BITS; 254 } 255 else 256 { 257 if (bitno >= BITSET_SIZE_ (src)) 258 return 0; 259 260 windex = bitno / BITSET_WORD_BITS; 261 bitno = bitno % BITSET_WORD_BITS; 262 263 if (bitno) 264 { 265 /* Handle the case where we start within a word. 266 Most often, this is executed with large bitsets 267 with many set bits where we filled the array 268 on the previous call to this function. */ 269 270 bitoff = windex * BITSET_WORD_BITS; 271 word = srcp[windex] >> bitno; 272 for (bitno = bitoff + bitno; word; bitno++) 273 { 274 if (word & 1) 275 { 276 list[count++] = bitno; 277 if (count >= num) 278 { 279 *next = bitno + 1; 280 return count; 281 } 282 } 283 word >>= 1; 284 } 285 windex++; 286 } 287 bitoff = windex * BITSET_WORD_BITS; 288 } 289 290 for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) 291 { 292 if (!(word = srcp[windex])) 293 continue; 294 295 if ((count + BITSET_WORD_BITS) < num) 296 { 297 for (bitno = bitoff; word; bitno++) 298 { 299 if (word & 1) 300 list[count++] = bitno; 301 word >>= 1; 302 } 303 } 304 else 305 { 306 for (bitno = bitoff; word; bitno++) 307 { 308 if (word & 1) 309 { 310 list[count++] = bitno; 311 if (count >= num) 312 { 313 *next = bitno + 1; 314 return count; 315 } 316 } 317 word >>= 1; 318 } 319 } 320 } 321 322 *next = bitoff; 323 return count; 324 } 325 326 327 /* Ensure that any unused bits within the last word are clear. */ 328 static inline void 329 vbitset_unused_clear (dst) 330 bitset dst; 331 { 332 unsigned int last_bit; 333 334 last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS; 335 if (last_bit) 336 VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &= 337 ((bitset_word) 1 << last_bit) - 1; 338 } 339 340 341 static void 342 vbitset_ones (bitset dst) 343 { 344 bitset_word *dstp = VBITSET_WORDS (dst); 345 unsigned int bytes; 346 347 bytes = sizeof (bitset_word) * VBITSET_SIZE (dst); 348 349 memset (dstp, -1, bytes); 350 vbitset_unused_clear (dst); 351 } 352 353 354 static void 355 vbitset_zero (bitset dst) 356 { 357 bitset_word *dstp = VBITSET_WORDS (dst); 358 unsigned int bytes; 359 360 bytes = sizeof (bitset_word) * VBITSET_SIZE (dst); 361 362 memset (dstp, 0, bytes); 363 } 364 365 366 static bool 367 vbitset_empty_p (bitset dst) 368 { 369 unsigned int i; 370 bitset_word *dstp = VBITSET_WORDS (dst); 371 372 for (i = 0; i < VBITSET_SIZE (dst); i++) 373 if (dstp[i]) 374 return 0; 375 376 return 1; 377 } 378 379 380 static void 381 vbitset_copy1 (bitset dst, bitset src) 382 { 383 bitset_word *srcp; 384 bitset_word *dstp; 385 bitset_windex ssize; 386 bitset_windex dsize; 387 388 if (src == dst) 389 return; 390 391 vbitset_resize (dst, BITSET_SIZE_ (src)); 392 393 srcp = VBITSET_WORDS (src); 394 dstp = VBITSET_WORDS (dst); 395 ssize = VBITSET_SIZE (src); 396 dsize = VBITSET_SIZE (dst); 397 398 memcpy (dstp, srcp, sizeof (bitset_word) * ssize); 399 400 memset (dstp + sizeof (bitset_word) * ssize, 0, 401 sizeof (bitset_word) * (dsize - ssize)); 402 } 403 404 405 static void 406 vbitset_not (bitset dst, bitset src) 407 { 408 unsigned int i; 409 bitset_word *srcp; 410 bitset_word *dstp; 411 bitset_windex ssize; 412 bitset_windex dsize; 413 414 vbitset_resize (dst, BITSET_SIZE_ (src)); 415 416 srcp = VBITSET_WORDS (src); 417 dstp = VBITSET_WORDS (dst); 418 ssize = VBITSET_SIZE (src); 419 dsize = VBITSET_SIZE (dst); 420 421 for (i = 0; i < ssize; i++) 422 *dstp++ = ~(*srcp++); 423 424 vbitset_unused_clear (dst); 425 memset (dstp + sizeof (bitset_word) * ssize, 0, 426 sizeof (bitset_word) * (dsize - ssize)); 427 } 428 429 430 static bool 431 vbitset_equal_p (bitset dst, bitset src) 432 { 433 unsigned int i; 434 bitset_word *srcp = VBITSET_WORDS (src); 435 bitset_word *dstp = VBITSET_WORDS (dst); 436 bitset_windex ssize = VBITSET_SIZE (src); 437 bitset_windex dsize = VBITSET_SIZE (dst); 438 439 for (i = 0; i < min (ssize, dsize); i++) 440 if (*srcp++ != *dstp++) 441 return 0; 442 443 if (ssize > dsize) 444 { 445 for (; i < ssize; i++) 446 if (*srcp++) 447 return 0; 448 } 449 else 450 { 451 for (; i < dsize; i++) 452 if (*dstp++) 453 return 0; 454 } 455 456 return 1; 457 } 458 459 460 static bool 461 vbitset_subset_p (bitset dst, bitset src) 462 { 463 unsigned int i; 464 bitset_word *srcp = VBITSET_WORDS (src); 465 bitset_word *dstp = VBITSET_WORDS (dst); 466 bitset_windex ssize = VBITSET_SIZE (src); 467 bitset_windex dsize = VBITSET_SIZE (dst); 468 469 for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++) 470 if (*dstp != (*srcp | *dstp)) 471 return 0; 472 473 if (ssize > dsize) 474 { 475 for (; i < ssize; i++) 476 if (*srcp++) 477 return 0; 478 } 479 480 return 1; 481 } 482 483 484 static bool 485 vbitset_disjoint_p (bitset dst, bitset src) 486 { 487 unsigned int i; 488 bitset_word *srcp = VBITSET_WORDS (src); 489 bitset_word *dstp = VBITSET_WORDS (dst); 490 bitset_windex ssize = VBITSET_SIZE (src); 491 bitset_windex dsize = VBITSET_SIZE (dst); 492 493 for (i = 0; i < min (ssize, dsize); i++) 494 if (*srcp++ & *dstp++) 495 return 0; 496 497 return 1; 498 } 499 500 501 static void 502 vbitset_and (bitset dst, bitset src1, bitset src2) 503 { 504 unsigned int i; 505 bitset_word *src1p; 506 bitset_word *src2p; 507 bitset_word *dstp; 508 bitset_windex ssize1; 509 bitset_windex ssize2; 510 bitset_windex dsize; 511 512 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 513 514 dsize = VBITSET_SIZE (dst); 515 ssize1 = VBITSET_SIZE (src1); 516 ssize2 = VBITSET_SIZE (src2); 517 dstp = VBITSET_WORDS (dst); 518 src1p = VBITSET_WORDS (src1); 519 src2p = VBITSET_WORDS (src2); 520 521 for (i = 0; i < min (ssize1, ssize2); i++) 522 *dstp++ = *src1p++ & *src2p++; 523 524 memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2))); 525 } 526 527 528 static bool 529 vbitset_and_cmp (bitset dst, bitset src1, bitset src2) 530 { 531 unsigned int i; 532 int changed = 0; 533 bitset_word *src1p; 534 bitset_word *src2p; 535 bitset_word *dstp; 536 bitset_windex ssize1; 537 bitset_windex ssize2; 538 bitset_windex dsize; 539 540 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 541 542 dsize = VBITSET_SIZE (dst); 543 ssize1 = VBITSET_SIZE (src1); 544 ssize2 = VBITSET_SIZE (src2); 545 dstp = VBITSET_WORDS (dst); 546 src1p = VBITSET_WORDS (src1); 547 src2p = VBITSET_WORDS (src2); 548 549 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) 550 { 551 bitset_word tmp = *src1p++ & *src2p++; 552 553 if (*dstp != tmp) 554 { 555 changed = 1; 556 *dstp = tmp; 557 } 558 } 559 560 if (ssize2 > ssize1) 561 { 562 src1p = src2p; 563 ssize1 = ssize2; 564 } 565 566 for (; i < ssize1; i++, dstp++) 567 { 568 if (*dstp != 0) 569 { 570 changed = 1; 571 *dstp = 0; 572 } 573 } 574 575 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); 576 577 return changed; 578 } 579 580 581 static void 582 vbitset_andn (bitset dst, bitset src1, bitset src2) 583 { 584 unsigned int i; 585 bitset_word *src1p; 586 bitset_word *src2p; 587 bitset_word *dstp; 588 bitset_windex ssize1; 589 bitset_windex ssize2; 590 bitset_windex dsize; 591 592 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 593 594 dsize = VBITSET_SIZE (dst); 595 ssize1 = VBITSET_SIZE (src1); 596 ssize2 = VBITSET_SIZE (src2); 597 dstp = VBITSET_WORDS (dst); 598 src1p = VBITSET_WORDS (src1); 599 src2p = VBITSET_WORDS (src2); 600 601 for (i = 0; i < min (ssize1, ssize2); i++) 602 *dstp++ = *src1p++ & ~(*src2p++); 603 604 if (ssize2 > ssize1) 605 { 606 for (; i < ssize2; i++) 607 *dstp++ = 0; 608 609 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2)); 610 } 611 else 612 { 613 for (; i < ssize1; i++) 614 *dstp++ = *src1p++; 615 616 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); 617 } 618 } 619 620 621 static bool 622 vbitset_andn_cmp (bitset dst, bitset src1, bitset src2) 623 { 624 unsigned int i; 625 int changed = 0; 626 bitset_word *src1p; 627 bitset_word *src2p; 628 bitset_word *dstp; 629 bitset_windex ssize1; 630 bitset_windex ssize2; 631 bitset_windex dsize; 632 633 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 634 635 dsize = VBITSET_SIZE (dst); 636 ssize1 = VBITSET_SIZE (src1); 637 ssize2 = VBITSET_SIZE (src2); 638 dstp = VBITSET_WORDS (dst); 639 src1p = VBITSET_WORDS (src1); 640 src2p = VBITSET_WORDS (src2); 641 642 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) 643 { 644 bitset_word tmp = *src1p++ & ~(*src2p++); 645 646 if (*dstp != tmp) 647 { 648 changed = 1; 649 *dstp = tmp; 650 } 651 } 652 653 if (ssize2 > ssize1) 654 { 655 for (; i < ssize2; i++, dstp++) 656 { 657 if (*dstp != 0) 658 { 659 changed = 1; 660 *dstp = 0; 661 } 662 } 663 664 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2)); 665 } 666 else 667 { 668 for (; i < ssize1; i++, dstp++) 669 { 670 bitset_word tmp = *src1p++; 671 672 if (*dstp != tmp) 673 { 674 changed = 1; 675 *dstp = tmp; 676 } 677 } 678 679 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); 680 } 681 682 return changed; 683 } 684 685 686 static void 687 vbitset_or (bitset dst, bitset src1, bitset src2) 688 { 689 unsigned int i; 690 bitset_word *src1p; 691 bitset_word *src2p; 692 bitset_word *dstp; 693 bitset_windex ssize1; 694 bitset_windex ssize2; 695 bitset_windex dsize; 696 697 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 698 699 dsize = VBITSET_SIZE (dst); 700 ssize1 = VBITSET_SIZE (src1); 701 ssize2 = VBITSET_SIZE (src2); 702 dstp = VBITSET_WORDS (dst); 703 src1p = VBITSET_WORDS (src1); 704 src2p = VBITSET_WORDS (src2); 705 706 for (i = 0; i < min (ssize1, ssize2); i++) 707 *dstp++ = *src1p++ | *src2p++; 708 709 if (ssize2 > ssize1) 710 { 711 src1p = src2p; 712 ssize1 = ssize2; 713 } 714 715 for (; i < ssize1; i++) 716 *dstp++ = *src1p++; 717 718 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); 719 } 720 721 722 static bool 723 vbitset_or_cmp (bitset dst, bitset src1, bitset src2) 724 { 725 unsigned int i; 726 int changed = 0; 727 bitset_word *src1p; 728 bitset_word *src2p; 729 bitset_word *dstp; 730 bitset_windex ssize1; 731 bitset_windex ssize2; 732 bitset_windex dsize; 733 734 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 735 736 dsize = VBITSET_SIZE (dst); 737 ssize1 = VBITSET_SIZE (src1); 738 ssize2 = VBITSET_SIZE (src2); 739 dstp = VBITSET_WORDS (dst); 740 src1p = VBITSET_WORDS (src1); 741 src2p = VBITSET_WORDS (src2); 742 743 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) 744 { 745 bitset_word tmp = *src1p++ | *src2p++; 746 747 if (*dstp != tmp) 748 { 749 changed = 1; 750 *dstp = tmp; 751 } 752 } 753 754 if (ssize2 > ssize1) 755 { 756 src1p = src2p; 757 ssize1 = ssize2; 758 } 759 760 for (; i < ssize1; i++, dstp++) 761 { 762 bitset_word tmp = *src1p++; 763 764 if (*dstp != tmp) 765 { 766 changed = 1; 767 *dstp = tmp; 768 } 769 } 770 771 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); 772 773 return changed; 774 } 775 776 777 static void 778 vbitset_xor (bitset dst, bitset src1, bitset src2) 779 { 780 unsigned int i; 781 bitset_word *src1p; 782 bitset_word *src2p; 783 bitset_word *dstp; 784 bitset_windex ssize1; 785 bitset_windex ssize2; 786 bitset_windex dsize; 787 788 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 789 790 dsize = VBITSET_SIZE (dst); 791 ssize1 = VBITSET_SIZE (src1); 792 ssize2 = VBITSET_SIZE (src2); 793 dstp = VBITSET_WORDS (dst); 794 src1p = VBITSET_WORDS (src1); 795 src2p = VBITSET_WORDS (src2); 796 797 for (i = 0; i < min (ssize1, ssize2); i++) 798 *dstp++ = *src1p++ ^ *src2p++; 799 800 if (ssize2 > ssize1) 801 { 802 src1p = src2p; 803 ssize1 = ssize2; 804 } 805 806 for (; i < ssize1; i++) 807 *dstp++ = *src1p++; 808 809 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); 810 } 811 812 813 static bool 814 vbitset_xor_cmp (bitset dst, bitset src1, bitset src2) 815 { 816 unsigned int i; 817 int changed = 0; 818 bitset_word *src1p; 819 bitset_word *src2p; 820 bitset_word *dstp; 821 bitset_windex ssize1; 822 bitset_windex ssize2; 823 bitset_windex dsize; 824 825 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2))); 826 827 dsize = VBITSET_SIZE (dst); 828 ssize1 = VBITSET_SIZE (src1); 829 ssize2 = VBITSET_SIZE (src2); 830 dstp = VBITSET_WORDS (dst); 831 src1p = VBITSET_WORDS (src1); 832 src2p = VBITSET_WORDS (src2); 833 834 for (i = 0; i < min (ssize1, ssize2); i++, dstp++) 835 { 836 bitset_word tmp = *src1p++ ^ *src2p++; 837 838 if (*dstp != tmp) 839 { 840 changed = 1; 841 *dstp = tmp; 842 } 843 } 844 845 if (ssize2 > ssize1) 846 { 847 src1p = src2p; 848 ssize1 = ssize2; 849 } 850 851 for (; i < ssize1; i++, dstp++) 852 { 853 bitset_word tmp = *src1p++; 854 855 if (*dstp != tmp) 856 { 857 changed = 1; 858 *dstp = tmp; 859 } 860 } 861 862 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1)); 863 864 return changed; 865 } 866 867 868 /* FIXME, these operations need fixing for different size 869 bitsets. */ 870 871 static void 872 vbitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3) 873 { 874 unsigned int i; 875 bitset_word *src1p; 876 bitset_word *src2p; 877 bitset_word *src3p; 878 bitset_word *dstp; 879 bitset_windex size; 880 881 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) 882 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) 883 { 884 bitset_and_or_ (dst, src1, src2, src3); 885 return; 886 } 887 888 vbitset_resize (dst, BITSET_NBITS_ (src1)); 889 890 src1p = VBITSET_WORDS (src1); 891 src2p = VBITSET_WORDS (src2); 892 src3p = VBITSET_WORDS (src3); 893 dstp = VBITSET_WORDS (dst); 894 size = VBITSET_SIZE (dst); 895 896 for (i = 0; i < size; i++) 897 *dstp++ = (*src1p++ & *src2p++) | *src3p++; 898 } 899 900 901 static bool 902 vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 903 { 904 unsigned int i; 905 int changed = 0; 906 bitset_word *src1p; 907 bitset_word *src2p; 908 bitset_word *src3p; 909 bitset_word *dstp; 910 bitset_windex size; 911 912 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) 913 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) 914 return bitset_and_or_cmp_ (dst, src1, src2, src3); 915 916 vbitset_resize (dst, BITSET_NBITS_ (src1)); 917 918 src1p = VBITSET_WORDS (src1); 919 src2p = VBITSET_WORDS (src2); 920 src3p = VBITSET_WORDS (src3); 921 dstp = VBITSET_WORDS (dst); 922 size = VBITSET_SIZE (dst); 923 924 for (i = 0; i < size; i++, dstp++) 925 { 926 bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; 927 928 if (*dstp != tmp) 929 { 930 changed = 1; 931 *dstp = tmp; 932 } 933 } 934 return changed; 935 } 936 937 938 static void 939 vbitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) 940 { 941 unsigned int i; 942 bitset_word *src1p; 943 bitset_word *src2p; 944 bitset_word *src3p; 945 bitset_word *dstp; 946 bitset_windex size; 947 948 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) 949 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) 950 { 951 bitset_andn_or_ (dst, src1, src2, src3); 952 return; 953 } 954 955 vbitset_resize (dst, BITSET_NBITS_ (src1)); 956 957 src1p = VBITSET_WORDS (src1); 958 src2p = VBITSET_WORDS (src2); 959 src3p = VBITSET_WORDS (src3); 960 dstp = VBITSET_WORDS (dst); 961 size = VBITSET_SIZE (dst); 962 963 for (i = 0; i < size; i++) 964 *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++; 965 } 966 967 968 static bool 969 vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 970 { 971 unsigned int i; 972 int changed = 0; 973 bitset_word *src1p; 974 bitset_word *src2p; 975 bitset_word *src3p; 976 bitset_word *dstp; 977 bitset_windex size; 978 979 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) 980 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) 981 return bitset_andn_or_cmp_ (dst, src1, src2, src3); 982 983 vbitset_resize (dst, BITSET_NBITS_ (src1)); 984 985 src1p = VBITSET_WORDS (src1); 986 src2p = VBITSET_WORDS (src2); 987 src3p = VBITSET_WORDS (src3); 988 dstp = VBITSET_WORDS (dst); 989 size = VBITSET_SIZE (dst); 990 991 for (i = 0; i < size; i++, dstp++) 992 { 993 bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; 994 995 if (*dstp != tmp) 996 { 997 changed = 1; 998 *dstp = tmp; 999 } 1000 } 1001 return changed; 1002 } 1003 1004 1005 static void 1006 vbitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3) 1007 { 1008 unsigned int i; 1009 bitset_word *src1p; 1010 bitset_word *src2p; 1011 bitset_word *src3p; 1012 bitset_word *dstp; 1013 bitset_windex size; 1014 1015 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) 1016 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) 1017 { 1018 bitset_or_and_ (dst, src1, src2, src3); 1019 return; 1020 } 1021 1022 vbitset_resize (dst, BITSET_NBITS_ (src1)); 1023 1024 src1p = VBITSET_WORDS (src1); 1025 src2p = VBITSET_WORDS (src2); 1026 src3p = VBITSET_WORDS (src3); 1027 dstp = VBITSET_WORDS (dst); 1028 size = VBITSET_SIZE (dst); 1029 1030 for (i = 0; i < size; i++) 1031 *dstp++ = (*src1p++ | *src2p++) & *src3p++; 1032 } 1033 1034 1035 static bool 1036 vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 1037 { 1038 unsigned int i; 1039 int changed = 0; 1040 bitset_word *src1p; 1041 bitset_word *src2p; 1042 bitset_word *src3p; 1043 bitset_word *dstp; 1044 bitset_windex size; 1045 1046 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2) 1047 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3)) 1048 return bitset_or_and_cmp_ (dst, src1, src2, src3); 1049 1050 vbitset_resize (dst, BITSET_NBITS_ (src1)); 1051 1052 src1p = VBITSET_WORDS (src1); 1053 src2p = VBITSET_WORDS (src2); 1054 src3p = VBITSET_WORDS (src3); 1055 dstp = VBITSET_WORDS (dst); 1056 size = VBITSET_SIZE (dst); 1057 1058 for (i = 0; i < size; i++, dstp++) 1059 { 1060 bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; 1061 1062 if (*dstp != tmp) 1063 { 1064 changed = 1; 1065 *dstp = tmp; 1066 } 1067 } 1068 return changed; 1069 } 1070 1071 1072 static void 1073 vbitset_copy (bitset dst, bitset src) 1074 { 1075 if (BITSET_COMPATIBLE_ (dst, src)) 1076 vbitset_copy1 (dst, src); 1077 else 1078 bitset_copy_ (dst, src); 1079 } 1080 1081 1082 /* Vector of operations for multiple word bitsets. */ 1083 struct bitset_vtable vbitset_vtable = { 1084 vbitset_set, 1085 vbitset_reset, 1086 bitset_toggle_, 1087 vbitset_test, 1088 vbitset_resize, 1089 bitset_size_, 1090 bitset_count_, 1091 vbitset_empty_p, 1092 vbitset_ones, 1093 vbitset_zero, 1094 vbitset_copy, 1095 vbitset_disjoint_p, 1096 vbitset_equal_p, 1097 vbitset_not, 1098 vbitset_subset_p, 1099 vbitset_and, 1100 vbitset_and_cmp, 1101 vbitset_andn, 1102 vbitset_andn_cmp, 1103 vbitset_or, 1104 vbitset_or_cmp, 1105 vbitset_xor, 1106 vbitset_xor_cmp, 1107 vbitset_and_or, 1108 vbitset_and_or_cmp, 1109 vbitset_andn_or, 1110 vbitset_andn_or_cmp, 1111 vbitset_or_and, 1112 vbitset_or_and_cmp, 1113 vbitset_list, 1114 vbitset_list_reverse, 1115 NULL, 1116 BITSET_VARRAY 1117 }; 1118 1119 1120 size_t 1121 vbitset_bytes (n_bits) 1122 bitset_bindex n_bits ATTRIBUTE_UNUSED; 1123 { 1124 return sizeof (struct vbitset_struct); 1125 } 1126 1127 1128 bitset 1129 vbitset_init (bset, n_bits) 1130 bitset bset; 1131 bitset_bindex n_bits; 1132 { 1133 bset->b.vtable = &vbitset_vtable; 1134 1135 bset->b.cindex = 0; 1136 1137 VBITSET_SIZE (bset) = 0; 1138 vbitset_resize (bset, n_bits); 1139 return bset; 1140 } 1141
