lib/vbitset.c

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