lib/bitset/table.c

   1 /* Functions to support expandable bitsets.
   2
   3    Copyright (C) 2002-2006, 2009-2015, 2018-2020 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 <https://www.gnu.org/licenses/>.  */
  19
  20 #include <config.h>
  21
  22 #include "bitset/table.h"
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include "obstack.h"
  28 #include "xalloc.h"
  29
  30 /* This file implements expandable bitsets.  These bitsets can be of
  31    arbitrary length and are more efficient than arrays of bits for
  32    large sparse sets.
  33
  34    Empty elements are represented by a NULL pointer in the table of
  35    element pointers.  An alternative is to point to a special zero
  36    element.  Similarly, we could represent an all 1's element with
  37    another special ones element pointer.
  38
  39    Bitsets are commonly empty so we need to ensure that this special
  40    case is fast.  A zero bitset is indicated when cdata is 0.  This is
  41    conservative since cdata may be non zero and the bitset may still
  42    be zero.
  43
  44    The bitset cache can be disabled either by setting cindex to
  45    BITSET_WINDEX_MAX or by setting csize to 0.  Here
  46    we use the former approach since cindex needs to be updated whenever
  47    cdata is changed.
  48 */
  49
  50
  51 /* Number of words to use for each element.  */
  52 #define TBITSET_ELT_WORDS 2
  53
  54 /* Number of bits stored in each element.  */
  55 #define TBITSET_ELT_BITS \
  56   ((unsigned) (TBITSET_ELT_WORDS * BITSET_WORD_BITS))
  57
  58 /* Tbitset element.  We use an array of bits.  */
  59 typedef struct tbitset_elt_struct
  60 {
  61   union
  62   {
  63     bitset_word words[TBITSET_ELT_WORDS];       /* Bits that are set.  */
  64     struct tbitset_elt_struct *next;
  65   }
  66   u;
  67 }
  68 tbitset_elt;
  69
  70
  71 typedef tbitset_elt *tbitset_elts;
  72
  73
  74 /* Number of elements to initially allocate.  */
  75
  76 #ifndef TBITSET_INITIAL_SIZE
  77 # define TBITSET_INITIAL_SIZE 2
  78 #endif
  79
  80
  81 enum tbitset_find_mode
  82   { TBITSET_FIND, TBITSET_CREATE, TBITSET_SUBST };
  83
  84 static tbitset_elt tbitset_zero_elts[1]; /* Elements of all zero bits.  */
  85
  86 /* Obstack to allocate bitset elements from.  */
  87 static struct obstack tbitset_obstack;
  88 static bool tbitset_obstack_init = false;
  89 static tbitset_elt *tbitset_free_list;  /* Free list of bitset elements.  */
  90
  91 #define TBITSET_N_ELTS(N) (((N) + TBITSET_ELT_BITS - 1) / TBITSET_ELT_BITS)
  92 #define TBITSET_ELTS(BSET) ((BSET)->e.elts)
  93 #define TBITSET_SIZE(BSET) TBITSET_N_ELTS (BITSET_NBITS_ (BSET))
  94 #define TBITSET_ASIZE(BSET) ((BSET)->e.size)
  95
  96 #define TBITSET_NEXT(ELT) ((ELT)->u.next)
  97 #define TBITSET_WORDS(ELT) ((ELT)->u.words)
  98
  99 /* Disable bitset cache and mark BSET as being zero.  */
 100 #define TBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
 101         (BSET)->b.cdata = 0)
 102
 103 #define TBITSET_CACHE_DISABLE(BSET)  ((BSET)->b.cindex = BITSET_WINDEX_MAX)
 104
 105 /* Disable bitset cache and mark BSET as being possibly non-zero.  */
 106 #define TBITSET_NONZERO_SET(BSET) \
 107  (TBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
 108
 109 /* A conservative estimate of whether the bitset is zero.
 110    This is non-zero only if we know for sure that the bitset is zero.  */
 111 #define TBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
 112
 113 /* Enable cache to point to element with table index EINDEX.
 114    The element must exist.  */
 115 #define TBITSET_CACHE_SET(BSET, EINDEX) \
 116  ((BSET)->b.cindex = (EINDEX) * TBITSET_ELT_WORDS, \
 117   (BSET)->b.cdata = TBITSET_WORDS (TBITSET_ELTS (BSET) [EINDEX]))
 118
 119 #undef min
 120 #undef max
 121 #define min(a, b) ((a) > (b) ? (b) : (a))
 122 #define max(a, b) ((a) > (b) ? (a) : (b))
 123
 124 static bitset_bindex
 125 tbitset_resize (bitset src, bitset_bindex n_bits)
 126 {
 127   if (n_bits == BITSET_NBITS_ (src))
 128     return n_bits;
 129
 130   bitset_windex oldsize = TBITSET_SIZE (src);
 131   bitset_windex newsize = TBITSET_N_ELTS (n_bits);
 132
 133   if (oldsize < newsize)
 134     {
 135       /* The bitset needs to grow.  If we already have enough memory
 136          allocated, then just zero what we need.  */
 137       if (newsize > TBITSET_ASIZE (src))
 138         {
 139           /* We need to allocate more memory.  When oldsize is
 140              non-zero this means that we are changing the size, so
 141              grow the bitset 25% larger than requested to reduce
 142              number of reallocations.  */
 143
 144           bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
 145           TBITSET_ELTS (src)
 146             = xrealloc (TBITSET_ELTS (src), size * sizeof (tbitset_elt *));
 147           TBITSET_ASIZE (src) = size;
 148         }
 149
 150       memset (TBITSET_ELTS (src) + oldsize, 0,
 151               (newsize - oldsize) * sizeof (tbitset_elt *));
 152     }
 153   else
 154     {
 155       /* The bitset needs to shrink.  There's no point deallocating
 156          the memory unless it is shrinking by a reasonable amount.  */
 157       if ((oldsize - newsize) >= oldsize / 2)
 158         {
 159           void *p
 160             = realloc (TBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
 161           if (p)
 162             {
 163               TBITSET_ELTS (src) = p;
 164               TBITSET_ASIZE (src) = newsize;
 165             }
 166         }
 167
 168       /* Need to prune any excess bits.  FIXME.  */
 169     }
 170
 171   BITSET_NBITS_ (src) = n_bits;
 172   return n_bits;
 173 }
 174
 175
 176 /* Allocate a tbitset element.  The bits are not cleared.  */
 177 static inline tbitset_elt *
 178 tbitset_elt_alloc (void)
 179 {
 180   tbitset_elt *elt;
 181
 182   if (tbitset_free_list != 0)
 183     {
 184       elt = tbitset_free_list;
 185       tbitset_free_list = TBITSET_NEXT (elt);
 186     }
 187   else
 188     {
 189       if (!tbitset_obstack_init)
 190         {
 191           tbitset_obstack_init = true;
 192
 193           /* Let particular systems override the size of a chunk.  */
 194
 195 #ifndef OBSTACK_CHUNK_SIZE
 196 # define OBSTACK_CHUNK_SIZE 0
 197 #endif
 198
 199           /* Let them override the alloc and free routines too.  */
 200
 201 #ifndef OBSTACK_CHUNK_ALLOC
 202 # define OBSTACK_CHUNK_ALLOC xmalloc
 203 #endif
 204
 205 #ifndef OBSTACK_CHUNK_FREE
 206 # define OBSTACK_CHUNK_FREE free
 207 #endif
 208
 209 #if !(defined __GNUC__ || defined __clang__)
 210 # define __alignof__(type) 0
 211 #endif
 212
 213           obstack_specify_allocation (&tbitset_obstack, OBSTACK_CHUNK_SIZE,
 214                                       __alignof__ (tbitset_elt),
 215                                       OBSTACK_CHUNK_ALLOC,
 216                                       OBSTACK_CHUNK_FREE);
 217         }
 218
 219       /* Perhaps we should add a number of new elements to the free
 220          list.  */
 221       elt = (tbitset_elt *) obstack_alloc (&tbitset_obstack,
 222                                            sizeof (tbitset_elt));
 223     }
 224
 225   return elt;
 226 }
 227
 228
 229 /* Allocate a tbitset element.  The bits are cleared.  */
 230 static inline tbitset_elt *
 231 tbitset_elt_calloc (void)
 232 {
 233   tbitset_elt *elt = tbitset_elt_alloc ();
 234   memset (TBITSET_WORDS (elt), 0, sizeof (TBITSET_WORDS (elt)));
 235   return elt;
 236 }
 237
 238
 239 static inline void
 240 tbitset_elt_free (tbitset_elt *elt)
 241 {
 242   TBITSET_NEXT (elt) = tbitset_free_list;
 243   tbitset_free_list = elt;
 244 }
 245
 246
 247 /* Remove element with index EINDEX from bitset BSET.  */
 248 static inline void
 249 tbitset_elt_remove (bitset bset, bitset_windex eindex)
 250 {
 251   tbitset_elts *elts = TBITSET_ELTS (bset);
 252   tbitset_elt *elt = elts[eindex];
 253
 254   elts[eindex] = 0;
 255   tbitset_elt_free (elt);
 256 }
 257
 258
 259 /* Add ELT into elts at index EINDEX of bitset BSET.  */
 260 static inline void
 261 tbitset_elt_add (bitset bset, tbitset_elt *elt, bitset_windex eindex)
 262 {
 263   tbitset_elts *elts = TBITSET_ELTS (bset);
 264   /* Assume that the elts entry not allocated.  */
 265   elts[eindex] = elt;
 266 }
 267
 268
 269 /* Are all bits in an element zero?  */
 270 static inline bool
 271 tbitset_elt_zero_p (tbitset_elt *elt)
 272 {
 273   for (int i = 0; i < TBITSET_ELT_WORDS; i++)
 274     if (TBITSET_WORDS (elt)[i])
 275       return false;
 276   return true;
 277 }
 278
 279
 280 static tbitset_elt *
 281 tbitset_elt_find (bitset bset, bitset_bindex bindex,
 282                   enum tbitset_find_mode mode)
 283 {
 284   bitset_windex eindex = bindex / TBITSET_ELT_BITS;
 285
 286   tbitset_elts *elts = TBITSET_ELTS (bset);
 287   bitset_windex size = TBITSET_SIZE (bset);
 288
 289   if (eindex < size)
 290     {
 291       tbitset_elt *elt = elts[eindex];
 292       if (elt)
 293         {
 294           if (TBITSET_WORDS (elt) != bset->b.cdata)
 295             TBITSET_CACHE_SET (bset, eindex);
 296           return elt;
 297         }
 298     }
 299
 300   /* The element could not be found.  */
 301
 302   switch (mode)
 303     {
 304     default:
 305       abort ();
 306
 307     case TBITSET_FIND:
 308       return NULL;
 309
 310     case TBITSET_CREATE:
 311       if (eindex >= size)
 312         tbitset_resize (bset, bindex);
 313
 314       /* Create a new element.  */
 315       {
 316         tbitset_elt *elt = tbitset_elt_calloc ();
 317         tbitset_elt_add (bset, elt, eindex);
 318         TBITSET_CACHE_SET (bset, eindex);
 319         return elt;
 320       }
 321
 322     case TBITSET_SUBST:
 323       return &tbitset_zero_elts[0];
 324     }
 325 }
 326
 327
 328 /* Weed out the zero elements from the elts.  */
 329 static inline bitset_windex
 330 tbitset_weed (bitset bset)
 331 {
 332   if (TBITSET_ZERO_P (bset))
 333     return 0;
 334
 335   tbitset_elts *elts = TBITSET_ELTS (bset);
 336   bitset_windex count = 0;
 337   bitset_windex j;
 338   for (j = 0; j < TBITSET_SIZE (bset); j++)
 339     {
 340       tbitset_elt *elt = elts[j];
 341
 342       if (elt)
 343         {
 344           if (tbitset_elt_zero_p (elt))
 345             {
 346               tbitset_elt_remove (bset, j);
 347               count++;
 348             }
 349         }
 350       else
 351         count++;
 352     }
 353
 354   count = j - count;
 355   if (!count)
 356     {
 357       /* All the bits are zero.  We could shrink the elts.
 358          For now just mark BSET as known to be zero.  */
 359       TBITSET_ZERO_SET (bset);
 360     }
 361   else
 362     TBITSET_NONZERO_SET (bset);
 363
 364   return count;
 365 }
 366
 367
 368 /* Set all bits in the bitset to zero.  */
 369 static inline void
 370 tbitset_zero (bitset bset)
 371 {
 372   if (TBITSET_ZERO_P (bset))
 373     return;
 374
 375   tbitset_elts *elts = TBITSET_ELTS (bset);
 376   for (bitset_windex j = 0; j < TBITSET_SIZE (bset); j++)
 377     {
 378       tbitset_elt *elt = elts[j];
 379       if (elt)
 380         tbitset_elt_remove (bset, j);
 381     }
 382
 383   /* All the bits are zero.  We could shrink the elts.
 384      For now just mark BSET as known to be zero.  */
 385   TBITSET_ZERO_SET (bset);
 386 }
 387
 388
 389 static inline bool
 390 tbitset_equal_p (bitset dst, bitset src)
 391 {
 392   if (src == dst)
 393     return true;
 394
 395   tbitset_weed (dst);
 396   tbitset_weed (src);
 397
 398   if (TBITSET_SIZE (src) != TBITSET_SIZE (dst))
 399     return false;
 400
 401   tbitset_elts *selts = TBITSET_ELTS (src);
 402   tbitset_elts *delts = TBITSET_ELTS (dst);
 403
 404   for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
 405     {
 406       tbitset_elt *selt = selts[j];
 407       tbitset_elt *delt = delts[j];
 408
 409       if (!selt && !delt)
 410         continue;
 411       if ((selt && !delt) || (!selt && delt))
 412         return false;
 413
 414       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 415         if (TBITSET_WORDS (selt)[i] != TBITSET_WORDS (delt)[i])
 416           return false;
 417     }
 418   return true;
 419 }
 420
 421
 422 /* Copy bits from bitset SRC to bitset DST.  */
 423 static inline void
 424 tbitset_copy_ (bitset dst, bitset src)
 425 {
 426   if (src == dst)
 427     return;
 428
 429   tbitset_zero (dst);
 430
 431   if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
 432     tbitset_resize (dst, BITSET_NBITS_ (src));
 433
 434   tbitset_elts *selts = TBITSET_ELTS (src);
 435   tbitset_elts *delts = TBITSET_ELTS (dst);
 436   for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
 437     {
 438       tbitset_elt *selt = selts[j];
 439       if (selt)
 440         {
 441           tbitset_elt *tmp = tbitset_elt_alloc ();
 442           delts[j] = tmp;
 443           memcpy (TBITSET_WORDS (tmp), TBITSET_WORDS (selt),
 444                   sizeof (TBITSET_WORDS (selt)));
 445         }
 446     }
 447   TBITSET_NONZERO_SET (dst);
 448 }
 449
 450
 451 /* Copy bits from bitset SRC to bitset DST.  Return true if
 452    bitsets different.  */
 453 static inline bool
 454 tbitset_copy_cmp (bitset dst, bitset src)
 455 {
 456   if (src == dst)
 457     return false;
 458
 459   if (TBITSET_ZERO_P (dst))
 460     {
 461       tbitset_copy_ (dst, src);
 462       return !TBITSET_ZERO_P (src);
 463     }
 464
 465   if (tbitset_equal_p (dst, src))
 466     return false;
 467
 468   tbitset_copy_ (dst, src);
 469   return true;
 470 }
 471
 472
 473 /* Set bit BITNO in bitset DST.  */
 474 static void
 475 tbitset_set (bitset dst, bitset_bindex bitno)
 476 {
 477   bitset_windex windex = bitno / BITSET_WORD_BITS;
 478
 479   tbitset_elt_find (dst, bitno, TBITSET_CREATE);
 480
 481   dst->b.cdata[windex - dst->b.cindex] |=
 482     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
 483 }
 484
 485
 486 /* Reset bit BITNO in bitset DST.  */
 487 static void
 488 tbitset_reset (bitset dst, bitset_bindex bitno)
 489 {
 490   bitset_windex windex = bitno / BITSET_WORD_BITS;
 491
 492   if (!tbitset_elt_find (dst, bitno, TBITSET_FIND))
 493     return;
 494
 495   dst->b.cdata[windex - dst->b.cindex] &=
 496     ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 497
 498   /* If all the data is zero, perhaps we should remove it now...
 499      However, there is a good chance that the element will be needed
 500      again soon.  */
 501 }
 502
 503
 504 /* Test bit BITNO in bitset SRC.  */
 505 static bool
 506 tbitset_test (bitset src, bitset_bindex bitno)
 507 {
 508   bitset_windex windex = bitno / BITSET_WORD_BITS;
 509
 510   return (tbitset_elt_find (src, bitno, TBITSET_FIND)
 511           && ((src->b.cdata[windex - src->b.cindex]
 512                >> (bitno % BITSET_WORD_BITS))
 513               & 1));
 514 }
 515
 516
 517 static void
 518 tbitset_free (bitset bset)
 519 {
 520   tbitset_zero (bset);
 521   free (TBITSET_ELTS (bset));
 522 }
 523
 524
 525 /* Find list of up to NUM bits set in BSET starting from and including
 526  *NEXT and store in array LIST.  Return with actual number of bits
 527  found and with *NEXT indicating where search stopped.  */
 528 static bitset_bindex
 529 tbitset_list_reverse (bitset bset, bitset_bindex *list,
 530                       bitset_bindex num, bitset_bindex *next)
 531 {
 532   if (TBITSET_ZERO_P (bset))
 533     return 0;
 534
 535   bitset_windex size = TBITSET_SIZE (bset);
 536   bitset_bindex n_bits = size * TBITSET_ELT_BITS;
 537   bitset_bindex rbitno = *next;
 538
 539   if (rbitno >= n_bits)
 540     return 0;
 541
 542   tbitset_elts *elts = TBITSET_ELTS (bset);
 543
 544   bitset_bindex bitno = n_bits - (rbitno + 1);
 545
 546   bitset_windex windex = bitno / BITSET_WORD_BITS;
 547   bitset_windex eindex = bitno / TBITSET_ELT_BITS;
 548   bitset_windex woffset = windex - eindex * TBITSET_ELT_WORDS;
 549
 550   /* If num is 1, we could speed things up with a binary search
 551      of the word of interest.  */
 552   bitset_bindex count = 0;
 553   unsigned bitcnt = bitno % BITSET_WORD_BITS;
 554   bitset_bindex bitoff = windex * BITSET_WORD_BITS;
 555
 556   do
 557     {
 558       tbitset_elt *elt = elts[eindex];
 559       if (elt)
 560         {
 561           bitset_word *srcp = TBITSET_WORDS (elt);
 562
 563           do
 564             {
 565               bitset_word word = srcp[woffset];
 566               if (bitcnt + 1 < BITSET_WORD_BITS)
 567                 /* We're starting in the middle of a word: smash bits to ignore.  */
 568                 word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
 569               BITSET_FOR_EACH_BIT_REVERSE(pos, word)
 570                 {
 571                   list[count++] = bitoff + pos;
 572                   if (count >= num)
 573                     {
 574                       *next = n_bits - (bitoff + pos);
 575                       return count;
 576                     }
 577                 }
 578               bitoff -= BITSET_WORD_BITS;
 579               bitcnt = BITSET_WORD_BITS - 1;
 580             }
 581           while (woffset--);
 582         }
 583
 584       woffset = TBITSET_ELT_WORDS - 1;
 585       bitoff = eindex * TBITSET_ELT_BITS - BITSET_WORD_BITS;
 586     }
 587   while (eindex--);
 588
 589   *next = n_bits - (bitoff + 1);
 590   return count;
 591 }
 592
 593
 594 /* Find list of up to NUM bits set in BSET starting from and including
 595    *NEXT and store in array LIST.  Return with actual number of bits
 596    found and with *NEXT indicating where search stopped.  */
 597 static bitset_bindex
 598 tbitset_list (bitset bset, bitset_bindex *list,
 599               bitset_bindex num, bitset_bindex *next)
 600 {
 601   if (TBITSET_ZERO_P (bset))
 602     return 0;
 603
 604   bitset_bindex bitno = *next;
 605   bitset_bindex count = 0;
 606
 607   tbitset_elts *elts = TBITSET_ELTS (bset);
 608   bitset_windex size = TBITSET_SIZE (bset);
 609   bitset_windex eindex = bitno / TBITSET_ELT_BITS;
 610
 611   if (bitno % TBITSET_ELT_BITS)
 612     {
 613       /* We need to start within an element.  This is not very common.  */
 614       tbitset_elt *elt = elts[eindex];
 615       if (elt)
 616         {
 617           bitset_word *srcp = TBITSET_WORDS (elt);
 618           bitset_windex woffset = eindex * TBITSET_ELT_WORDS;
 619
 620           for (bitset_windex windex = bitno / BITSET_WORD_BITS;
 621                (windex - woffset) < TBITSET_ELT_WORDS; windex++)
 622             {
 623               bitset_word word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
 624
 625               BITSET_FOR_EACH_BIT (pos, word)
 626                 {
 627                   list[count++] = bitno + pos;
 628                   if (count >= num)
 629                     {
 630                       *next = bitno + pos + 1;
 631                       return count;
 632                     }
 633                 }
 634               bitno = (windex + 1) * BITSET_WORD_BITS;
 635             }
 636         }
 637
 638       /* Skip to next element.  */
 639       eindex++;
 640     }
 641
 642   /* If num is 1, we could speed things up with a binary search
 643      of the word of interest.  */
 644
 645   for (; eindex < size; eindex++)
 646     {
 647       tbitset_elt *elt = elts[eindex];
 648       if (!elt)
 649         continue;
 650
 651       bitset_word *srcp = TBITSET_WORDS (elt);
 652       bitset_windex windex = eindex * TBITSET_ELT_WORDS;
 653       bitno = windex * BITSET_WORD_BITS;
 654
 655       /* Is there enough room to avoid checking in each iteration? */
 656       if ((count + TBITSET_ELT_BITS) < num)
 657         {
 658           /* The coast is clear, plant boot!  */
 659
 660 #if TBITSET_ELT_WORDS == 2
 661           bitset_word word = srcp[0];
 662           if (word)
 663             BITSET_FOR_EACH_BIT (pos, word)
 664               list[count++] = bitno + pos;
 665           windex++;
 666           bitno = windex * BITSET_WORD_BITS;
 667
 668           word = srcp[1];
 669           if (word)
 670             BITSET_FOR_EACH_BIT (pos, word)
 671               list[count++] = bitno + pos;
 672           windex++;
 673           bitno = windex * BITSET_WORD_BITS;
 674 #else
 675           for (int i = 0; i < TBITSET_ELT_WORDS; i++, windex++)
 676             {
 677               bitset_word word = srcp[i];
 678               if (word)
 679                 BITSET_FOR_EACH_BIT (pos, word)
 680                   list[count++] = bitno + pos;
 681               bitno = windex * BITSET_WORD_BITS;
 682             }
 683 #endif
 684         }
 685       else
 686         {
 687           /* Tread more carefully since we need to check
 688              if array overflows.  */
 689           for (int i = 0; i < TBITSET_ELT_WORDS; i++)
 690             {
 691               bitset_word word = srcp[i];
 692               if (word)
 693                 BITSET_FOR_EACH_BIT (pos, word)
 694                   {
 695                     list[count++] = bitno + pos;
 696                     if (count >= num)
 697                       {
 698                         *next = bitno + pos + 1;
 699                         return count;
 700                       }
 701                   }
 702               windex++;
 703               bitno = windex * BITSET_WORD_BITS;
 704             }
 705         }
 706     }
 707
 708   *next = bitno;
 709   return count;
 710 }
 711
 712
 713 /* Ensure that any unused bits within the last element are clear.  */
 714 static inline void
 715 tbitset_unused_clear (bitset dst)
 716 {
 717   bitset_bindex n_bits = BITSET_NBITS_ (dst);
 718   unsigned last_bit = n_bits % TBITSET_ELT_BITS;
 719
 720   if (last_bit)
 721     {
 722       tbitset_elts *elts = TBITSET_ELTS (dst);
 723
 724       bitset_windex eindex = n_bits / TBITSET_ELT_BITS;
 725
 726       tbitset_elt *elt = elts[eindex];
 727       if (elt)
 728         {
 729           bitset_word *srcp = TBITSET_WORDS (elt);
 730
 731           bitset_windex windex = n_bits / BITSET_WORD_BITS;
 732           bitset_windex woffset = eindex * TBITSET_ELT_WORDS;
 733
 734           srcp[windex - woffset]
 735             &= ((bitset_word) 1 << (last_bit % BITSET_WORD_BITS)) - 1;
 736           windex++;
 737           for (; (windex - woffset) < TBITSET_ELT_WORDS; windex++)
 738             srcp[windex - woffset] = 0;
 739         }
 740     }
 741 }
 742
 743
 744 static void
 745 tbitset_ones (bitset dst)
 746 {
 747   for (bitset_windex j = 0; j < TBITSET_SIZE (dst); j++)
 748     {
 749       /* Create new elements if they cannot be found.  Perhaps
 750          we should just add pointers to a ones element?  */
 751       tbitset_elt *elt =
 752         tbitset_elt_find (dst, j * TBITSET_ELT_BITS, TBITSET_CREATE);
 753       memset (TBITSET_WORDS (elt), -1, sizeof (TBITSET_WORDS (elt)));
 754     }
 755   TBITSET_NONZERO_SET (dst);
 756   tbitset_unused_clear (dst);
 757 }
 758
 759
 760 static bool
 761 tbitset_empty_p (bitset dst)
 762 {
 763   if (TBITSET_ZERO_P (dst))
 764     return true;
 765
 766   tbitset_elts *elts = TBITSET_ELTS (dst);
 767   for (bitset_windex j = 0; j < TBITSET_SIZE (dst); j++)
 768     {
 769       tbitset_elt *elt = elts[j];
 770
 771       if (elt)
 772         {
 773           if (!tbitset_elt_zero_p (elt))
 774             return false;
 775           /* Do some weeding as we go.  */
 776           tbitset_elt_remove (dst, j);
 777         }
 778     }
 779
 780   /* All the bits are zero.  We could shrink the elts.
 781      For now just mark DST as known to be zero.  */
 782   TBITSET_ZERO_SET (dst);
 783   return true;
 784 }
 785
 786
 787 static void
 788 tbitset_not (bitset dst, bitset src)
 789 {
 790   tbitset_resize (dst, BITSET_NBITS_ (src));
 791
 792   for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
 793     {
 794       /* Create new elements for dst if they cannot be found
 795          or substitute zero elements if src elements not found.  */
 796       tbitset_elt *selt =
 797         tbitset_elt_find (src, j * TBITSET_ELT_BITS, TBITSET_SUBST);
 798       tbitset_elt *delt =
 799         tbitset_elt_find (dst, j * TBITSET_ELT_BITS, TBITSET_CREATE);
 800
 801       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 802         TBITSET_WORDS (delt)[i] = ~TBITSET_WORDS (selt)[i];
 803     }
 804   TBITSET_NONZERO_SET (dst);
 805   tbitset_unused_clear (dst);
 806 }
 807
 808
 809 /* Is DST == DST | SRC?  */
 810 static bool
 811 tbitset_subset_p (bitset dst, bitset src)
 812 {
 813   tbitset_elts *selts = TBITSET_ELTS (src);
 814   tbitset_elts *delts = TBITSET_ELTS (dst);
 815
 816   bitset_windex ssize = TBITSET_SIZE (src);
 817   bitset_windex dsize = TBITSET_SIZE (dst);
 818
 819   for (bitset_windex j = 0; j < ssize; j++)
 820     {
 821       tbitset_elt *selt = j < ssize ? selts[j] : 0;
 822       tbitset_elt *delt = j < dsize ? delts[j] : 0;
 823
 824       if (!selt && !delt)
 825         continue;
 826
 827       if (!selt)
 828         selt = &tbitset_zero_elts[0];
 829       if (!delt)
 830         delt = &tbitset_zero_elts[0];
 831
 832       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 833         if (TBITSET_WORDS (delt)[i]
 834             != (TBITSET_WORDS (selt)[i] | TBITSET_WORDS (delt)[i]))
 835           return false;
 836     }
 837   return true;
 838 }
 839
 840
 841 /* Is DST & SRC == 0?  */
 842 static bool
 843 tbitset_disjoint_p (bitset dst, bitset src)
 844 {
 845   tbitset_elts *selts = TBITSET_ELTS (src);
 846   tbitset_elts *delts = TBITSET_ELTS (dst);
 847
 848   bitset_windex ssize = TBITSET_SIZE (src);
 849   bitset_windex dsize = TBITSET_SIZE (dst);
 850
 851   for (bitset_windex j = 0; j < ssize; j++)
 852     {
 853       tbitset_elt *selt = j < ssize ? selts[j] : 0;
 854       tbitset_elt *delt = j < dsize ? delts[j] : 0;
 855
 856       if (!selt || !delt)
 857         continue;
 858
 859       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 860         if ((TBITSET_WORDS (selt)[i] & TBITSET_WORDS (delt)[i]))
 861           return false;
 862     }
 863   return true;
 864 }
 865
 866
 867
 868 static bool
 869 tbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
 870 {
 871   bool changed = false;
 872
 873   tbitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
 874
 875   bitset_windex ssize1 = TBITSET_SIZE (src1);
 876   bitset_windex ssize2 = TBITSET_SIZE (src2);
 877   bitset_windex dsize = TBITSET_SIZE (dst);
 878   bitset_windex size = ssize1;
 879   if (size < ssize2)
 880     size = ssize2;
 881
 882   tbitset_elts *selts1 = TBITSET_ELTS (src1);
 883   tbitset_elts *selts2 = TBITSET_ELTS (src2);
 884   tbitset_elts *delts = TBITSET_ELTS (dst);
 885
 886   bitset_windex j = 0;
 887   for (j = 0; j < size; j++)
 888     {
 889       tbitset_elt *selt1 = j < ssize1 ? selts1[j] : 0;
 890       tbitset_elt *selt2 = j < ssize2 ? selts2[j] : 0;
 891       tbitset_elt *delt = j < dsize ? delts[j] : 0;
 892
 893       if (!selt1 && !selt2)
 894         {
 895           if (delt)
 896             {
 897               changed = true;
 898               tbitset_elt_remove (dst, j);
 899             }
 900           continue;
 901         }
 902
 903       if (!selt1)
 904         selt1 = &tbitset_zero_elts[0];
 905       if (!selt2)
 906         selt2 = &tbitset_zero_elts[0];
 907       if (!delt)
 908         delt = tbitset_elt_calloc ();
 909       else
 910         delts[j] = 0;
 911
 912       bitset_word *srcp1 = TBITSET_WORDS (selt1);
 913       bitset_word *srcp2 = TBITSET_WORDS (selt2);
 914       bitset_word *dstp = TBITSET_WORDS (delt);
 915       switch (op)
 916         {
 917         default:
 918           abort ();
 919
 920         case BITSET_OP_OR:
 921           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 922             {
 923               bitset_word tmp = *srcp1++ | *srcp2++;
 924
 925               if (*dstp != tmp)
 926                 {
 927                   changed = true;
 928                   *dstp = tmp;
 929                 }
 930             }
 931           break;
 932
 933         case BITSET_OP_AND:
 934           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 935             {
 936               bitset_word tmp = *srcp1++ & *srcp2++;
 937
 938               if (*dstp != tmp)
 939                 {
 940                   changed = true;
 941                   *dstp = tmp;
 942                 }
 943             }
 944           break;
 945
 946         case BITSET_OP_XOR:
 947           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 948             {
 949               bitset_word tmp = *srcp1++ ^ *srcp2++;
 950
 951               if (*dstp != tmp)
 952                 {
 953                   changed = true;
 954                   *dstp = tmp;
 955                 }
 956             }
 957           break;
 958
 959         case BITSET_OP_ANDN:
 960           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 961             {
 962               bitset_word tmp = *srcp1++ & ~(*srcp2++);
 963
 964               if (*dstp != tmp)
 965                 {
 966                   changed = true;
 967                   *dstp = tmp;
 968                 }
 969             }
 970           break;
 971         }
 972
 973       if (!tbitset_elt_zero_p (delt))
 974         tbitset_elt_add (dst, delt, j);
 975       else
 976         tbitset_elt_free (delt);
 977     }
 978
 979   /* If we have elements of DST left over, free them all.  */
 980   for (; j < dsize; j++)
 981     {
 982       changed = true;
 983
 984       tbitset_elt *delt = delts[j];
 985       if (delt)
 986         tbitset_elt_remove (dst, j);
 987     }
 988
 989   TBITSET_NONZERO_SET (dst);
 990   return changed;
 991 }
 992
 993
 994 static bool
 995 tbitset_and_cmp (bitset dst, bitset src1, bitset src2)
 996 {
 997   if (TBITSET_ZERO_P (src2))
 998     {
 999       tbitset_weed (dst);
1000       bool changed = TBITSET_ZERO_P (dst);
1001       tbitset_zero (dst);
1002       return changed;
1003     }
1004   else if (TBITSET_ZERO_P (src1))
1005     {
1006       tbitset_weed (dst);
1007       bool changed = TBITSET_ZERO_P (dst);
1008       tbitset_zero (dst);
1009       return changed;
1010     }
1011   else
1012     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1013 }
1014
1015
1016 static void
1017 tbitset_and (bitset dst, bitset src1, bitset src2)
1018 {
1019   tbitset_and_cmp (dst, src1, src2);
1020 }
1021
1022
1023 static bool
1024 tbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
1025 {
1026   if (TBITSET_ZERO_P (src2))
1027     return tbitset_copy_cmp (dst, src1);
1028   else if (TBITSET_ZERO_P (src1))
1029     {
1030       tbitset_weed (dst);
1031       bool changed = TBITSET_ZERO_P (dst);
1032       tbitset_zero (dst);
1033       return changed;
1034     }
1035   else
1036     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1037 }
1038
1039
1040 static void
1041 tbitset_andn (bitset dst, bitset src1, bitset src2)
1042 {
1043   tbitset_andn_cmp (dst, src1, src2);
1044 }
1045
1046
1047 static bool
1048 tbitset_or_cmp (bitset dst, bitset src1, bitset src2)
1049 {
1050   if (TBITSET_ZERO_P (src2))
1051     return tbitset_copy_cmp (dst, src1);
1052   else if (TBITSET_ZERO_P (src1))
1053     return tbitset_copy_cmp (dst, src2);
1054   else
1055     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1056 }
1057
1058
1059 static void
1060 tbitset_or (bitset dst, bitset src1, bitset src2)
1061 {
1062   tbitset_or_cmp (dst, src1, src2);
1063 }
1064
1065
1066 static bool
1067 tbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1068 {
1069   if (TBITSET_ZERO_P (src2))
1070     return tbitset_copy_cmp (dst, src1);
1071   else if (TBITSET_ZERO_P (src1))
1072     return tbitset_copy_cmp (dst, src2);
1073   else
1074     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1075 }
1076
1077
1078 static void
1079 tbitset_xor (bitset dst, bitset src1, bitset src2)
1080 {
1081   tbitset_xor_cmp (dst, src1, src2);
1082 }
1083
1084
1085 static void
1086 tbitset_copy (bitset dst, bitset src)
1087 {
1088   if (BITSET_COMPATIBLE_ (dst, src))
1089     tbitset_copy_ (dst, src);
1090   else
1091     bitset_copy_ (dst, src);
1092 }
1093
1094
1095 /* Vector of operations for linked-list bitsets.  */
1096 struct bitset_vtable tbitset_vtable = {
1097   tbitset_set,
1098   tbitset_reset,
1099   bitset_toggle_,
1100   tbitset_test,
1101   tbitset_resize,
1102   bitset_size_,
1103   bitset_count_,
1104   tbitset_empty_p,
1105   tbitset_ones,
1106   tbitset_zero,
1107   tbitset_copy,
1108   tbitset_disjoint_p,
1109   tbitset_equal_p,
1110   tbitset_not,
1111   tbitset_subset_p,
1112   tbitset_and,
1113   tbitset_and_cmp,
1114   tbitset_andn,
1115   tbitset_andn_cmp,
1116   tbitset_or,
1117   tbitset_or_cmp,
1118   tbitset_xor,
1119   tbitset_xor_cmp,
1120   bitset_and_or_,
1121   bitset_and_or_cmp_,
1122   bitset_andn_or_,
1123   bitset_andn_or_cmp_,
1124   bitset_or_and_,
1125   bitset_or_and_cmp_,
1126   tbitset_list,
1127   tbitset_list_reverse,
1128   tbitset_free,
1129   BITSET_TABLE
1130 };
1131
1132
1133 /* Return size of initial structure.  */
1134 size_t
1135 tbitset_bytes (bitset_bindex n_bits MAYBE_UNUSED)
1136 {
1137   return sizeof (struct tbitset_struct);
1138 }
1139
1140
1141 /* Initialize a bitset.  */
1142
1143 bitset
1144 tbitset_init (bitset bset, bitset_bindex n_bits)
1145 {
1146   bset->b.vtable = &tbitset_vtable;
1147
1148   bset->b.csize = TBITSET_ELT_WORDS;
1149
1150   TBITSET_ZERO_SET (bset);
1151
1152   TBITSET_ASIZE (bset) = 0;
1153   TBITSET_ELTS (bset) = 0;
1154   tbitset_resize (bset, n_bits);
1155
1156   return bset;
1157 }
1158
1159
1160 void
1161 tbitset_release_memory (void)
1162 {
1163   tbitset_free_list = 0;
1164   if (tbitset_obstack_init)
1165     {
1166       tbitset_obstack_init = false;
1167       obstack_free (&tbitset_obstack, NULL);
1168     }
1169 }