Home | History | Annotate | Download | only in lib
      1 /* Array bitsets.
      2 
      3    Copyright (C) 2002-2003, 2006, 2009-2012 Free Software Foundation,
      4    Inc.
      5 
      6    Contributed by Michael Hayes (m.hayes (at) elec.canterbury.ac.nz).
      7 
      8    This program is free software: you can redistribute it and/or modify
      9    it under the terms of the GNU General Public License as published by
     10    the Free Software Foundation, either version 3 of the License, or
     11    (at your option) any later version.
     12 
     13    This program is distributed in the hope that it will be useful,
     14    but WITHOUT ANY WARRANTY; without even the implied warranty of
     15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     16    GNU General Public License for more details.
     17 
     18    You should have received a copy of the GNU General Public License
     19    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
     20 
     21 #include <config.h>
     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 }
    829