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