1 /* Array bitsets. 2 Copyright (C) 2002, 2003, 2006 Free Software Foundation, Inc. 3 Contributed by Michael Hayes (m.hayes (at) elec.canterbury.ac.nz). 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 2 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; if not, write to the Free Software Foundation, 17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 18 19 #ifdef HAVE_CONFIG_H 20 # include <config.h> 21 #endif 22 23 #include "abitset.h" 24 #include <stddef.h> 25 #include <stdlib.h> 26 #include <string.h> 27 28 /* This file implements fixed size bitsets stored as an array 29 of words. Any unused bits in the last word must be zero. */ 30 31 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS) 32 #define ABITSET_WORDS(X) ((X)->a.words) 33 34 35 static bitset_bindex 36 abitset_resize (bitset src, bitset_bindex size) 37 { 38 /* These bitsets have a fixed size. */ 39 if (BITSET_SIZE_ (src) != size) 40 abort (); 41 42 return size; 43 } 44 45 /* Find list of up to NUM bits set in BSET starting from and including 46 *NEXT and store in array LIST. Return with actual number of bits 47 found and with *NEXT indicating where search stopped. */ 48 static bitset_bindex 49 abitset_small_list (bitset src, bitset_bindex *list, 50 bitset_bindex num, bitset_bindex *next) 51 { 52 bitset_bindex bitno; 53 bitset_bindex count; 54 bitset_windex size; 55 bitset_word word; 56 57 word = ABITSET_WORDS (src)[0]; 58 59 /* Short circuit common case. */ 60 if (!word) 61 return 0; 62 63 size = BITSET_SIZE_ (src); 64 bitno = *next; 65 if (bitno >= size) 66 return 0; 67 68 word >>= bitno; 69 70 /* If num is 1, we could speed things up with a binary search 71 of the word of interest. */ 72 73 if (num >= BITSET_WORD_BITS) 74 { 75 for (count = 0; word; bitno++) 76 { 77 if (word & 1) 78 list[count++] = bitno; 79 word >>= 1; 80 } 81 } 82 else 83 { 84 for (count = 0; word; bitno++) 85 { 86 if (word & 1) 87 { 88 list[count++] = bitno; 89 if (count >= num) 90 { 91 bitno++; 92 break; 93 } 94 } 95 word >>= 1; 96 } 97 } 98 99 *next = bitno; 100 return count; 101 } 102 103 104 /* Set bit BITNO in bitset DST. */ 105 static void 106 abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED) 107 { 108 /* This should never occur for abitsets since we should always hit 109 the cache. It is likely someone is trying to access outside the 110 bounds of the bitset. */ 111 abort (); 112 } 113 114 115 /* Reset bit BITNO in bitset DST. */ 116 static void 117 abitset_reset (bitset dst ATTRIBUTE_UNUSED, 118 bitset_bindex bitno ATTRIBUTE_UNUSED) 119 { 120 /* This should never occur for abitsets since we should always hit 121 the cache. It is likely someone is trying to access outside the 122 bounds of the bitset. Since the bit is zero anyway, let it pass. */ 123 } 124 125 126 /* Test bit BITNO in bitset SRC. */ 127 static bool 128 abitset_test (bitset src ATTRIBUTE_UNUSED, 129 bitset_bindex bitno ATTRIBUTE_UNUSED) 130 { 131 /* This should never occur for abitsets since we should always 132 hit the cache. */ 133 return false; 134 } 135 136 137 /* Find list of up to NUM bits set in BSET in reverse order, starting 138 from and including NEXT and store in array LIST. Return with 139 actual number of bits found and with *NEXT indicating where search 140 stopped. */ 141 static bitset_bindex 142 abitset_list_reverse (bitset src, bitset_bindex *list, 143 bitset_bindex num, bitset_bindex *next) 144 { 145 bitset_bindex bitno; 146 bitset_bindex rbitno; 147 bitset_bindex count; 148 bitset_windex windex; 149 unsigned int bitcnt; 150 bitset_bindex bitoff; 151 bitset_word *srcp = ABITSET_WORDS (src); 152 bitset_bindex n_bits = BITSET_SIZE_ (src); 153 154 rbitno = *next; 155 156 /* If num is 1, we could speed things up with a binary search 157 of the word of interest. */ 158 159 if (rbitno >= n_bits) 160 return 0; 161 162 count = 0; 163 164 bitno = n_bits - (rbitno + 1); 165 166 windex = bitno / BITSET_WORD_BITS; 167 bitcnt = bitno % BITSET_WORD_BITS; 168 bitoff = windex * BITSET_WORD_BITS; 169 170 do 171 { 172 bitset_word word; 173 174 word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt); 175 for (; word; bitcnt--) 176 { 177 if (word & BITSET_MSB) 178 { 179 list[count++] = bitoff + bitcnt; 180 if (count >= num) 181 { 182 *next = n_bits - (bitoff + bitcnt); 183 return count; 184 } 185 } 186 word <<= 1; 187 } 188 bitoff -= BITSET_WORD_BITS; 189 bitcnt = BITSET_WORD_BITS - 1; 190 } 191 while (windex--); 192 193 *next = n_bits - (bitoff + 1); 194 return count; 195 } 196 197 198 /* Find list of up to NUM bits set in BSET starting from and including 199 *NEXT and store in array LIST. Return with actual number of bits 200 found and with *NEXT indicating where search stopped. */ 201 static bitset_bindex 202 abitset_list (bitset src, bitset_bindex *list, 203 bitset_bindex num, bitset_bindex *next) 204 { 205 bitset_bindex bitno; 206 bitset_bindex count; 207 bitset_windex windex; 208 bitset_bindex bitoff; 209 bitset_windex size = src->b.csize; 210 bitset_word *srcp = ABITSET_WORDS (src); 211 bitset_word word; 212 213 bitno = *next; 214 215 count = 0; 216 if (!bitno) 217 { 218 /* Many bitsets are zero, so make this common case fast. */ 219 for (windex = 0; windex < size && !srcp[windex]; windex++) 220 continue; 221 if (windex >= size) 222 return 0; 223 224 /* If num is 1, we could speed things up with a binary search 225 of the current word. */ 226 227 bitoff = windex * BITSET_WORD_BITS; 228 } 229 else 230 { 231 if (bitno >= BITSET_SIZE_ (src)) 232 return 0; 233 234 windex = bitno / BITSET_WORD_BITS; 235 bitno = bitno % BITSET_WORD_BITS; 236 237 if (bitno) 238 { 239 /* Handle the case where we start within a word. 240 Most often, this is executed with large bitsets 241 with many set bits where we filled the array 242 on the previous call to this function. */ 243 244 bitoff = windex * BITSET_WORD_BITS; 245 word = srcp[windex] >> bitno; 246 for (bitno = bitoff + bitno; word; bitno++) 247 { 248 if (word & 1) 249 { 250 list[count++] = bitno; 251 if (count >= num) 252 { 253 *next = bitno + 1; 254 return count; 255 } 256 } 257 word >>= 1; 258 } 259 windex++; 260 } 261 bitoff = windex * BITSET_WORD_BITS; 262 } 263 264 for (; windex < size; windex++, bitoff += BITSET_WORD_BITS) 265 { 266 if (!(word = srcp[windex])) 267 continue; 268 269 if ((count + BITSET_WORD_BITS) < num) 270 { 271 for (bitno = bitoff; word; bitno++) 272 { 273 if (word & 1) 274 list[count++] = bitno; 275 word >>= 1; 276 } 277 } 278 else 279 { 280 for (bitno = bitoff; word; bitno++) 281 { 282 if (word & 1) 283 { 284 list[count++] = bitno; 285 if (count >= num) 286 { 287 *next = bitno + 1; 288 return count; 289 } 290 } 291 word >>= 1; 292 } 293 } 294 } 295 296 *next = bitoff; 297 return count; 298 } 299 300 301 /* Ensure that any unused bits within the last word are clear. */ 302 static inline void 303 abitset_unused_clear (bitset dst) 304 { 305 unsigned int last_bit; 306 307 last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS; 308 if (last_bit) 309 ABITSET_WORDS (dst)[dst->b.csize - 1] &= 310 ((bitset_word) 1 << last_bit) - 1; 311 } 312 313 314 static void 315 abitset_ones (bitset dst) 316 { 317 bitset_word *dstp = ABITSET_WORDS (dst); 318 size_t bytes; 319 320 bytes = sizeof (bitset_word) * dst->b.csize; 321 322 memset (dstp, -1, bytes); 323 abitset_unused_clear (dst); 324 } 325 326 327 static void 328 abitset_zero (bitset dst) 329 { 330 bitset_word *dstp = ABITSET_WORDS (dst); 331 size_t bytes; 332 333 bytes = sizeof (bitset_word) * dst->b.csize; 334 335 memset (dstp, 0, bytes); 336 } 337 338 339 static bool 340 abitset_empty_p (bitset dst) 341 { 342 bitset_windex i; 343 bitset_word *dstp = ABITSET_WORDS (dst); 344 345 for (i = 0; i < dst->b.csize; i++) 346 if (dstp[i]) 347 return false; 348 349 return true; 350 } 351 352 353 static void 354 abitset_copy1 (bitset dst, bitset src) 355 { 356 bitset_word *srcp = ABITSET_WORDS (src); 357 bitset_word *dstp = ABITSET_WORDS (dst); 358 bitset_windex size = dst->b.csize; 359 360 if (srcp == dstp) 361 return; 362 memcpy (dstp, srcp, sizeof (bitset_word) * size); 363 } 364 365 366 static void 367 abitset_not (bitset dst, bitset src) 368 { 369 bitset_windex i; 370 bitset_word *srcp = ABITSET_WORDS (src); 371 bitset_word *dstp = ABITSET_WORDS (dst); 372 bitset_windex size = dst->b.csize; 373 374 for (i = 0; i < size; i++) 375 *dstp++ = ~(*srcp++); 376 abitset_unused_clear (dst); 377 } 378 379 380 static bool 381 abitset_equal_p (bitset dst, bitset src) 382 { 383 bitset_windex i; 384 bitset_word *srcp = ABITSET_WORDS (src); 385 bitset_word *dstp = ABITSET_WORDS (dst); 386 bitset_windex size = dst->b.csize; 387 388 for (i = 0; i < size; i++) 389 if (*srcp++ != *dstp++) 390 return false; 391 return true; 392 } 393 394 395 static bool 396 abitset_subset_p (bitset dst, bitset src) 397 { 398 bitset_windex i; 399 bitset_word *srcp = ABITSET_WORDS (src); 400 bitset_word *dstp = ABITSET_WORDS (dst); 401 bitset_windex size = dst->b.csize; 402 403 for (i = 0; i < size; i++, dstp++, srcp++) 404 if (*dstp != (*srcp | *dstp)) 405 return false; 406 return true; 407 } 408 409 410 static bool 411 abitset_disjoint_p (bitset dst, bitset src) 412 { 413 bitset_windex i; 414 bitset_word *srcp = ABITSET_WORDS (src); 415 bitset_word *dstp = ABITSET_WORDS (dst); 416 bitset_windex size = dst->b.csize; 417 418 for (i = 0; i < size; i++) 419 if (*srcp++ & *dstp++) 420 return false; 421 422 return true; 423 } 424 425 426 static void 427 abitset_and (bitset dst, bitset src1, bitset src2) 428 { 429 bitset_windex i; 430 bitset_word *src1p = ABITSET_WORDS (src1); 431 bitset_word *src2p = ABITSET_WORDS (src2); 432 bitset_word *dstp = ABITSET_WORDS (dst); 433 bitset_windex size = dst->b.csize; 434 435 for (i = 0; i < size; i++) 436 *dstp++ = *src1p++ & *src2p++; 437 } 438 439 440 static bool 441 abitset_and_cmp (bitset dst, bitset src1, bitset src2) 442 { 443 bitset_windex i; 444 bool changed = false; 445 bitset_word *src1p = ABITSET_WORDS (src1); 446 bitset_word *src2p = ABITSET_WORDS (src2); 447 bitset_word *dstp = ABITSET_WORDS (dst); 448 bitset_windex size = dst->b.csize; 449 450 for (i = 0; i < size; i++, dstp++) 451 { 452 bitset_word tmp = *src1p++ & *src2p++; 453 454 if (*dstp != tmp) 455 { 456 changed = true; 457 *dstp = tmp; 458 } 459 } 460 return changed; 461 } 462 463 464 static void 465 abitset_andn (bitset dst, bitset src1, bitset src2) 466 { 467 bitset_windex i; 468 bitset_word *src1p = ABITSET_WORDS (src1); 469 bitset_word *src2p = ABITSET_WORDS (src2); 470 bitset_word *dstp = ABITSET_WORDS (dst); 471 bitset_windex size = dst->b.csize; 472 473 for (i = 0; i < size; i++) 474 *dstp++ = *src1p++ & ~(*src2p++); 475 } 476 477 478 static bool 479 abitset_andn_cmp (bitset dst, bitset src1, bitset src2) 480 { 481 bitset_windex i; 482 bool changed = false; 483 bitset_word *src1p = ABITSET_WORDS (src1); 484 bitset_word *src2p = ABITSET_WORDS (src2); 485 bitset_word *dstp = ABITSET_WORDS (dst); 486 bitset_windex size = dst->b.csize; 487 488 for (i = 0; i < size; i++, dstp++) 489 { 490 bitset_word tmp = *src1p++ & ~(*src2p++); 491 492 if (*dstp != tmp) 493 { 494 changed = true; 495 *dstp = tmp; 496 } 497 } 498 return changed; 499 } 500 501 502 static void 503 abitset_or (bitset dst, bitset src1, bitset src2) 504 { 505 bitset_windex i; 506 bitset_word *src1p = ABITSET_WORDS (src1); 507 bitset_word *src2p = ABITSET_WORDS (src2); 508 bitset_word *dstp = ABITSET_WORDS (dst); 509 bitset_windex size = dst->b.csize; 510 511 for (i = 0; i < size; i++) 512 *dstp++ = *src1p++ | *src2p++; 513 } 514 515 516 static bool 517 abitset_or_cmp (bitset dst, bitset src1, bitset src2) 518 { 519 bitset_windex i; 520 bool changed = false; 521 bitset_word *src1p = ABITSET_WORDS (src1); 522 bitset_word *src2p = ABITSET_WORDS (src2); 523 bitset_word *dstp = ABITSET_WORDS (dst); 524 bitset_windex size = dst->b.csize; 525 526 for (i = 0; i < size; i++, dstp++) 527 { 528 bitset_word tmp = *src1p++ | *src2p++; 529 530 if (*dstp != tmp) 531 { 532 changed = true; 533 *dstp = tmp; 534 } 535 } 536 return changed; 537 } 538 539 540 static void 541 abitset_xor (bitset dst, bitset src1, bitset src2) 542 { 543 bitset_windex i; 544 bitset_word *src1p = ABITSET_WORDS (src1); 545 bitset_word *src2p = ABITSET_WORDS (src2); 546 bitset_word *dstp = ABITSET_WORDS (dst); 547 bitset_windex size = dst->b.csize; 548 549 for (i = 0; i < size; i++) 550 *dstp++ = *src1p++ ^ *src2p++; 551 } 552 553 554 static bool 555 abitset_xor_cmp (bitset dst, bitset src1, bitset src2) 556 { 557 bitset_windex i; 558 bool changed = false; 559 bitset_word *src1p = ABITSET_WORDS (src1); 560 bitset_word *src2p = ABITSET_WORDS (src2); 561 bitset_word *dstp = ABITSET_WORDS (dst); 562 bitset_windex size = dst->b.csize; 563 564 for (i = 0; i < size; i++, dstp++) 565 { 566 bitset_word tmp = *src1p++ ^ *src2p++; 567 568 if (*dstp != tmp) 569 { 570 changed = true; 571 *dstp = tmp; 572 } 573 } 574 return changed; 575 } 576 577 578 static void 579 abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3) 580 { 581 bitset_windex i; 582 bitset_word *src1p = ABITSET_WORDS (src1); 583 bitset_word *src2p = ABITSET_WORDS (src2); 584 bitset_word *src3p = ABITSET_WORDS (src3); 585 bitset_word *dstp = ABITSET_WORDS (dst); 586 bitset_windex size = dst->b.csize; 587 588 for (i = 0; i < size; i++) 589 *dstp++ = (*src1p++ & *src2p++) | *src3p++; 590 } 591 592 593 static bool 594 abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 595 { 596 bitset_windex i; 597 bool changed = false; 598 bitset_word *src1p = ABITSET_WORDS (src1); 599 bitset_word *src2p = ABITSET_WORDS (src2); 600 bitset_word *src3p = ABITSET_WORDS (src3); 601 bitset_word *dstp = ABITSET_WORDS (dst); 602 bitset_windex size = dst->b.csize; 603 604 for (i = 0; i < size; i++, dstp++) 605 { 606 bitset_word tmp = (*src1p++ & *src2p++) | *src3p++; 607 608 if (*dstp != tmp) 609 { 610 changed = true; 611 *dstp = tmp; 612 } 613 } 614 return changed; 615 } 616 617 618 static void 619 abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) 620 { 621 bitset_windex i; 622 bitset_word *src1p = ABITSET_WORDS (src1); 623 bitset_word *src2p = ABITSET_WORDS (src2); 624 bitset_word *src3p = ABITSET_WORDS (src3); 625 bitset_word *dstp = ABITSET_WORDS (dst); 626 bitset_windex size = dst->b.csize; 627 628 for (i = 0; i < size; i++) 629 *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++; 630 } 631 632 633 static bool 634 abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 635 { 636 bitset_windex i; 637 bool changed = false; 638 bitset_word *src1p = ABITSET_WORDS (src1); 639 bitset_word *src2p = ABITSET_WORDS (src2); 640 bitset_word *src3p = ABITSET_WORDS (src3); 641 bitset_word *dstp = ABITSET_WORDS (dst); 642 bitset_windex size = dst->b.csize; 643 644 for (i = 0; i < size; i++, dstp++) 645 { 646 bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++; 647 648 if (*dstp != tmp) 649 { 650 changed = true; 651 *dstp = tmp; 652 } 653 } 654 return changed; 655 } 656 657 658 static void 659 abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3) 660 { 661 bitset_windex i; 662 bitset_word *src1p = ABITSET_WORDS (src1); 663 bitset_word *src2p = ABITSET_WORDS (src2); 664 bitset_word *src3p = ABITSET_WORDS (src3); 665 bitset_word *dstp = ABITSET_WORDS (dst); 666 bitset_windex size = dst->b.csize; 667 668 for (i = 0; i < size; i++) 669 *dstp++ = (*src1p++ | *src2p++) & *src3p++; 670 } 671 672 673 static bool 674 abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) 675 { 676 bitset_windex i; 677 bool changed = false; 678 bitset_word *src1p = ABITSET_WORDS (src1); 679 bitset_word *src2p = ABITSET_WORDS (src2); 680 bitset_word *src3p = ABITSET_WORDS (src3); 681 bitset_word *dstp = ABITSET_WORDS (dst); 682 bitset_windex size = dst->b.csize; 683 684 for (i = 0; i < size; i++, dstp++) 685 { 686 bitset_word tmp = (*src1p++ | *src2p++) & *src3p++; 687 688 if (*dstp != tmp) 689 { 690 changed = true; 691 *dstp = tmp; 692 } 693 } 694 return changed; 695 } 696 697 698 static void 699 abitset_copy (bitset dst, bitset src) 700 { 701 if (BITSET_COMPATIBLE_ (dst, src)) 702 abitset_copy1 (dst, src); 703 else 704 bitset_copy_ (dst, src); 705 } 706 707 708 /* Vector of operations for single word bitsets. */ 709 struct bitset_vtable abitset_small_vtable = { 710 abitset_set, 711 abitset_reset, 712 bitset_toggle_, 713 abitset_test, 714 abitset_resize, 715 bitset_size_, 716 bitset_count_, 717 abitset_empty_p, 718 abitset_ones, 719 abitset_zero, 720 abitset_copy, 721 abitset_disjoint_p, 722 abitset_equal_p, 723 abitset_not, 724 abitset_subset_p, 725 abitset_and, 726 abitset_and_cmp, 727 abitset_andn, 728 abitset_andn_cmp, 729 abitset_or, 730 abitset_or_cmp, 731 abitset_xor, 732 abitset_xor_cmp, 733 abitset_and_or, 734 abitset_and_or_cmp, 735 abitset_andn_or, 736 abitset_andn_or_cmp, 737 abitset_or_and, 738 abitset_or_and_cmp, 739 abitset_small_list, 740 abitset_list_reverse, 741 NULL, 742 BITSET_ARRAY 743 }; 744 745 746 /* Vector of operations for multiple word bitsets. */ 747 struct bitset_vtable abitset_vtable = { 748 abitset_set, 749 abitset_reset, 750 bitset_toggle_, 751 abitset_test, 752 abitset_resize, 753 bitset_size_, 754 bitset_count_, 755 abitset_empty_p, 756 abitset_ones, 757 abitset_zero, 758 abitset_copy, 759 abitset_disjoint_p, 760 abitset_equal_p, 761 abitset_not, 762 abitset_subset_p, 763 abitset_and, 764 abitset_and_cmp, 765 abitset_andn, 766 abitset_andn_cmp, 767 abitset_or, 768 abitset_or_cmp, 769 abitset_xor, 770 abitset_xor_cmp, 771 abitset_and_or, 772 abitset_and_or_cmp, 773 abitset_andn_or, 774 abitset_andn_or_cmp, 775 abitset_or_and, 776 abitset_or_and_cmp, 777 abitset_list, 778 abitset_list_reverse, 779 NULL, 780 BITSET_ARRAY 781 }; 782 783 784 size_t 785 abitset_bytes (bitset_bindex n_bits) 786 { 787 bitset_windex size; 788 size_t bytes; 789 size_t header_size = offsetof (union bitset_union, a.words); 790 struct bitset_align_struct { char a; union bitset_union b; }; 791 size_t bitset_alignment = offsetof (struct bitset_align_struct, b); 792 793 size = ABITSET_N_WORDS (n_bits); 794 bytes = header_size + size * sizeof (bitset_word); 795 796 /* Align the size properly for a vector of abitset objects. */ 797 if (header_size % bitset_alignment != 0 798 || sizeof (bitset_word) % bitset_alignment != 0) 799 { 800 bytes += bitset_alignment - 1; 801 bytes -= bytes % bitset_alignment; 802 } 803 804 return bytes; 805 } 806 807 808 bitset 809 abitset_init (bitset bset, bitset_bindex n_bits) 810 { 811 bitset_windex size; 812 813 size = ABITSET_N_WORDS (n_bits); 814 BITSET_NBITS_ (bset) = n_bits; 815 816 /* Use optimized routines if bitset fits within a single word. 817 There is probably little merit if using caching since 818 the small bitset will always fit in the cache. */ 819 if (size == 1) 820 bset->b.vtable = &abitset_small_vtable; 821 else 822 bset->b.vtable = &abitset_vtable; 823 824 bset->b.cindex = 0; 825 bset->b.csize = size; 826 bset->b.cdata = ABITSET_WORDS (bset); 827 return bset; 828 } 829
