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