1 /* Functions to support link list bitsets. 2 3 Copyright (C) 2002-2004, 2006, 2009-2012 Free Software Foundation, 4 Inc. 5 6 Contributed by Michael Hayes (m.hayes (at) 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 "lbitset.h" 24 25 #include "obstack.h" 26 #include <stddef.h> 27 #include <stdlib.h> 28 #include <stdio.h> 29 #include <string.h> 30 31 /* This file implements linked-list bitsets. These bitsets can be of 32 arbitrary length and are more efficient than arrays of bits for 33 large sparse sets. 34 35 Usually if all the bits in an element are zero we remove the element 36 from the list. However, a side effect of the bit caching is that we 37 do not always notice when an element becomes zero. Hence the 38 lbitset_weed function which removes zero elements. */ 39 40 41 /* Number of words to use for each element. The larger the value the 42 greater the size of the cache and the shorter the time to find a given bit 43 but the more memory wasted for sparse bitsets and the longer the time 44 to search for set bits. 45 46 The routines that dominate timing profiles are lbitset_elt_find 47 and lbitset_elt_link, especially when accessing the bits randomly. */ 48 49 #define LBITSET_ELT_WORDS 2 50 51 typedef bitset_word lbitset_word; 52 53 #define LBITSET_WORD_BITS BITSET_WORD_BITS 54 55 /* Number of bits stored in each element. */ 56 #define LBITSET_ELT_BITS \ 57 ((unsigned int) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS)) 58 59 /* Lbitset element. We use an array of bits for each element. 60 These are linked together in a doubly-linked list. */ 61 typedef struct lbitset_elt_struct 62 { 63 struct lbitset_elt_struct *next; /* Next element. */ 64 struct lbitset_elt_struct *prev; /* Previous element. */ 65 bitset_windex index; /* bitno / BITSET_WORD_BITS. */ 66 bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */ 67 } 68 lbitset_elt; 69 70 71 enum lbitset_find_mode 72 { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST }; 73 74 static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */ 75 76 /* Obstack to allocate bitset elements from. */ 77 static struct obstack lbitset_obstack; 78 static bool lbitset_obstack_init = false; 79 static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */ 80 81 extern void debug_lbitset (bitset); 82 83 #define LBITSET_CURRENT1(X) \ 84 ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words))) 85 86 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata) 87 88 #define LBITSET_HEAD(X) ((X)->l.head) 89 #define LBITSET_TAIL(X) ((X)->l.tail) 90 91 /* Allocate a lbitset element. The bits are not cleared. */ 92 static inline lbitset_elt * 93 lbitset_elt_alloc (void) 94 { 95 lbitset_elt *elt; 96 97 if (lbitset_free_list != 0) 98 { 99 elt = lbitset_free_list; 100 lbitset_free_list = elt->next; 101 } 102 else 103 { 104 if (!lbitset_obstack_init) 105 { 106 lbitset_obstack_init = true; 107 108 /* Let particular systems override the size of a chunk. */ 109 110 #ifndef OBSTACK_CHUNK_SIZE 111 #define OBSTACK_CHUNK_SIZE 0 112 #endif 113 114 /* Let them override the alloc and free routines too. */ 115 116 #ifndef OBSTACK_CHUNK_ALLOC 117 #define OBSTACK_CHUNK_ALLOC xmalloc 118 #endif 119 120 #ifndef OBSTACK_CHUNK_FREE 121 #define OBSTACK_CHUNK_FREE free 122 #endif 123 124 #if ! defined __GNUC__ || __GNUC__ < 2 125 #define __alignof__(type) 0 126 #endif 127 128 obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE, 129 __alignof__ (lbitset_elt), 130 OBSTACK_CHUNK_ALLOC, 131 OBSTACK_CHUNK_FREE); 132 } 133 134 /* Perhaps we should add a number of new elements to the free 135 list. */ 136 elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack, 137 sizeof (lbitset_elt)); 138 } 139 140 return elt; 141 } 142 143 144 /* Allocate a lbitset element. The bits are cleared. */ 145 static inline lbitset_elt * 146 lbitset_elt_calloc (void) 147 { 148 lbitset_elt *elt; 149 150 elt = lbitset_elt_alloc (); 151 memset (elt->words, 0, sizeof (elt->words)); 152 return elt; 153 } 154 155 156 static inline void 157 lbitset_elt_free (lbitset_elt *elt) 158 { 159 elt->next = lbitset_free_list; 160 lbitset_free_list = elt; 161 } 162 163 164 /* Unlink element ELT from bitset BSET. */ 165 static inline void 166 lbitset_elt_unlink (bitset bset, lbitset_elt *elt) 167 { 168 lbitset_elt *next = elt->next; 169 lbitset_elt *prev = elt->prev; 170 171 if (prev) 172 prev->next = next; 173 174 if (next) 175 next->prev = prev; 176 177 if (LBITSET_HEAD (bset) == elt) 178 LBITSET_HEAD (bset) = next; 179 if (LBITSET_TAIL (bset) == elt) 180 LBITSET_TAIL (bset) = prev; 181 182 /* Update cache pointer. Since the first thing we try is to insert 183 before current, make current the next entry in preference to the 184 previous. */ 185 if (LBITSET_CURRENT (bset) == elt) 186 { 187 if (next) 188 { 189 bset->b.cdata = next->words; 190 bset->b.cindex = next->index; 191 } 192 else if (prev) 193 { 194 bset->b.cdata = prev->words; 195 bset->b.cindex = prev->index; 196 } 197 else 198 { 199 bset->b.csize = 0; 200 bset->b.cdata = 0; 201 } 202 } 203 204 lbitset_elt_free (elt); 205 } 206 207 208 /* Cut the chain of bitset BSET before element ELT and free the 209 elements. */ 210 static inline void 211 lbitset_prune (bitset bset, lbitset_elt *elt) 212 { 213 lbitset_elt *next; 214 215 if (!elt) 216 return; 217 218 if (elt->prev) 219 { 220 LBITSET_TAIL (bset) = elt->prev; 221 bset->b.cdata = elt->prev->words; 222 bset->b.cindex = elt->prev->index; 223 elt->prev->next = 0; 224 } 225 else 226 { 227 LBITSET_HEAD (bset) = 0; 228 LBITSET_TAIL (bset) = 0; 229 bset->b.cdata = 0; 230 bset->b.csize = 0; 231 } 232 233 for (; elt; elt = next) 234 { 235 next = elt->next; 236 lbitset_elt_free (elt); 237 } 238 } 239 240 241 /* Are all bits in an element zero? */ 242 static inline bool 243 lbitset_elt_zero_p (lbitset_elt *elt) 244 { 245 int i; 246 247 for (i = 0; i < LBITSET_ELT_WORDS; i++) 248 if (elt->words[i]) 249 return false; 250 251 return true; 252 } 253 254 255 /* Link the bitset element into the current bitset linked list. */ 256 static inline void 257 lbitset_elt_link (bitset bset, lbitset_elt *elt) 258 { 259 bitset_windex windex = elt->index; 260 lbitset_elt *ptr; 261 lbitset_elt *current; 262 263 if (bset->b.csize) 264 current = LBITSET_CURRENT (bset); 265 else 266 current = LBITSET_HEAD (bset); 267 268 /* If this is the first and only element, add it in. */ 269 if (LBITSET_HEAD (bset) == 0) 270 { 271 elt->next = elt->prev = 0; 272 LBITSET_HEAD (bset) = elt; 273 LBITSET_TAIL (bset) = elt; 274 } 275 276 /* If this index is less than that of the current element, it goes 277 somewhere before the current element. */ 278 else if (windex < bset->b.cindex) 279 { 280 for (ptr = current; 281 ptr->prev && ptr->prev->index > windex; ptr = ptr->prev) 282 continue; 283 284 if (ptr->prev) 285 ptr->prev->next = elt; 286 else 287 LBITSET_HEAD (bset) = elt; 288 289 elt->prev = ptr->prev; 290 elt->next = ptr; 291 ptr->prev = elt; 292 } 293 294 /* Otherwise, it must go somewhere after the current element. */ 295 else 296 { 297 for (ptr = current; 298 ptr->next && ptr->next->index < windex; ptr = ptr->next) 299 continue; 300 301 if (ptr->next) 302 ptr->next->prev = elt; 303 else 304 LBITSET_TAIL (bset) = elt; 305 306 elt->next = ptr->next; 307 elt->prev = ptr; 308 ptr->next = elt; 309 } 310 311 /* Set up so this is the first element searched. */ 312 bset->b.cindex = windex; 313 bset->b.csize = LBITSET_ELT_WORDS; 314 bset->b.cdata = elt->words; 315 } 316 317 318 static lbitset_elt * 319 lbitset_elt_find (bitset bset, bitset_windex windex, 320 enum lbitset_find_mode mode) 321 { 322 lbitset_elt *elt; 323 lbitset_elt *current; 324 325 if (bset->b.csize) 326 { 327 current = LBITSET_CURRENT (bset); 328 /* Check if element is the cached element. */ 329 if ((windex - bset->b.cindex) < bset->b.csize) 330 return current; 331 } 332 else 333 { 334 current = LBITSET_HEAD (bset); 335 } 336 337 if (current) 338 { 339 if (windex < bset->b.cindex) 340 { 341 for (elt = current; 342 elt->prev && elt->index > windex; elt = elt->prev) 343 continue; 344 } 345 else 346 { 347 for (elt = current; 348 elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex; 349 elt = elt->next) 350 continue; 351 } 352 353 /* ELT is the nearest to the one we want. If it's not the one 354 we want, the one we want does not exist. */ 355 if (windex - elt->index < LBITSET_ELT_WORDS) 356 { 357 bset->b.cindex = elt->index; 358 bset->b.csize = LBITSET_ELT_WORDS; 359 bset->b.cdata = elt->words; 360 return elt; 361 } 362 } 363 364 switch (mode) 365 { 366 default: 367 abort (); 368 369 case LBITSET_FIND: 370 return 0; 371 372 case LBITSET_CREATE: 373 windex -= windex % LBITSET_ELT_WORDS; 374 375 elt = lbitset_elt_calloc (); 376 elt->index = windex; 377 lbitset_elt_link (bset, elt); 378 return elt; 379 380 case LBITSET_SUBST: 381 return &lbitset_zero_elts[0]; 382 } 383 } 384 385 386 /* Weed out the zero elements from the list. */ 387 static inline void 388 lbitset_weed (bitset bset) 389 { 390 lbitset_elt *elt; 391 lbitset_elt *next; 392 393 for (elt = LBITSET_HEAD (bset); elt; elt = next) 394 { 395 next = elt->next; 396 if (lbitset_elt_zero_p (elt)) 397 lbitset_elt_unlink (bset, elt); 398 } 399 } 400 401 402 /* Set all bits in the bitset to zero. */ 403 static void 404 lbitset_zero (bitset bset) 405 { 406 lbitset_elt *head; 407 408 head = LBITSET_HEAD (bset); 409 if (!head) 410 return; 411 412 /* Clear a bitset by freeing the linked list at the head element. */ 413 lbitset_prune (bset, head); 414 } 415 416 417 /* Is DST == SRC? */ 418 static inline bool 419 lbitset_equal_p (bitset dst, bitset src) 420 { 421 lbitset_elt *selt; 422 lbitset_elt *delt; 423 int j; 424 425 if (src == dst) 426 return true; 427 428 lbitset_weed (src); 429 lbitset_weed (dst); 430 for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); 431 selt && delt; selt = selt->next, delt = delt->next) 432 { 433 if (selt->index != delt->index) 434 return false; 435 436 for (j = 0; j < LBITSET_ELT_WORDS; j++) 437 if (delt->words[j] != selt->words[j]) 438 return false; 439 } 440 return !selt && !delt; 441 } 442 443 444 /* Copy bits from bitset SRC to bitset DST. */ 445 static inline void 446 lbitset_copy (bitset dst, bitset src) 447 { 448 lbitset_elt *elt; 449 lbitset_elt *head; 450 lbitset_elt *prev; 451 lbitset_elt *tmp; 452 453 if (src == dst) 454 return; 455 456 lbitset_zero (dst); 457 458 head = LBITSET_HEAD (src); 459 if (!head) 460 return; 461 462 prev = 0; 463 for (elt = head; elt; elt = elt->next) 464 { 465 tmp = lbitset_elt_alloc (); 466 tmp->index = elt->index; 467 tmp->prev = prev; 468 tmp->next = 0; 469 if (prev) 470 prev->next = tmp; 471 else 472 LBITSET_HEAD (dst) = tmp; 473 prev = tmp; 474 475 memcpy (tmp->words, elt->words, sizeof (elt->words)); 476 } 477 LBITSET_TAIL (dst) = tmp; 478 479 dst->b.csize = LBITSET_ELT_WORDS; 480 dst->b.cdata = LBITSET_HEAD (dst)->words; 481 dst->b.cindex = LBITSET_HEAD (dst)->index; 482 } 483 484 485 /* Copy bits from bitset SRC to bitset DST. Return true if 486 bitsets different. */ 487 static inline bool 488 lbitset_copy_cmp (bitset dst, bitset src) 489 { 490 if (src == dst) 491 return false; 492 493 if (!LBITSET_HEAD (dst)) 494 { 495 lbitset_copy (dst, src); 496 return LBITSET_HEAD (src) != 0; 497 } 498 499 if (lbitset_equal_p (dst, src)) 500 return false; 501 502 lbitset_copy (dst, src); 503 return true; 504 } 505 506 507 static bitset_bindex 508 lbitset_resize (bitset src, bitset_bindex size) 509 { 510 BITSET_NBITS_ (src) = size; 511 512 /* Need to prune any excess bits. FIXME. */ 513 return size; 514 } 515 516 /* Set bit BITNO in bitset DST. */ 517 static void 518 lbitset_set (bitset dst, bitset_bindex bitno) 519 { 520 bitset_windex windex = bitno / BITSET_WORD_BITS; 521 522 lbitset_elt_find (dst, windex, LBITSET_CREATE); 523 524 dst->b.cdata[windex - dst->b.cindex] |= 525 (bitset_word) 1 << (bitno % BITSET_WORD_BITS); 526 } 527 528 529 /* Reset bit BITNO in bitset DST. */ 530 static void 531 lbitset_reset (bitset dst, bitset_bindex bitno) 532 { 533 bitset_windex windex = bitno / BITSET_WORD_BITS; 534 535 if (!lbitset_elt_find (dst, windex, LBITSET_FIND)) 536 return; 537 538 dst->b.cdata[windex - dst->b.cindex] &= 539 ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); 540 541 /* If all the data is zero, perhaps we should unlink it now... */ 542 } 543 544 545 /* Test bit BITNO in bitset SRC. */ 546 static bool 547 lbitset_test (bitset src, bitset_bindex bitno) 548 { 549 bitset_windex windex = bitno / BITSET_WORD_BITS; 550 551 return (lbitset_elt_find (src, windex, LBITSET_FIND) 552 && ((src->b.cdata[windex - src->b.cindex] 553 >> (bitno % BITSET_WORD_BITS)) 554 & 1)); 555 } 556 557 558 static void 559 lbitset_free (bitset bset) 560 { 561 lbitset_zero (bset); 562 } 563 564 565 /* Find list of up to NUM bits set in BSET starting from and including 566 *NEXT and store in array LIST. Return with actual number of bits 567 found and with *NEXT indicating where search stopped. */ 568 static bitset_bindex 569 lbitset_list_reverse (bitset bset, bitset_bindex *list, 570 bitset_bindex num, bitset_bindex *next) 571 { 572 bitset_bindex rbitno; 573 bitset_bindex bitno; 574 unsigned int bcount; 575 bitset_bindex boffset; 576 bitset_windex windex; 577 bitset_bindex count; 578 lbitset_elt *elt; 579 bitset_word word; 580 bitset_bindex n_bits; 581 582 elt = LBITSET_TAIL (bset); 583 if (!elt) 584 return 0; 585 586 n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS; 587 rbitno = *next; 588 589 if (rbitno >= n_bits) 590 return 0; 591 592 bitno = n_bits - (rbitno + 1); 593 594 windex = bitno / BITSET_WORD_BITS; 595 596 /* Skip back to starting element. */ 597 for (; elt && elt->index > windex; elt = elt->prev) 598 continue; 599 600 if (!elt) 601 return 0; 602 603 if (windex >= elt->index + LBITSET_ELT_WORDS) 604 { 605 /* We are trying to start in no-mans land so start 606 at end of current elt. */ 607 bcount = BITSET_WORD_BITS - 1; 608 windex = elt->index + LBITSET_ELT_WORDS - 1; 609 } 610 else 611 { 612 bcount = bitno % BITSET_WORD_BITS; 613 } 614 615 count = 0; 616 boffset = windex * BITSET_WORD_BITS; 617 618 /* If num is 1, we could speed things up with a binary search 619 of the word of interest. */ 620 621 while (elt) 622 { 623 bitset_word *srcp = elt->words; 624 625 for (; (windex - elt->index) < LBITSET_ELT_WORDS; 626 windex--, boffset -= BITSET_WORD_BITS, 627 bcount = BITSET_WORD_BITS - 1) 628 { 629 word = 630 srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount); 631 632 for (; word; bcount--) 633 { 634 if (word & BITSET_MSB) 635 { 636 list[count++] = boffset + bcount; 637 if (count >= num) 638 { 639 *next = n_bits - (boffset + bcount); 640 return count; 641 } 642 } 643 word <<= 1; 644 } 645 } 646 647 elt = elt->prev; 648 if (elt) 649 { 650 windex = elt->index + LBITSET_ELT_WORDS - 1; 651 boffset = windex * BITSET_WORD_BITS; 652 } 653 } 654 655 *next = n_bits - (boffset + 1); 656 return count; 657 } 658 659 660 /* Find list of up to NUM bits set in BSET starting from and including 661 *NEXT and store in array LIST. Return with actual number of bits 662 found and with *NEXT indicating where search stopped. */ 663 static bitset_bindex 664 lbitset_list (bitset bset, bitset_bindex *list, 665 bitset_bindex num, bitset_bindex *next) 666 { 667 bitset_bindex bitno; 668 bitset_windex windex; 669 bitset_bindex count; 670 lbitset_elt *elt; 671 lbitset_elt *head; 672 bitset_word word; 673 674 head = LBITSET_HEAD (bset); 675 if (!head) 676 return 0; 677 678 bitno = *next; 679 count = 0; 680 681 if (!bitno) 682 { 683 /* This is the most common case. */ 684 685 /* Start with the first element. */ 686 elt = head; 687 windex = elt->index; 688 bitno = windex * BITSET_WORD_BITS; 689 } 690 else 691 { 692 windex = bitno / BITSET_WORD_BITS; 693 694 /* Skip to starting element. */ 695 for (elt = head; 696 elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex; 697 elt = elt->next) 698 continue; 699 700 if (!elt) 701 return 0; 702 703 if (windex < elt->index) 704 { 705 windex = elt->index; 706 bitno = windex * BITSET_WORD_BITS; 707 } 708 else 709 { 710 bitset_word *srcp = elt->words; 711 712 /* We are starting within an element. */ 713 714 for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) 715 { 716 word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS); 717 718 for (; word; bitno++) 719 { 720 if (word & 1) 721 { 722 list[count++] = bitno; 723 if (count >= num) 724 { 725 *next = bitno + 1; 726 return count; 727 } 728 } 729 word >>= 1; 730 } 731 bitno = (windex + 1) * BITSET_WORD_BITS; 732 } 733 734 elt = elt->next; 735 if (elt) 736 { 737 windex = elt->index; 738 bitno = windex * BITSET_WORD_BITS; 739 } 740 } 741 } 742 743 744 /* If num is 1, we could speed things up with a binary search 745 of the word of interest. */ 746 747 while (elt) 748 { 749 int i; 750 bitset_word *srcp = elt->words; 751 752 if ((count + LBITSET_ELT_BITS) < num) 753 { 754 /* The coast is clear, plant boot! */ 755 756 #if LBITSET_ELT_WORDS == 2 757 word = srcp[0]; 758 if (word) 759 { 760 if (!(word & 0xffff)) 761 { 762 word >>= 16; 763 bitno += 16; 764 } 765 if (!(word & 0xff)) 766 { 767 word >>= 8; 768 bitno += 8; 769 } 770 for (; word; bitno++) 771 { 772 if (word & 1) 773 list[count++] = bitno; 774 word >>= 1; 775 } 776 } 777 windex++; 778 bitno = windex * BITSET_WORD_BITS; 779 780 word = srcp[1]; 781 if (word) 782 { 783 if (!(word & 0xffff)) 784 { 785 word >>= 16; 786 bitno += 16; 787 } 788 for (; word; bitno++) 789 { 790 if (word & 1) 791 list[count++] = bitno; 792 word >>= 1; 793 } 794 } 795 windex++; 796 bitno = windex * BITSET_WORD_BITS; 797 #else 798 for (i = 0; i < LBITSET_ELT_WORDS; i++) 799 { 800 word = srcp[i]; 801 if (word) 802 { 803 if (!(word & 0xffff)) 804 { 805 word >>= 16; 806 bitno += 16; 807 } 808 if (!(word & 0xff)) 809 { 810 word >>= 8; 811 bitno += 8; 812 } 813 for (; word; bitno++) 814 { 815 if (word & 1) 816 list[count++] = bitno; 817 word >>= 1; 818 } 819 } 820 windex++; 821 bitno = windex * BITSET_WORD_BITS; 822 } 823 #endif 824 } 825 else 826 { 827 /* Tread more carefully since we need to check 828 if array overflows. */ 829 830 for (i = 0; i < LBITSET_ELT_WORDS; i++) 831 { 832 for (word = srcp[i]; word; bitno++) 833 { 834 if (word & 1) 835 { 836 list[count++] = bitno; 837 if (count >= num) 838 { 839 *next = bitno + 1; 840 return count; 841 } 842 } 843 word >>= 1; 844 } 845 windex++; 846 bitno = windex * BITSET_WORD_BITS; 847 } 848 } 849 850 elt = elt->next; 851 if (elt) 852 { 853 windex = elt->index; 854 bitno = windex * BITSET_WORD_BITS; 855 } 856 } 857 858 *next = bitno; 859 return count; 860 } 861 862 863 static bool 864 lbitset_empty_p (bitset dst) 865 { 866 lbitset_elt *elt; 867 lbitset_elt *next; 868 869 for (elt = LBITSET_HEAD (dst); elt; elt = next) 870 { 871 next = elt->next; 872 if (!lbitset_elt_zero_p (elt)) 873 return 0; 874 /* Weed as we go. */ 875 lbitset_elt_unlink (dst, elt); 876 } 877 878 return 1; 879 } 880 881 882 /* Ensure that any unused bits within the last element are clear. */ 883 static inline void 884 lbitset_unused_clear (bitset dst) 885 { 886 unsigned int last_bit; 887 bitset_bindex n_bits; 888 889 n_bits = BITSET_SIZE_ (dst); 890 last_bit = n_bits % LBITSET_ELT_BITS; 891 892 if (last_bit) 893 { 894 lbitset_elt *elt; 895 bitset_windex windex; 896 bitset_word *srcp; 897 898 elt = LBITSET_TAIL (dst); 899 srcp = elt->words; 900 windex = n_bits / BITSET_WORD_BITS; 901 902 srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1; 903 windex++; 904 905 for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++) 906 srcp[windex - elt->index] = 0; 907 } 908 } 909 910 911 static void 912 lbitset_ones (bitset dst) 913 { 914 bitset_windex i; 915 bitset_windex windex; 916 lbitset_elt *elt; 917 918 /* This is a decidedly unfriendly operation for a linked list 919 bitset! It makes a sparse bitset become dense. An alternative 920 is to have a flag that indicates that the bitset stores the 921 complement of what it indicates. */ 922 923 windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; 924 925 for (i = 0; i < windex; i += LBITSET_ELT_WORDS) 926 { 927 /* Create new elements if they cannot be found. */ 928 elt = lbitset_elt_find (dst, i, LBITSET_CREATE); 929 memset (elt->words, -1, sizeof (elt->words)); 930 } 931 932 lbitset_unused_clear (dst); 933 } 934 935 936 static void 937 lbitset_not (bitset dst, bitset src) 938 { 939 lbitset_elt *selt; 940 lbitset_elt *delt; 941 bitset_windex i; 942 unsigned int j; 943 bitset_windex windex; 944 945 windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS; 946 947 for (i = 0; i < windex; i += LBITSET_ELT_WORDS) 948 { 949 /* Create new elements for dst if they cannot be found 950 or substitute zero elements if src elements not found. */ 951 selt = lbitset_elt_find (src, i, LBITSET_SUBST); 952 delt = lbitset_elt_find (dst, i, LBITSET_CREATE); 953 954 for (j = 0; j < LBITSET_ELT_WORDS; j++) 955 delt->words[j] = ~selt->words[j]; 956 } 957 lbitset_unused_clear (dst); 958 lbitset_weed (dst); 959 return; 960 } 961 962 963 /* Is DST == DST | SRC? */ 964 static bool 965 lbitset_subset_p (bitset dst, bitset src) 966 { 967 lbitset_elt *selt; 968 lbitset_elt *delt; 969 unsigned int j; 970 971 for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); 972 selt || delt; selt = selt->next, delt = delt->next) 973 { 974 if (!selt) 975 selt = &lbitset_zero_elts[0]; 976 else if (!delt) 977 delt = &lbitset_zero_elts[0]; 978 else if (selt->index != delt->index) 979 { 980 if (selt->index < delt->index) 981 { 982 lbitset_zero_elts[2].next = delt; 983 delt = &lbitset_zero_elts[2]; 984 } 985 else 986 { 987 lbitset_zero_elts[1].next = selt; 988 selt = &lbitset_zero_elts[1]; 989 } 990 } 991 992 for (j = 0; j < LBITSET_ELT_WORDS; j++) 993 if (delt->words[j] != (selt->words[j] | delt->words[j])) 994 return false; 995 } 996 return true; 997 } 998 999 1000 /* Is DST & SRC == 0? */ 1001 static bool 1002 lbitset_disjoint_p (bitset dst, bitset src) 1003 { 1004 lbitset_elt *selt; 1005 lbitset_elt *delt; 1006 unsigned int j; 1007 1008 for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst); 1009 selt && delt; selt = selt->next, delt = delt->next) 1010 { 1011 if (selt->index != delt->index) 1012 { 1013 if (selt->index < delt->index) 1014 { 1015 lbitset_zero_elts[2].next = delt; 1016 delt = &lbitset_zero_elts[2]; 1017 } 1018 else 1019 { 1020 lbitset_zero_elts[1].next = selt; 1021 selt = &lbitset_zero_elts[1]; 1022 } 1023 /* Since the elements are different, there is no 1024 intersection of these elements. */ 1025 continue; 1026 } 1027 1028 for (j = 0; j < LBITSET_ELT_WORDS; j++) 1029 if (selt->words[j] & delt->words[j]) 1030 return false; 1031 } 1032 return true; 1033 } 1034 1035 1036 static bool 1037 lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op) 1038 { 1039 lbitset_elt *selt1 = LBITSET_HEAD (src1); 1040 lbitset_elt *selt2 = LBITSET_HEAD (src2); 1041 lbitset_elt *delt = LBITSET_HEAD (dst); 1042 bitset_windex windex1; 1043 bitset_windex windex2; 1044 bitset_windex windex; 1045 lbitset_elt *stmp1; 1046 lbitset_elt *stmp2; 1047 lbitset_elt *dtmp; 1048 bitset_word *srcp1; 1049 bitset_word *srcp2; 1050 bitset_word *dstp; 1051 bool changed = false; 1052 unsigned int i; 1053 1054 LBITSET_HEAD (dst) = 0; 1055 dst->b.csize = 0; 1056 1057 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; 1058 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; 1059 1060 while (selt1 || selt2) 1061 { 1062 /* Figure out whether we need to substitute zero elements for 1063 missing links. */ 1064 if (windex1 == windex2) 1065 { 1066 windex = windex1; 1067 stmp1 = selt1; 1068 stmp2 = selt2; 1069 selt1 = selt1->next; 1070 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; 1071 selt2 = selt2->next; 1072 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; 1073 } 1074 else if (windex1 < windex2) 1075 { 1076 windex = windex1; 1077 stmp1 = selt1; 1078 stmp2 = &lbitset_zero_elts[0]; 1079 selt1 = selt1->next; 1080 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX; 1081 } 1082 else 1083 { 1084 windex = windex2; 1085 stmp1 = &lbitset_zero_elts[0]; 1086 stmp2 = selt2; 1087 selt2 = selt2->next; 1088 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX; 1089 } 1090 1091 /* Find the appropriate element from DST. Begin by discarding 1092 elements that we've skipped. */ 1093 while (delt && delt->index < windex) 1094 { 1095 changed = true; 1096 dtmp = delt; 1097 delt = delt->next; 1098 lbitset_elt_free (dtmp); 1099 } 1100 if (delt && delt->index == windex) 1101 { 1102 dtmp = delt; 1103 delt = delt->next; 1104 } 1105 else 1106 dtmp = lbitset_elt_calloc (); 1107 1108 /* Do the operation, and if any bits are set, link it into the 1109 linked list. */ 1110 srcp1 = stmp1->words; 1111 srcp2 = stmp2->words; 1112 dstp = dtmp->words; 1113 switch (op) 1114 { 1115 default: 1116 abort (); 1117 1118 case BITSET_OP_OR: 1119 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1120 { 1121 bitset_word tmp = *srcp1++ | *srcp2++; 1122 1123 if (*dstp != tmp) 1124 { 1125 changed = true; 1126 *dstp = tmp; 1127 } 1128 } 1129 break; 1130 1131 case BITSET_OP_AND: 1132 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1133 { 1134 bitset_word tmp = *srcp1++ & *srcp2++; 1135 1136 if (*dstp != tmp) 1137 { 1138 changed = true; 1139 *dstp = tmp; 1140 } 1141 } 1142 break; 1143 1144 case BITSET_OP_XOR: 1145 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1146 { 1147 bitset_word tmp = *srcp1++ ^ *srcp2++; 1148 1149 if (*dstp != tmp) 1150 { 1151 changed = true; 1152 *dstp = tmp; 1153 } 1154 } 1155 break; 1156 1157 case BITSET_OP_ANDN: 1158 for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++) 1159 { 1160 bitset_word tmp = *srcp1++ & ~(*srcp2++); 1161 1162 if (*dstp != tmp) 1163 { 1164 changed = true; 1165 *dstp = tmp; 1166 } 1167 } 1168 break; 1169 } 1170 1171 if (!lbitset_elt_zero_p (dtmp)) 1172 { 1173 dtmp->index = windex; 1174 /* Perhaps this could be optimised... */ 1175 lbitset_elt_link (dst, dtmp); 1176 } 1177 else 1178 { 1179 lbitset_elt_free (dtmp); 1180 } 1181 } 1182 1183 /* If we have elements of DST left over, free them all. */ 1184 if (delt) 1185 { 1186 changed = true; 1187 lbitset_prune (dst, delt); 1188 } 1189 1190 return changed; 1191 } 1192 1193 1194 static bool 1195 lbitset_and_cmp (bitset dst, bitset src1, bitset src2) 1196 { 1197 lbitset_elt *selt1 = LBITSET_HEAD (src1); 1198 lbitset_elt *selt2 = LBITSET_HEAD (src2); 1199 bool changed; 1200 1201 if (!selt2) 1202 { 1203 lbitset_weed (dst); 1204 changed = !LBITSET_HEAD (dst); 1205 lbitset_zero (dst); 1206 return changed; 1207 } 1208 else if (!selt1) 1209 { 1210 lbitset_weed (dst); 1211 changed = !LBITSET_HEAD (dst); 1212 lbitset_zero (dst); 1213 return changed; 1214 } 1215 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND); 1216 } 1217 1218 1219 static void 1220 lbitset_and (bitset dst, bitset src1, bitset src2) 1221 { 1222 lbitset_and_cmp (dst, src1, src2); 1223 } 1224 1225 1226 static bool 1227 lbitset_andn_cmp (bitset dst, bitset src1, bitset src2) 1228 { 1229 lbitset_elt *selt1 = LBITSET_HEAD (src1); 1230 lbitset_elt *selt2 = LBITSET_HEAD (src2); 1231 bool changed; 1232 1233 if (!selt2) 1234 { 1235 return lbitset_copy_cmp (dst, src1); 1236 } 1237 else if (!selt1) 1238 { 1239 lbitset_weed (dst); 1240 changed = !LBITSET_HEAD (dst); 1241 lbitset_zero (dst); 1242 return changed; 1243 } 1244 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN); 1245 } 1246 1247 1248 static void 1249 lbitset_andn (bitset dst, bitset src1, bitset src2) 1250 { 1251 lbitset_andn_cmp (dst, src1, src2); 1252 } 1253 1254 1255 static bool 1256 lbitset_or_cmp (bitset dst, bitset src1, bitset src2) 1257 { 1258 lbitset_elt *selt1 = LBITSET_HEAD (src1); 1259 lbitset_elt *selt2 = LBITSET_HEAD (src2); 1260 1261 if (!selt2) 1262 { 1263 return lbitset_copy_cmp (dst, src1); 1264 } 1265 else if (!selt1) 1266 { 1267 return lbitset_copy_cmp (dst, src2); 1268 } 1269 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR); 1270 } 1271 1272 1273 static void 1274 lbitset_or (bitset dst, bitset src1, bitset src2) 1275 { 1276 lbitset_or_cmp (dst, src1, src2); 1277 } 1278 1279 1280 static bool 1281 lbitset_xor_cmp (bitset dst, bitset src1, bitset src2) 1282 { 1283 lbitset_elt *selt1 = LBITSET_HEAD (src1); 1284 lbitset_elt *selt2 = LBITSET_HEAD (src2); 1285 1286 if (!selt2) 1287 { 1288 return lbitset_copy_cmp (dst, src1); 1289 } 1290 else if (!selt1) 1291 { 1292 return lbitset_copy_cmp (dst, src2); 1293 } 1294 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR); 1295 } 1296 1297 1298 static void 1299 lbitset_xor (bitset dst, bitset src1, bitset src2) 1300 { 1301 lbitset_xor_cmp (dst, src1, src2); 1302 } 1303 1304 1305 1306 /* Vector of operations for linked-list bitsets. */ 1307 struct bitset_vtable lbitset_vtable = { 1308 lbitset_set, 1309 lbitset_reset, 1310 bitset_toggle_, 1311 lbitset_test, 1312 lbitset_resize, 1313 bitset_size_, 1314 bitset_count_, 1315 lbitset_empty_p, 1316 lbitset_ones, 1317 lbitset_zero, 1318 lbitset_copy, 1319 lbitset_disjoint_p, 1320 lbitset_equal_p, 1321 lbitset_not, 1322 lbitset_subset_p, 1323 lbitset_and, 1324 lbitset_and_cmp, 1325 lbitset_andn, 1326 lbitset_andn_cmp, 1327 lbitset_or, 1328 lbitset_or_cmp, 1329 lbitset_xor, 1330 lbitset_xor_cmp, 1331 bitset_and_or_, 1332 bitset_and_or_cmp_, 1333 bitset_andn_or_, 1334 bitset_andn_or_cmp_, 1335 bitset_or_and_, 1336 bitset_or_and_cmp_, 1337 lbitset_list, 1338 lbitset_list_reverse, 1339 lbitset_free, 1340 BITSET_LIST 1341 }; 1342 1343 1344 /* Return size of initial structure. */ 1345 size_t 1346 lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED) 1347 { 1348 return sizeof (struct lbitset_struct); 1349 } 1350 1351 1352 /* Initialize a bitset. */ 1353 bitset 1354 lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED) 1355 { 1356 BITSET_NBITS_ (bset) = n_bits; 1357 bset->b.vtable = &lbitset_vtable; 1358 return bset; 1359 } 1360 1361 1362 void 1363 lbitset_release_memory (void) 1364 { 1365 lbitset_free_list = 0; 1366 if (lbitset_obstack_init) 1367 { 1368 lbitset_obstack_init = false; 1369 obstack_free (&lbitset_obstack, NULL); 1370 } 1371 } 1372 1373 1374 /* Function to be called from debugger to debug lbitset. */ 1375 void 1376 debug_lbitset (bitset bset) 1377 { 1378 lbitset_elt *elt; 1379 unsigned int i; 1380 1381 if (!bset) 1382 return; 1383 1384 for (elt = LBITSET_HEAD (bset); elt; elt = elt->next) 1385 { 1386 fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index); 1387 for (i = 0; i < LBITSET_ELT_WORDS; i++) 1388 { 1389 unsigned int j; 1390 bitset_word word; 1391 1392 word = elt->words[i]; 1393 1394 fprintf (stderr, " Word %u:", i); 1395 for (j = 0; j < LBITSET_WORD_BITS; j++) 1396 if ((word & ((bitset_word) 1 << j))) 1397 fprintf (stderr, " %u", j); 1398 fprintf (stderr, "\n"); 1399 } 1400 } 1401 } 1402
