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