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