lib/vbitset.c

   1 /* Variable array 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 "vbitset.h"
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 /* This file implements variable size bitsets stored as a variable
  29    length array of words.  Any unused bits in the last word must be
  30    zero.
  31
  32    Note that binary or ternary operations assume that each bitset operand
  33    has the same size.
  34 */
  35
  36 static void vbitset_unused_clear PARAMS ((bitset));
  37
  38 static void vbitset_set PARAMS ((bitset, bitset_bindex));
  39 static void vbitset_reset PARAMS ((bitset, bitset_bindex));
  40 static bool vbitset_test PARAMS ((bitset, bitset_bindex));
  41 static bitset_bindex vbitset_list PARAMS ((bitset, bitset_bindex *,
  42                                            bitset_bindex,
  43                                            bitset_bindex *));
  44 static bitset_bindex vbitset_list_reverse PARAMS ((bitset, bitset_bindex *,
  45                                                    bitset_bindex,
  46                                                    bitset_bindex *));
  47
  48 #define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
  49 #define VBITSET_WORDS(X) ((X)->b.cdata)
  50 #define VBITSET_SIZE(X) ((X)->b.csize)
  51 #define VBITSET_ASIZE(X) ((X)->v.size)
  52
  53
  54 #define min(a, b) ((a) > (b) ? (b) : (a))
  55 #define max(a, b) ((a) > (b) ? (a) : (b))
  56
  57 static bitset_bindex
  58 vbitset_resize (src, n_bits)
  59      bitset src;
  60      bitset_bindex n_bits;
  61 {
  62   bitset_windex oldsize;
  63   bitset_windex newsize;
  64
  65   if (n_bits == BITSET_NBITS_ (src))
  66     return n_bits;
  67
  68   oldsize = VBITSET_SIZE (src);
  69   newsize = VBITSET_N_WORDS (n_bits);
  70
  71   if (oldsize < newsize)
  72     {
  73       bitset_windex size;
  74
  75       /* The bitset needs to grow.  If we already have enough memory
  76          allocated, then just zero what we need.  */
  77       if (newsize > VBITSET_ASIZE (src))
  78         {
  79           /* We need to allocate more memory.  When oldsize is
  80              non-zero this means that we are changing the size, so
  81              grow the bitset 25% larger than requested to reduce
  82              number of reallocations.  */
  83
  84           if (oldsize == 0)
  85             size = newsize;
  86           else
  87             size = newsize + newsize / 4;
  88
  89           VBITSET_WORDS (src)
  90             = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
  91           VBITSET_ASIZE (src) = size;
  92         }
  93
  94       memset (VBITSET_WORDS (src) + oldsize, 0,
  95               (newsize - oldsize) * sizeof (bitset_word));
  96       VBITSET_SIZE (src) = newsize;
  97     }
  98   else
  99     {
 100       /* The bitset needs to shrink.  There's no point deallocating
 101          the memory unless it is shrinking by a reasonable amount.  */
 102       if ((oldsize - newsize) >= oldsize / 2)
 103         {
 104           VBITSET_WORDS (src)
 105             = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
 106           VBITSET_ASIZE (src) = newsize;
 107         }
 108
 109       /* Need to prune any excess bits.  FIXME.  */
 110
 111       VBITSET_SIZE (src) = newsize;
 112     }
 113
 114   BITSET_NBITS_ (src) = n_bits;
 115   return n_bits;
 116 }
 117
 118
 119 /* Set bit BITNO in bitset DST.  */
 120 static void
 121 vbitset_set (dst, bitno)
 122      bitset dst;
 123      bitset_bindex bitno;
 124 {
 125   bitset_windex windex = bitno / BITSET_WORD_BITS;
 126
 127   /* Perhaps we should abort.  The user should explicitly call
 128      bitset_resize since this will not catch the case when we set a
 129      bit larger than the current size but smaller than the allocated
 130      size.  */
 131   vbitset_resize (dst, bitno);
 132
 133   dst->b.cdata[windex - dst->b.cindex] |=
 134     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
 135 }
 136
 137
 138 /* Reset bit BITNO in bitset DST.  */
 139 static void
 140 vbitset_reset (dst, bitno)
 141      bitset dst ATTRIBUTE_UNUSED;
 142      bitset_bindex bitno ATTRIBUTE_UNUSED;
 143 {
 144   /* We must be accessing outside the cache so the bit is
 145      zero anyway.  */
 146 }
 147
 148
 149 /* Test bit BITNO in bitset SRC.  */
 150 static bool
 151 vbitset_test (src, bitno)
 152      bitset src ATTRIBUTE_UNUSED;
 153      bitset_bindex bitno ATTRIBUTE_UNUSED;
 154 {
 155   /* We must be accessing outside the cache so the bit is
 156      zero anyway.  */
 157   return 0;
 158 }
 159
 160
 161 /* Find list of up to NUM bits set in BSET in reverse order, starting
 162    from and including NEXT and store in array LIST.  Return with
 163    actual number of bits found and with *NEXT indicating where search
 164    stopped.  */
 165 static bitset_bindex
 166 vbitset_list_reverse (src, list, num, next)
 167      bitset src;
 168      bitset_bindex *list;
 169      bitset_bindex num;
 170      bitset_bindex *next;
 171 {
 172   bitset_bindex bitno;
 173   bitset_bindex rbitno;
 174   bitset_bindex count;
 175   bitset_windex windex;
 176   unsigned int bitcnt;
 177   bitset_bindex bitoff;
 178   bitset_word *srcp = VBITSET_WORDS (src);
 179   bitset_bindex n_bits = BITSET_SIZE_ (src);
 180
 181   rbitno = *next;
 182
 183   /* If num is 1, we could speed things up with a binary search
 184      of the word of interest.  */
 185
 186   if (rbitno >= n_bits)
 187     return 0;
 188
 189   count = 0;
 190
 191   bitno = n_bits - (rbitno + 1);
 192
 193   windex = bitno / BITSET_WORD_BITS;
 194   bitcnt = bitno % BITSET_WORD_BITS;
 195   bitoff = windex * BITSET_WORD_BITS;
 196
 197   do
 198     {
 199       bitset_word word;
 200
 201       word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
 202       for (; word; bitcnt--)
 203         {
 204           if (word & BITSET_MSB)
 205             {
 206               list[count++] = bitoff + bitcnt;
 207               if (count >= num)
 208                 {
 209                   *next = n_bits - (bitoff + bitcnt);
 210                   return count;
 211                 }
 212             }
 213           word <<= 1;
 214         }
 215       bitoff -= BITSET_WORD_BITS;
 216       bitcnt = BITSET_WORD_BITS - 1;
 217     }
 218   while (windex--);
 219
 220   *next = n_bits - (bitoff + 1);
 221   return count;
 222 }
 223
 224
 225 /* Find list of up to NUM bits set in BSET starting from and including
 226  *NEXT and store in array LIST.  Return with actual number of bits
 227  found and with *NEXT indicating where search stopped.  */
 228 static bitset_bindex
 229 vbitset_list (src, list, num, next)
 230      bitset src;
 231      bitset_bindex *list;
 232      bitset_bindex num;
 233      bitset_bindex *next;
 234 {
 235   bitset_bindex bitno;
 236   bitset_bindex count;
 237   bitset_windex windex;
 238   bitset_bindex bitoff;
 239   bitset_windex size = VBITSET_SIZE (src);
 240   bitset_word *srcp = VBITSET_WORDS (src);
 241   bitset_word word;
 242
 243   bitno = *next;
 244
 245   count = 0;
 246   if (!bitno)
 247     {
 248       /* Many bitsets are zero, so make this common case fast.  */
 249       for (windex = 0; windex < size && !srcp[windex]; windex++)
 250         continue;
 251       if (windex >= size)
 252         return 0;
 253
 254       /* If num is 1, we could speed things up with a binary search
 255          of the current word.  */
 256
 257       bitoff = windex * BITSET_WORD_BITS;
 258     }
 259   else
 260     {
 261       if (bitno >= BITSET_SIZE_ (src))
 262         return 0;
 263
 264       windex = bitno / BITSET_WORD_BITS;
 265       bitno = bitno % BITSET_WORD_BITS;
 266
 267       if (bitno)
 268         {
 269           /* Handle the case where we start within a word.
 270              Most often, this is executed with large bitsets
 271              with many set bits where we filled the array
 272              on the previous call to this function.  */
 273
 274           bitoff = windex * BITSET_WORD_BITS;
 275           word = srcp[windex] >> bitno;
 276           for (bitno = bitoff + bitno; word; bitno++)
 277             {
 278               if (word & 1)
 279                 {
 280                   list[count++] = bitno;
 281                   if (count >= num)
 282                     {
 283                       *next = bitno + 1;
 284                       return count;
 285                     }
 286                 }
 287               word >>= 1;
 288             }
 289           windex++;
 290         }
 291       bitoff = windex * BITSET_WORD_BITS;
 292     }
 293
 294   for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
 295     {
 296       if (!(word = srcp[windex]))
 297         continue;
 298
 299       if ((count + BITSET_WORD_BITS) < num)
 300         {
 301           for (bitno = bitoff; word; bitno++)
 302             {
 303               if (word & 1)
 304                 list[count++] = bitno;
 305               word >>= 1;
 306             }
 307         }
 308       else
 309         {
 310           for (bitno = bitoff; word; bitno++)
 311             {
 312               if (word & 1)
 313                 {
 314                   list[count++] = bitno;
 315                   if (count >= num)
 316                     {
 317                       *next = bitno + 1;
 318                       return count;
 319                     }
 320                 }
 321               word >>= 1;
 322             }
 323         }
 324     }
 325
 326   *next = bitoff;
 327   return count;
 328 }
 329
 330
 331 /* Ensure that any unused bits within the last word are clear.  */
 332 static inline void
 333 vbitset_unused_clear (dst)
 334      bitset dst;
 335 {
 336   unsigned int last_bit;
 337
 338   last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
 339   if (last_bit)
 340     VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &=
 341       ((bitset_word) 1 << last_bit) - 1;
 342 }
 343
 344
 345 static void
 346 vbitset_ones (dst)
 347      bitset dst;
 348 {
 349   bitset_word *dstp = VBITSET_WORDS (dst);
 350   unsigned int bytes;
 351
 352   bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
 353
 354   memset (dstp, -1, bytes);
 355   vbitset_unused_clear (dst);
 356 }
 357
 358
 359 static void
 360 vbitset_zero (dst)
 361      bitset dst;
 362 {
 363   bitset_word *dstp = VBITSET_WORDS (dst);
 364   unsigned int bytes;
 365
 366   bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
 367
 368   memset (dstp, 0, bytes);
 369 }
 370
 371
 372 static bool
 373 vbitset_empty_p (dst)
 374      bitset dst;
 375 {
 376   unsigned int i;
 377   bitset_word *dstp = VBITSET_WORDS (dst);
 378
 379   for (i = 0; i < VBITSET_SIZE (dst); i++)
 380     if (dstp[i])
 381       return 0;
 382
 383   return 1;
 384 }
 385
 386
 387 static void
 388 vbitset_copy1 (dst, src)
 389      bitset dst;
 390      bitset src;
 391 {
 392   bitset_word *srcp;
 393   bitset_word *dstp;
 394   bitset_windex ssize;
 395   bitset_windex dsize;
 396
 397   if (src == dst)
 398       return;
 399
 400   vbitset_resize (dst, BITSET_SIZE_ (src));
 401
 402   srcp = VBITSET_WORDS (src);
 403   dstp = VBITSET_WORDS (dst);
 404   ssize = VBITSET_SIZE (src);
 405   dsize = VBITSET_SIZE (dst);
 406
 407   memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
 408
 409   memset (dstp + sizeof (bitset_word) * ssize, 0,
 410           sizeof (bitset_word) * (dsize - ssize));
 411 }
 412
 413
 414 static void
 415 vbitset_not (dst, src)
 416      bitset dst;
 417      bitset src;
 418 {
 419   unsigned int i;
 420   bitset_word *srcp;
 421   bitset_word *dstp;
 422   bitset_windex ssize;
 423   bitset_windex dsize;
 424
 425   vbitset_resize (dst, BITSET_SIZE_ (src));
 426
 427   srcp = VBITSET_WORDS (src);
 428   dstp = VBITSET_WORDS (dst);
 429   ssize = VBITSET_SIZE (src);
 430   dsize = VBITSET_SIZE (dst);
 431
 432   for (i = 0; i < ssize; i++)
 433       *dstp++ = ~(*srcp++);
 434
 435   vbitset_unused_clear (dst);
 436   memset (dstp + sizeof (bitset_word) * ssize, 0,
 437           sizeof (bitset_word) * (dsize - ssize));
 438 }
 439
 440
 441 static bool
 442 vbitset_equal_p (dst, src)
 443      bitset dst;
 444      bitset src;
 445 {
 446   unsigned int i;
 447   bitset_word *srcp = VBITSET_WORDS (src);
 448   bitset_word *dstp = VBITSET_WORDS (dst);
 449   bitset_windex ssize = VBITSET_SIZE (src);
 450   bitset_windex dsize = VBITSET_SIZE (dst);
 451
 452   for (i = 0; i < min (ssize, dsize); i++)
 453       if (*srcp++ != *dstp++)
 454           return 0;
 455
 456   if (ssize > dsize)
 457     {
 458       for (; i < ssize; i++)
 459         if (*srcp++)
 460           return 0;
 461     }
 462   else
 463     {
 464       for (; i < dsize; i++)
 465         if (*dstp++)
 466           return 0;
 467     }
 468
 469   return 1;
 470 }
 471
 472
 473 static bool
 474 vbitset_subset_p (dst, src)
 475      bitset dst;
 476      bitset src;
 477 {
 478   unsigned int i;
 479   bitset_word *srcp = VBITSET_WORDS (src);
 480   bitset_word *dstp = VBITSET_WORDS (dst);
 481   bitset_windex ssize = VBITSET_SIZE (src);
 482   bitset_windex dsize = VBITSET_SIZE (dst);
 483
 484   for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
 485       if (*dstp != (*srcp | *dstp))
 486           return 0;
 487
 488   if (ssize > dsize)
 489     {
 490       for (; i < ssize; i++)
 491         if (*srcp++)
 492           return 0;
 493     }
 494
 495   return 1;
 496 }
 497
 498
 499 static bool
 500 vbitset_disjoint_p (dst, src)
 501      bitset dst;
 502      bitset src;
 503 {
 504   unsigned int i;
 505   bitset_word *srcp = VBITSET_WORDS (src);
 506   bitset_word *dstp = VBITSET_WORDS (dst);
 507   bitset_windex ssize = VBITSET_SIZE (src);
 508   bitset_windex dsize = VBITSET_SIZE (dst);
 509
 510   for (i = 0; i < min (ssize, dsize); i++)
 511       if (*srcp++ & *dstp++)
 512           return 0;
 513
 514   return 1;
 515 }
 516
 517
 518 static void
 519 vbitset_and (dst, src1, src2)
 520      bitset dst;
 521      bitset src1;
 522      bitset src2;
 523 {
 524   unsigned int i;
 525   bitset_word *src1p;
 526   bitset_word *src2p;
 527   bitset_word *dstp;
 528   bitset_windex ssize1;
 529   bitset_windex ssize2;
 530   bitset_windex dsize;
 531
 532   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 533
 534   dsize = VBITSET_SIZE (dst);
 535   ssize1 = VBITSET_SIZE (src1);
 536   ssize2 = VBITSET_SIZE (src2);
 537   dstp = VBITSET_WORDS (dst);
 538   src1p = VBITSET_WORDS (src1);
 539   src2p = VBITSET_WORDS (src2);
 540
 541   for (i = 0; i < min (ssize1, ssize2); i++)
 542       *dstp++ = *src1p++ & *src2p++;
 543
 544   memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2)));
 545 }
 546
 547
 548 static bool
 549 vbitset_and_cmp (dst, src1, src2)
 550      bitset dst;
 551      bitset src1;
 552      bitset src2;
 553 {
 554   unsigned int i;
 555   int changed = 0;
 556   bitset_word *src1p;
 557   bitset_word *src2p;
 558   bitset_word *dstp;
 559   bitset_windex ssize1;
 560   bitset_windex ssize2;
 561   bitset_windex dsize;
 562
 563   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 564
 565   dsize = VBITSET_SIZE (dst);
 566   ssize1 = VBITSET_SIZE (src1);
 567   ssize2 = VBITSET_SIZE (src2);
 568   dstp = VBITSET_WORDS (dst);
 569   src1p = VBITSET_WORDS (src1);
 570   src2p = VBITSET_WORDS (src2);
 571
 572   for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
 573     {
 574       bitset_word tmp = *src1p++ & *src2p++;
 575
 576       if (*dstp != tmp)
 577         {
 578           changed = 1;
 579           *dstp = tmp;
 580         }
 581     }
 582
 583   if (ssize2 > ssize1)
 584     {
 585       src1p = src2p;
 586       ssize1 = ssize2;
 587     }
 588
 589   for (; i < ssize1; i++, dstp++)
 590     {
 591       if (*dstp != 0)
 592         {
 593           changed = 1;
 594           *dstp = 0;
 595         }
 596     }
 597
 598   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
 599
 600   return changed;
 601 }
 602
 603
 604 static void
 605 vbitset_andn (dst, src1, src2)
 606      bitset dst;
 607      bitset src1;
 608      bitset src2;
 609 {
 610   unsigned int i;
 611   bitset_word *src1p;
 612   bitset_word *src2p;
 613   bitset_word *dstp;
 614   bitset_windex ssize1;
 615   bitset_windex ssize2;
 616   bitset_windex dsize;
 617
 618   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 619
 620   dsize = VBITSET_SIZE (dst);
 621   ssize1 = VBITSET_SIZE (src1);
 622   ssize2 = VBITSET_SIZE (src2);
 623   dstp = VBITSET_WORDS (dst);
 624   src1p = VBITSET_WORDS (src1);
 625   src2p = VBITSET_WORDS (src2);
 626
 627   for (i = 0; i < min (ssize1, ssize2); i++)
 628       *dstp++ = *src1p++ & ~(*src2p++);
 629
 630   if (ssize2 > ssize1)
 631     {
 632       for (; i < ssize2; i++)
 633         *dstp++ = 0;
 634
 635       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
 636     }
 637   else
 638     {
 639       for (; i < ssize1; i++)
 640         *dstp++ = *src1p++;
 641
 642       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
 643     }
 644 }
 645
 646
 647 static bool
 648 vbitset_andn_cmp (dst, src1, src2)
 649      bitset dst;
 650      bitset src1;
 651      bitset src2;
 652 {
 653   unsigned int i;
 654   int changed = 0;
 655   bitset_word *src1p;
 656   bitset_word *src2p;
 657   bitset_word *dstp;
 658   bitset_windex ssize1;
 659   bitset_windex ssize2;
 660   bitset_windex dsize;
 661
 662   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 663
 664   dsize = VBITSET_SIZE (dst);
 665   ssize1 = VBITSET_SIZE (src1);
 666   ssize2 = VBITSET_SIZE (src2);
 667   dstp = VBITSET_WORDS (dst);
 668   src1p = VBITSET_WORDS (src1);
 669   src2p = VBITSET_WORDS (src2);
 670
 671   for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
 672     {
 673       bitset_word tmp = *src1p++ & ~(*src2p++);
 674
 675       if (*dstp != tmp)
 676         {
 677           changed = 1;
 678           *dstp = tmp;
 679         }
 680     }
 681
 682   if (ssize2 > ssize1)
 683     {
 684       for (; i < ssize2; i++, dstp++)
 685         {
 686           if (*dstp != 0)
 687             {
 688               changed = 1;
 689               *dstp = 0;
 690             }
 691         }
 692
 693       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
 694     }
 695   else
 696     {
 697       for (; i < ssize1; i++, dstp++)
 698         {
 699           bitset_word tmp = *src1p++;
 700
 701           if (*dstp != tmp)
 702             {
 703               changed = 1;
 704               *dstp = tmp;
 705             }
 706         }
 707
 708       memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
 709     }
 710
 711   return changed;
 712 }
 713
 714
 715 static void
 716 vbitset_or (dst, src1, src2)
 717      bitset dst;
 718      bitset src1;
 719      bitset src2;
 720 {
 721   unsigned int i;
 722   bitset_word *src1p;
 723   bitset_word *src2p;
 724   bitset_word *dstp;
 725   bitset_windex ssize1;
 726   bitset_windex ssize2;
 727   bitset_windex dsize;
 728
 729   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 730
 731   dsize = VBITSET_SIZE (dst);
 732   ssize1 = VBITSET_SIZE (src1);
 733   ssize2 = VBITSET_SIZE (src2);
 734   dstp = VBITSET_WORDS (dst);
 735   src1p = VBITSET_WORDS (src1);
 736   src2p = VBITSET_WORDS (src2);
 737
 738   for (i = 0; i < min (ssize1, ssize2); i++)
 739       *dstp++ = *src1p++ | *src2p++;
 740
 741   if (ssize2 > ssize1)
 742     {
 743       src1p = src2p;
 744       ssize1 = ssize2;
 745     }
 746
 747   for (; i < ssize1; i++)
 748     *dstp++ = *src1p++;
 749
 750   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
 751 }
 752
 753
 754 static bool
 755 vbitset_or_cmp (dst, src1, src2)
 756      bitset dst;
 757      bitset src1;
 758      bitset src2;
 759 {
 760   unsigned int i;
 761   int changed = 0;
 762   bitset_word *src1p;
 763   bitset_word *src2p;
 764   bitset_word *dstp;
 765   bitset_windex ssize1;
 766   bitset_windex ssize2;
 767   bitset_windex dsize;
 768
 769   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 770
 771   dsize = VBITSET_SIZE (dst);
 772   ssize1 = VBITSET_SIZE (src1);
 773   ssize2 = VBITSET_SIZE (src2);
 774   dstp = VBITSET_WORDS (dst);
 775   src1p = VBITSET_WORDS (src1);
 776   src2p = VBITSET_WORDS (src2);
 777
 778   for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
 779     {
 780       bitset_word tmp = *src1p++ | *src2p++;
 781
 782       if (*dstp != tmp)
 783         {
 784           changed = 1;
 785           *dstp = tmp;
 786         }
 787     }
 788
 789   if (ssize2 > ssize1)
 790     {
 791       src1p = src2p;
 792       ssize1 = ssize2;
 793     }
 794
 795   for (; i < ssize1; i++, dstp++)
 796     {
 797       bitset_word tmp = *src1p++;
 798
 799       if (*dstp != tmp)
 800         {
 801           changed = 1;
 802           *dstp = tmp;
 803         }
 804     }
 805
 806   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
 807
 808   return changed;
 809 }
 810
 811
 812 static void
 813 vbitset_xor (dst, src1, src2)
 814      bitset dst;
 815      bitset src1;
 816      bitset src2;
 817 {
 818   unsigned int i;
 819   bitset_word *src1p;
 820   bitset_word *src2p;
 821   bitset_word *dstp;
 822   bitset_windex ssize1;
 823   bitset_windex ssize2;
 824   bitset_windex dsize;
 825
 826   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 827
 828   dsize = VBITSET_SIZE (dst);
 829   ssize1 = VBITSET_SIZE (src1);
 830   ssize2 = VBITSET_SIZE (src2);
 831   dstp = VBITSET_WORDS (dst);
 832   src1p = VBITSET_WORDS (src1);
 833   src2p = VBITSET_WORDS (src2);
 834
 835   for (i = 0; i < min (ssize1, ssize2); i++)
 836       *dstp++ = *src1p++ ^ *src2p++;
 837
 838   if (ssize2 > ssize1)
 839     {
 840       src1p = src2p;
 841       ssize1 = ssize2;
 842     }
 843
 844   for (; i < ssize1; i++)
 845     *dstp++ = *src1p++;
 846
 847   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
 848 }
 849
 850
 851 static bool
 852 vbitset_xor_cmp (dst, src1, src2)
 853      bitset dst;
 854      bitset src1;
 855      bitset src2;
 856 {
 857   unsigned int i;
 858   int changed = 0;
 859   bitset_word *src1p;
 860   bitset_word *src2p;
 861   bitset_word *dstp;
 862   bitset_windex ssize1;
 863   bitset_windex ssize2;
 864   bitset_windex dsize;
 865
 866   vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
 867
 868   dsize = VBITSET_SIZE (dst);
 869   ssize1 = VBITSET_SIZE (src1);
 870   ssize2 = VBITSET_SIZE (src2);
 871   dstp = VBITSET_WORDS (dst);
 872   src1p = VBITSET_WORDS (src1);
 873   src2p = VBITSET_WORDS (src2);
 874
 875   for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
 876     {
 877       bitset_word tmp = *src1p++ ^ *src2p++;
 878
 879       if (*dstp != tmp)
 880         {
 881           changed = 1;
 882           *dstp = tmp;
 883         }
 884     }
 885
 886   if (ssize2 > ssize1)
 887     {
 888       src1p = src2p;
 889       ssize1 = ssize2;
 890     }
 891
 892   for (; i < ssize1; i++, dstp++)
 893     {
 894       bitset_word tmp = *src1p++;
 895
 896       if (*dstp != tmp)
 897         {
 898           changed = 1;
 899           *dstp = tmp;
 900         }
 901     }
 902
 903   memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
 904
 905   return changed;
 906 }
 907
 908
 909 /* FIXME, these operations need fixing for different size
 910    bitsets.  */
 911
 912 static void
 913 vbitset_and_or (dst, src1, src2, src3)
 914      bitset dst;
 915      bitset src1;
 916      bitset src2;
 917      bitset src3;
 918 {
 919   unsigned int i;
 920   bitset_word *src1p;
 921   bitset_word *src2p;
 922   bitset_word *src3p;
 923   bitset_word *dstp;
 924   bitset_windex size;
 925
 926   if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
 927       || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
 928     {
 929       bitset_and_or_ (dst, src1, src2, src3);
 930       return;
 931     }
 932
 933   vbitset_resize (dst, BITSET_NBITS_ (src1));
 934
 935   src1p = VBITSET_WORDS (src1);
 936   src2p = VBITSET_WORDS (src2);
 937   src3p = VBITSET_WORDS (src3);
 938   dstp = VBITSET_WORDS (dst);
 939   size = VBITSET_SIZE (dst);
 940
 941   for (i = 0; i < size; i++)
 942       *dstp++ = (*src1p++ & *src2p++) | *src3p++;
 943 }
 944
 945
 946 static bool
 947 vbitset_and_or_cmp (dst, src1, src2, src3)
 948      bitset dst;
 949      bitset src1;
 950      bitset src2;
 951      bitset src3;
 952 {
 953   unsigned int i;
 954   int changed = 0;
 955   bitset_word *src1p;
 956   bitset_word *src2p;
 957   bitset_word *src3p;
 958   bitset_word *dstp;
 959   bitset_windex size;
 960
 961   if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
 962       || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
 963     return bitset_and_or_cmp_ (dst, src1, src2, src3);
 964
 965   vbitset_resize (dst, BITSET_NBITS_ (src1));
 966
 967   src1p = VBITSET_WORDS (src1);
 968   src2p = VBITSET_WORDS (src2);
 969   src3p = VBITSET_WORDS (src3);
 970   dstp = VBITSET_WORDS (dst);
 971   size = VBITSET_SIZE (dst);
 972
 973   for (i = 0; i < size; i++, dstp++)
 974     {
 975       bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
 976
 977       if (*dstp != tmp)
 978         {
 979           changed = 1;
 980           *dstp = tmp;
 981         }
 982     }
 983   return changed;
 984 }
 985
 986
 987 static void
 988 vbitset_andn_or (dst, src1, src2, src3)
 989      bitset dst;
 990      bitset src1;
 991      bitset src2;
 992      bitset src3;
 993 {
 994   unsigned int i;
 995   bitset_word *src1p;
 996   bitset_word *src2p;
 997   bitset_word *src3p;
 998   bitset_word *dstp;
 999   bitset_windex size;
1000
1001   if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
1002       || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
1003     {
1004       bitset_andn_or_ (dst, src1, src2, src3);
1005       return;
1006     }
1007
1008   vbitset_resize (dst, BITSET_NBITS_ (src1));
1009
1010   src1p = VBITSET_WORDS (src1);
1011   src2p = VBITSET_WORDS (src2);
1012   src3p = VBITSET_WORDS (src3);
1013   dstp = VBITSET_WORDS (dst);
1014   size = VBITSET_SIZE (dst);
1015
1016   for (i = 0; i < size; i++)
1017       *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
1018 }
1019
1020
1021 static bool
1022 vbitset_andn_or_cmp (dst, src1, src2, src3)
1023      bitset dst;
1024      bitset src1;
1025      bitset src2;
1026      bitset src3;
1027 {
1028   unsigned int i;
1029   int changed = 0;
1030   bitset_word *src1p;
1031   bitset_word *src2p;
1032   bitset_word *src3p;
1033   bitset_word *dstp;
1034   bitset_windex size;
1035
1036   if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
1037       || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
1038     return bitset_andn_or_cmp_ (dst, src1, src2, src3);
1039
1040   vbitset_resize (dst, BITSET_NBITS_ (src1));
1041
1042   src1p = VBITSET_WORDS (src1);
1043   src2p = VBITSET_WORDS (src2);
1044   src3p = VBITSET_WORDS (src3);
1045   dstp = VBITSET_WORDS (dst);
1046   size = VBITSET_SIZE (dst);
1047
1048   for (i = 0; i < size; i++, dstp++)
1049     {
1050       bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
1051
1052       if (*dstp != tmp)
1053         {
1054           changed = 1;
1055           *dstp = tmp;
1056         }
1057     }
1058   return changed;
1059 }
1060
1061
1062 static void
1063 vbitset_or_and (dst, src1, src2, src3)
1064      bitset dst;
1065      bitset src1;
1066      bitset src2;
1067      bitset src3;
1068 {
1069   unsigned int i;
1070   bitset_word *src1p;
1071   bitset_word *src2p;
1072   bitset_word *src3p;
1073   bitset_word *dstp;
1074   bitset_windex size;
1075
1076   if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
1077       || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
1078     {
1079       bitset_or_and_ (dst, src1, src2, src3);
1080       return;
1081     }
1082
1083   vbitset_resize (dst, BITSET_NBITS_ (src1));
1084
1085   src1p = VBITSET_WORDS (src1);
1086   src2p = VBITSET_WORDS (src2);
1087   src3p = VBITSET_WORDS (src3);
1088   dstp = VBITSET_WORDS (dst);
1089   size = VBITSET_SIZE (dst);
1090
1091   for (i = 0; i < size; i++)
1092       *dstp++ = (*src1p++ | *src2p++) & *src3p++;
1093 }
1094
1095
1096 static bool
1097 vbitset_or_and_cmp (dst, src1, src2, src3)
1098      bitset dst;
1099      bitset src1;
1100      bitset src2;
1101      bitset src3;
1102 {
1103   unsigned int i;
1104   int changed = 0;
1105   bitset_word *src1p;
1106   bitset_word *src2p;
1107   bitset_word *src3p;
1108   bitset_word *dstp;
1109   bitset_windex size;
1110
1111   if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
1112       || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
1113     return bitset_or_and_cmp_ (dst, src1, src2, src3);
1114
1115   vbitset_resize (dst, BITSET_NBITS_ (src1));
1116
1117   src1p = VBITSET_WORDS (src1);
1118   src2p = VBITSET_WORDS (src2);
1119   src3p = VBITSET_WORDS (src3);
1120   dstp = VBITSET_WORDS (dst);
1121   size = VBITSET_SIZE (dst);
1122
1123   for (i = 0; i < size; i++, dstp++)
1124     {
1125       bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
1126
1127       if (*dstp != tmp)
1128         {
1129           changed = 1;
1130           *dstp = tmp;
1131         }
1132     }
1133   return changed;
1134 }
1135
1136
1137 void
1138 vbitset_copy (dst, src)
1139      bitset dst;
1140      bitset src;
1141 {
1142   if (BITSET_COMPATIBLE_ (dst, src))
1143       vbitset_copy1 (dst, src);
1144   else
1145       bitset_copy_ (dst, src);
1146 }
1147
1148
1149 /* Vector of operations for multiple word bitsets.  */
1150 struct bitset_vtable vbitset_vtable = {
1151   vbitset_set,
1152   vbitset_reset,
1153   bitset_toggle_,
1154   vbitset_test,
1155   vbitset_resize,
1156   bitset_size_,
1157   bitset_count_,
1158   vbitset_empty_p,
1159   vbitset_ones,
1160   vbitset_zero,
1161   vbitset_copy,
1162   vbitset_disjoint_p,
1163   vbitset_equal_p,
1164   vbitset_not,
1165   vbitset_subset_p,
1166   vbitset_and,
1167   vbitset_and_cmp,
1168   vbitset_andn,
1169   vbitset_andn_cmp,
1170   vbitset_or,
1171   vbitset_or_cmp,
1172   vbitset_xor,
1173   vbitset_xor_cmp,
1174   vbitset_and_or,
1175   vbitset_and_or_cmp,
1176   vbitset_andn_or,
1177   vbitset_andn_or_cmp,
1178   vbitset_or_and,
1179   vbitset_or_and_cmp,
1180   vbitset_list,
1181   vbitset_list_reverse,
1182   NULL,
1183   BITSET_VARRAY
1184 };
1185
1186
1187 size_t
1188 vbitset_bytes (n_bits)
1189      bitset_bindex n_bits ATTRIBUTE_UNUSED;
1190 {
1191   return sizeof (struct vbitset_struct);
1192 }
1193
1194
1195 bitset
1196 vbitset_init (bset, n_bits)
1197      bitset bset;
1198      bitset_bindex n_bits;
1199 {
1200   bset->b.vtable = &vbitset_vtable;
1201
1202   bset->b.cindex = 0;
1203
1204   VBITSET_SIZE (bset) = 0;
1205   vbitset_resize (bset, n_bits);
1206   return bset;
1207 }