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