lib/ebitset.c

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