lib/ebitset.c

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