lib/vbitset.c

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