maint/gnulib/lib/bitset/array.c

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

DEFINITIONS
