1/* Array bitsets. 2 3 Copyright (C) 2002-2003, 2006, 2009-2012 Free Software Foundation, 4 Inc. 5 6 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). 7 8 This program is free software: you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation, either version 3 of the License, or 11 (at your option) any later version. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 20 21#include <config.h> 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 35static bitset_bindex 36abitset_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. */ 48static bitset_bindex 49abitset_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. */ 105static void 106abitset_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. */ 116static void 117abitset_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. */ 127static bool 128abitset_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. */ 141static bitset_bindex 142abitset_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. */ 201static bitset_bindex 202abitset_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. */ 302static inline void 303abitset_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 314static void 315abitset_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 327static void 328abitset_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 339static bool 340abitset_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 353static void 354abitset_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 366static void 367abitset_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 380static bool 381abitset_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 395static bool 396abitset_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 410static bool 411abitset_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 426static void 427abitset_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 440static bool 441abitset_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 464static void 465abitset_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 478static bool 479abitset_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 502static void 503abitset_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 516static bool 517abitset_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 540static void 541abitset_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 554static bool 555abitset_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 578static void 579abitset_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 593static bool 594abitset_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 618static void 619abitset_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 633static bool 634abitset_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 658static void 659abitset_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 673static bool 674abitset_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 698static void 699abitset_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. */ 709struct 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. */ 747struct 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 784size_t 785abitset_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 808bitset 809abitset_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