lib/lbitset.c

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