lib/lbitset.c

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