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