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