lib/ebitset.c

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