lib/lbitset.c

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