lib/ebitset.c

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