lib/lbitset.c

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