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