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