lib/ebitset.c

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