lib/ebitset.c

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