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] |= (1 << (bitno % BITSET_WORD_BITS));
 589 }
 590
 591
 592 /* Reset bit BITNO in bitset DST.  */
 593 static void
 594 lbitset_reset (dst, bitno)
 595      bitset dst;
 596      bitset_bindex bitno;
 597 {
 598   bitset_windex windex = bitno / BITSET_WORD_BITS;
 599
 600   if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
 601     return;
 602
 603   dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
 604
 605   /* If all the data is zero, perhaps we should unlink it now...  */
 606 }
 607
 608
 609 /* Test bit BITNO in bitset SRC.  */
 610 static int
 611 lbitset_test (src, bitno)
 612      bitset src;
 613      bitset_bindex bitno;
 614 {
 615   bitset_windex windex = bitno / BITSET_WORD_BITS;
 616
 617   if (!lbitset_elt_find (src, windex, LBITSET_FIND))
 618     return 0;
 619
 620   return (src->b.cdata[windex - src->b.cindex]
 621           >> (bitno % BITSET_WORD_BITS)) & 1;
 622 }
 623
 624
 625 static void
 626 lbitset_free (bset)
 627      bitset bset;
 628 {
 629   lbitset_zero (bset);
 630 }
 631
 632
 633 /* Find list of up to NUM bits set in BSET starting from and including
 634  *NEXT and store in array LIST.  Return with actual number of bits
 635  found and with *NEXT indicating where search stopped.  */
 636 static int
 637 lbitset_reverse_list (bset, list, num, next)
 638      bitset bset;
 639      bitset_bindex *list;
 640      bitset_bindex num;
 641      bitset_bindex *next;
 642 {
 643   bitset_bindex rbitno;
 644   bitset_bindex bitno;
 645   unsigned int bcount;
 646   bitset_bindex boffset;
 647   bitset_windex windex;
 648   bitset_bindex count;
 649   lbitset_elt *elt;
 650   bitset_word word;
 651   bitset_bindex n_bits;
 652
 653   elt = LBITSET_TAIL (bset);
 654   if (!elt)
 655     return 0;
 656
 657   n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
 658   rbitno = *next;
 659
 660   if (rbitno >= n_bits)
 661     return 0;
 662
 663   bitno = n_bits - (rbitno + 1);
 664
 665   windex = bitno / BITSET_WORD_BITS;
 666
 667   /* Skip back to starting element.  */
 668   for (; elt && elt->index > windex; elt = elt->prev)
 669     continue;
 670
 671   if (!elt)
 672     return 0;
 673
 674   /* If num is 1, we could speed things up with a binary search
 675      of the word of interest.  */
 676
 677   count = 0;
 678   bcount = bitno % BITSET_WORD_BITS;
 679   boffset = windex * BITSET_WORD_BITS;
 680
 681   while (elt)
 682     {
 683       bitset_word *srcp = elt->words;
 684
 685       for (; (windex - elt->index) < LBITSET_ELT_WORDS;
 686            windex--, boffset -= BITSET_WORD_BITS,
 687              bcount = BITSET_WORD_BITS - 1)
 688         {
 689           word =
 690             srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount);
 691
 692           for (; word; bcount--)
 693             {
 694               if (word & BITSET_MSB)
 695                 {
 696                   list[count++] = boffset + bcount;
 697                   if (count >= num)
 698                     {
 699                       *next = n_bits - (boffset + bcount);
 700                       return count;
 701                     }
 702                 }
 703               word <<= 1;
 704             }
 705         }
 706
 707       elt = elt->prev;
 708       if (elt)
 709         {
 710           windex = elt->index + LBITSET_ELT_WORDS - 1;
 711           boffset = windex * BITSET_WORD_BITS;
 712         }
 713     }
 714
 715   *next = n_bits - (boffset + 1);
 716   return count;
 717 }
 718
 719
 720 /* Find list of up to NUM bits set in BSET starting from and including
 721  *NEXT and store in array LIST.  Return with actual number of bits
 722  found and with *NEXT indicating where search stopped.  */
 723 static int
 724 lbitset_list (bset, list, num, next)
 725      bitset bset;
 726      bitset_bindex *list;
 727      bitset_bindex num;
 728      bitset_bindex *next;
 729 {
 730   bitset_bindex bitno;
 731   bitset_windex windex;
 732   bitset_bindex count;
 733   lbitset_elt *elt;
 734   lbitset_elt *head;
 735   bitset_word word;
 736
 737   head = LBITSET_HEAD (bset);
 738   if (!head)
 739     return 0;
 740
 741   bitno = *next;
 742   count = 0;
 743
 744   if (!bitno)
 745     {
 746       /* This is the most common case.  */
 747
 748       /* Start with the first element.  */
 749       elt = head;
 750       windex = elt->index;
 751       bitno = windex * BITSET_WORD_BITS;
 752     }
 753   else
 754     {
 755       windex = bitno / BITSET_WORD_BITS;
 756
 757       /* Skip to starting element.  */
 758       for (elt = head;
 759            elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
 760            elt = elt->next)
 761         continue;
 762
 763       if (!elt)
 764         return 0;
 765
 766       if (windex < elt->index)
 767         {
 768           windex = elt->index;
 769           bitno = windex * BITSET_WORD_BITS;
 770         }
 771       else
 772         {
 773           bitset_word *srcp = elt->words;
 774
 775           /* We are starting within an element.  */
 776
 777           for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
 778             {
 779               word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS);
 780
 781               for (; word; bitno++)
 782                 {
 783                   if (word & 1)
 784                     {
 785                       list[count++] = bitno;
 786                       if (count >= num)
 787                         {
 788                           *next = bitno + 1;
 789                           return count;
 790                         }
 791                     }
 792                   word >>= 1;
 793                 }
 794               bitno = (windex + 1) * BITSET_WORD_BITS;
 795             }
 796
 797           elt = elt->next;
 798           if (elt)
 799             {
 800               windex = elt->index;
 801               bitno = windex * BITSET_WORD_BITS;
 802             }
 803         }
 804     }
 805
 806
 807   /* If num is 1, we could speed things up with a binary search
 808      of the word of interest.  */
 809
 810   while (elt)
 811     {
 812       int i;
 813       bitset_word *srcp = elt->words;
 814
 815       if ((count + LBITSET_ELT_BITS) < num)
 816         {
 817           /* The coast is clear, plant boot!  */
 818
 819 #if LBITSET_ELT_WORDS == 2
 820           word = srcp[0];
 821           if (word)
 822             {
 823               if (!(word & 0xffff))
 824                 {
 825                   word >>= 16;
 826                   bitno += 16;
 827                 }
 828               if (!(word & 0xff))
 829                 {
 830                   word >>= 8;
 831                   bitno += 8;
 832                 }
 833               for (; word; bitno++)
 834                 {
 835                   if (word & 1)
 836                     list[count++] = bitno;
 837                   word >>= 1;
 838                 }
 839             }
 840           windex++;
 841           bitno = windex * BITSET_WORD_BITS;
 842
 843           word = srcp[1];
 844           if (word)
 845             {
 846               if (!(word & 0xffff))
 847                 {
 848                   word >>= 16;
 849                   bitno += 16;
 850                 }
 851               for (; word; bitno++)
 852                 {
 853                   if (word & 1)
 854                     list[count++] = bitno;
 855                   word >>= 1;
 856                 }
 857             }
 858           windex++;
 859           bitno = windex * BITSET_WORD_BITS;
 860 #else
 861           for (i = 0; i < LBITSET_ELT_WORDS; i++)
 862             {
 863               word = srcp[i];
 864               if (word)
 865                 {
 866                   if (!(word & 0xffff))
 867                     {
 868                       word >>= 16;
 869                       bitno += 16;
 870                     }
 871                   if (!(word & 0xff))
 872                     {
 873                       word >>= 8;
 874                       bitno += 8;
 875                     }
 876                   for (; word; bitno++)
 877                     {
 878                       if (word & 1)
 879                         list[count++] = bitno;
 880                       word >>= 1;
 881                     }
 882                 }
 883               windex++;
 884               bitno = windex * BITSET_WORD_BITS;
 885             }
 886 #endif
 887         }
 888       else
 889         {
 890           /* Tread more carefully since we need to check
 891              if array overflows.  */
 892
 893           for (i = 0; i < LBITSET_ELT_WORDS; i++)
 894             {
 895               for (word = srcp[i]; word; bitno++)
 896                 {
 897                   if (word & 1)
 898                     {
 899                       list[count++] = bitno;
 900                       if (count >= num)
 901                         {
 902                           *next = bitno + 1;
 903                           return count;
 904                         }
 905                     }
 906                   word >>= 1;
 907                 }
 908               windex++;
 909               bitno = windex * BITSET_WORD_BITS;
 910             }
 911         }
 912
 913       elt = elt->next;
 914       if (elt)
 915         {
 916           windex = elt->index;
 917           bitno = windex * BITSET_WORD_BITS;
 918         }
 919     }
 920
 921   *next = bitno;
 922   return count;
 923 }
 924
 925
 926 static int
 927 lbitset_op1 (dst, op)
 928      bitset dst;
 929      enum bitset_ops op;
 930 {
 931   unsigned int i;
 932   bitset_windex windex;
 933   lbitset_elt *elt;
 934
 935   switch (op)
 936     {
 937     case BITSET_OP_ZERO:
 938       lbitset_zero (dst);
 939       break;
 940
 941     case BITSET_OP_ONES:
 942       /* This is a decidedly unfriendly operation for a linked list
 943          bitset!   */
 944       elt = LBITSET_TAIL (dst);
 945       /* Ignore empty set.  */
 946       if (!elt)
 947         return 0;
 948
 949       windex = elt->index;
 950       for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
 951         {
 952           /* Create new elements if they cannot be found.  */
 953           elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 954           memset (elt->words, ~0, sizeof (elt->words));
 955         }
 956       break;
 957
 958     case BITSET_OP_EMPTY_P:
 959       lbitset_weed (dst);
 960       if (LBITSET_HEAD (dst))
 961         return 0;
 962       break;
 963
 964     default:
 965       abort ();
 966     }
 967
 968   return 1;
 969 }
 970
 971
 972 static int
 973 lbitset_op2 (dst, src, op)
 974      bitset dst;
 975      bitset src;
 976      enum bitset_ops op;
 977 {
 978   lbitset_elt *elt;
 979   lbitset_elt *selt;
 980   lbitset_elt *delt;
 981   unsigned int i;
 982   unsigned int j;
 983   bitset_windex windex;
 984
 985   switch (op)
 986     {
 987     case BITSET_OP_COPY:
 988       lbitset_copy (dst, src);
 989       break;
 990
 991     case BITSET_OP_NOT:
 992       /* This is another unfriendly operation for a linked list
 993          bitset!  */
 994       elt = LBITSET_TAIL (dst);
 995       /* Ignore empty set.  */
 996       if (!elt)
 997         return 0;
 998
 999       windex = elt->index;
1000       for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
1001         {
1002           /* Create new elements for dst if they cannot be found
1003              or substitute zero elements if src elements not found.  */
1004           selt = lbitset_elt_find (dst, i, LBITSET_SUBST);
1005           delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
1006
1007           for (j = 0; j < LBITSET_ELT_WORDS; j++)
1008             delt->words[j] = ~selt->words[j];
1009         }
1010       lbitset_weed (dst);
1011       break;
1012
1013       /* Return 1 if DST == SRC.  */
1014     case BITSET_OP_EQUAL_P:
1015       return lbitset_equal_p (dst, src);
1016       break;
1017
1018       /* Return 1 if DST == DST | SRC.  */
1019     case BITSET_OP_SUBSET_P:
1020       for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
1021            selt || delt; selt = selt->next, delt = delt->next)
1022         {
1023           if (!selt)
1024             selt = &lbitset_zero_elts[0];
1025           else if (!delt)
1026             delt = &lbitset_zero_elts[0];
1027           else if (selt->index != delt->index)
1028             {
1029               if (selt->index < delt->index)
1030                 {
1031                   lbitset_zero_elts[2].next = delt;
1032                   delt = &lbitset_zero_elts[2];
1033                 }
1034               else
1035                 {
1036                   lbitset_zero_elts[1].next = selt;
1037                   selt = &lbitset_zero_elts[1];
1038                 }
1039             }
1040
1041           for (j = 0; j < LBITSET_ELT_WORDS; j++)
1042             if (delt->words[j] != (selt->words[j] | delt->words[j]))
1043               return 0;
1044         }
1045       break;
1046
1047       /* Return 1 if DST & SRC == 0.  */
1048     case BITSET_OP_DISJOINT_P:
1049       for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
1050            selt && delt; selt = selt->next, delt = delt->next)
1051         {
1052           if (selt->index != delt->index)
1053             {
1054               if (selt->index < delt->index)
1055                 {
1056                   lbitset_zero_elts[2].next = delt;
1057                   delt = &lbitset_zero_elts[2];
1058                 }
1059               else
1060                 {
1061                   lbitset_zero_elts[1].next = selt;
1062                   selt = &lbitset_zero_elts[1];
1063                 }
1064               /* Since the elements are different, there is no
1065                  intersection of these elements.  */
1066               continue;
1067             }
1068
1069           for (j = 0; j < LBITSET_ELT_WORDS; j++)
1070             if (selt->words[j] & delt->words[j])
1071               return 0;
1072         }
1073       break;
1074
1075     default:
1076       abort ();
1077     }
1078
1079   return 1;
1080 }
1081
1082
1083 static int
1084 lbitset_op3 (dst, src1, src2, op)
1085      bitset dst;
1086      bitset src1;
1087      bitset src2;
1088      enum bitset_ops op;
1089 {
1090   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1091   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1092   lbitset_elt *delt = LBITSET_HEAD (dst);
1093   bitset_windex windex1;
1094   bitset_windex windex2;
1095   bitset_windex windex;
1096   lbitset_elt *stmp1;
1097   lbitset_elt *stmp2;
1098   lbitset_elt *dtmp;
1099   bitset_word *srcp1;
1100   bitset_word *srcp2;
1101   bitset_word *dstp;
1102   int changed = 0;
1103   unsigned int i;
1104
1105   /* Fast track common, simple cases.  */
1106   if (!selt2)
1107     {
1108       if (op == BITSET_OP_AND)
1109         {
1110           lbitset_weed (dst);
1111           changed = !LBITSET_HEAD (dst);
1112           lbitset_zero (dst);
1113           return changed;
1114         }
1115       else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR
1116                || op == BITSET_OP_XOR)
1117         {
1118           return lbitset_copy_compare (dst, src1);
1119         }
1120     }
1121   else if (!selt1)
1122     {
1123       if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
1124         {
1125           lbitset_weed (dst);
1126           changed = !LBITSET_HEAD (dst);
1127           lbitset_zero (dst);
1128           return changed;
1129         }
1130       else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
1131         {
1132           return lbitset_copy_compare (dst, src2);
1133         }
1134     }
1135
1136   LBITSET_HEAD (dst) = 0;
1137   dst->b.csize = 0;
1138
1139   windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
1140   windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
1141
1142   while (selt1 || selt2)
1143     {
1144       /* Figure out whether we need to substitute zero elements for
1145          missing links.  */
1146       if (windex1 == windex2)
1147         {
1148           windex = windex1;
1149           stmp1 = selt1;
1150           stmp2 = selt2;
1151           selt1 = selt1->next;
1152           windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
1153           selt2 = selt2->next;
1154           windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
1155         }
1156       else if (windex1 < windex2)
1157         {
1158           windex = windex1;
1159           stmp1 = selt1;
1160           stmp2 = &lbitset_zero_elts[0];
1161           selt1 = selt1->next;
1162           windex1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
1163         }
1164       else
1165         {
1166           windex = windex2;
1167           stmp1 = &lbitset_zero_elts[0];
1168           stmp2 = selt2;
1169           selt2 = selt2->next;
1170           windex2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
1171         }
1172
1173       /* Find the appropriate element from DST.  Begin by discarding
1174          elements that we've skipped.  */
1175       while (delt && delt->index < windex)
1176         {
1177           changed = 1;
1178           dtmp = delt;
1179           delt = delt->next;
1180           lbitset_elt_free (dtmp);
1181         }
1182       if (delt && delt->index == windex)
1183         {
1184           dtmp = delt;
1185           delt = delt->next;
1186         }
1187       else
1188         dtmp = lbitset_elt_calloc ();
1189
1190       /* Do the operation, and if any bits are set, link it into the
1191          linked list.  */
1192       srcp1 = stmp1->words;
1193       srcp2 = stmp2->words;
1194       dstp = dtmp->words;
1195       switch (op)
1196         {
1197         case BITSET_OP_OR:
1198           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1199             {
1200               bitset_word tmp = *srcp1++ | *srcp2++;
1201
1202               if (*dstp != tmp)
1203                 {
1204                   changed = 1;
1205                   *dstp = tmp;
1206                 }
1207             }
1208           break;
1209
1210         case BITSET_OP_AND:
1211           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1212             {
1213               bitset_word tmp = *srcp1++ & *srcp2++;
1214
1215               if (*dstp != tmp)
1216                 {
1217                   changed = 1;
1218                   *dstp = tmp;
1219                 }
1220             }
1221           break;
1222
1223         case BITSET_OP_XOR:
1224           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1225             {
1226               bitset_word tmp = *srcp1++ ^ *srcp2++;
1227
1228               if (*dstp != tmp)
1229                 {
1230                   changed = 1;
1231                   *dstp = tmp;
1232                 }
1233             }
1234           break;
1235
1236         case BITSET_OP_ANDN:
1237           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1238             {
1239               bitset_word tmp = *srcp1++ & ~(*srcp2++);
1240
1241               if (*dstp != tmp)
1242                 {
1243                   changed = 1;
1244                   *dstp = tmp;
1245                 }
1246             }
1247           break;
1248
1249         default:
1250           abort ();
1251         }
1252
1253       if (!lbitset_elt_zero_p (dtmp))
1254         {
1255           dtmp->index = windex;
1256           /* Perhaps this could be optimised...  */
1257           lbitset_elt_link (dst, dtmp);
1258         }
1259       else
1260         {
1261           lbitset_elt_free (dtmp);
1262         }
1263     }
1264
1265   /* If we have elements of DST left over, free them all.  */
1266   if (delt)
1267     {
1268       changed = 1;
1269       lbitset_prune (dst, delt);
1270     }
1271
1272   return changed;
1273 }
1274
1275
1276 /* Vector of operations for linked-list bitsets.  */
1277 struct bitset_ops_struct lbitset_ops = {
1278   lbitset_set,
1279   lbitset_reset,
1280   lbitset_test,
1281   lbitset_size,
1282   lbitset_op1,
1283   lbitset_op2,
1284   lbitset_op3,
1285   bitset_op4,
1286   lbitset_list,
1287   lbitset_reverse_list,
1288   lbitset_free,
1289   BITSET_LIST
1290 };
1291
1292
1293 /* Return size of initial structure.  */
1294 int
1295 lbitset_bytes (n_bits)
1296      bitset_bindex n_bits ATTRIBUTE_UNUSED;
1297 {
1298   return sizeof (struct bitset_struct);
1299 }
1300
1301
1302 /* Initialize a bitset.  */
1303
1304 bitset
1305 lbitset_init (bset, n_bits)
1306      bitset bset;
1307      bitset_bindex n_bits ATTRIBUTE_UNUSED;
1308 {
1309   bset->b.ops = &lbitset_ops;
1310   return bset;
1311 }
1312
1313
1314 void
1315 lbitset_release_memory ()
1316 {
1317   lbitset_free_list = 0;
1318   if (lbitset_obstack_init)
1319     {
1320       lbitset_obstack_init = 0;
1321       obstack_free (&lbitset_obstack, NULL);
1322     }
1323 }