lib/lbitset.c

   1 /* Functions to support link list bitsets.
   2    Copyright (C) 2002, 2003, 2004, 2006 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 Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 # include <config.h>
  21 #endif
  22
  23 #include "lbitset.h"
  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 (elt && (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 *elt;
 939   lbitset_elt *selt;
 940   lbitset_elt *delt;
 941   bitset_windex i;
 942   unsigned int j;
 943   bitset_windex windex;
 944
 945   /* This is another unfriendly operation for a linked list
 946      bitset!  */
 947   elt = LBITSET_TAIL (dst);
 948
 949   windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
 950
 951   for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
 952     {
 953       /* Create new elements for dst if they cannot be found
 954          or substitute zero elements if src elements not found.  */
 955       selt = lbitset_elt_find (src, i, LBITSET_SUBST);
 956       delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 957
 958       for (j = 0; j < LBITSET_ELT_WORDS; j++)
 959         delt->words[j] = ~selt->words[j];
 960     }
 961   lbitset_unused_clear (dst);
 962   lbitset_weed (dst);
 963   return;
 964 }
 965
 966
 967 /* Is DST == DST | SRC?  */
 968 static bool
 969 lbitset_subset_p (bitset dst, bitset src)
 970 {
 971   lbitset_elt *selt;
 972   lbitset_elt *delt;
 973   unsigned int j;
 974
 975   for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
 976        selt || delt; selt = selt->next, delt = delt->next)
 977     {
 978       if (!selt)
 979         selt = &lbitset_zero_elts[0];
 980       else if (!delt)
 981         delt = &lbitset_zero_elts[0];
 982       else if (selt->index != delt->index)
 983         {
 984           if (selt->index < delt->index)
 985             {
 986               lbitset_zero_elts[2].next = delt;
 987               delt = &lbitset_zero_elts[2];
 988             }
 989           else
 990             {
 991               lbitset_zero_elts[1].next = selt;
 992               selt = &lbitset_zero_elts[1];
 993             }
 994         }
 995
 996       for (j = 0; j < LBITSET_ELT_WORDS; j++)
 997         if (delt->words[j] != (selt->words[j] | delt->words[j]))
 998           return false;
 999     }
1000   return true;
1001 }
1002
1003
1004 /* Is DST & SRC == 0?  */
1005 static bool
1006 lbitset_disjoint_p (bitset dst, bitset src)
1007 {
1008   lbitset_elt *selt;
1009   lbitset_elt *delt;
1010   unsigned int j;
1011
1012   for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
1013        selt && delt; selt = selt->next, delt = delt->next)
1014     {
1015       if (selt->index != delt->index)
1016         {
1017           if (selt->index < delt->index)
1018             {
1019               lbitset_zero_elts[2].next = delt;
1020               delt = &lbitset_zero_elts[2];
1021             }
1022           else
1023             {
1024               lbitset_zero_elts[1].next = selt;
1025               selt = &lbitset_zero_elts[1];
1026             }
1027           /* Since the elements are different, there is no
1028              intersection of these elements.  */
1029           continue;
1030         }
1031
1032       for (j = 0; j < LBITSET_ELT_WORDS; j++)
1033         if (selt->words[j] & delt->words[j])
1034           return false;
1035     }
1036   return true;
1037 }
1038
1039
1040 static bool
1041 lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
1042 {
1043   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1044   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1045   lbitset_elt *delt = LBITSET_HEAD (dst);
1046   bitset_windex windex1;
1047   bitset_windex windex2;
1048   bitset_windex windex;
1049   lbitset_elt *stmp1;
1050   lbitset_elt *stmp2;
1051   lbitset_elt *dtmp;
1052   bitset_word *srcp1;
1053   bitset_word *srcp2;
1054   bitset_word *dstp;
1055   bool changed = false;
1056   unsigned int i;
1057
1058   LBITSET_HEAD (dst) = 0;
1059   dst->b.csize = 0;
1060
1061   windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
1062   windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
1063
1064   while (selt1 || selt2)
1065     {
1066       /* Figure out whether we need to substitute zero elements for
1067          missing links.  */
1068       if (windex1 == windex2)
1069         {
1070           windex = windex1;
1071           stmp1 = selt1;
1072           stmp2 = selt2;
1073           selt1 = selt1->next;
1074           windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
1075           selt2 = selt2->next;
1076           windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
1077         }
1078       else if (windex1 < windex2)
1079         {
1080           windex = windex1;
1081           stmp1 = selt1;
1082           stmp2 = &lbitset_zero_elts[0];
1083           selt1 = selt1->next;
1084           windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
1085         }
1086       else
1087         {
1088           windex = windex2;
1089           stmp1 = &lbitset_zero_elts[0];
1090           stmp2 = selt2;
1091           selt2 = selt2->next;
1092           windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
1093         }
1094
1095       /* Find the appropriate element from DST.  Begin by discarding
1096          elements that we've skipped.  */
1097       while (delt && delt->index < windex)
1098         {
1099           changed = true;
1100           dtmp = delt;
1101           delt = delt->next;
1102           lbitset_elt_free (dtmp);
1103         }
1104       if (delt && delt->index == windex)
1105         {
1106           dtmp = delt;
1107           delt = delt->next;
1108         }
1109       else
1110         dtmp = lbitset_elt_calloc ();
1111
1112       /* Do the operation, and if any bits are set, link it into the
1113          linked list.  */
1114       srcp1 = stmp1->words;
1115       srcp2 = stmp2->words;
1116       dstp = dtmp->words;
1117       switch (op)
1118         {
1119         default:
1120           abort ();
1121
1122         case BITSET_OP_OR:
1123           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1124             {
1125               bitset_word tmp = *srcp1++ | *srcp2++;
1126
1127               if (*dstp != tmp)
1128                 {
1129                   changed = true;
1130                   *dstp = tmp;
1131                 }
1132             }
1133           break;
1134
1135         case BITSET_OP_AND:
1136           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1137             {
1138               bitset_word tmp = *srcp1++ & *srcp2++;
1139
1140               if (*dstp != tmp)
1141                 {
1142                   changed = true;
1143                   *dstp = tmp;
1144                 }
1145             }
1146           break;
1147
1148         case BITSET_OP_XOR:
1149           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1150             {
1151               bitset_word tmp = *srcp1++ ^ *srcp2++;
1152
1153               if (*dstp != tmp)
1154                 {
1155                   changed = true;
1156                   *dstp = tmp;
1157                 }
1158             }
1159           break;
1160
1161         case BITSET_OP_ANDN:
1162           for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1163             {
1164               bitset_word tmp = *srcp1++ & ~(*srcp2++);
1165
1166               if (*dstp != tmp)
1167                 {
1168                   changed = true;
1169                   *dstp = tmp;
1170                 }
1171             }
1172           break;
1173         }
1174
1175       if (!lbitset_elt_zero_p (dtmp))
1176         {
1177           dtmp->index = windex;
1178           /* Perhaps this could be optimised...  */
1179           lbitset_elt_link (dst, dtmp);
1180         }
1181       else
1182         {
1183           lbitset_elt_free (dtmp);
1184         }
1185     }
1186
1187   /* If we have elements of DST left over, free them all.  */
1188   if (delt)
1189     {
1190       changed = true;
1191       lbitset_prune (dst, delt);
1192     }
1193
1194   return changed;
1195 }
1196
1197
1198 static bool
1199 lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
1200 {
1201   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1202   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1203   bool changed;
1204
1205   if (!selt2)
1206     {
1207       lbitset_weed (dst);
1208       changed = !LBITSET_HEAD (dst);
1209       lbitset_zero (dst);
1210       return changed;
1211     }
1212   else if (!selt1)
1213     {
1214       lbitset_weed (dst);
1215       changed = !LBITSET_HEAD (dst);
1216       lbitset_zero (dst);
1217       return changed;
1218     }
1219   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1220 }
1221
1222
1223 static void
1224 lbitset_and (bitset dst, bitset src1, bitset src2)
1225 {
1226   lbitset_and_cmp (dst, src1, src2);
1227 }
1228
1229
1230 static bool
1231 lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
1232 {
1233   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1234   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1235   bool changed;
1236
1237   if (!selt2)
1238     {
1239       return lbitset_copy_cmp (dst, src1);
1240     }
1241   else if (!selt1)
1242     {
1243       lbitset_weed (dst);
1244       changed = !LBITSET_HEAD (dst);
1245       lbitset_zero (dst);
1246       return changed;
1247     }
1248   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1249 }
1250
1251
1252 static void
1253 lbitset_andn (bitset dst, bitset src1, bitset src2)
1254 {
1255   lbitset_andn_cmp (dst, src1, src2);
1256 }
1257
1258
1259 static bool
1260 lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
1261 {
1262   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1263   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1264
1265   if (!selt2)
1266     {
1267       return lbitset_copy_cmp (dst, src1);
1268     }
1269   else if (!selt1)
1270     {
1271       return lbitset_copy_cmp (dst, src2);
1272     }
1273   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1274 }
1275
1276
1277 static void
1278 lbitset_or (bitset dst, bitset src1, bitset src2)
1279 {
1280   lbitset_or_cmp (dst, src1, src2);
1281 }
1282
1283
1284 static bool
1285 lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1286 {
1287   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1288   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1289
1290   if (!selt2)
1291     {
1292       return lbitset_copy_cmp (dst, src1);
1293     }
1294   else if (!selt1)
1295     {
1296       return lbitset_copy_cmp (dst, src2);
1297     }
1298   return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1299 }
1300
1301
1302 static void
1303 lbitset_xor (bitset dst, bitset src1, bitset src2)
1304 {
1305   lbitset_xor_cmp (dst, src1, src2);
1306 }
1307
1308
1309
1310 /* Vector of operations for linked-list bitsets.  */
1311 struct bitset_vtable lbitset_vtable = {
1312   lbitset_set,
1313   lbitset_reset,
1314   bitset_toggle_,
1315   lbitset_test,
1316   lbitset_resize,
1317   bitset_size_,
1318   bitset_count_,
1319   lbitset_empty_p,
1320   lbitset_ones,
1321   lbitset_zero,
1322   lbitset_copy,
1323   lbitset_disjoint_p,
1324   lbitset_equal_p,
1325   lbitset_not,
1326   lbitset_subset_p,
1327   lbitset_and,
1328   lbitset_and_cmp,
1329   lbitset_andn,
1330   lbitset_andn_cmp,
1331   lbitset_or,
1332   lbitset_or_cmp,
1333   lbitset_xor,
1334   lbitset_xor_cmp,
1335   bitset_and_or_,
1336   bitset_and_or_cmp_,
1337   bitset_andn_or_,
1338   bitset_andn_or_cmp_,
1339   bitset_or_and_,
1340   bitset_or_and_cmp_,
1341   lbitset_list,
1342   lbitset_list_reverse,
1343   lbitset_free,
1344   BITSET_LIST
1345 };
1346
1347
1348 /* Return size of initial structure.  */
1349 size_t
1350 lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
1351 {
1352   return sizeof (struct lbitset_struct);
1353 }
1354
1355
1356 /* Initialize a bitset.  */
1357 bitset
1358 lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
1359 {
1360   BITSET_NBITS_ (bset) = n_bits;
1361   bset->b.vtable = &lbitset_vtable;
1362   return bset;
1363 }
1364
1365
1366 void
1367 lbitset_release_memory (void)
1368 {
1369   lbitset_free_list = 0;
1370   if (lbitset_obstack_init)
1371     {
1372       lbitset_obstack_init = false;
1373       obstack_free (&lbitset_obstack, NULL);
1374     }
1375 }
1376
1377
1378 /* Function to be called from debugger to debug lbitset.  */
1379 void
1380 debug_lbitset (bitset bset)
1381 {
1382   lbitset_elt *elt;
1383   unsigned int i;
1384
1385   if (!bset)
1386     return;
1387
1388   for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
1389     {
1390       fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index);
1391       for (i = 0; i < LBITSET_ELT_WORDS; i++)
1392         {
1393           unsigned int j;
1394           bitset_word word;
1395
1396           word = elt->words[i];
1397
1398           fprintf (stderr, "  Word %u:", i);
1399           for (j = 0; j < LBITSET_WORD_BITS; j++)
1400             if ((word & ((bitset_word) 1 << j)))
1401               fprintf (stderr, " %u", j);
1402           fprintf (stderr, "\n");
1403         }
1404     }
1405 }