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