lib/lbitset.c

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