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 #ifdef HAVE_CONFIG_H
  20 # include <config.h>
  21 #endif
  22
  23 #include "abitset.h"
  24 #include <stddef.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 /* This file implements fixed size bitsets stored as an array
  29    of words.  Any unused bits in the last word must be zero.  */
  30
  31 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
  32 #define ABITSET_WORDS(X) ((X)->a.words)
  33
  34
  35 static bitset_bindex
  36 abitset_resize (bitset src, bitset_bindex size)
  37 {
  38     /* These bitsets have a fixed size.  */
  39     if (BITSET_SIZE_ (src) != size)
  40       abort ();
  41
  42     return size;
  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 = BITSET_SIZE_ (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 hit
 109      the cache.  It is likely someone is trying to access outside the
 110      bounds of the bitset.  */
 111   abort ();
 112 }
 113
 114
 115 /* Reset bit BITNO in bitset DST.  */
 116 static void
 117 abitset_reset (bitset dst ATTRIBUTE_UNUSED,
 118                bitset_bindex bitno ATTRIBUTE_UNUSED)
 119 {
 120   /* This should never occur for abitsets since we should always hit
 121      the cache.  It is likely someone is trying to access outside the
 122      bounds of the bitset.  Since the bit is zero anyway, let it pass.  */
 123 }
 124
 125
 126 /* Test bit BITNO in bitset SRC.  */
 127 static bool
 128 abitset_test (bitset src ATTRIBUTE_UNUSED,
 129               bitset_bindex bitno ATTRIBUTE_UNUSED)
 130 {
 131   /* This should never occur for abitsets since we should always
 132      hit the cache.  */
 133   return false;
 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 = BITSET_SIZE_ (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 >= BITSET_SIZE_ (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 = BITSET_SIZE_ (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 bool
 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 false;
 348
 349   return true;
 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 bool
 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 false;
 391   return true;
 392 }
 393
 394
 395 static bool
 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 false;
 406   return true;
 407 }
 408
 409
 410 static bool
 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 false;
 421
 422   return true;
 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 bool
 441 abitset_and_cmp (bitset dst, bitset src1, bitset src2)
 442 {
 443   bitset_windex i;
 444   bool changed = false;
 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 = true;
 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 bool
 479 abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
 480 {
 481   bitset_windex i;
 482   bool changed = false;
 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 = true;
 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 bool
 517 abitset_or_cmp (bitset dst, bitset src1, bitset src2)
 518 {
 519   bitset_windex i;
 520   bool changed = false;
 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 = true;
 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 bool
 555 abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
 556 {
 557   bitset_windex i;
 558   bool changed = false;
 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 = true;
 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 bool
 594 abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 595 {
 596   bitset_windex i;
 597   bool changed = false;
 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 = true;
 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 bool
 634 abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 635 {
 636   bitset_windex i;
 637   bool changed = false;
 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 = true;
 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 bool
 674 abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
 675 {
 676   bitset_windex i;
 677   bool changed = false;
 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 = true;
 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_resize,
 715   bitset_size_,
 716   bitset_count_,
 717   abitset_empty_p,
 718   abitset_ones,
 719   abitset_zero,
 720   abitset_copy,
 721   abitset_disjoint_p,
 722   abitset_equal_p,
 723   abitset_not,
 724   abitset_subset_p,
 725   abitset_and,
 726   abitset_and_cmp,
 727   abitset_andn,
 728   abitset_andn_cmp,
 729   abitset_or,
 730   abitset_or_cmp,
 731   abitset_xor,
 732   abitset_xor_cmp,
 733   abitset_and_or,
 734   abitset_and_or_cmp,
 735   abitset_andn_or,
 736   abitset_andn_or_cmp,
 737   abitset_or_and,
 738   abitset_or_and_cmp,
 739   abitset_small_list,
 740   abitset_list_reverse,
 741   NULL,
 742   BITSET_ARRAY
 743 };
 744
 745
 746 /* Vector of operations for multiple word bitsets.  */
 747 struct bitset_vtable abitset_vtable = {
 748   abitset_set,
 749   abitset_reset,
 750   bitset_toggle_,
 751   abitset_test,
 752   abitset_resize,
 753   bitset_size_,
 754   bitset_count_,
 755   abitset_empty_p,
 756   abitset_ones,
 757   abitset_zero,
 758   abitset_copy,
 759   abitset_disjoint_p,
 760   abitset_equal_p,
 761   abitset_not,
 762   abitset_subset_p,
 763   abitset_and,
 764   abitset_and_cmp,
 765   abitset_andn,
 766   abitset_andn_cmp,
 767   abitset_or,
 768   abitset_or_cmp,
 769   abitset_xor,
 770   abitset_xor_cmp,
 771   abitset_and_or,
 772   abitset_and_or_cmp,
 773   abitset_andn_or,
 774   abitset_andn_or_cmp,
 775   abitset_or_and,
 776   abitset_or_and_cmp,
 777   abitset_list,
 778   abitset_list_reverse,
 779   NULL,
 780   BITSET_ARRAY
 781 };
 782
 783
 784 size_t
 785 abitset_bytes (bitset_bindex n_bits)
 786 {
 787   bitset_windex size;
 788   size_t bytes;
 789   size_t header_size = offsetof (union bitset_union, a.words);
 790   struct bitset_align_struct { char a; union bitset_union b; };
 791   size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
 792
 793   size = ABITSET_N_WORDS (n_bits);
 794   bytes = header_size + size * sizeof (bitset_word);
 795
 796   /* Align the size properly for a vector of abitset objects.  */
 797   if (header_size % bitset_alignment != 0
 798       || sizeof (bitset_word) % bitset_alignment != 0)
 799     {
 800       bytes += bitset_alignment - 1;
 801       bytes -= bytes % bitset_alignment;
 802     }
 803
 804   return bytes;
 805 }
 806
 807
 808 bitset
 809 abitset_init (bitset bset, bitset_bindex n_bits)
 810 {
 811   bitset_windex size;
 812
 813   size = ABITSET_N_WORDS (n_bits);
 814   BITSET_NBITS_ (bset) = n_bits;
 815
 816   /* Use optimized routines if bitset fits within a single word.
 817      There is probably little merit if using caching since
 818      the small bitset will always fit in the cache.  */
 819   if (size == 1)
 820     bset->b.vtable = &abitset_small_vtable;
 821   else
 822     bset->b.vtable = &abitset_vtable;
 823
 824   bset->b.cindex = 0;
 825   bset->b.csize = size;
 826   bset->b.cdata = ABITSET_WORDS (bset);
 827   return bset;
 828 }