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