lib/vbitset.c

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