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