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] |=
 582     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
 583 }
 584
 585
 586 /* Reset bit BITNO in bitset DST.  */
 587 static void
 588 ebitset_reset (dst, bitno)
 589      bitset dst;
 590      bitset_bindex bitno;
 591 {
 592   bitset_windex windex = bitno / BITSET_WORD_BITS;
 593
 594   if (!ebitset_elt_find (dst, windex, EBITSET_FIND))
 595     return;
 596
 597   dst->b.cdata[windex - dst->b.cindex] &=
 598     ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 599
 600   /* If all the data is zero, perhaps we should remove it now...
 601      However, there is a good chance that the element will be needed
 602      again soon.  */
 603 }
 604
 605
 606 /* Test bit BITNO in bitset SRC.  */
 607 static int
 608 ebitset_test (src, bitno)
 609      bitset src;
 610      bitset_bindex bitno;
 611 {
 612   bitset_windex windex = bitno / BITSET_WORD_BITS;
 613
 614   if (!ebitset_elt_find (src, windex, EBITSET_FIND))
 615     return 0;
 616
 617   return (src->b.
 618           cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
 619 }
 620
 621
 622 static void
 623 ebitset_free (bset)
 624      bitset bset;
 625 {
 626   ebitset_zero (bset);
 627   free (EBITSET_ELTS (bset));
 628 }
 629
 630
 631 /* Find list of up to NUM bits set in BSET starting from and including
 632  *NEXT and store in array LIST.  Return with actual number of bits
 633  found and with *NEXT indicating where search stopped.  */
 634 static int
 635 ebitset_reverse_list (bset, list, num, next)
 636      bitset bset;
 637      bitset_bindex *list;
 638      bitset_bindex num;
 639      bitset_bindex *next;
 640 {
 641   bitset_bindex n_bits;
 642   bitset_bindex bitno;
 643   bitset_bindex rbitno;
 644   unsigned int bcount;
 645   bitset_bindex boffset;
 646   bitset_windex windex;
 647   unsigned int eindex;
 648   bitset_windex woffset;
 649   bitset_bindex count;
 650   bitset_windex size;
 651   ebitset_elts *elts;
 652
 653   if (EBITSET_OP_ZERO_P (bset))
 654     return 0;
 655
 656   size = EBITSET_SIZE (bset);
 657   n_bits = size * EBITSET_ELT_BITS;
 658   rbitno = *next;
 659
 660   if (rbitno >= n_bits)
 661     return 0;
 662
 663   elts = EBITSET_ELTS (bset);
 664
 665   bitno = n_bits - (rbitno + 1);
 666
 667   windex = bitno / BITSET_WORD_BITS;
 668   eindex = bitno / EBITSET_ELT_BITS;
 669   woffset = windex - eindex * EBITSET_ELT_WORDS;
 670
 671   /* If num is 1, we could speed things up with a binary search
 672      of the word of interest.  */
 673
 674   count = 0;
 675   bcount = bitno % BITSET_WORD_BITS;
 676   boffset = windex * BITSET_WORD_BITS;
 677
 678   do
 679     {
 680       ebitset_elt *elt;
 681
 682       elt = elts[eindex];
 683       if (elt)
 684         {
 685           bitset_word *srcp;
 686
 687           srcp = EBITSET_WORDS (elt);
 688
 689           do
 690             {
 691               bitset_word word;
 692
 693               word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
 694
 695               for (; word; bcount--)
 696                 {
 697                   if (word & BITSET_MSB)
 698                     {
 699                       list[count++] = boffset + bcount;
 700                       if (count >= num)
 701                         {
 702                           *next = n_bits - (boffset + bcount);
 703                           return count;
 704                         }
 705                     }
 706                   word <<= 1;
 707                 }
 708
 709               boffset -= BITSET_WORD_BITS;
 710               bcount = BITSET_WORD_BITS - 1;
 711             }
 712           while (woffset--);
 713
 714           woffset = EBITSET_ELT_WORDS;
 715         }
 716
 717       boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
 718     }
 719   while (eindex--);
 720
 721   *next = n_bits - (boffset + 1);
 722   return count;
 723 }
 724
 725
 726 /* Find list of up to NUM bits set in BSET starting from and including
 727  *NEXT and store in array LIST.  Return with actual number of bits
 728  found and with *NEXT indicating where search stopped.  */
 729 static int
 730 ebitset_list (bset, list, num, next)
 731      bitset bset;
 732      bitset_bindex *list;
 733      bitset_bindex num;
 734      bitset_bindex *next;
 735 {
 736   bitset_bindex bitno;
 737   bitset_windex windex;
 738   unsigned int eindex;
 739   bitset_bindex count;
 740   bitset_windex size;
 741   ebitset_elt *elt;
 742   bitset_word word;
 743   ebitset_elts *elts;
 744
 745   if (EBITSET_OP_ZERO_P (bset))
 746     return 0;
 747
 748   bitno = *next;
 749   count = 0;
 750
 751   elts = EBITSET_ELTS (bset);
 752   size = EBITSET_SIZE (bset);
 753   eindex = bitno / EBITSET_ELT_BITS;
 754
 755   if (bitno % EBITSET_ELT_BITS)
 756     {
 757       /* We need to start within an element.  This is not very common.  */
 758
 759       elt = elts[eindex];
 760       if (elt)
 761         {
 762           bitset_windex woffset;
 763           bitset_word *srcp = EBITSET_WORDS (elt);
 764
 765           windex = bitno / BITSET_WORD_BITS;
 766           woffset = eindex / EBITSET_ELT_WORDS;
 767
 768           for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
 769             {
 770               word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
 771
 772               for (; word; bitno++)
 773                 {
 774                   if (word & 1)
 775                     {
 776                       list[count++] = bitno;
 777                       if (count >= num)
 778                         {
 779                           *next = bitno + 1;
 780                           return count;
 781                         }
 782                     }
 783                   word >>= 1;
 784                 }
 785               bitno = (windex + 1) * BITSET_WORD_BITS;
 786             }
 787         }
 788
 789       /* Skip to next element.  */
 790       eindex++;
 791     }
 792
 793   /* If num is 1, we could speed things up with a binary search
 794      of the word of interest.  */
 795
 796   for (; eindex < size; eindex++)
 797     {
 798       int i;
 799       bitset_word *srcp;
 800
 801       elt = elts[eindex];
 802       if (!elt)
 803         continue;
 804
 805       srcp = EBITSET_WORDS (elt);
 806       windex = eindex * EBITSET_ELT_WORDS;
 807
 808       if ((count + EBITSET_ELT_BITS) < num)
 809         {
 810           /* The coast is clear, plant boot!  */
 811
 812           for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
 813             {
 814               bitno = windex * BITSET_WORD_BITS;
 815
 816               word = srcp[i];
 817               if (word)
 818                 {
 819                   if (!(word & 0xffff))
 820                     {
 821                       word >>= 16;
 822                       bitno += 16;
 823                     }
 824                   if (!(word & 0xff))
 825                     {
 826                       word >>= 8;
 827                       bitno += 8;
 828                     }
 829                   for (; word; bitno++)
 830                     {
 831                       if (word & 1)
 832                         list[count++] = bitno;
 833                       word >>= 1;
 834                     }
 835                 }
 836             }
 837         }
 838       else
 839         {
 840           /* Tread more carefully since we need to check
 841              if array overflows.  */
 842
 843           for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
 844             {
 845               bitno = windex * BITSET_WORD_BITS;
 846
 847               for (word = srcp[i]; word; bitno++)
 848                 {
 849                   if (word & 1)
 850                     {
 851                       list[count++] = bitno;
 852                       if (count >= num)
 853                         {
 854                           *next = bitno + 1;
 855                           return count;
 856                         }
 857                     }
 858                   word >>= 1;
 859                 }
 860             }
 861         }
 862     }
 863
 864   *next = bitno;
 865   return count;
 866 }
 867
 868
 869 static int
 870 ebitset_op1 (dst, op)
 871      bitset dst;
 872      enum bitset_ops op;
 873 {
 874   bitset_windex j;
 875   ebitset_elt *elt;
 876
 877   switch (op)
 878     {
 879     case BITSET_OP_ZERO:
 880       ebitset_zero (dst);
 881       return 1;
 882
 883     case BITSET_OP_ONES:
 884       for (j = 0; j < EBITSET_SIZE (dst); j++)
 885         {
 886           /* Create new elements if they cannot be found.  Perhaps
 887              we should just add pointers to a ones element.  */
 888           elt =
 889             ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
 890           memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
 891         }
 892       break;
 893
 894     case BITSET_OP_EMPTY_P:
 895       return !ebitset_weed (dst);
 896
 897     default:
 898       abort ();
 899     }
 900
 901   EBITSET_NONZERO_SET (dst);
 902   return 1;
 903 }
 904
 905
 906 static int
 907 ebitset_op2 (dst, src, op)
 908      bitset dst;
 909      bitset src;
 910      enum bitset_ops op;
 911 {
 912   ebitset_elt *selt;
 913   ebitset_elt *delt;
 914   unsigned int i;
 915   bitset_windex j;
 916
 917   switch (op)
 918     {
 919     case BITSET_OP_COPY:
 920       ebitset_copy (dst, src);
 921       break;
 922
 923     case BITSET_OP_NOT:
 924       for (j = 0; j < EBITSET_SIZE (src); j++)
 925         {
 926           /* Create new elements for dst if they cannot be found
 927              or substitute zero elements if src elements not found.  */
 928           selt =
 929             ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
 930           delt =
 931             ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
 932
 933           for (i = 0; i < EBITSET_ELT_WORDS; i++)
 934             EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
 935         }
 936       break;
 937
 938       /* Return 1 if DST == SRC.  */
 939     case BITSET_OP_EQUAL_P:
 940       return ebitset_equal_p (dst, src);
 941
 942       /* Return 1 if DST == DST | SRC.  */
 943     case BITSET_OP_SUBSET_P:
 944       {
 945         ebitset_elts *selts;
 946         ebitset_elts *delts;
 947         bitset_windex ssize;
 948         bitset_windex dsize;
 949
 950         selts = EBITSET_ELTS (src);
 951         delts = EBITSET_ELTS (dst);
 952
 953         ssize = EBITSET_SIZE (src);
 954         dsize = EBITSET_SIZE (dst);
 955
 956         for (j = 0; j < ssize; j++)
 957           {
 958             selt = j < ssize ? selts[j] : 0;
 959             delt = j < dsize ? delts[j] : 0;
 960
 961             if (!selt && !delt)
 962               continue;
 963
 964             if (!selt)
 965               selt = &ebitset_zero_elts[0];
 966             if (!delt)
 967               delt = &ebitset_zero_elts[0];
 968
 969             for (i = 0; i < EBITSET_ELT_WORDS; i++)
 970               if (EBITSET_WORDS (delt)[i]
 971                   != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
 972                 return 0;
 973           }
 974         return 1;
 975       }
 976       break;
 977
 978       /* Return 1 if DST & SRC == 0.  */
 979     case BITSET_OP_DISJOINT_P:
 980       {
 981         ebitset_elts *selts;
 982         ebitset_elts *delts;
 983         bitset_windex ssize;
 984         bitset_windex dsize;
 985
 986         selts = EBITSET_ELTS (src);
 987         delts = EBITSET_ELTS (dst);
 988
 989         ssize = EBITSET_SIZE (src);
 990         dsize = EBITSET_SIZE (dst);
 991
 992         for (j = 0; j < ssize; j++)
 993           {
 994             selt = j < ssize ? selts[j] : 0;
 995             delt = j < dsize ? delts[j] : 0;
 996
 997             if (!selt || !delt)
 998               continue;
 999
1000             for (i = 0; i < EBITSET_ELT_WORDS; i++)
1001               if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
1002                 return 0;
1003           }
1004         return 1;
1005       }
1006       break;
1007
1008     default:
1009       abort ();
1010     }
1011
1012   EBITSET_NONZERO_SET (dst);
1013   return 1;
1014 }
1015
1016
1017 static int
1018 ebitset_op3 (dst, src1, src2, op)
1019      bitset dst;
1020      bitset src1;
1021      bitset src2;
1022      enum bitset_ops op;
1023 {
1024   bitset_windex ssize1;
1025   bitset_windex ssize2;
1026   bitset_windex dsize;
1027   bitset_windex size;
1028   ebitset_elts *selts1;
1029   ebitset_elts *selts2;
1030   ebitset_elts *delts;
1031   bitset_word *srcp1;
1032   bitset_word *srcp2;
1033   bitset_word *dstp;
1034   int changed = 0;
1035   unsigned int i;
1036   bitset_windex j;
1037
1038   /* Fast track common, simple cases.  */
1039   if (EBITSET_OP_ZERO_P (src2))
1040     {
1041       if (op == BITSET_OP_AND)
1042         {
1043           ebitset_weed (dst);
1044           changed = EBITSET_OP_ZERO_P (dst);
1045           ebitset_zero (dst);
1046           return changed;
1047         }
1048       else if (op == BITSET_OP_ANDN || op == BITSET_OP_OR
1049                || op == BITSET_OP_XOR)
1050         {
1051           return ebitset_copy_compare (dst, src1);
1052         }
1053     }
1054   else if (EBITSET_OP_ZERO_P (src1))
1055     {
1056       if (op == BITSET_OP_AND || op == BITSET_OP_ANDN)
1057         {
1058           ebitset_weed (dst);
1059           changed = EBITSET_OP_ZERO_P (dst);
1060           ebitset_zero (dst);
1061           return changed;
1062         }
1063       else if (op == BITSET_OP_OR || op == BITSET_OP_XOR)
1064         {
1065           return ebitset_copy_compare (dst, src2);
1066         }
1067     }
1068
1069   ssize1 = EBITSET_SIZE (src1);
1070   ssize2 = EBITSET_SIZE (src2);
1071   dsize = EBITSET_SIZE (dst);
1072   size = ssize1;
1073   if (size < ssize2)
1074     size = ssize2;
1075
1076   if (size > dsize)
1077     ebitset_elts_grow (dst, size - dsize);
1078
1079   selts1 = EBITSET_ELTS (src1);
1080   selts2 = EBITSET_ELTS (src2);
1081   delts = EBITSET_ELTS (dst);
1082
1083   for (j = 0; j < size; j++)
1084     {
1085       ebitset_elt *selt1;
1086       ebitset_elt *selt2;
1087       ebitset_elt *delt;
1088
1089       selt1 = j < ssize1 ? selts1[j] : 0;
1090       selt2 = j < ssize2 ? selts2[j] : 0;
1091       delt = j < dsize ? delts[j] : 0;
1092
1093       if (!selt1 && !selt2)
1094         {
1095           if (delt)
1096             {
1097               changed = 1;
1098               ebitset_elt_remove (dst, j);
1099             }
1100           continue;
1101         }
1102
1103       if (!selt1)
1104         selt1 = &ebitset_zero_elts[0];
1105       if (!selt2)
1106         selt2 = &ebitset_zero_elts[0];
1107       if (!delt)
1108         delt = ebitset_elt_calloc ();
1109       else
1110         delts[j] = 0;
1111
1112       srcp1 = EBITSET_WORDS (selt1);
1113       srcp2 = EBITSET_WORDS (selt2);
1114       dstp = EBITSET_WORDS (delt);
1115       switch (op)
1116         {
1117         case BITSET_OP_OR:
1118           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1119             {
1120               bitset_word tmp = *srcp1++ | *srcp2++;
1121
1122               if (*dstp != tmp)
1123                 {
1124                   changed = 1;
1125                   *dstp = tmp;
1126                 }
1127             }
1128           break;
1129
1130         case BITSET_OP_AND:
1131           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1132             {
1133               bitset_word tmp = *srcp1++ & *srcp2++;
1134
1135               if (*dstp != tmp)
1136                 {
1137                   changed = 1;
1138                   *dstp = tmp;
1139                 }
1140             }
1141           break;
1142
1143         case BITSET_OP_XOR:
1144           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1145             {
1146               bitset_word tmp = *srcp1++ ^ *srcp2++;
1147
1148               if (*dstp != tmp)
1149                 {
1150                   changed = 1;
1151                   *dstp = tmp;
1152                 }
1153             }
1154           break;
1155
1156         case BITSET_OP_ANDN:
1157           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1158             {
1159               bitset_word tmp = *srcp1++ & ~(*srcp2++);
1160
1161               if (*dstp != tmp)
1162                 {
1163                   changed = 1;
1164                   *dstp = tmp;
1165                 }
1166             }
1167           break;
1168
1169         default:
1170           abort ();
1171         }
1172
1173       if (!ebitset_elt_zero_p (delt))
1174         {
1175           ebitset_elt_add (dst, delt, j);
1176         }
1177       else
1178         {
1179           ebitset_elt_free (delt);
1180         }
1181     }
1182
1183   /* If we have elements of DST left over, free them all.  */
1184   for (; j < dsize; j++)
1185     {
1186       ebitset_elt *delt;
1187
1188       changed = 1;
1189
1190       delt = delts[j];
1191
1192       if (delt)
1193         ebitset_elt_remove (dst, j);
1194     }
1195
1196   EBITSET_NONZERO_SET (dst);
1197   return changed;
1198 }
1199
1200
1201 /* Vector of operations for linked-list bitsets.  */
1202 struct bitset_ops_struct ebitset_ops = {
1203   ebitset_set,
1204   ebitset_reset,
1205   ebitset_test,
1206   ebitset_size,
1207   ebitset_op1,
1208   ebitset_op2,
1209   ebitset_op3,
1210   bitset_op4,
1211   ebitset_list,
1212   ebitset_reverse_list,
1213   ebitset_free,
1214   BITSET_TABLE
1215 };
1216
1217
1218 /* Return size of initial structure.  */
1219 int
1220 ebitset_bytes (n_bits)
1221      bitset_bindex n_bits ATTRIBUTE_UNUSED;
1222 {
1223   return sizeof (struct bitset_struct);
1224 }
1225
1226
1227 /* Initialize a bitset.  */
1228
1229 bitset
1230 ebitset_init (bset, n_bits)
1231      bitset bset;
1232      bitset_bindex n_bits;
1233 {
1234   unsigned int size;
1235
1236   bset->b.ops = &ebitset_ops;
1237
1238   bset->b.csize = EBITSET_ELT_WORDS;
1239
1240   EBITSET_OP_ZERO_SET (bset);
1241
1242   size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
1243     : EBITSET_INITIAL_SIZE;
1244
1245   EBITSET_SIZE (bset) = 0;
1246   EBITSET_ELTS (bset) = 0;
1247   ebitset_elts_grow (bset, size);
1248
1249   return bset;
1250 }
1251
1252
1253 void
1254 ebitset_release_memory ()
1255 {
1256   ebitset_free_list = 0;
1257   if (ebitset_obstack_init)
1258     {
1259       ebitset_obstack_init = 0;
1260       obstack_free (&ebitset_obstack, NULL);
1261     }
1262 }