lib/ebitset.c

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