lib/abitset.c

   1 /* Array bitsets.
   2    Copyright (C) 2002 Free Software Foundation, Inc.
   3    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18 */
  19
  20 #ifdef HAVE_CONFIG_H
  21 #include "config.h"
  22 #endif
  23
  24 #include "abitset.h"
  25 #include <stddef.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28
  29 /* This file implements fixed size bitsets stored as an array
  30    of words.  Any unused bits in the last word must be zero.  */
  31
  32 static void abitset_unused_clear PARAMS ((bitset));
  33 static void abitset_ones PARAMS ((bitset));
  34 static void abitset_zero PARAMS ((bitset));
  35 static int abitset_empty_p PARAMS ((bitset));
  36 static void abitset_copy1 PARAMS ((bitset, bitset));
  37 static void abitset_not PARAMS ((bitset, bitset));
  38 static int abitset_equal_p PARAMS ((bitset, bitset));
  39 static int abitset_subset_p PARAMS ((bitset, bitset));
  40 static int abitset_disjoint_p PARAMS ((bitset, bitset));
  41 static void abitset_and PARAMS ((bitset, bitset, bitset));
  42 static int abitset_and_cmp PARAMS ((bitset, bitset, bitset));
  43 static void abitset_andn PARAMS ((bitset, bitset, bitset));
  44 static int abitset_andn_cmp PARAMS ((bitset, bitset, bitset));
  45 static void abitset_or PARAMS ((bitset, bitset, bitset));
  46 static int abitset_or_cmp PARAMS ((bitset, bitset, bitset));
  47 static void abitset_xor PARAMS ((bitset, bitset, bitset));
  48 static int abitset_xor_cmp PARAMS ((bitset, bitset, bitset));
  49 static void abitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
  50 static int abitset_and_or_cmp PARAMS ((bitset, bitset, bitset, bitset));
  51 static void abitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
  52 static int abitset_andn_or_cmp PARAMS ((bitset, bitset, bitset, bitset));
  53 static void abitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
  54 static int abitset_or_and_cmp PARAMS ((bitset, bitset, bitset, bitset));
  55 static void abitset_copy PARAMS ((bitset, bitset));
  56
  57 static bitset_bindex abitset_small_list PARAMS ((bitset, bitset_bindex *,
  58                                                  bitset_bindex,
  59                                                  bitset_bindex *));
  60
  61 static void abitset_set PARAMS ((bitset, bitset_bindex));
  62 static void abitset_reset PARAMS ((bitset, bitset_bindex));
  63 static int abitset_test PARAMS ((bitset, bitset_bindex));
  64 static bitset_bindex abitset_size PARAMS ((bitset));
  65 static bitset_bindex abitset_list PARAMS ((bitset, bitset_bindex *,
  66                                            bitset_bindex, bitset_bindex *));
  67 static bitset_bindex abitset_list_reverse
  68 PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
  69
  70 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
  71 #define ABITSET_WORDS(X) ((X)->a.words)
  72 #define ABITSET_N_BITS(X) ((X)->a.n_bits)
  73
  74
  75 /* Return size in bits of bitset SRC.  */
  76 static bitset_bindex
  77 abitset_size (src)
  78      bitset src;
  79 {
  80   return ABITSET_N_BITS (src);
  81 }
  82
  83
  84 /* Find list of up to NUM bits set in BSET starting from and including
  85  *NEXT and store in array LIST.  Return with actual number of bits
  86  found and with *NEXT indicating where search stopped.  */
  87 static bitset_bindex
  88 abitset_small_list (src, list, num, next)
  89      bitset src;
  90      bitset_bindex *list;
  91      bitset_bindex num;
  92      bitset_bindex *next;
  93 {
  94   bitset_bindex bitno;
  95   bitset_bindex count;
  96   bitset_windex size;
  97   bitset_word word;
  98
  99   word = ABITSET_WORDS (src)[0];
 100
 101   /* Short circuit common case.  */
 102   if (!word)
 103     return 0;
 104
 105   size = ABITSET_N_BITS (src);
 106   bitno = *next;
 107   if (bitno >= size)
 108     return 0;
 109
 110   word >>= bitno;
 111
 112   /* If num is 1, we could speed things up with a binary search
 113      of the word of interest.  */
 114
 115   if (num >= BITSET_WORD_BITS)
 116     {
 117       for (count = 0; word; bitno++)
 118         {
 119           if (word & 1)
 120             list[count++] = bitno;
 121           word >>= 1;
 122         }
 123     }
 124   else
 125     {
 126       for (count = 0; word; bitno++)
 127         {
 128           if (word & 1)
 129             {
 130               list[count++] = bitno;
 131               if (count >= num)
 132                 {
 133                   bitno++;
 134                   break;
 135                 }
 136             }
 137           word >>= 1;
 138         }
 139     }
 140
 141   *next = bitno;
 142   return count;
 143 }
 144
 145
 146 /* Set bit BITNO in bitset DST.  */
 147 static void
 148 abitset_set (dst, bitno)
 149      bitset dst ATTRIBUTE_UNUSED;
 150      bitset_bindex bitno ATTRIBUTE_UNUSED;
 151 {
 152   /* This should never occur for abitsets since we should always
 153      hit the cache.  */
 154   abort ();
 155 }
 156
 157
 158 /* Reset bit BITNO in bitset DST.  */
 159 static void
 160 abitset_reset (dst, bitno)
 161      bitset dst ATTRIBUTE_UNUSED;
 162      bitset_bindex bitno ATTRIBUTE_UNUSED;
 163 {
 164   /* This should never occur for abitsets since we should always
 165      hit the cache.  */
 166   abort ();
 167 }
 168
 169
 170 /* Test bit BITNO in bitset SRC.  */
 171 static int
 172 abitset_test (src, bitno)
 173      bitset src ATTRIBUTE_UNUSED;
 174      bitset_bindex bitno ATTRIBUTE_UNUSED;
 175 {
 176   /* This should never occur for abitsets since we should always
 177      hit the cache.  */
 178   abort ();
 179   return 0;
 180 }
 181
 182
 183 /* Find list of up to NUM bits set in BSET in reverse order, starting
 184    from and including NEXT and store in array LIST.  Return with
 185    actual number of bits found and with *NEXT indicating where search
 186    stopped.  */
 187 static bitset_bindex
 188 abitset_list_reverse (src, list, num, next)
 189      bitset src;
 190      bitset_bindex *list;
 191      bitset_bindex num;
 192      bitset_bindex *next;
 193 {
 194   bitset_bindex bitno;
 195   bitset_bindex rbitno;
 196   bitset_bindex count;
 197   bitset_windex windex;
 198   unsigned int bitcnt;
 199   bitset_bindex bitoff;
 200   bitset_word *srcp = ABITSET_WORDS (src);
 201   bitset_bindex n_bits = ABITSET_N_BITS (src);
 202
 203   rbitno = *next;
 204
 205   /* If num is 1, we could speed things up with a binary search
 206      of the word of interest.  */
 207
 208   if (rbitno >= n_bits)
 209     return 0;
 210
 211   count = 0;
 212
 213   bitno = n_bits - (rbitno + 1);
 214
 215   windex = bitno / BITSET_WORD_BITS;
 216   bitcnt = bitno % BITSET_WORD_BITS;
 217   bitoff = windex * BITSET_WORD_BITS;
 218
 219   do
 220     {
 221       bitset_word word;
 222
 223       word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
 224       for (; word; bitcnt--)
 225         {
 226           if (word & BITSET_MSB)
 227             {
 228               list[count++] = bitoff + bitcnt;
 229               if (count >= num)
 230                 {
 231                   *next = n_bits - (bitoff + bitcnt);
 232                   return count;
 233                 }
 234             }
 235           word <<= 1;
 236         }
 237       bitoff -= BITSET_WORD_BITS;
 238       bitcnt = BITSET_WORD_BITS - 1;
 239     }
 240   while (windex--);
 241
 242   *next = n_bits - (bitoff + 1);
 243   return count;
 244 }
 245
 246
 247 /* Find list of up to NUM bits set in BSET starting from and including
 248  *NEXT and store in array LIST.  Return with actual number of bits
 249  found and with *NEXT indicating where search stopped.  */
 250 static bitset_bindex
 251 abitset_list (src, list, num, next)
 252      bitset src;
 253      bitset_bindex *list;
 254      bitset_bindex num;
 255      bitset_bindex *next;
 256 {
 257   bitset_bindex bitno;
 258   bitset_bindex count;
 259   bitset_windex windex;
 260   bitset_bindex bitoff;
 261   bitset_windex size = src->b.csize;
 262   bitset_word *srcp = ABITSET_WORDS (src);
 263   bitset_word word;
 264
 265   bitno = *next;
 266
 267   count = 0;
 268   if (!bitno)
 269     {
 270       /* Many bitsets are zero, so make this common case fast.  */
 271       for (windex = 0; windex < size && !srcp[windex]; windex++)
 272         continue;
 273       if (windex >= size)
 274         return 0;
 275
 276       /* If num is 1, we could speed things up with a binary search
 277          of the current word.  */
 278
 279       bitoff = windex * BITSET_WORD_BITS;
 280     }
 281   else
 282     {
 283       if (bitno >= ABITSET_N_BITS (src))
 284         return 0;
 285
 286       windex = bitno / BITSET_WORD_BITS;
 287       bitno = bitno % BITSET_WORD_BITS;
 288
 289       if (bitno)
 290         {
 291           /* Handle the case where we start within a word.
 292              Most often, this is executed with large bitsets
 293              with many set bits where we filled the array
 294              on the previous call to this function.  */
 295
 296           bitoff = windex * BITSET_WORD_BITS;
 297           word = srcp[windex] >> bitno;
 298           for (bitno = bitoff + bitno; word; bitno++)
 299             {
 300               if (word & 1)
 301                 {
 302                   list[count++] = bitno;
 303                   if (count >= num)
 304                     {
 305                       *next = bitno + 1;
 306                       return count;
 307                     }
 308                 }
 309               word >>= 1;
 310             }
 311           windex++;
 312         }
 313       bitoff = windex * BITSET_WORD_BITS;
 314     }
 315
 316   for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
 317     {
 318       if (!(word = srcp[windex]))
 319         continue;
 320
 321       if ((count + BITSET_WORD_BITS) < num)
 322         {
 323           for (bitno = bitoff; word; bitno++)
 324             {
 325               if (word & 1)
 326                 list[count++] = bitno;
 327               word >>= 1;
 328             }
 329         }
 330       else
 331         {
 332           for (bitno = bitoff; word; bitno++)
 333             {
 334               if (word & 1)
 335                 {
 336                   list[count++] = bitno;
 337                   if (count >= num)
 338                     {
 339                       *next = bitno + 1;
 340                       return count;
 341                     }
 342                 }
 343               word >>= 1;
 344             }
 345         }
 346     }
 347
 348   *next = bitoff;
 349   return count;
 350 }
 351
 352
 353 /* Ensure that any unused bits within the last word are clear.  */
 354 static inline void
 355 abitset_unused_clear (dst)
 356      bitset dst;
 357 {
 358   unsigned int last_bit;
 359
 360   last_bit = ABITSET_N_BITS (dst) % BITSET_WORD_BITS;
 361   if (last_bit)
 362     ABITSET_WORDS (dst)[dst->b.csize - 1] &=
 363       ((bitset_word) 1 << last_bit) - 1;
 364 }
 365
 366
 367 static void
 368 abitset_ones (dst)
 369      bitset dst;
 370 {
 371   bitset_word *dstp = ABITSET_WORDS (dst);
 372   size_t bytes;
 373
 374   bytes = sizeof (bitset_word) * dst->b.csize;
 375
 376   memset (dstp, -1, bytes);
 377   abitset_unused_clear (dst);
 378 }
 379
 380
 381 static void
 382 abitset_zero (dst)
 383      bitset dst;
 384 {
 385   bitset_word *dstp = ABITSET_WORDS (dst);
 386   size_t bytes;
 387
 388   bytes = sizeof (bitset_word) * dst->b.csize;
 389
 390   memset (dstp, 0, bytes);
 391 }
 392
 393
 394 static int
 395 abitset_empty_p (dst)
 396      bitset dst;
 397 {
 398   bitset_windex i;
 399   bitset_word *dstp = ABITSET_WORDS (dst);
 400
 401   for (i = 0; i < dst->b.csize; i++)
 402     if (dstp[i])
 403       return 0;
 404
 405   return 1;
 406 }
 407
 408
 409 static void
 410 abitset_copy1 (dst, src)
 411      bitset dst;
 412      bitset src;
 413 {
 414   bitset_word *srcp = ABITSET_WORDS (src);
 415   bitset_word *dstp = ABITSET_WORDS (dst);
 416   bitset_windex size = dst->b.csize;
 417
 418   if (srcp == dstp)
 419       return;
 420   memcpy (dstp, srcp, sizeof (bitset_word) * size);
 421 }
 422
 423
 424 static void
 425 abitset_not (dst, src)
 426      bitset dst;
 427      bitset src;
 428 {
 429   bitset_windex i;
 430   bitset_word *srcp = ABITSET_WORDS (src);
 431   bitset_word *dstp = ABITSET_WORDS (dst);
 432   bitset_windex size = dst->b.csize;
 433
 434   for (i = 0; i < size; i++)
 435       *dstp++ = ~(*srcp++);
 436   abitset_unused_clear (dst);
 437 }
 438
 439
 440 static int
 441 abitset_equal_p (dst, src)
 442      bitset dst;
 443      bitset src;
 444 {
 445   bitset_windex i;
 446   bitset_word *srcp = ABITSET_WORDS (src);
 447   bitset_word *dstp = ABITSET_WORDS (dst);
 448   bitset_windex size = dst->b.csize;
 449
 450   for (i = 0; i < size; i++)
 451       if (*srcp++ != *dstp++)
 452           return 0;
 453   return 1;
 454 }
 455
 456
 457 static int
 458 abitset_subset_p (dst, src)
 459      bitset dst;
 460      bitset src;
 461 {
 462   bitset_windex i;
 463   bitset_word *srcp = ABITSET_WORDS (src);
 464   bitset_word *dstp = ABITSET_WORDS (dst);
 465   bitset_windex size = dst->b.csize;
 466
 467   for (i = 0; i < size; i++, dstp++, srcp++)
 468       if (*dstp != (*srcp | *dstp))
 469           return 0;
 470   return 1;
 471 }
 472
 473
 474 static int
 475 abitset_disjoint_p (dst, src)
 476      bitset dst;
 477      bitset src;
 478 {
 479   bitset_windex i;
 480   bitset_word *srcp = ABITSET_WORDS (src);
 481   bitset_word *dstp = ABITSET_WORDS (dst);
 482   bitset_windex size = dst->b.csize;
 483
 484   for (i = 0; i < size; i++)
 485       if (*srcp++ & *dstp++)
 486           return 0;
 487
 488   return 1;
 489 }
 490
 491
 492 static void
 493 abitset_and (dst, src1, src2)
 494      bitset dst;
 495      bitset src1;
 496      bitset src2;
 497 {
 498   bitset_windex i;
 499   bitset_word *src1p = ABITSET_WORDS (src1);
 500   bitset_word *src2p = ABITSET_WORDS (src2);
 501   bitset_word *dstp = ABITSET_WORDS (dst);
 502   bitset_windex size = dst->b.csize;
 503
 504   for (i = 0; i < size; i++)
 505       *dstp++ = *src1p++ & *src2p++;
 506 }
 507
 508
 509 static int
 510 abitset_and_cmp (dst, src1, src2)
 511      bitset dst;
 512      bitset src1;
 513      bitset src2;
 514 {
 515   bitset_windex i;
 516   int changed = 0;
 517   bitset_word *src1p = ABITSET_WORDS (src1);
 518   bitset_word *src2p = ABITSET_WORDS (src2);
 519   bitset_word *dstp = ABITSET_WORDS (dst);
 520   bitset_windex size = dst->b.csize;
 521
 522   for (i = 0; i < size; i++, dstp++)
 523     {
 524       bitset_word tmp = *src1p++ & *src2p++;
 525
 526       if (*dstp != tmp)
 527         {
 528           changed = 1;
 529           *dstp = tmp;
 530         }
 531     }
 532   return changed;
 533 }
 534
 535
 536 static void
 537 abitset_andn (dst, src1, src2)
 538      bitset dst;
 539      bitset src1;
 540      bitset src2;
 541 {
 542   bitset_windex i;
 543   bitset_word *src1p = ABITSET_WORDS (src1);
 544   bitset_word *src2p = ABITSET_WORDS (src2);
 545   bitset_word *dstp = ABITSET_WORDS (dst);
 546   bitset_windex size = dst->b.csize;
 547
 548   for (i = 0; i < size; i++)
 549       *dstp++ = *src1p++ & ~(*src2p++);
 550 }
 551
 552
 553 static int
 554 abitset_andn_cmp (dst, src1, src2)
 555      bitset dst;
 556      bitset src1;
 557      bitset src2;
 558 {
 559   bitset_windex i;
 560   int changed = 0;
 561   bitset_word *src1p = ABITSET_WORDS (src1);
 562   bitset_word *src2p = ABITSET_WORDS (src2);
 563   bitset_word *dstp = ABITSET_WORDS (dst);
 564   bitset_windex size = dst->b.csize;
 565
 566   for (i = 0; i < size; i++, dstp++)
 567     {
 568       bitset_word tmp = *src1p++ & ~(*src2p++);
 569
 570       if (*dstp != tmp)
 571         {
 572           changed = 1;
 573           *dstp = tmp;
 574         }
 575     }
 576   return changed;
 577 }
 578
 579
 580 static void
 581 abitset_or (dst, src1, src2)
 582      bitset dst;
 583      bitset src1;
 584      bitset src2;
 585 {
 586   bitset_windex i;
 587   bitset_word *src1p = ABITSET_WORDS (src1);
 588   bitset_word *src2p = ABITSET_WORDS (src2);
 589   bitset_word *dstp = ABITSET_WORDS (dst);
 590   bitset_windex size = dst->b.csize;
 591
 592   for (i = 0; i < size; i++)
 593       *dstp++ = *src1p++ | *src2p++;
 594 }
 595
 596
 597 static int
 598 abitset_or_cmp (dst, src1, src2)
 599      bitset dst;
 600      bitset src1;
 601      bitset src2;
 602 {
 603   bitset_windex i;
 604   int changed = 0;
 605   bitset_word *src1p = ABITSET_WORDS (src1);
 606   bitset_word *src2p = ABITSET_WORDS (src2);
 607   bitset_word *dstp = ABITSET_WORDS (dst);
 608   bitset_windex size = dst->b.csize;
 609
 610   for (i = 0; i < size; i++, dstp++)
 611     {
 612       bitset_word tmp = *src1p++ | *src2p++;
 613
 614       if (*dstp != tmp)
 615         {
 616           changed = 1;
 617           *dstp = tmp;
 618         }
 619     }
 620   return changed;
 621 }
 622
 623
 624 static void
 625 abitset_xor (dst, src1, src2)
 626      bitset dst;
 627      bitset src1;
 628      bitset src2;
 629 {
 630   bitset_windex i;
 631   bitset_word *src1p = ABITSET_WORDS (src1);
 632   bitset_word *src2p = ABITSET_WORDS (src2);
 633   bitset_word *dstp = ABITSET_WORDS (dst);
 634   bitset_windex size = dst->b.csize;
 635
 636   for (i = 0; i < size; i++)
 637       *dstp++ = *src1p++ ^ *src2p++;
 638 }
 639
 640
 641 static int
 642 abitset_xor_cmp (dst, src1, src2)
 643      bitset dst;
 644      bitset src1;
 645      bitset src2;
 646 {
 647   bitset_windex i;
 648   int changed = 0;
 649   bitset_word *src1p = ABITSET_WORDS (src1);
 650   bitset_word *src2p = ABITSET_WORDS (src2);
 651   bitset_word *dstp = ABITSET_WORDS (dst);
 652   bitset_windex size = dst->b.csize;
 653
 654   for (i = 0; i < size; i++, dstp++)
 655     {
 656       bitset_word tmp = *src1p++ ^ *src2p++;
 657
 658       if (*dstp != tmp)
 659         {
 660           changed = 1;
 661           *dstp = tmp;
 662         }
 663     }
 664   return changed;
 665 }
 666
 667
 668 static void
 669 abitset_and_or (dst, src1, src2, src3)
 670      bitset dst;
 671      bitset src1;
 672      bitset src2;
 673      bitset src3;
 674 {
 675   bitset_windex i;
 676   bitset_word *src1p = ABITSET_WORDS (src1);
 677   bitset_word *src2p = ABITSET_WORDS (src2);
 678   bitset_word *src3p = ABITSET_WORDS (src3);
 679   bitset_word *dstp = ABITSET_WORDS (dst);
 680   bitset_windex size = dst->b.csize;
 681
 682   for (i = 0; i < size; i++)
 683       *dstp++ = (*src1p++ & *src2p++) | *src3p++;
 684 }
 685
 686
 687 static int
 688 abitset_and_or_cmp (dst, src1, src2, src3)
 689      bitset dst;
 690      bitset src1;
 691      bitset src2;
 692      bitset src3;
 693 {
 694   bitset_windex i;
 695   int changed = 0;
 696   bitset_word *src1p = ABITSET_WORDS (src1);
 697   bitset_word *src2p = ABITSET_WORDS (src2);
 698   bitset_word *src3p = ABITSET_WORDS (src3);
 699   bitset_word *dstp = ABITSET_WORDS (dst);
 700   bitset_windex size = dst->b.csize;
 701
 702   for (i = 0; i < size; i++, dstp++)
 703     {
 704       bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
 705
 706       if (*dstp != tmp)
 707         {
 708           changed = 1;
 709           *dstp = tmp;
 710         }
 711     }
 712   return changed;
 713 }
 714
 715
 716 static void
 717 abitset_andn_or (dst, src1, src2, src3)
 718      bitset dst;
 719      bitset src1;
 720      bitset src2;
 721      bitset src3;
 722 {
 723   bitset_windex i;
 724   bitset_word *src1p = ABITSET_WORDS (src1);
 725   bitset_word *src2p = ABITSET_WORDS (src2);
 726   bitset_word *src3p = ABITSET_WORDS (src3);
 727   bitset_word *dstp = ABITSET_WORDS (dst);
 728   bitset_windex size = dst->b.csize;
 729
 730   for (i = 0; i < size; i++)
 731       *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
 732 }
 733
 734
 735 static int
 736 abitset_andn_or_cmp (dst, src1, src2, src3)
 737      bitset dst;
 738      bitset src1;
 739      bitset src2;
 740      bitset src3;
 741 {
 742   bitset_windex i;
 743   int changed = 0;
 744   bitset_word *src1p = ABITSET_WORDS (src1);
 745   bitset_word *src2p = ABITSET_WORDS (src2);
 746   bitset_word *src3p = ABITSET_WORDS (src3);
 747   bitset_word *dstp = ABITSET_WORDS (dst);
 748   bitset_windex size = dst->b.csize;
 749
 750   for (i = 0; i < size; i++, dstp++)
 751     {
 752       bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
 753
 754       if (*dstp != tmp)
 755         {
 756           changed = 1;
 757           *dstp = tmp;
 758         }
 759     }
 760   return changed;
 761 }
 762
 763
 764 static void
 765 abitset_or_and (dst, src1, src2, src3)
 766      bitset dst;
 767      bitset src1;
 768      bitset src2;
 769      bitset src3;
 770 {
 771   bitset_windex i;
 772   bitset_word *src1p = ABITSET_WORDS (src1);
 773   bitset_word *src2p = ABITSET_WORDS (src2);
 774   bitset_word *src3p = ABITSET_WORDS (src3);
 775   bitset_word *dstp = ABITSET_WORDS (dst);
 776   bitset_windex size = dst->b.csize;
 777
 778   for (i = 0; i < size; i++)
 779       *dstp++ = (*src1p++ | *src2p++) & *src3p++;
 780 }
 781
 782
 783 static int
 784 abitset_or_and_cmp (dst, src1, src2, src3)
 785      bitset dst;
 786      bitset src1;
 787      bitset src2;
 788      bitset src3;
 789 {
 790   bitset_windex i;
 791   int changed = 0;
 792   bitset_word *src1p = ABITSET_WORDS (src1);
 793   bitset_word *src2p = ABITSET_WORDS (src2);
 794   bitset_word *src3p = ABITSET_WORDS (src3);
 795   bitset_word *dstp = ABITSET_WORDS (dst);
 796   bitset_windex size = dst->b.csize;
 797
 798   for (i = 0; i < size; i++, dstp++)
 799     {
 800       bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
 801
 802       if (*dstp != tmp)
 803         {
 804           changed = 1;
 805           *dstp = tmp;
 806         }
 807     }
 808   return changed;
 809 }
 810
 811
 812 static void
 813 abitset_copy (dst, src)
 814      bitset dst;
 815      bitset src;
 816 {
 817   if (BITSET_COMPATIBLE_ (dst, src))
 818       abitset_copy1 (dst, src);
 819   else
 820       bitset_copy_ (dst, src);
 821 }
 822
 823
 824 /* Vector of operations for single word bitsets.  */
 825 struct bitset_vtable abitset_small_vtable = {
 826   abitset_set,
 827   abitset_reset,
 828   bitset_toggle_,
 829   abitset_test,
 830   abitset_size,
 831   bitset_count_,
 832   abitset_empty_p,
 833   abitset_ones,
 834   abitset_zero,
 835   abitset_copy,
 836   abitset_disjoint_p,
 837   abitset_equal_p,
 838   abitset_not,
 839   abitset_subset_p,
 840   abitset_and,
 841   abitset_and_cmp,
 842   abitset_andn,
 843   abitset_andn_cmp,
 844   abitset_or,
 845   abitset_or_cmp,
 846   abitset_xor,
 847   abitset_xor_cmp,
 848   abitset_and_or,
 849   abitset_and_or_cmp,
 850   abitset_andn_or,
 851   abitset_andn_or_cmp,
 852   abitset_or_and,
 853   abitset_or_and_cmp,
 854   abitset_small_list,
 855   abitset_list_reverse,
 856   NULL,
 857   BITSET_ARRAY
 858 };
 859
 860
 861 /* Vector of operations for multiple word bitsets.  */
 862 struct bitset_vtable abitset_vtable = {
 863   abitset_set,
 864   abitset_reset,
 865   bitset_toggle_,
 866   abitset_test,
 867   abitset_size,
 868   bitset_count_,
 869   abitset_empty_p,
 870   abitset_ones,
 871   abitset_zero,
 872   abitset_copy,
 873   abitset_disjoint_p,
 874   abitset_equal_p,
 875   abitset_not,
 876   abitset_subset_p,
 877   abitset_and,
 878   abitset_and_cmp,
 879   abitset_andn,
 880   abitset_andn_cmp,
 881   abitset_or,
 882   abitset_or_cmp,
 883   abitset_xor,
 884   abitset_xor_cmp,
 885   abitset_and_or,
 886   abitset_and_or_cmp,
 887   abitset_andn_or,
 888   abitset_andn_or_cmp,
 889   abitset_or_and,
 890   abitset_or_and_cmp,
 891   abitset_list,
 892   abitset_list_reverse,
 893   NULL,
 894   BITSET_ARRAY
 895 };
 896
 897
 898 size_t
 899 abitset_bytes (n_bits)
 900      bitset_bindex n_bits;
 901 {
 902   bitset_windex size;
 903   size_t bytes;
 904   size_t header_size = offsetof (union bitset_union, a.words);
 905   struct bitset_align_struct { char a; union bitset_union b; };
 906   size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
 907
 908   size = ABITSET_N_WORDS (n_bits);
 909   bytes = header_size + size * sizeof (bitset_word);
 910
 911   /* Align the size properly for a vector of abitset objects.  */
 912   if (header_size % bitset_alignment != 0
 913       || sizeof (bitset_word) % bitset_alignment != 0)
 914     {
 915       bytes += bitset_alignment - 1;
 916       bytes -= bytes % bitset_alignment;
 917     }
 918
 919   return bytes;
 920 }
 921
 922
 923 bitset
 924 abitset_init (bset, n_bits)
 925      bitset bset;
 926      bitset_bindex n_bits;
 927 {
 928   bitset_windex size;
 929
 930   size = ABITSET_N_WORDS (n_bits);
 931   ABITSET_N_BITS (bset) = n_bits;
 932
 933   /* Use optimized routines if bitset fits within a single word.
 934      There is probably little merit if using caching since
 935      the small bitset will always fit in the cache.  */
 936   if (size == 1)
 937     bset->b.vtable = &abitset_small_vtable;
 938   else
 939     bset->b.vtable = &abitset_vtable;
 940
 941   bset->b.cindex = 0;
 942   bset->b.csize = size;
 943   bset->b.cdata = ABITSET_WORDS (bset);
 944   return bset;
 945 }