lib/lbitset.c

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