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