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