lib/lbitset.c

   1 /* Functions to support link list bitsets.
   2    Copyright (C) 2002, 2003 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 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
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 */
  19
  20 #ifdef HAVE_CONFIG_H
  21 #include "config.h"
  22 #endif
  23
  24 #include "lbitset.h"
  25 #include "obstack.h"
  26 #include <stddef.h>
  27 #include <stdlib.h>
  28 #include <stdio.h>
  29
  30 /* This file implements linked-list bitsets.  These bitsets can be of
  31    arbitrary length and are more efficient than arrays of bits for
  32    large sparse sets.
  33
  34    Usually if all the bits in an element are zero we remove the element
  35    from the list.  However, a side effect of the bit caching is that we
  36    do not always notice when an element becomes zero.  Hence the
  37    lbitset_weed function which removes zero elements.  */
  38
  39
  40 /* Number of words to use for each element.  The larger the value the
  41    greater the size of the cache and the shorter the time to find a given bit
  42    but the more memory wasted for sparse bitsets and the longer the time
  43    to search for set bits.  */
  44
  45 #define LBITSET_ELT_WORDS 2
  46
  47 typedef bitset_word lbitset_word;
  48
  49 #define LBITSET_WORD_BITS BITSET_WORD_BITS
  50
  51 /* Number of bits stored in each element.  */
  52 #define LBITSET_ELT_BITS \
  53   ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
  54
  55 /* Lbitset element.   We use an array of bits for each element.
  56    These are linked together in a doubly-linked list.  */
  57 typedef struct lbitset_elt_struct
  58 {
  59   struct lbitset_elt_struct *next;      /* Next element.  */
  60   struct lbitset_elt_struct *prev;      /* Previous element.  */
  61   bitset_windex index;  /* bitno / BITSET_WORD_BITS.  */
  62   bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set.  */
  63 }
  64 lbitset_elt;
  65
  66
  67 enum lbitset_find_mode
  68   { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
  69
  70 static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits.  */
  71
  72 /* Obstack to allocate bitset elements from.  */
  73 static struct obstack lbitset_obstack;
  74 static bool lbitset_obstack_init = false;
  75 static lbitset_elt *lbitset_free_list;  /* Free list of bitset elements.  */
  76
  77 extern void debug_lbitset PARAMS ((bitset));
  78
  79 #define LBITSET_CURRENT1(X) \
  80   ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
  81
  82 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
  83
  84 #define LBITSET_HEAD(X) ((X)->l.head)
  85 #define LBITSET_TAIL(X) ((X)->l.tail)
  86
  87 /* Allocate a lbitset element.  The bits are not cleared.  */
  88 static inline lbitset_elt *
  89 lbitset_elt_alloc (void)
  90 {
  91   lbitset_elt *elt;
  92
  93   if (lbitset_free_list != 0)
  94     {
  95       elt = lbitset_free_list;
  96       lbitset_free_list = elt->next;
  97     }
  98   else
  99     {
 100       if (!lbitset_obstack_init)
 101         {
 102           lbitset_obstack_init = true;
 103
 104           /* Let particular systems override the size of a chunk.  */
 105
 106 #ifndef OBSTACK_CHUNK_SIZE
 107 #define OBSTACK_CHUNK_SIZE 0
 108 #endif
 109
 110           /* Let them override the alloc and free routines too.  */
 111
 112 #ifndef OBSTACK_CHUNK_ALLOC
 113 #define OBSTACK_CHUNK_ALLOC xmalloc
 114 #endif
 115
 116 #ifndef OBSTACK_CHUNK_FREE
 117 #define OBSTACK_CHUNK_FREE free
 118 #endif
 119
 120 #if !defined(__GNUC__) || (__GNUC__ < 2)
 121 #define __alignof__(type) 0
 122 #endif
 123
 124           obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
 125                                       __alignof__ (lbitset_elt),
 126                                       (void *(*)PARAMS ((long)))
 127                                       OBSTACK_CHUNK_ALLOC,
 128                                       (void (*)PARAMS ((void *)))
 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     case LBITSET_FIND:
 365       return 0;
 366
 367     case LBITSET_CREATE:
 368       windex -= windex % LBITSET_ELT_WORDS;
 369
 370       elt = lbitset_elt_calloc ();
 371       elt->index = windex;
 372       lbitset_elt_link (bset, elt);
 373       return elt;
 374
 375     case LBITSET_SUBST:
 376       return &lbitset_zero_elts[0];
 377
 378     default:
 379       abort ();
 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 /* Return size in bits of bitset SRC.  */
 506 static bitset_bindex
 507 lbitset_size (bitset src)
 508 {
 509   lbitset_elt *elt;
 510
 511   elt = LBITSET_TAIL (src);
 512   if (!elt)
 513     return 0;
 514
 515   /* Return current size of bitset in bits.  */
 516   return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
 517 }
 518
 519
 520 /* Set bit BITNO in bitset DST.  */
 521 static void
 522 lbitset_set (bitset dst, bitset_bindex bitno)
 523 {
 524   bitset_windex windex = bitno / BITSET_WORD_BITS;
 525
 526   lbitset_elt_find (dst, windex, LBITSET_CREATE);
 527
 528   dst->b.cdata[windex - dst->b.cindex] |=
 529     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
 530 }
 531
 532
 533 /* Reset bit BITNO in bitset DST.  */
 534 static void
 535 lbitset_reset (bitset dst, bitset_bindex bitno)
 536 {
 537   bitset_windex windex = bitno / BITSET_WORD_BITS;
 538
 539   if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
 540     return;
 541
 542   dst->b.cdata[windex - dst->b.cindex] &=
 543     ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 544
 545   /* If all the data is zero, perhaps we should unlink it now...  */
 546 }
 547
 548
 549 /* Test bit BITNO in bitset SRC.  */
 550 static bool
 551 lbitset_test (bitset src, bitset_bindex bitno)
 552 {
 553   bitset_windex windex = bitno / BITSET_WORD_BITS;
 554
 555   return (lbitset_elt_find (src, windex, LBITSET_FIND)
 556           && ((src->b.cdata[windex - src->b.cindex]
 557                >> (bitno % BITSET_WORD_BITS))
 558               & 1));
 559 }
 560
 561
 562 static void
 563 lbitset_free (bitset bset)
 564 {
 565   lbitset_zero (bset);
 566 }
 567
 568
 569 /* Find list of up to NUM bits set in BSET starting from and including
 570  *NEXT and store in array LIST.  Return with actual number of bits
 571  found and with *NEXT indicating where search stopped.  */
 572 static bitset_bindex
 573 lbitset_list_reverse (bitset bset, bitset_bindex *list,
 574                       bitset_bindex num, bitset_bindex *next)
 575 {
 576   bitset_bindex rbitno;
 577   bitset_bindex bitno;
 578   unsigned int bcount;
 579   bitset_bindex boffset;
 580   bitset_windex windex;
 581   bitset_bindex count;
 582   lbitset_elt *elt;
 583   bitset_word word;
 584   bitset_bindex n_bits;
 585
 586   elt = LBITSET_TAIL (bset);
 587   if (!elt)
 588     return 0;
 589
 590   n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
 591   rbitno = *next;
 592
 593   if (rbitno >= n_bits)
 594     return 0;
 595
 596   bitno = n_bits - (rbitno + 1);
 597
 598   windex = bitno / BITSET_WORD_BITS;
 599
 600   /* Skip back to starting element.  */
 601   for (; elt && elt->index > windex; elt = elt->prev)
 602     continue;
 603
 604   if (!elt)
 605     return 0;
 606
 607   if (windex >= elt->index + LBITSET_ELT_WORDS)
 608     {
 609       /* We are trying to start in no-mans land so start
 610          at end of current elt.  */
 611       bcount = BITSET_WORD_BITS - 1;
 612       windex = elt->index + LBITSET_ELT_WORDS - 1;
 613     }
 614   else
 615     {
 616       bcount = bitno % BITSET_WORD_BITS;
 617     }
 618
 619   count = 0;
 620   boffset = windex * BITSET_WORD_BITS;
 621
 622   /* If num is 1, we could speed things up with a binary search
 623      of the word of interest.  */
 624
 625   while (elt)
 626     {
 627       bitset_word *srcp = elt->words;
 628
 629       for (; (windex - elt->index) < LBITSET_ELT_WORDS;
 630            windex--, boffset -= BITSET_WORD_BITS,
 631              bcount = BITSET_WORD_BITS - 1)
 632         {
 633           word =
 634             srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount);
 635
 636           for (; word; bcount--)
 637             {
 638               if (word & BITSET_MSB)
 639                 {
 640                   list[count++] = boffset + bcount;
 641                   if (count >= num)
 642                     {
 643                       *next = n_bits - (boffset + bcount);
 644                       return count;
 645                     }
 646                 }
 647               word <<= 1;
 648             }
 649         }
 650
 651       elt = elt->prev;
 652       if (elt)
 653         {
 654           windex = elt->index + LBITSET_ELT_WORDS - 1;
 655           boffset = windex * BITSET_WORD_BITS;
 656         }
 657     }
 658
 659   *next = n_bits - (boffset + 1);
 660   return count;
 661 }
 662
 663
 664 /* Find list of up to NUM bits set in BSET starting from and including
 665  *NEXT and store in array LIST.  Return with actual number of bits
 666  found and with *NEXT indicating where search stopped.  */
 667 static bitset_bindex
 668 lbitset_list (bitset bset, bitset_bindex *list,
 669               bitset_bindex num, bitset_bindex *next)
 670 {
 671   bitset_bindex bitno;
 672   bitset_windex windex;
 673   bitset_bindex count;
 674   lbitset_elt *elt;
 675   lbitset_elt *head;
 676   bitset_word word;
 677
 678   head = LBITSET_HEAD (bset);
 679   if (!head)
 680     return 0;
 681
 682   bitno = *next;
 683   count = 0;
 684
 685   if (!bitno)
 686     {
 687       /* This is the most common case.  */
 688
 689       /* Start with the first element.  */
 690       elt = head;
 691       windex = elt->index;
 692       bitno = windex * BITSET_WORD_BITS;
 693     }
 694   else
 695     {
 696       windex = bitno / BITSET_WORD_BITS;
 697
 698       /* Skip to starting element.  */
 699       for (elt = head;
 700            elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
 701            elt = elt->next)
 702         continue;
 703
 704       if (!elt)
 705         return 0;
 706
 707       if (windex < elt->index)
 708         {
 709           windex = elt->index;
 710           bitno = windex * BITSET_WORD_BITS;
 711         }
 712       else
 713         {
 714           bitset_word *srcp = elt->words;
 715
 716           /* We are starting within an element.  */
 717
 718           for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
 719             {
 720               word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS);
 721
 722               for (; word; bitno++)
 723                 {
 724                   if (word & 1)
 725                     {
 726                       list[count++] = bitno;
 727                       if (count >= num)
 728                         {
 729                           *next = bitno + 1;
 730                           return count;
 731                         }
 732                     }
 733                   word >>= 1;
 734                 }
 735               bitno = (windex + 1) * BITSET_WORD_BITS;
 736             }
 737
 738           elt = elt->next;
 739           if (elt)
 740             {
 741               windex = elt->index;
 742               bitno = windex * BITSET_WORD_BITS;
 743             }
 744         }
 745     }
 746
 747
 748   /* If num is 1, we could speed things up with a binary search
 749      of the word of interest.  */
 750
 751   while (elt)
 752     {
 753       int i;
 754       bitset_word *srcp = elt->words;
 755
 756       if ((count + LBITSET_ELT_BITS) < num)
 757         {
 758           /* The coast is clear, plant boot!  */
 759
 760 #if LBITSET_ELT_WORDS == 2
 761           word = srcp[0];
 762           if (word)
 763             {
 764               if (!(word & 0xffff))
 765                 {
 766                   word >>= 16;
 767                   bitno += 16;
 768                 }
 769               if (!(word & 0xff))
 770                 {
 771                   word >>= 8;
 772                   bitno += 8;
 773                 }
 774               for (; word; bitno++)
 775                 {
 776                   if (word & 1)
 777                     list[count++] = bitno;
 778                   word >>= 1;
 779                 }
 780             }
 781           windex++;
 782           bitno = windex * BITSET_WORD_BITS;
 783
 784           word = srcp[1];
 785           if (word)
 786             {
 787               if (!(word & 0xffff))
 788                 {
 789                   word >>= 16;
 790                   bitno += 16;
 791                 }
 792               for (; word; bitno++)
 793                 {
 794                   if (word & 1)
 795                     list[count++] = bitno;
 796                   word >>= 1;
 797                 }
 798             }
 799           windex++;
 800           bitno = windex * BITSET_WORD_BITS;
 801 #else
 802           for (i = 0; i < LBITSET_ELT_WORDS; i++)
 803             {
 804               word = srcp[i];
 805               if (word)
 806                 {
 807                   if (!(word & 0xffff))
 808                     {
 809                       word >>= 16;
 810                       bitno += 16;
 811                     }
 812                   if (!(word & 0xff))
 813                     {
 814                       word >>= 8;
 815                       bitno += 8;
 816                     }
 817                   for (; word; bitno++)
 818                     {
 819                       if (word & 1)
 820                         list[count++] = bitno;
 821                       word >>= 1;
 822                     }
 823                 }
 824               windex++;
 825               bitno = windex * BITSET_WORD_BITS;
 826             }
 827 #endif
 828         }
 829       else
 830         {
 831           /* Tread more carefully since we need to check
 832              if array overflows.  */
 833
 834           for (i = 0; i < LBITSET_ELT_WORDS; i++)
 835             {
 836               for (word = srcp[i]; word; bitno++)
 837                 {
 838                   if (word & 1)
 839                     {
 840                       list[count++] = bitno;
 841                       if (count >= num)
 842                         {
 843                           *next = bitno + 1;
 844                           return count;
 845                         }
 846                     }
 847                   word >>= 1;
 848                 }
 849               windex++;
 850               bitno = windex * BITSET_WORD_BITS;
 851             }
 852         }
 853
 854       elt = elt->next;
 855       if (elt)
 856         {
 857           windex = elt->index;
 858           bitno = windex * BITSET_WORD_BITS;
 859         }
 860     }
 861
 862   *next = bitno;
 863   return count;
 864 }
 865
 866
 867 static bool
 868 lbitset_empty_p (bitset dst)
 869 {
 870   lbitset_weed (dst);
 871   return !LBITSET_HEAD (dst);
 872 }
 873
 874
 875 static void
 876 lbitset_ones (bitset dst)
 877 {
 878   bitset_windex i;
 879   bitset_windex windex;
 880   lbitset_elt *elt;
 881
 882   /* This is a decidedly unfriendly operation for a linked list
 883       bitset!  It makes a sparse bitset become dense.  An alternative
 884       is to have a flag that indicates that the bitset stores the
 885       complement of what it indicates.  */
 886   elt = LBITSET_TAIL (dst);
 887   /* Ignore empty set.  */
 888   if (!elt)
 889     return;
 890
 891   windex = elt->index;
 892   for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
 893     {
 894       /* Create new elements if they cannot be found.  */
 895       elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 896       memset (elt->words, -1, sizeof (elt->words));
 897     }
 898 }
 899
 900
 901 static void
 902 lbitset_not (bitset dst, bitset src)
 903 {
 904   lbitset_elt *elt;
 905   lbitset_elt *selt;
 906   lbitset_elt *delt;
 907   bitset_windex i;
 908   unsigned int j;
 909   bitset_windex windex;
 910
 911   /* This is another unfriendly operation for a linked list
 912      bitset!  */
 913   elt = LBITSET_TAIL (dst);
 914   /* Ignore empty set.  */
 915   if (!elt)
 916     return;
 917
 918   windex = elt->index;
 919   for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
 920     {
 921       /* Create new elements for dst if they cannot be found
 922          or substitute zero elements if src elements not found.  */
 923       selt = lbitset_elt_find (src, i, LBITSET_SUBST);
 924       delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 925
 926       for (j = 0; j < LBITSET_ELT_WORDS; j++)
 927         delt->words[j] = ~selt->words[j];
 928     }
 929   lbitset_weed (dst);
 930   return;
 931 }
 932
 933
 934 /* Is DST == DST | SRC?  */
 935 static bool
 936 lbitset_subset_p (bitset dst, bitset src)
 937 {
 938   lbitset_elt *selt;
 939   lbitset_elt *delt;
 940   unsigned int j;
 941
 942   for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
 943        selt || delt; selt = selt->next, delt = delt->next)
 944     {
 945       if (!selt)
 946         selt = &lbitset_zero_elts[0];
 947       else if (!delt)
 948         delt = &lbitset_zero_elts[0];
 949       else if (selt->index != delt->index)
 950         {
 951           if (selt->index < delt->index)
 952             {
 953               lbitset_zero_elts[2].next = delt;
 954               delt = &lbitset_zero_elts[2];
 955             }
 956           else
 957             {
 958               lbitset_zero_elts[1].next = selt;
 959               selt = &lbitset_zero_elts[1];
 960             }
 961         }
 962
 963       for (j = 0; j < LBITSET_ELT_WORDS; j++)
 964         if (delt->words[j] != (selt->words[j] | delt->words[j]))
 965           return false;
 966     }
 967   return true;
 968 }
 969
 970
 971 /* Is DST & SRC == 0?  */
 972 static bool
 973 lbitset_disjoint_p (bitset dst, bitset src)
 974 {
 975   lbitset_elt *selt;
 976   lbitset_elt *delt;
 977   unsigned int j;
 978
 979   for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
 980        selt && delt; selt = selt->next, delt = delt->next)
 981     {
 982       if (selt->index != delt->index)
 983         {
 984           if (selt->index < delt->index)
 985             {
 986               lbitset_zero_elts[2].next = delt;
 987               delt = &lbitset_zero_elts[2];
 988             }
 989           else
 990             {
 991               lbitset_zero_elts[1].next = selt;
 992               selt = &lbitset_zero_elts[1];
 993             }
 994           /* Since the elements are different, there is no
 995              intersection of these elements.  */
 996           continue;
 997         }
 998
 999       for (j = 0; j < LBITSET_ELT_WORDS; j++)
1000         if (selt->words[j] & delt->words[j])
1001           return false;
1002     }
1003   return true;
1004 }
1005
1006
1007 static bool
1008 lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
1009 {
1010   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1011   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1012   lbitset_elt *delt = LBITSET_HEAD (dst);
1013   bitset_windex windex1;
1014   bitset_windex windex2;
1015   bitset_windex windex;
1016   lbitset_elt *stmp1;
1017   lbitset_elt *stmp2;
1018   lbitset_elt *dtmp;
1019   bitset_word *srcp1;
1020   bitset_word *srcp2;
1021   bitset_word *dstp;
1022   bool changed = false;
1023   unsigned int i;
1024
1025   LBITSET_HEAD (dst) = 0;
1026   dst->b.csize = 0;
1027
1028   windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
1029   windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
1030
1031   while (selt1 || selt2)
1032     {
1033       /* Figure out whether we need to substitute zero elements for
1034          missing links.  */
1035       if (windex1 == windex2)
1036         {
1037           windex = windex1;
1038           stmp1 = selt1;
1039           stmp2 = selt2;
1040           selt1 = selt1->next;
1041           windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
1042           selt2 = selt2->next;
1043           windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
1044         }
1045       else if (windex1 < windex2)
1046         {
1047           windex = windex1;
1048           stmp1 = selt1;
1049           stmp2 = &lbitset_zero_elts[0];
1050           selt1 = selt1->next;
1051           windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
1052         }
1053       else
1054         {
1055           windex = windex2;
1056           stmp1 = &lbitset_zero_elts[0];
1057           stmp2 = selt2;
1058           selt2 = selt2->next;
1059           windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
1060         }
1061
1062       /* Find the appropriate element from DST.  Begin by discarding
1063          elements that we've skipped.  */
1064       while (delt && delt->index < windex)
1065         {
1066           changed = true;
1067           dtmp = delt;
1068           delt = delt->next;
1069           lbitset_elt_free (dtmp);
1070         }
1071       if (delt && delt->index == windex)
1072         {
1073           dtmp = delt;
1074           delt = delt->next;
1075         }
1076       else
1077         dtmp = lbitset_elt_calloc ();
1078
1079       /* Do the operation, and if any bits are set, link it into the
1080          linked list.  */
1081       srcp1 = stmp1->words;
1082       srcp2 = stmp2->words;
1083       dstp = dtmp->words;
1084       switch (op)
1085         {
1086         case BITSET_OP_OR:
1087           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1088             {
1089               bitset_word tmp = *srcp1++ | *srcp2++;
1090
1091               if (*dstp != tmp)
1092                 {
1093                   changed = true;
1094                   *dstp = tmp;
1095                 }
1096             }
1097           break;
1098
1099         case BITSET_OP_AND:
1100           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1101             {
1102               bitset_word tmp = *srcp1++ & *srcp2++;
1103
1104               if (*dstp != tmp)
1105                 {
1106                   changed = true;
1107                   *dstp = tmp;
1108                 }
1109             }
1110           break;
1111
1112         case BITSET_OP_XOR:
1113           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1114             {
1115               bitset_word tmp = *srcp1++ ^ *srcp2++;
1116
1117               if (*dstp != tmp)
1118                 {
1119                   changed = true;
1120                   *dstp = tmp;
1121                 }
1122             }
1123           break;
1124
1125         case BITSET_OP_ANDN:
1126           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1127             {
1128               bitset_word tmp = *srcp1++ & ~(*srcp2++);
1129
1130               if (*dstp != tmp)
1131                 {
1132                   changed = true;
1133                   *dstp = tmp;
1134                 }
1135             }
1136           break;
1137
1138         default:
1139           abort ();
1140         }
1141
1142       if (!lbitset_elt_zero_p (dtmp))
1143         {
1144           dtmp->index = windex;
1145           /* Perhaps this could be optimised...  */
1146           lbitset_elt_link (dst, dtmp);
1147         }
1148       else
1149         {
1150           lbitset_elt_free (dtmp);
1151         }
1152     }
1153
1154   /* If we have elements of DST left over, free them all.  */
1155   if (delt)
1156     {
1157       changed = true;
1158       lbitset_prune (dst, delt);
1159     }
1160
1161   return changed;
1162 }
1163
1164
1165 static bool
1166 lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
1167 {
1168   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1169   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1170   bool changed;
1171
1172   if (!selt2)
1173     {
1174       lbitset_weed (dst);
1175       changed = !LBITSET_HEAD (dst);
1176       lbitset_zero (dst);
1177       return changed;
1178     }
1179   else if (!selt1)
1180     {
1181       lbitset_weed (dst);
1182       changed = !LBITSET_HEAD (dst);
1183       lbitset_zero (dst);
1184       return changed;
1185     }
1186   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1187 }
1188
1189
1190 static void
1191 lbitset_and (bitset dst, bitset src1, bitset src2)
1192 {
1193   lbitset_and_cmp (dst, src1, src2);
1194 }
1195
1196
1197 static bool
1198 lbitset_andn_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       return lbitset_copy_cmp (dst, src1);
1207     }
1208   else if (!selt1)
1209     {
1210       lbitset_weed (dst);
1211       changed = !LBITSET_HEAD (dst);
1212       lbitset_zero (dst);
1213       return changed;
1214     }
1215   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1216 }
1217
1218
1219 static void
1220 lbitset_andn (bitset dst, bitset src1, bitset src2)
1221 {
1222   lbitset_andn_cmp (dst, src1, src2);
1223 }
1224
1225
1226 static bool
1227 lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
1228 {
1229   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1230   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1231
1232   if (!selt2)
1233     {
1234       return lbitset_copy_cmp (dst, src1);
1235     }
1236   else if (!selt1)
1237     {
1238       return lbitset_copy_cmp (dst, src2);
1239     }
1240   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1241 }
1242
1243
1244 static void
1245 lbitset_or (bitset dst, bitset src1, bitset src2)
1246 {
1247   lbitset_or_cmp (dst, src1, src2);
1248 }
1249
1250
1251 static bool
1252 lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1253 {
1254   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1255   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1256
1257   if (!selt2)
1258     {
1259       return lbitset_copy_cmp (dst, src1);
1260     }
1261   else if (!selt1)
1262     {
1263       return lbitset_copy_cmp (dst, src2);
1264     }
1265   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1266 }
1267
1268
1269 static void
1270 lbitset_xor (bitset dst, bitset src1, bitset src2)
1271 {
1272   lbitset_xor_cmp (dst, src1, src2);
1273 }
1274
1275
1276
1277 /* Vector of operations for linked-list bitsets.  */
1278 struct bitset_vtable lbitset_vtable = {
1279   lbitset_set,
1280   lbitset_reset,
1281   bitset_toggle_,
1282   lbitset_test,
1283   lbitset_size,
1284   bitset_count_,
1285   lbitset_empty_p,
1286   lbitset_ones,
1287   lbitset_zero,
1288   lbitset_copy,
1289   lbitset_disjoint_p,
1290   lbitset_equal_p,
1291   lbitset_not,
1292   lbitset_subset_p,
1293   lbitset_and,
1294   lbitset_and_cmp,
1295   lbitset_andn,
1296   lbitset_andn_cmp,
1297   lbitset_or,
1298   lbitset_or_cmp,
1299   lbitset_xor,
1300   lbitset_xor_cmp,
1301   bitset_and_or_,
1302   bitset_and_or_cmp_,
1303   bitset_andn_or_,
1304   bitset_andn_or_cmp_,
1305   bitset_or_and_,
1306   bitset_or_and_cmp_,
1307   lbitset_list,
1308   lbitset_list_reverse,
1309   lbitset_free,
1310   BITSET_LIST
1311 };
1312
1313
1314 /* Return size of initial structure.  */
1315 size_t
1316 lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
1317 {
1318   return sizeof (struct lbitset_struct);
1319 }
1320
1321
1322 /* Initialize a bitset.  */
1323 bitset
1324 lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
1325 {
1326   bset->b.vtable = &lbitset_vtable;
1327   return bset;
1328 }
1329
1330
1331 void
1332 lbitset_release_memory (void)
1333 {
1334   lbitset_free_list = 0;
1335   if (lbitset_obstack_init)
1336     {
1337       lbitset_obstack_init = false;
1338       obstack_free (&lbitset_obstack, NULL);
1339     }
1340 }
1341
1342
1343 /* Function to be called from debugger to debug lbitset.  */
1344 void
1345 debug_lbitset (bitset bset)
1346 {
1347   lbitset_elt *elt;
1348   unsigned int i;
1349
1350   if (!bset)
1351     return;
1352
1353   for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
1354     {
1355       fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index);
1356       for (i = 0; i < LBITSET_ELT_WORDS; i++)
1357         {
1358           unsigned int j;
1359           bitset_word word;
1360
1361           word = elt->words[i];
1362
1363           fprintf (stderr, "  Word %u:", i);
1364           for (j = 0; j < LBITSET_WORD_BITS; j++)
1365             if ((word & ((bitset_word) 1 << j)))
1366               fprintf (stderr, " %u", j);
1367           fprintf (stderr, "\n");
1368         }
1369     }
1370 }