lib/bitset/vector.c

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