lib/ebitset.c

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