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