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