maint/gnulib/lib/bitset/vector.c

/* */
This source file includes following definitions.
vbitset_resize
vbitset_set
vbitset_reset
vbitset_test
vbitset_list_reverse
vbitset_list
vbitset_unused_clear
vbitset_ones
vbitset_zero
vbitset_empty_p
vbitset_copy1
vbitset_not
vbitset_equal_p
vbitset_subset_p
vbitset_disjoint_p
vbitset_and
vbitset_and_cmp
vbitset_andn
vbitset_andn_cmp
vbitset_or
vbitset_or_cmp
vbitset_xor
vbitset_xor_cmp
vbitset_and_or
vbitset_and_or_cmp
vbitset_andn_or
vbitset_andn_or_cmp
vbitset_or_and
vbitset_or_and_cmp
vbitset_copy
vbitset_free
vbitset_bytes
vbitset_init
   1 /* Variable array bitsets.
   2 
   3    Copyright (C) 2002-2006, 2009-2015, 2018-2021 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 (MAYBE_UNUSED bitset dst, MAYBE_UNUSED bitset_bindex bitno)
     /*  */
 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 (MAYBE_UNUSED bitset src,
     /*  */
 139               MAYBE_UNUSED bitset_bindex bitno)
 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 (MAYBE_UNUSED bitset_bindex n_bits)
     /*  */
 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 }
/* */
root/maint/gnulib/lib/bitset/vector.c

DEFINITIONS
