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    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 int ebitset_obstack_init = 0;
  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 = 1;
 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 /* Return nonzero if all bits in an element are zero.  */
 246 static inline int
 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 0;
 254
 255   return 1;
 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 int
 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 1;
 414
 415   ebitset_weed (dst);
 416   ebitset_weed (src);
 417
 418   if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
 419     return 0;
 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 0;
 434
 435       for (i = 0; i < EBITSET_ELT_WORDS; i++)
 436         if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
 437           return 0;
 438     }
 439   return 1;
 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 non-zero if
 480    bitsets different.  */
 481 static inline int
 482 ebitset_copy_cmp (bitset dst, bitset src)
 483 {
 484   if (src == dst)
 485     return 0;
 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 0;
 495
 496   ebitset_copy_ (dst, src);
 497   return 1;
 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 int
 543 ebitset_test (bitset src, bitset_bindex bitno)
 544 {
 545   bitset_windex windex = bitno / BITSET_WORD_BITS;
 546
 547   if (!ebitset_elt_find (src, windex, EBITSET_FIND))
 548     return 0;
 549
 550   return (src->b.
 551           cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
 552 }
 553
 554
 555 static void
 556 ebitset_free (bitset bset)
 557 {
 558   ebitset_zero (bset);
 559   free (EBITSET_ELTS (bset));
 560 }
 561
 562
 563 /* Find list of up to NUM bits set in BSET starting from and including
 564  *NEXT and store in array LIST.  Return with actual number of bits
 565  found and with *NEXT indicating where search stopped.  */
 566 static bitset_bindex
 567 ebitset_list_reverse (bitset bset, bitset_bindex *list,
 568                       bitset_bindex num, bitset_bindex *next)
 569 {
 570   bitset_bindex n_bits;
 571   bitset_bindex bitno;
 572   bitset_bindex rbitno;
 573   unsigned int bcount;
 574   bitset_bindex boffset;
 575   bitset_windex windex;
 576   bitset_windex eindex;
 577   bitset_windex woffset;
 578   bitset_bindex count;
 579   bitset_windex size;
 580   ebitset_elts *elts;
 581
 582   if (EBITSET_ZERO_P (bset))
 583     return 0;
 584
 585   size = EBITSET_SIZE (bset);
 586   n_bits = size * EBITSET_ELT_BITS;
 587   rbitno = *next;
 588
 589   if (rbitno >= n_bits)
 590     return 0;
 591
 592   elts = EBITSET_ELTS (bset);
 593
 594   bitno = n_bits - (rbitno + 1);
 595
 596   windex = bitno / BITSET_WORD_BITS;
 597   eindex = bitno / EBITSET_ELT_BITS;
 598   woffset = windex - eindex * EBITSET_ELT_WORDS;
 599
 600   /* If num is 1, we could speed things up with a binary search
 601      of the word of interest.  */
 602
 603   count = 0;
 604   bcount = bitno % BITSET_WORD_BITS;
 605   boffset = windex * BITSET_WORD_BITS;
 606
 607   do
 608     {
 609       ebitset_elt *elt;
 610       bitset_word *srcp;
 611
 612       elt = elts[eindex];
 613       if (elt)
 614         {
 615           srcp = EBITSET_WORDS (elt);
 616
 617           do
 618             {
 619               bitset_word word;
 620
 621               word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
 622
 623               for (; word; bcount--)
 624                 {
 625                   if (word & BITSET_MSB)
 626                     {
 627                       list[count++] = boffset + bcount;
 628                       if (count >= num)
 629                         {
 630                           *next = n_bits - (boffset + bcount);
 631                           return count;
 632                         }
 633                     }
 634                   word <<= 1;
 635                 }
 636               boffset -= BITSET_WORD_BITS;
 637               bcount = BITSET_WORD_BITS - 1;
 638             }
 639           while (woffset--);
 640         }
 641
 642       woffset = EBITSET_ELT_WORDS - 1;
 643       boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
 644     }
 645   while (eindex--);
 646
 647   *next = n_bits - (boffset + 1);
 648   return count;
 649 }
 650
 651
 652 /* Find list of up to NUM bits set in BSET starting from and including
 653  *NEXT and store in array LIST.  Return with actual number of bits
 654  found and with *NEXT indicating where search stopped.  */
 655 static bitset_bindex
 656 ebitset_list (bitset bset, bitset_bindex *list,
 657               bitset_bindex num, bitset_bindex *next)
 658 {
 659   bitset_bindex bitno;
 660   bitset_windex windex;
 661   bitset_windex eindex;
 662   bitset_bindex count;
 663   bitset_windex size;
 664   ebitset_elt *elt;
 665   bitset_word word;
 666   ebitset_elts *elts;
 667
 668   if (EBITSET_ZERO_P (bset))
 669     return 0;
 670
 671   bitno = *next;
 672   count = 0;
 673
 674   elts = EBITSET_ELTS (bset);
 675   size = EBITSET_SIZE (bset);
 676   eindex = bitno / EBITSET_ELT_BITS;
 677
 678   if (bitno % EBITSET_ELT_BITS)
 679     {
 680       /* We need to start within an element.  This is not very common.  */
 681
 682       elt = elts[eindex];
 683       if (elt)
 684         {
 685           bitset_windex woffset;
 686           bitset_word *srcp = EBITSET_WORDS (elt);
 687
 688           windex = bitno / BITSET_WORD_BITS;
 689           woffset = eindex * EBITSET_ELT_WORDS;
 690
 691           for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
 692             {
 693               word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
 694
 695               for (; word; bitno++)
 696                 {
 697                   if (word & 1)
 698                     {
 699                       list[count++] = bitno;
 700                       if (count >= num)
 701                         {
 702                           *next = bitno + 1;
 703                           return count;
 704                         }
 705                     }
 706                   word >>= 1;
 707                 }
 708               bitno = (windex + 1) * BITSET_WORD_BITS;
 709             }
 710         }
 711
 712       /* Skip to next element.  */
 713       eindex++;
 714     }
 715
 716   /* If num is 1, we could speed things up with a binary search
 717      of the word of interest.  */
 718
 719   for (; eindex < size; eindex++)
 720     {
 721       int i;
 722       bitset_word *srcp;
 723
 724       elt = elts[eindex];
 725       if (!elt)
 726         continue;
 727
 728       srcp = EBITSET_WORDS (elt);
 729       windex = eindex * EBITSET_ELT_WORDS;
 730
 731       if ((count + EBITSET_ELT_BITS) < num)
 732         {
 733           /* The coast is clear, plant boot!  */
 734
 735           for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
 736             {
 737               bitno = windex * BITSET_WORD_BITS;
 738
 739               word = srcp[i];
 740               if (word)
 741                 {
 742                   if (!(word & 0xffff))
 743                     {
 744                       word >>= 16;
 745                       bitno += 16;
 746                     }
 747                   if (!(word & 0xff))
 748                     {
 749                       word >>= 8;
 750                       bitno += 8;
 751                     }
 752                   for (; word; bitno++)
 753                     {
 754                       if (word & 1)
 755                         list[count++] = bitno;
 756                       word >>= 1;
 757                     }
 758                 }
 759             }
 760         }
 761       else
 762         {
 763           /* Tread more carefully since we need to check
 764              if array overflows.  */
 765
 766           for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
 767             {
 768               bitno = windex * BITSET_WORD_BITS;
 769
 770               for (word = srcp[i]; word; bitno++)
 771                 {
 772                   if (word & 1)
 773                     {
 774                       list[count++] = bitno;
 775                       if (count >= num)
 776                         {
 777                           *next = bitno + 1;
 778                           return count;
 779                         }
 780                     }
 781                   word >>= 1;
 782                 }
 783             }
 784         }
 785     }
 786
 787   *next = bitno;
 788   return count;
 789 }
 790
 791
 792 static void
 793 ebitset_ones (bitset dst)
 794 {
 795   bitset_windex j;
 796   ebitset_elt *elt;
 797
 798
 799   for (j = 0; j < EBITSET_SIZE (dst); j++)
 800     {
 801       /* Create new elements if they cannot be found.  Perhaps
 802          we should just add pointers to a ones element.  */
 803       elt =
 804         ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
 805       memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
 806     }
 807   EBITSET_NONZERO_SET (dst);
 808 }
 809
 810
 811 static int
 812 ebitset_empty_p (bitset dst)
 813 {
 814   return !ebitset_weed (dst);
 815 }
 816
 817
 818 static void
 819 ebitset_not (bitset dst, bitset src)
 820 {
 821   unsigned int i;
 822   ebitset_elt *selt;
 823   ebitset_elt *delt;
 824   bitset_windex j;
 825
 826   for (j = 0; j < EBITSET_SIZE (src); j++)
 827     {
 828       /* Create new elements for dst if they cannot be found
 829              or substitute zero elements if src elements not found.  */
 830       selt =
 831         ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
 832       delt =
 833         ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
 834
 835       for (i = 0; i < EBITSET_ELT_WORDS; i++)
 836         EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
 837     }
 838   EBITSET_NONZERO_SET (dst);
 839 }
 840
 841
 842 /* Return 1 if DST == DST | SRC.  */
 843 static int
 844 ebitset_subset_p (bitset dst, bitset src)
 845 {
 846   bitset_windex j;
 847   ebitset_elts *selts;
 848   ebitset_elts *delts;
 849   bitset_windex ssize;
 850   bitset_windex dsize;
 851
 852   selts = EBITSET_ELTS (src);
 853   delts = EBITSET_ELTS (dst);
 854
 855   ssize = EBITSET_SIZE (src);
 856   dsize = EBITSET_SIZE (dst);
 857
 858   for (j = 0; j < ssize; j++)
 859     {
 860       unsigned int i;
 861       ebitset_elt *selt;
 862       ebitset_elt *delt;
 863
 864       selt = j < ssize ? selts[j] : 0;
 865       delt = j < dsize ? delts[j] : 0;
 866
 867       if (!selt && !delt)
 868         continue;
 869
 870       if (!selt)
 871         selt = &ebitset_zero_elts[0];
 872       if (!delt)
 873         delt = &ebitset_zero_elts[0];
 874
 875       for (i = 0; i < EBITSET_ELT_WORDS; i++)
 876         if (EBITSET_WORDS (delt)[i]
 877             != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
 878           return 0;
 879     }
 880   return 1;
 881 }
 882
 883
 884 /* Return 1 if DST & SRC == 0.  */
 885 static int
 886 ebitset_disjoint_p (bitset dst, bitset src)
 887 {
 888   bitset_windex j;
 889   ebitset_elts *selts;
 890   ebitset_elts *delts;
 891   bitset_windex ssize;
 892   bitset_windex dsize;
 893
 894   selts = EBITSET_ELTS (src);
 895   delts = EBITSET_ELTS (dst);
 896
 897   ssize = EBITSET_SIZE (src);
 898   dsize = EBITSET_SIZE (dst);
 899
 900   for (j = 0; j < ssize; j++)
 901     {
 902       unsigned int i;
 903       ebitset_elt *selt;
 904       ebitset_elt *delt;
 905
 906       selt = j < ssize ? selts[j] : 0;
 907       delt = j < dsize ? delts[j] : 0;
 908
 909       if (!selt || !delt)
 910         continue;
 911
 912       for (i = 0; i < EBITSET_ELT_WORDS; i++)
 913         if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
 914           return 0;
 915     }
 916   return 1;
 917 }
 918
 919
 920
 921 static int
 922 ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
 923 {
 924   bitset_windex ssize1;
 925   bitset_windex ssize2;
 926   bitset_windex dsize;
 927   bitset_windex size;
 928   ebitset_elts *selts1;
 929   ebitset_elts *selts2;
 930   ebitset_elts *delts;
 931   bitset_word *srcp1;
 932   bitset_word *srcp2;
 933   bitset_word *dstp;
 934   int changed = 0;
 935   unsigned int i;
 936   bitset_windex j;
 937
 938   ssize1 = EBITSET_SIZE (src1);
 939   ssize2 = EBITSET_SIZE (src2);
 940   dsize = EBITSET_SIZE (dst);
 941   size = ssize1;
 942   if (size < ssize2)
 943     size = ssize2;
 944
 945   if (size > dsize)
 946     ebitset_elts_grow (dst, size - dsize);
 947
 948   selts1 = EBITSET_ELTS (src1);
 949   selts2 = EBITSET_ELTS (src2);
 950   delts = EBITSET_ELTS (dst);
 951
 952   for (j = 0; j < size; j++)
 953     {
 954       ebitset_elt *selt1;
 955       ebitset_elt *selt2;
 956       ebitset_elt *delt;
 957
 958       selt1 = j < ssize1 ? selts1[j] : 0;
 959       selt2 = j < ssize2 ? selts2[j] : 0;
 960       delt = j < dsize ? delts[j] : 0;
 961
 962       if (!selt1 && !selt2)
 963         {
 964           if (delt)
 965             {
 966               changed = 1;
 967               ebitset_elt_remove (dst, j);
 968             }
 969           continue;
 970         }
 971
 972       if (!selt1)
 973         selt1 = &ebitset_zero_elts[0];
 974       if (!selt2)
 975         selt2 = &ebitset_zero_elts[0];
 976       if (!delt)
 977         delt = ebitset_elt_calloc ();
 978       else
 979         delts[j] = 0;
 980
 981       srcp1 = EBITSET_WORDS (selt1);
 982       srcp2 = EBITSET_WORDS (selt2);
 983       dstp = EBITSET_WORDS (delt);
 984       switch (op)
 985         {
 986         case BITSET_OP_OR:
 987           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
 988             {
 989               bitset_word tmp = *srcp1++ | *srcp2++;
 990
 991               if (*dstp != tmp)
 992                 {
 993                   changed = 1;
 994                   *dstp = tmp;
 995                 }
 996             }
 997           break;
 998
 999         case BITSET_OP_AND:
1000           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1001             {
1002               bitset_word tmp = *srcp1++ & *srcp2++;
1003
1004               if (*dstp != tmp)
1005                 {
1006                   changed = 1;
1007                   *dstp = tmp;
1008                 }
1009             }
1010           break;
1011
1012         case BITSET_OP_XOR:
1013           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1014             {
1015               bitset_word tmp = *srcp1++ ^ *srcp2++;
1016
1017               if (*dstp != tmp)
1018                 {
1019                   changed = 1;
1020                   *dstp = tmp;
1021                 }
1022             }
1023           break;
1024
1025         case BITSET_OP_ANDN:
1026           for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1027             {
1028               bitset_word tmp = *srcp1++ & ~(*srcp2++);
1029
1030               if (*dstp != tmp)
1031                 {
1032                   changed = 1;
1033                   *dstp = tmp;
1034                 }
1035             }
1036           break;
1037
1038         default:
1039           abort ();
1040         }
1041
1042       if (!ebitset_elt_zero_p (delt))
1043         {
1044           ebitset_elt_add (dst, delt, j);
1045         }
1046       else
1047         {
1048           ebitset_elt_free (delt);
1049         }
1050     }
1051
1052   /* If we have elements of DST left over, free them all.  */
1053   for (; j < dsize; j++)
1054     {
1055       ebitset_elt *delt;
1056
1057       changed = 1;
1058
1059       delt = delts[j];
1060
1061       if (delt)
1062         ebitset_elt_remove (dst, j);
1063     }
1064
1065   EBITSET_NONZERO_SET (dst);
1066   return changed;
1067 }
1068
1069
1070 static int
1071 ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
1072 {
1073   int changed;
1074
1075   if (EBITSET_ZERO_P (src2))
1076     {
1077       ebitset_weed (dst);
1078       changed = EBITSET_ZERO_P (dst);
1079       ebitset_zero (dst);
1080       return changed;
1081     }
1082   else if (EBITSET_ZERO_P (src1))
1083     {
1084       ebitset_weed (dst);
1085       changed = EBITSET_ZERO_P (dst);
1086       ebitset_zero (dst);
1087       return changed;
1088     }
1089   return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1090 }
1091
1092
1093 static void
1094 ebitset_and (bitset dst, bitset src1, bitset src2)
1095 {
1096   ebitset_and_cmp (dst, src1, src2);
1097 }
1098
1099
1100 static int
1101 ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
1102 {
1103   int changed;
1104
1105   if (EBITSET_ZERO_P (src2))
1106     {
1107       return ebitset_copy_cmp (dst, src1);
1108     }
1109   else if (EBITSET_ZERO_P (src1))
1110     {
1111       ebitset_weed (dst);
1112       changed = EBITSET_ZERO_P (dst);
1113       ebitset_zero (dst);
1114       return changed;
1115     }
1116   return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1117 }
1118
1119
1120 static void
1121 ebitset_andn (bitset dst, bitset src1, bitset src2)
1122 {
1123   ebitset_andn_cmp (dst, src1, src2);
1124 }
1125
1126
1127 static int
1128 ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
1129 {
1130   if (EBITSET_ZERO_P (src2))
1131     {
1132       return ebitset_copy_cmp (dst, src1);
1133     }
1134   else if (EBITSET_ZERO_P (src1))
1135     {
1136       return ebitset_copy_cmp (dst, src2);
1137     }
1138   return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1139 }
1140
1141
1142 static void
1143 ebitset_or (bitset dst, bitset src1, bitset src2)
1144 {
1145   ebitset_or_cmp (dst, src1, src2);
1146 }
1147
1148
1149 static int
1150 ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1151 {
1152   if (EBITSET_ZERO_P (src2))
1153     {
1154       return ebitset_copy_cmp (dst, src1);
1155     }
1156   else if (EBITSET_ZERO_P (src1))
1157     {
1158       return ebitset_copy_cmp (dst, src2);
1159     }
1160   return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1161 }
1162
1163
1164 static void
1165 ebitset_xor (bitset dst, bitset src1, bitset src2)
1166 {
1167   ebitset_xor_cmp (dst, src1, src2);
1168 }
1169
1170
1171 static void
1172 ebitset_copy (bitset dst, bitset src)
1173 {
1174   if (BITSET_COMPATIBLE_ (dst, src))
1175       ebitset_copy_ (dst, src);
1176   else
1177       bitset_copy_ (dst, src);
1178 }
1179
1180
1181 /* Vector of operations for linked-list bitsets.  */
1182 struct bitset_vtable ebitset_vtable = {
1183   ebitset_set,
1184   ebitset_reset,
1185   bitset_toggle_,
1186   ebitset_test,
1187   ebitset_size,
1188   bitset_count_,
1189   ebitset_empty_p,
1190   ebitset_ones,
1191   ebitset_zero,
1192   ebitset_copy,
1193   ebitset_disjoint_p,
1194   ebitset_equal_p,
1195   ebitset_not,
1196   ebitset_subset_p,
1197   ebitset_and,
1198   ebitset_and_cmp,
1199   ebitset_andn,
1200   ebitset_andn_cmp,
1201   ebitset_or,
1202   ebitset_or_cmp,
1203   ebitset_xor,
1204   ebitset_xor_cmp,
1205   bitset_and_or_,
1206   bitset_and_or_cmp_,
1207   bitset_andn_or_,
1208   bitset_andn_or_cmp_,
1209   bitset_or_and_,
1210   bitset_or_and_cmp_,
1211   ebitset_list,
1212   ebitset_list_reverse,
1213   ebitset_free,
1214   BITSET_TABLE
1215 };
1216
1217
1218 /* Return size of initial structure.  */
1219 size_t
1220 ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
1221 {
1222   return sizeof (struct ebitset_struct);
1223 }
1224
1225
1226 /* Initialize a bitset.  */
1227
1228 bitset
1229 ebitset_init (bitset bset, bitset_bindex n_bits)
1230 {
1231   bitset_windex size;
1232
1233   bset->b.vtable = &ebitset_vtable;
1234
1235   bset->b.csize = EBITSET_ELT_WORDS;
1236
1237   EBITSET_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 (void)
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 }