lib/vbitset.c

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