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