lib/abitset.c

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