lib/ebitset.c

   1 /* Functions to support expandable bitsets.
   2    Copyright (C) 2002 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
  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    some large number 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) (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 /* Head of ebitset linked list.  */
  72 typedef struct ebitset_struct
  73 {
  74   unsigned int size;            /* Number of elements.  */
  75   ebitset_elts *elts;           /* Expanding array of pointers to elements.  */
  76 }
  77 *ebitset;
  78
  79
  80 /* Number of elements to initially allocate.  */
  81
  82 #ifndef EBITSET_INITIAL_SIZE
  83 #define EBITSET_INITIAL_SIZE 2
  84 #endif
  85
  86 /* Minimum number of elements to grow table.  */
  87
  88 #ifndef EBITSET_GROW_SIZE
  89 #define EBITSET_GROW_SIZE 4
  90 #endif
  91
  92 struct bitset_struct
  93 {
  94   struct bbitset_struct b;
  95   struct ebitset_struct e;
  96 };
  97
  98 enum ebitset_find_mode
  99   { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
 100
 101 static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits.  */
 102
 103 /* Obstack to allocate bitset elements from.  */
 104 static struct obstack ebitset_obstack;
 105 static int ebitset_obstack_init = 0;
 106 static ebitset_elt *ebitset_free_list;  /* Free list of bitset elements.  */
 107
 108 static void ebitset_elts_grow PARAMS ((bitset, unsigned int));
 109 static ebitset_elt *ebitset_elt_alloc PARAMS ((void));
 110 static ebitset_elt *ebitset_elt_calloc PARAMS ((void));
 111 static void ebitset_elt_add PARAMS ((bitset, ebitset_elt *, unsigned int));
 112 static void ebitset_elt_remove PARAMS ((bitset, unsigned int));
 113 static void ebitset_elt_free PARAMS ((ebitset_elt *));
 114 static ebitset_elt *ebitset_elt_find PARAMS ((bitset, bitset_windex,
 115                                               enum ebitset_find_mode));
 116 static ebitset_elt *ebitset_elt_last PARAMS ((bitset));
 117 static int ebitset_elt_zero_p PARAMS ((ebitset_elt *));
 118
 119 static int ebitset_weed PARAMS ((bitset));
 120 static void ebitset_zero PARAMS ((bitset));
 121 static int ebitset_equal_p PARAMS ((bitset, bitset));
 122 static void ebitset_copy PARAMS ((bitset, bitset));
 123 static int ebitset_copy_compare PARAMS ((bitset, bitset));
 124 static void ebitset_set PARAMS ((bitset, bitset_bindex));
 125 static void ebitset_reset PARAMS ((bitset, bitset_bindex));
 126 static int ebitset_test PARAMS ((bitset, bitset_bindex));
 127 static int ebitset_size PARAMS ((bitset));
 128 static int ebitset_op1 PARAMS ((bitset, enum bitset_ops));
 129 static int ebitset_op2 PARAMS ((bitset, bitset, enum bitset_ops));
 130 static int ebitset_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
 131 static int ebitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
 132                                  bitset_bindex *));
 133 static int ebitset_reverse_list
 134 PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
 135 static void ebitset_free PARAMS ((bitset));
 136
 137 #define EBITSET_ELTS(BSET) ((BSET)->e.elts)
 138 #define EBITSET_SIZE(BSET) ((BSET)->e.size)
 139
 140 #define EBITSET_NEXT(ELT) ((ELT)->u.next)
 141 #define EBITSET_WORDS(ELT) ((ELT)->u.words)
 142
 143 /* Disable bitset cache and mark BSET as being zero.  */
 144 #define EBITSET_OP_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_INDEX_MAX, \
 145         (BSET)->b.cdata = 0)
 146
 147 #define EBITSET_CACHE_DISABLE(BSET)  ((BSET)->b.cindex = BITSET_INDEX_MAX)
 148
 149 /* Disable bitset cache and mark BSET as being possibly non-zero.  */
 150 #define EBITSET_NONZERO_SET(BSET) \
 151  (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
 152
 153 /* A conservative estimate of whether the bitset is zero.
 154    This is non-zero only if we know for sure that the bitset is zero.  */
 155 #define EBITSET_OP_ZERO_P(BSET) ((BSET)->b.cdata == 0)
 156
 157 /* Enable cache to point to element with table index EINDEX.
 158    The element must exist.  */
 159 #define EBITSET_CACHE_SET(BSET, EINDEX) \
 160  ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
 161   (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
 162
 163
 164 /* Grow the expandable table for BSET by SIZE elements.  */
 165 static void
 166 ebitset_elts_grow (bset, size)
 167      bitset bset;
 168      unsigned int size;
 169 {
 170   unsigned int oldsize;
 171   unsigned int newsize;
 172
 173   oldsize = EBITSET_SIZE (bset);
 174   newsize = oldsize + size;
 175
 176   EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
 177                                   newsize * sizeof (ebitset_elt *));
 178   EBITSET_SIZE (bset) = newsize;
 179
 180   memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *));
 181 }
 182
 183
 184 /* Allocate a ebitset element.  The bits are not cleared.  */
 185 static inline ebitset_elt *
 186 ebitset_elt_alloc ()
 187 {
 188   ebitset_elt *elt;
 189
 190   if (ebitset_free_list != 0)
 191     {
 192       elt = ebitset_free_list;
 193       ebitset_free_list = EBITSET_NEXT (elt);
 194     }
 195   else
 196     {
 197       if (!ebitset_obstack_init)
 198         {
 199           ebitset_obstack_init = 1;
 200
 201           /* Let particular systems override the size of a chunk.  */
 202
 203 #ifndef OBSTACK_CHUNK_SIZE
 204 #define OBSTACK_CHUNK_SIZE 0
 205 #endif
 206
 207           /* Let them override the alloc and free routines too.  */
 208
 209 #ifndef OBSTACK_CHUNK_ALLOC
 210 #define OBSTACK_CHUNK_ALLOC xmalloc
 211 #endif
 212
 213 #ifndef OBSTACK_CHUNK_FREE
 214 #define OBSTACK_CHUNK_FREE free
 215 #endif
 216
 217 #if !defined(__GNUC__) || (__GNUC__ < 2)
 218 #define __alignof__(type) 0
 219 #endif
 220
 221           obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
 222                                       __alignof__ (ebitset_elt),
 223                                       (void *(*)PARAMS ((long)))
 224                                       OBSTACK_CHUNK_ALLOC,
 225                                       (void (*)PARAMS ((void *)))
 226                                       OBSTACK_CHUNK_FREE);
 227         }
 228
 229       /* Perhaps we should add a number of new elements to the free
 230          list.  */
 231       elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,
 232                                            sizeof (ebitset_elt));
 233     }
 234
 235   return elt;
 236 }
 237
 238
 239 /* Allocate a ebitset element.  The bits are cleared.  */
 240 static inline ebitset_elt *
 241 ebitset_elt_calloc ()
 242 {
 243   ebitset_elt *elt;
 244
 245   elt = ebitset_elt_alloc ();
 246   memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt)));
 247   return elt;
 248 }
 249
 250
 251 static inline void
 252 ebitset_elt_free (elt)
 253      ebitset_elt *elt;
 254 {
 255   EBITSET_NEXT (elt) = ebitset_free_list;
 256   ebitset_free_list = elt;
 257 }
 258
 259
 260 /* Remove element with index EINDEX from bitset BSET.  */
 261 static inline void
 262 ebitset_elt_remove (bset, eindex)
 263      bitset bset;
 264      unsigned int eindex;
 265 {
 266   ebitset_elts *elts;
 267   ebitset_elt *elt;
 268
 269   elts = EBITSET_ELTS (bset);
 270
 271   elt = elts[eindex];
 272
 273   elts[eindex] = 0;
 274   ebitset_elt_free (elt);
 275 }
 276
 277
 278 /* Add ELT into elts at index EINDEX of bitset BSET.  */
 279 static inline void
 280 ebitset_elt_add (bset, elt, eindex)
 281      bitset bset;
 282      ebitset_elt *elt;
 283      unsigned int eindex;
 284 {
 285   ebitset_elts *elts;
 286
 287   elts = EBITSET_ELTS (bset);
 288   /* Assume that the elts entry not allocated.  */
 289   elts[eindex] = elt;
 290 }
 291
 292
 293 /* Return nonzero if all bits in an element are zero.  */
 294 static inline int
 295 ebitset_elt_zero_p (elt)
 296      ebitset_elt *elt;
 297 {
 298   int i;
 299
 300   for (i = 0; i < EBITSET_ELT_WORDS; i++)
 301     if (EBITSET_WORDS (elt)[i])
 302       return 0;
 303
 304   return 1;
 305 }
 306
 307
 308 static ebitset_elt *
 309 ebitset_elt_find (bset, windex, mode)
 310      bitset bset;
 311      bitset_windex windex;
 312      enum ebitset_find_mode mode;
 313 {
 314   ebitset_elt *elt;
 315   bitset_windex size;
 316   unsigned int eindex;
 317   ebitset_elts *elts;
 318
 319   eindex = windex / EBITSET_ELT_WORDS;
 320
 321   elts = EBITSET_ELTS (bset);
 322   size = EBITSET_SIZE (bset);
 323
 324   if (eindex < size)
 325     {
 326       if ((elt = elts[eindex]))
 327         {
 328           if (EBITSET_WORDS (elt) == bset->b.cdata)
 329             return elt;
 330
 331           EBITSET_CACHE_SET (bset, eindex);
 332           return elt;
 333         }
 334     }
 335
 336   /* The element could not be found.  */
 337
 338   switch (mode)
 339     {
 340     case EBITSET_FIND:
 341       return 0;
 342
 343     case EBITSET_CREATE:
 344       if (eindex >= size)
 345         {
 346           unsigned int extra;
 347
 348           extra = eindex - size + 1;
 349
 350           /* We need to expand the table by EXTRA elements.  It may be
 351              better with large bitsets to grow the number of
 352              elements by some fraction of the current size otherwise
 353              we can spend a lot of time slowly increasing the size of the
 354              bitset.  */
 355           if (extra < EBITSET_GROW_SIZE)
 356             extra = EBITSET_GROW_SIZE;
 357
 358           ebitset_elts_grow (bset, extra);
 359         }
 360
 361       /* Create a new element.  */
 362       elt = ebitset_elt_calloc ();
 363       ebitset_elt_add (bset, elt, eindex);
 364       EBITSET_CACHE_SET (bset, eindex);
 365       return elt;
 366
 367     case EBITSET_SUBST:
 368       return &ebitset_zero_elts[0];
 369
 370     default:
 371       abort ();
 372     }
 373 }
 374
 375
 376 static inline ebitset_elt *
 377 ebitset_elt_last (bset)
 378      bitset bset;
 379 {
 380   ebitset_elts *elts;
 381
 382   elts = EBITSET_ELTS (bset);
 383
 384   /* Assume that have at least one element in elts.  */
 385   return elts[EBITSET_SIZE (bset) - 1];
 386 }
 387
 388
 389 /* Weed out the zero elements from the elts.  */
 390 static inline int
 391 ebitset_weed (bset)
 392      bitset bset;
 393 {
 394   ebitset_elts *elts;
 395   bitset_windex j;
 396   int count;
 397
 398   if (EBITSET_OP_ZERO_P (bset))
 399     return 0;
 400
 401   elts = EBITSET_ELTS (bset);
 402   count = 0;
 403   for (j = 0; j < EBITSET_SIZE (bset); j++)
 404     {
 405       ebitset_elt *elt = elts[j];
 406
 407       if (elt)
 408         {
 409           if (elt && ebitset_elt_zero_p (elt))
 410             {
 411               ebitset_elt_remove (bset, j);
 412               count++;
 413             }
 414         }
 415       else
 416         count++;
 417     }
 418
 419   count = j - count;
 420   if (!count)
 421     {
 422       /* All the bits are zero.  We could shrink the elts.
 423          For now just mark BSET as known to be zero.  */
 424       EBITSET_OP_ZERO_SET (bset);
 425     }
 426   else
 427     EBITSET_NONZERO_SET (bset);
 428
 429   return count;
 430 }
 431
 432
 433 /* Set all bits in the bitset to zero.  */
 434 static inline void
 435 ebitset_zero (bset)
 436      bitset bset;
 437 {
 438   ebitset_elts *elts;
 439   bitset_windex j;
 440
 441   if (EBITSET_OP_ZERO_P (bset))
 442     return;
 443
 444   elts = EBITSET_ELTS (bset);
 445   for (j = 0; j < EBITSET_SIZE (bset); j++)
 446     {
 447       ebitset_elt *elt = elts[j];
 448
 449       if (elt)
 450         ebitset_elt_remove (bset, j);
 451     }
 452
 453   /* All the bits are zero.  We could shrink the elts.
 454      For now just mark BSET as known to be zero.  */
 455   EBITSET_OP_ZERO_SET (bset);
 456 }
 457
 458
 459 static inline int
 460 ebitset_equal_p (dst, src)
 461      bitset dst;
 462      bitset src;
 463 {
 464   ebitset_elts *selts;
 465   ebitset_elts *delts;
 466   bitset_windex j;
 467
 468   if (src == dst)
 469     return 1;
 470
 471   ebitset_weed (dst);
 472   ebitset_weed (src);
 473
 474   if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
 475     return 0;
 476
 477   selts = EBITSET_ELTS (src);
 478   delts = EBITSET_ELTS (dst);
 479
 480   for (j = 0; j < EBITSET_SIZE (src); j++)
 481     {
 482       unsigned int i;
 483       ebitset_elt *selt = selts[j];
 484       ebitset_elt *delt = delts[j];
 485
 486       if (!selt && !delt)
 487         continue;
 488       if ((selt && !delt) || (!selt && delt))
 489         return 0;
 490
 491       for (i = 0; i < EBITSET_ELT_WORDS; i++)
 492         if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
 493           return 0;
 494     }
 495   return 1;
 496 }
 497
 498
 499 /* Copy bits from bitset SRC to bitset DST.  */
 500 static inline void
 501 ebitset_copy (dst, src)
 502      bitset dst;
 503      bitset src;
 504 {
 505   ebitset_elts *selts;
 506   ebitset_elts *delts;
 507   bitset_windex j;
 508
 509   if (src == dst)
 510     return;
 511
 512   ebitset_zero (dst);
 513
 514   if (EBITSET_SIZE (dst) < EBITSET_SIZE (src))
 515     ebitset_elts_grow (dst, EBITSET_SIZE (src) - EBITSET_SIZE (dst));
 516
 517   selts = EBITSET_ELTS (src);
 518   delts = EBITSET_ELTS (dst);
 519   for (j = 0; j < EBITSET_SIZE (src); j++)
 520     {
 521       ebitset_elt *selt = selts[j];
 522
 523       if (selt)
 524         {
 525           ebitset_elt *tmp;
 526
 527           tmp = ebitset_elt_alloc ();
 528           delts[j] = tmp;
 529           memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
 530                   sizeof (EBITSET_WORDS (selt)));
 531         }
 532     }
 533   EBITSET_NONZERO_SET (dst);
 534 }
 535
 536
 537 /* Copy bits from bitset SRC to bitset DST.  Return non-zero if
 538    bitsets different.  */
 539 static inline int
 540 ebitset_copy_compare (dst, src)
 541      bitset dst;
 542      bitset src;
 543 {
 544   if (src == dst)
 545     return 0;
 546
 547   if (EBITSET_OP_ZERO_P (dst))
 548     {
 549       ebitset_copy (dst, src);
 550       return !EBITSET_OP_ZERO_P (src);
 551     }
 552
 553   if (ebitset_equal_p (dst, src))
 554     return 0;
 555
 556   ebitset_copy (dst, src);
 557   return 1;
 558 }
 559
 560
 561 /* Return size in bits of bitset SRC.  */
 562 static int
 563 ebitset_size (src)
 564      bitset src;
 565 {
 566   /* Return current size of bitset in bits.  */
 567   return EBITSET_SIZE (src) * EBITSET_ELT_BITS;
 568 }
 569
 570
 571 /* Set bit BITNO in bitset DST.  */
 572 static void
 573 ebitset_set (dst, bitno)
 574      bitset dst;
 575      bitset_bindex bitno;
 576 {
 577   bitset_windex windex = bitno / BITSET_WORD_BITS;
 578
 579   ebitset_elt_find (dst, windex, EBITSET_CREATE);
 580
 581   dst->b.cdata[windex - dst->b.cindex] |= (1 << (bitno % BITSET_WORD_BITS));
 582 }
 583
 584
 585 /* Reset bit BITNO in bitset DST.  */
 586 static void
 587 ebitset_reset (dst, bitno)
 588      bitset dst;
 589      bitset_bindex bitno;
 590 {
 591   bitset_windex windex = bitno / BITSET_WORD_BITS;
 592
 593   if (!ebitset_elt_find (dst, windex, EBITSET_FIND))
 594     return;
 595
 596   dst->b.cdata[windex - dst->b.cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
 597
 598   /* If all the data is zero, perhaps we should remove it now...
 599      However, there is a good chance that the element will be needed
 600      again soon.  */
 601 }
 602
 603
 604 /* Test bit BITNO in bitset SRC.  */
 605 static int
 606 ebitset_test (src, bitno)
 607      bitset src;
 608      bitset_bindex bitno;
 609 {
 610   bitset_windex windex = bitno / BITSET_WORD_BITS;
 611
 612   if (!ebitset_elt_find (src, windex, EBITSET_FIND))
 613     return 0;
 614
 615   return (src->b.
 616           cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
 617 }
 618
 619
 620 static void
 621 ebitset_free (bset)
 622      bitset bset;
 623 {
 624   ebitset_zero (bset);
 625   free (EBITSET_ELTS (bset));
 626 }
 627
 628
 629 /* Find list of up to NUM bits set in BSET starting from and including
 630  *NEXT and store in array LIST.  Return with actual number of bits
 631  found and with *NEXT indicating where search stopped.  */
 632 static int
 633 ebitset_reverse_list (bset, list, num, next)
 634      bitset bset;
 635      bitset_bindex *list;
 636      bitset_bindex num;
 637      bitset_bindex *next;
 638 {
 639   bitset_bindex n_bits;
 640   bitset_bindex bitno;
 641   bitset_bindex rbitno;
 642   unsigned int bcount;
 643   bitset_bindex boffset;
 644   bitset_windex windex;
 645   unsigned int eindex;
 646   bitset_windex woffset;
 647   bitset_bindex count;
 648   bitset_windex size;
 649   bitset_word word;
 650   ebitset_elts *elts;
 651
 652   if (EBITSET_OP_ZERO_P (bset))
 653     return 0;
 654
 655   size = EBITSET_SIZE (bset);
 656   n_bits = size * EBITSET_ELT_BITS;
 657   rbitno = *next;
 658
 659   if (rbitno >= n_bits)
 660     return 0;
 661
 662   elts = EBITSET_ELTS (bset);
 663
 664   bitno = n_bits - (rbitno + 1);
 665
 666   windex = bitno / BITSET_WORD_BITS;
 667   eindex = bitno / EBITSET_ELT_BITS;
 668   woffset = windex - eindex * EBITSET_ELT_WORDS;
 669
 670   /* If num is 1, we could speed things up with a binary search
 671      of the word of interest.  */
 672
 673   count = 0;
 674   bcount = bitno % BITSET_WORD_BITS;
 675   boffset = windex * BITSET_WORD_BITS;
 676
 677   for (; eindex != ~0U;
 678        boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS, eindex--)
 679     {
 680       ebitset_elt *elt;
 681       bitset_word *srcp;
 682
 683       elt = elts[eindex];
 684       if (!elt)
 685         continue;
 686
 687       srcp = EBITSET_WORDS (elt);
 688
 689       for (; woffset != ~0U; woffset--, boffset -= BITSET_WORD_BITS,
 690              bcount = BITSET_WORD_BITS - 1)
 691         {
 692           word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
 693
 694           for (; word; bcount--)
 695             {
 696               if (word & BITSET_MSB)
 697                 {
 698                   list[count++] = boffset + bcount;
 699                   if (count >= num)
 700                     {
 701                       *next = n_bits - (boffset + bcount);
 702                       return count;
 703                     }
 704                 }
 705               word <<= 1;
 706             }
 707         }
 708
 709       woffset = EBITSET_ELT_WORDS;
 710     }
 711
 712   *next = n_bits - (boffset + 1);
 713   return count;
 714 }
 715
 716
 717 /* Find list of up to NUM bits set in BSET starting from and including
 718  *NEXT and store in array LIST.  Return with actual number of bits
 719  found and with *NEXT indicating where search stopped.  */
 720 static int
 721 ebitset_list (bset, list, num, next)
 722      bitset bset;
 723      bitset_bindex *list;
 724      bitset_bindex num;
 725      bitset_bindex *next;
 726 {
 727   bitset_bindex bitno;
 728   bitset_windex windex;
 729   unsigned int eindex;
 730   bitset_bindex count;
 731   bitset_windex size;
 732   ebitset_elt *elt;
 733   bitset_word word;
 734   ebitset_elts *elts;
 735
 736   if (EBITSET_OP_ZERO_P (bset))
 737     return 0;
 738
 739   bitno = *next;
 740   count = 0;
 741
 742   elts = EBITSET_ELTS (bset);
 743   size = EBITSET_SIZE (bset);
 744   eindex = bitno / EBITSET_ELT_BITS;
 745
 746   if (bitno % EBITSET_ELT_BITS)
 747     {
 748       /* We need to start within an element.  This is not very common.  */
 749
 750       elt = elts[eindex];
 751       if (elt)
 752         {
 753           bitset_windex woffset;
 754           bitset_word *srcp = EBITSET_WORDS (elt);
 755
 756           windex = bitno / BITSET_WORD_BITS;
 757           woffset = eindex / EBITSET_ELT_WORDS;
 758
 759           for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
 760             {
 761               word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
 762
 763               for (; word; bitno++)
 764                 {
 765                   if (word & 1)
 766                     {
 767                       list[count++] = bitno;
 768                       if (count >= num)
 769                         {
 770                           *next = bitno + 1;
 771                           return count;
 772                         }
 773                     }
 774                   word >>= 1;
 775                 }
 776               bitno = (windex + 1) * BITSET_WORD_BITS;
 777             }
 778         }
 779
 780       /* Skip to next element.  */
 781       eindex++;
 782     }
 783
 784   /* If num is 1, we could speed things up with a binary search
 785      of the word of interest.  */
 786
 787   for (; eindex < size; eindex++)
 788     {
 789       int i;
 790       bitset_word *srcp;
 791
 792       elt = elts[eindex];
 793       if (!elt)
 794         continue;
 795
 796       srcp = EBITSET_WORDS (elt);
 797       windex = eindex * EBITSET_ELT_WORDS;
 798
 799       if ((count + EBITSET_ELT_BITS) < num)
 800         {
 801           /* The coast is clear, plant boot!  */
 802
 803           for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
 804             {
 805               bitno = windex * BITSET_WORD_BITS;
 806
 807               word = srcp[i];
 808               if (word)
 809                 {
 810                   if (!(word & 0xffff))
 811                     {
 812                       word >>= 16;
 813                       bitno += 16;
 814                     }
 815                   if (!(word & 0xff))
 816                     {
 817                       word >>= 8;
 818                       bitno += 8;
 819                     }
 820                   for (; word; bitno++)
 821                     {
 822                       if (word & 1)
 823                         list[count++] = bitno;
 824                       word >>= 1;
 825                     }
 826                 }
 827             }
 828         }
 829       else
 830         {
 831           /* Tread more carefully since we need to check
 832              if array overflows.  */
 833
 834           for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
 835             {
 836               bitno = windex * BITSET_WORD_BITS;
 837
 838               for (word = srcp[i]; word; bitno++)
 839                 {
 840                   if (word & 1)
 841                     {
 842                       list[count++] = bitno;
 843                       if (count >= num)
 844                         {
 845                           *next = bitno + 1;
 846                           return count;
 847                         }
 848                     }
 849                   word >>= 1;
 850                 }
 851             }
 852         }
 853     }
 854
 855   *next = bitno;
 856   return count;
 857 }
 858
 859
 860 static int
 861 ebitset_op1 (dst, op)
 862      bitset dst;
 863      enum bitset_ops op;
 864 {
 865   bitset_windex j;
 866   ebitset_elt *elt;
 867
 868   switch (op)
 869     {
 870     case BITSET_OP_ZERO:
 871       ebitset_zero (dst);
 872       return 1;
 873
 874     case BITSET_OP_ONES:
 875       for (j = 0; j < EBITSET_SIZE (dst); j++)
 876         {
 877           /* Create new elements if they cannot be found.  Perhaps
 878              we should just add pointers to a ones element.  */
 879           elt =
 880             ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
 881           memset (EBITSET_WORDS (elt), ~0, sizeof (EBITSET_WORDS (elt)));
 882         }
 883       break;
 884
 885     case BITSET_OP_EMPTY_P:
 886       return !ebitset_weed (dst);
 887
 888     default:
 889       abort ();
 890     }
 891
 892   EBITSET_NONZERO_SET (dst);
 893   return 1;
 894 }
 895
 896
 897 static int
 898 ebitset_op2 (dst, src, op)
 899      bitset dst;
 900      bitset src;
 901      enum bitset_ops op;
 902 {
 903   ebitset_elt *selt;
 904   ebitset_elt *delt;
 905   unsigned int i;
 906   bitset_windex j;
 907
 908   switch (op)
 909     {
 910     case BITSET_OP_COPY:
 911       ebitset_copy (dst, src);
 912       break;
 913
 914     case BITSET_OP_NOT:
 915       for (j = 0; j < EBITSET_SIZE (src); j++)
 916         {
 917           /* Create new elements for dst if they cannot be found
 918              or substitute zero elements if src elements not found.  */
 919           selt =
 920             ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
 921           delt =
 922             ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
 923
 924           for (i = 0; i < EBITSET_ELT_WORDS; i++)
 925             EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
 926         }
 927       break;
 928
 929       /* Return 1 if DST == SRC.  */
 930     case BITSET_OP_EQUAL_P:
 931       return ebitset_equal_p (dst, src);
 932
 933       /* Return 1 if DST == DST | SRC.  */
 934     case BITSET_OP_SUBSET_P:
 935       {
 936         ebitset_elts *selts;
 937         ebitset_elts *delts;
 938         bitset_windex ssize;
 939         bitset_windex dsize;
 940
 941         selts = EBITSET_ELTS (src);
 942         delts = EBITSET_ELTS (dst);
 943
 944         ssize = EBITSET_SIZE (src);
 945         dsize = EBITSET_SIZE (dst);
 946
 947         for (j = 0; j < ssize; j++)
 948           {
 949             selt = j < ssize ? selts[j] : 0;
 950             delt = j < dsize ? delts[j] : 0;
 951
 952             if (!selt && !delt)
 953               continue;
 954
 955             if (!selt)
 956               selt = &ebitset_zero_elts[0];
 957             if (!delt)
 958               delt = &ebitset_zero_elts[0];
 959
 960             for (i = 0; i < EBITSET_ELT_WORDS; i++)
 961               if (EBITSET_WORDS (delt)[i]
 962                   != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
 963                 return 0;
 964           }
 965         return 1;
 966       }
 967       break;
 968
 969       /* Return 1 if DST & SRC == 0.  */
 970     case BITSET_OP_DISJOINT_P:
 971       {
 972         ebitset_elts *selts;
 973         ebitset_elts *delts;
 974         bitset_windex ssize;
 975         bitset_windex dsize;
 976
 977         selts = EBITSET_ELTS (src);
 978         delts = EBITSET_ELTS (dst);
 979
 980         ssize = EBITSET_SIZE (src);
 981         dsize = EBITSET_SIZE (dst);
 982
 983         for (j = 0; j < ssize; j++)
 984           {
 985             selt = j < ssize ? selts[j] : 0;
 986             delt = j < dsize ? delts[j] : 0;
 987
 988             if (!selt || !delt)
 989               continue;
 990
 991             for (i = 0; i < EBITSET_ELT_WORDS; i++)
 992               if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
 993                 return 0;
 994           }
 995         return 1;
 996       }
 997       break;
 998
 999     default:
1000       abort ();
1001     }
1002
1003   EBITSET_NONZERO_SET (dst);
1004   return 1;
1005 }
1006
1007
1008 static int
1009 ebitset_op3 (dst, src1, src2, op)
1010      bitset dst;
1011      bitset src1;
1012      bitset src2;
1013      enum bitset_ops op;
1014 {
1015   bitset_windex ssize1;
1016   bitset_windex ssize2;
1017   bitset_windex dsize;
1018   bitset_windex size;
1019   ebitset_elts *selts1;
1020   ebitset_elts *selts2;
1021   ebitset_elts *delts;
1022   bitset_word *srcp1;
1023   bitset_word *srcp2;
1024   bitset_word *dstp;
1025   int changed = 0;
1026   unsigned int i;
1027   bitset_windex j;
1028
1029   /* Fast track common, simple cases.  */
1030   if (EBITSET_OP_ZERO_P (src2))
1031     {
1032       if (op == BITSET_OP_AND)
1033         {
1034           ebitset_weed (dst);
1035           changed = EBITSET_OP_ZERO_P (dst);
1036           ebitset_zero (dst);
1037           return changed;
1038         }
1039       else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR
1040                || op == BITSET_OP_XOR)
1041         {
1042           return ebitset_copy_compare (dst, src1);
1043         }
1044     }
1045   else if (EBITSET_OP_ZERO_P (src1))
1046     {
1047       if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
1048         {
1049           ebitset_weed (dst);
1050           changed = EBITSET_OP_ZERO_P (dst);
1051           ebitset_zero (dst);
1052           return changed;
1053         }
1054       else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
1055         {
1056           return ebitset_copy_compare (dst, src2);
1057         }
1058     }
1059
1060   ssize1 = EBITSET_SIZE (src1);
1061   ssize2 = EBITSET_SIZE (src2);
1062   dsize = EBITSET_SIZE (dst);
1063   size = ssize1;
1064   if (size < ssize2)
1065     size = ssize2;
1066
1067   if (size > dsize)
1068     ebitset_elts_grow (dst, size - dsize);
1069
1070   selts1 = EBITSET_ELTS (src1);
1071   selts2 = EBITSET_ELTS (src2);
1072   delts = EBITSET_ELTS (dst);
1073
1074   for (j = 0; j < size; j++)
1075     {
1076       ebitset_elt *selt1;
1077       ebitset_elt *selt2;
1078       ebitset_elt *delt;
1079
1080       selt1 = j < ssize1 ? selts1[j] : 0;
1081       selt2 = j < ssize2 ? selts2[j] : 0;
1082       delt = j < dsize ? delts[j] : 0;
1083
1084       if (!selt1 && !selt2)
1085         {
1086           if (delt)
1087             {
1088               changed = 1;
1089               ebitset_elt_remove (dst, j);
1090             }
1091           continue;
1092         }
1093
1094       if (!selt1)
1095         selt1 = &ebitset_zero_elts[0];
1096       if (!selt2)
1097         selt2 = &ebitset_zero_elts[0];
1098       if (!delt)
1099         delt = ebitset_elt_calloc ();
1100       else
1101         delts[j] = 0;
1102
1103       srcp1 = EBITSET_WORDS (selt1);
1104       srcp2 = EBITSET_WORDS (selt2);
1105       dstp = EBITSET_WORDS (delt);
1106       switch (op)
1107         {
1108         case BITSET_OP_OR:
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 = 1;
1116                   *dstp = tmp;
1117                 }
1118             }
1119           break;
1120
1121         case BITSET_OP_AND:
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 = 1;
1129                   *dstp = tmp;
1130                 }
1131             }
1132           break;
1133
1134         case BITSET_OP_XOR:
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 = 1;
1142                   *dstp = tmp;
1143                 }
1144             }
1145           break;
1146
1147         case BITSET_OP_ANDN:
1148           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1149             {
1150               bitset_word tmp = *srcp1++ & ~(*srcp2++);
1151
1152               if (*dstp != tmp)
1153                 {
1154                   changed = 1;
1155                   *dstp = tmp;
1156                 }
1157             }
1158           break;
1159
1160         default:
1161           abort ();
1162         }
1163
1164       if (!ebitset_elt_zero_p (delt))
1165         {
1166           ebitset_elt_add (dst, delt, j);
1167         }
1168       else
1169         {
1170           ebitset_elt_free (delt);
1171         }
1172     }
1173
1174   /* If we have elements of DST left over, free them all.  */
1175   for (; j < dsize; j++)
1176     {
1177       ebitset_elt *delt;
1178
1179       changed = 1;
1180
1181       delt = delts[j];
1182
1183       if (delt)
1184         ebitset_elt_remove (dst, j);
1185     }
1186
1187   EBITSET_NONZERO_SET (dst);
1188   return changed;
1189 }
1190
1191
1192 /* Vector of operations for linked-list bitsets.  */
1193 struct bitset_ops_struct ebitset_ops = {
1194   ebitset_set,
1195   ebitset_reset,
1196   ebitset_test,
1197   ebitset_size,
1198   ebitset_op1,
1199   ebitset_op2,
1200   ebitset_op3,
1201   bitset_op4,
1202   ebitset_list,
1203   ebitset_reverse_list,
1204   ebitset_free,
1205   BITSET_TABLE
1206 };
1207
1208
1209 /* Return size of initial structure.  */
1210 int
1211 ebitset_bytes (n_bits)
1212      bitset_bindex n_bits ATTRIBUTE_UNUSED;
1213 {
1214   return sizeof (struct bitset_struct);
1215 }
1216
1217
1218 /* Initialize a bitset.  */
1219
1220 bitset
1221 ebitset_init (bset, n_bits)
1222      bitset bset;
1223      bitset_bindex n_bits;
1224 {
1225   unsigned int size;
1226
1227   bset->b.ops = &ebitset_ops;
1228
1229   bset->b.csize = EBITSET_ELT_WORDS;
1230
1231   EBITSET_OP_ZERO_SET (bset);
1232
1233   size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
1234     : EBITSET_INITIAL_SIZE;
1235
1236   EBITSET_SIZE (bset) = 0;
1237   EBITSET_ELTS (bset) = 0;
1238   ebitset_elts_grow (bset, size);
1239
1240   return bset;
1241 }
1242
1243
1244 void
1245 ebitset_release_memory ()
1246 {
1247   ebitset_free_list = 0;
1248   if (ebitset_obstack_init)
1249     {
1250       ebitset_obstack_init = 0;
1251       obstack_free (&ebitset_obstack, NULL);
1252     }
1253 }