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