maint/gnulib/lib/bitset/table.c

/* */
This source file includes following definitions.
tbitset_resize
tbitset_elt_alloc
tbitset_elt_calloc
tbitset_elt_free
tbitset_elt_remove
tbitset_elt_add
tbitset_elt_zero_p
tbitset_elt_find
tbitset_weed
tbitset_zero
tbitset_equal_p
tbitset_copy_
tbitset_copy_cmp
tbitset_set
tbitset_reset
tbitset_test
tbitset_free
tbitset_list_reverse
tbitset_list
tbitset_unused_clear
tbitset_ones
tbitset_empty_p
tbitset_not
tbitset_subset_p
tbitset_disjoint_p
tbitset_op3_cmp
tbitset_and_cmp
tbitset_and
tbitset_andn_cmp
tbitset_andn
tbitset_or_cmp
tbitset_or
tbitset_xor_cmp
tbitset_xor
tbitset_copy
tbitset_bytes
tbitset_init
tbitset_release_memory
   1 /* Functions to support expandable bitsets.
   2 
   3    Copyright (C) 2002-2006, 2009-2015, 2018-2021 Free Software Foundation, Inc.
   4 
   5    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
   6 
   7    This program is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11 
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16 
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  19 
  20 #include <config.h>
  21 
  22 #include "bitset/table.h"
  23 
  24 #include <stdlib.h>
  25 #include <string.h>
  26 
  27 #include "obstack.h"
  28 #include "xalloc.h"
  29 
  30 /* This file implements expandable bitsets.  These bitsets can be of
  31    arbitrary length and are more efficient than arrays of bits for
  32    large sparse sets.
  33 
  34    Empty elements are represented by a NULL pointer in the table of
  35    element pointers.  An alternative is to point to a special zero
  36    element.  Similarly, we could represent an all 1's element with
  37    another special ones element pointer.
  38 
  39    Bitsets are commonly empty so we need to ensure that this special
  40    case is fast.  A zero bitset is indicated when cdata is 0.  This is
  41    conservative since cdata may be non zero and the bitset may still
  42    be zero.
  43 
  44    The bitset cache can be disabled either by setting cindex to
  45    BITSET_WINDEX_MAX or by setting csize to 0.  Here
  46    we use the former approach since cindex needs to be updated whenever
  47    cdata is changed.
  48 */
  49 
  50 
  51 /* Number of words to use for each element.  */
  52 #define TBITSET_ELT_WORDS 2
  53 
  54 /* Number of bits stored in each element.  */
  55 #define TBITSET_ELT_BITS \
  56   ((unsigned) (TBITSET_ELT_WORDS * BITSET_WORD_BITS))
  57 
  58 /* Tbitset element.  We use an array of bits.  */
  59 typedef struct tbitset_elt_struct
  60 {
  61   union
  62   {
  63     bitset_word words[TBITSET_ELT_WORDS];       /* Bits that are set.  */
  64     struct tbitset_elt_struct *next;
  65   }
  66   u;
  67 }
  68 tbitset_elt;
  69 
  70 
  71 typedef tbitset_elt *tbitset_elts;
  72 
  73 
  74 /* Number of elements to initially allocate.  */
  75 
  76 #ifndef TBITSET_INITIAL_SIZE
  77 # define TBITSET_INITIAL_SIZE 2
  78 #endif
  79 
  80 
  81 enum tbitset_find_mode
  82   { TBITSET_FIND, TBITSET_CREATE, TBITSET_SUBST };
  83 
  84 static tbitset_elt tbitset_zero_elts[1]; /* Elements of all zero bits.  */
  85 
  86 /* Obstack to allocate bitset elements from.  */
  87 static struct obstack tbitset_obstack;
  88 static bool tbitset_obstack_init = false;
  89 static tbitset_elt *tbitset_free_list;  /* Free list of bitset elements.  */
  90 
  91 #define TBITSET_N_ELTS(N) (((N) + TBITSET_ELT_BITS - 1) / TBITSET_ELT_BITS)
  92 #define TBITSET_ELTS(BSET) ((BSET)->e.elts)
  93 #define TBITSET_SIZE(BSET) TBITSET_N_ELTS (BITSET_NBITS_ (BSET))
  94 #define TBITSET_ASIZE(BSET) ((BSET)->e.size)
  95 
  96 #define TBITSET_NEXT(ELT) ((ELT)->u.next)
  97 #define TBITSET_WORDS(ELT) ((ELT)->u.words)
  98 
  99 /* Disable bitset cache and mark BSET as being zero.  */
 100 #define TBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
 101         (BSET)->b.cdata = 0)
 102 
 103 #define TBITSET_CACHE_DISABLE(BSET)  ((BSET)->b.cindex = BITSET_WINDEX_MAX)
 104 
 105 /* Disable bitset cache and mark BSET as being possibly non-zero.  */
 106 #define TBITSET_NONZERO_SET(BSET) \
 107  (TBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
 108 
 109 /* A conservative estimate of whether the bitset is zero.
 110    This is non-zero only if we know for sure that the bitset is zero.  */
 111 #define TBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
 112 
 113 /* Enable cache to point to element with table index EINDEX.
 114    The element must exist.  */
 115 #define TBITSET_CACHE_SET(BSET, EINDEX) \
 116  ((BSET)->b.cindex = (EINDEX) * TBITSET_ELT_WORDS, \
 117   (BSET)->b.cdata = TBITSET_WORDS (TBITSET_ELTS (BSET) [EINDEX]))
 118 
 119 #undef min
 120 #undef max
 121 #define min(a, b) ((a) > (b) ? (b) : (a))
 122 #define max(a, b) ((a) > (b) ? (a) : (b))
 123 
 124 static bitset_bindex
 125 tbitset_resize (bitset src, bitset_bindex n_bits)
     /*  */
 126 {
 127   if (n_bits == BITSET_NBITS_ (src))
 128     return n_bits;
 129 
 130   bitset_windex oldsize = TBITSET_SIZE (src);
 131   bitset_windex newsize = TBITSET_N_ELTS (n_bits);
 132 
 133   if (oldsize < newsize)
 134     {
 135       /* The bitset needs to grow.  If we already have enough memory
 136          allocated, then just zero what we need.  */
 137       if (newsize > TBITSET_ASIZE (src))
 138         {
 139           /* We need to allocate more memory.  When oldsize is
 140              non-zero this means that we are changing the size, so
 141              grow the bitset 25% larger than requested to reduce
 142              number of reallocations.  */
 143 
 144           bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
 145           TBITSET_ELTS (src)
 146             = xrealloc (TBITSET_ELTS (src), size * sizeof (tbitset_elt *));
 147           TBITSET_ASIZE (src) = size;
 148         }
 149 
 150       memset (TBITSET_ELTS (src) + oldsize, 0,
 151               (newsize - oldsize) * sizeof (tbitset_elt *));
 152     }
 153   else
 154     {
 155       /* The bitset needs to shrink.  There's no point deallocating
 156          the memory unless it is shrinking by a reasonable amount.  */
 157       if ((oldsize - newsize) >= oldsize / 2)
 158         {
 159           void *p
 160             = realloc (TBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
 161           if (p)
 162             {
 163               TBITSET_ELTS (src) = p;
 164               TBITSET_ASIZE (src) = newsize;
 165             }
 166         }
 167 
 168       /* Need to prune any excess bits.  FIXME.  */
 169     }
 170 
 171   BITSET_NBITS_ (src) = n_bits;
 172   return n_bits;
 173 }
 174 
 175 
 176 /* Allocate a tbitset element.  The bits are not cleared.  */
 177 static inline tbitset_elt *
 178 tbitset_elt_alloc (void)
     /*  */
 179 {
 180   tbitset_elt *elt;
 181 
 182   if (tbitset_free_list != 0)
 183     {
 184       elt = tbitset_free_list;
 185       tbitset_free_list = TBITSET_NEXT (elt);
 186     }
 187   else
 188     {
 189       if (!tbitset_obstack_init)
 190         {
 191           tbitset_obstack_init = true;
 192 
 193           /* Let particular systems override the size of a chunk.  */
 194 
 195 #ifndef OBSTACK_CHUNK_SIZE
 196 # define OBSTACK_CHUNK_SIZE 0
 197 #endif
 198 
 199           /* Let them override the alloc and free routines too.  */
 200 
 201 #ifndef OBSTACK_CHUNK_ALLOC
 202 # define OBSTACK_CHUNK_ALLOC xmalloc
 203 #endif
 204 
 205 #ifndef OBSTACK_CHUNK_FREE
 206 # define OBSTACK_CHUNK_FREE free
 207 #endif
 208 
 209 #if !(defined __GNUC__ || defined __clang__)
 210 # define __alignof__(type) 0
 211 #endif
 212 
 213           obstack_specify_allocation (&tbitset_obstack, OBSTACK_CHUNK_SIZE,
 214                                       __alignof__ (tbitset_elt),
 215                                       OBSTACK_CHUNK_ALLOC,
 216                                       OBSTACK_CHUNK_FREE);
 217         }
 218 
 219       /* Perhaps we should add a number of new elements to the free
 220          list.  */
 221       elt = (tbitset_elt *) obstack_alloc (&tbitset_obstack,
 222                                            sizeof (tbitset_elt));
 223     }
 224 
 225   return elt;
 226 }
 227 
 228 
 229 /* Allocate a tbitset element.  The bits are cleared.  */
 230 static inline tbitset_elt *
 231 tbitset_elt_calloc (void)
     /*  */
 232 {
 233   tbitset_elt *elt = tbitset_elt_alloc ();
 234   memset (TBITSET_WORDS (elt), 0, sizeof (TBITSET_WORDS (elt)));
 235   return elt;
 236 }
 237 
 238 
 239 static inline void
 240 tbitset_elt_free (tbitset_elt *elt)
     /*  */
 241 {
 242   TBITSET_NEXT (elt) = tbitset_free_list;
 243   tbitset_free_list = elt;
 244 }
 245 
 246 
 247 /* Remove element with index EINDEX from bitset BSET.  */
 248 static inline void
 249 tbitset_elt_remove (bitset bset, bitset_windex eindex)
     /*  */
 250 {
 251   tbitset_elts *elts = TBITSET_ELTS (bset);
 252   tbitset_elt *elt = elts[eindex];
 253 
 254   elts[eindex] = 0;
 255   tbitset_elt_free (elt);
 256 }
 257 
 258 
 259 /* Add ELT into elts at index EINDEX of bitset BSET.  */
 260 static inline void
 261 tbitset_elt_add (bitset bset, tbitset_elt *elt, bitset_windex eindex)
     /*  */
 262 {
 263   tbitset_elts *elts = TBITSET_ELTS (bset);
 264   /* Assume that the elts entry not allocated.  */
 265   elts[eindex] = elt;
 266 }
 267 
 268 
 269 /* Are all bits in an element zero?  */
 270 static inline bool
 271 tbitset_elt_zero_p (tbitset_elt *elt)
     /*  */
 272 {
 273   for (int i = 0; i < TBITSET_ELT_WORDS; i++)
 274     if (TBITSET_WORDS (elt)[i])
 275       return false;
 276   return true;
 277 }
 278 
 279 
 280 static tbitset_elt *
 281 tbitset_elt_find (bitset bset, bitset_bindex bindex,
     /*  */
 282                   enum tbitset_find_mode mode)
 283 {
 284   bitset_windex eindex = bindex / TBITSET_ELT_BITS;
 285 
 286   tbitset_elts *elts = TBITSET_ELTS (bset);
 287   bitset_windex size = TBITSET_SIZE (bset);
 288 
 289   if (eindex < size)
 290     {
 291       tbitset_elt *elt = elts[eindex];
 292       if (elt)
 293         {
 294           if (TBITSET_WORDS (elt) != bset->b.cdata)
 295             TBITSET_CACHE_SET (bset, eindex);
 296           return elt;
 297         }
 298     }
 299 
 300   /* The element could not be found.  */
 301 
 302   switch (mode)
 303     {
 304     default:
 305       abort ();
 306 
 307     case TBITSET_FIND:
 308       return NULL;
 309 
 310     case TBITSET_CREATE:
 311       if (eindex >= size)
 312         tbitset_resize (bset, bindex);
 313 
 314       /* Create a new element.  */
 315       {
 316         tbitset_elt *elt = tbitset_elt_calloc ();
 317         tbitset_elt_add (bset, elt, eindex);
 318         TBITSET_CACHE_SET (bset, eindex);
 319         return elt;
 320       }
 321 
 322     case TBITSET_SUBST:
 323       return &tbitset_zero_elts[0];
 324     }
 325 }
 326 
 327 
 328 /* Weed out the zero elements from the elts.  */
 329 static inline bitset_windex
 330 tbitset_weed (bitset bset)
     /*  */
 331 {
 332   if (TBITSET_ZERO_P (bset))
 333     return 0;
 334 
 335   tbitset_elts *elts = TBITSET_ELTS (bset);
 336   bitset_windex count = 0;
 337   bitset_windex j;
 338   for (j = 0; j < TBITSET_SIZE (bset); j++)
 339     {
 340       tbitset_elt *elt = elts[j];
 341 
 342       if (elt)
 343         {
 344           if (tbitset_elt_zero_p (elt))
 345             {
 346               tbitset_elt_remove (bset, j);
 347               count++;
 348             }
 349         }
 350       else
 351         count++;
 352     }
 353 
 354   count = j - count;
 355   if (!count)
 356     {
 357       /* All the bits are zero.  We could shrink the elts.
 358          For now just mark BSET as known to be zero.  */
 359       TBITSET_ZERO_SET (bset);
 360     }
 361   else
 362     TBITSET_NONZERO_SET (bset);
 363 
 364   return count;
 365 }
 366 
 367 
 368 /* Set all bits in the bitset to zero.  */
 369 static inline void
 370 tbitset_zero (bitset bset)
     /*  */
 371 {
 372   if (TBITSET_ZERO_P (bset))
 373     return;
 374 
 375   tbitset_elts *elts = TBITSET_ELTS (bset);
 376   for (bitset_windex j = 0; j < TBITSET_SIZE (bset); j++)
 377     {
 378       tbitset_elt *elt = elts[j];
 379       if (elt)
 380         tbitset_elt_remove (bset, j);
 381     }
 382 
 383   /* All the bits are zero.  We could shrink the elts.
 384      For now just mark BSET as known to be zero.  */
 385   TBITSET_ZERO_SET (bset);
 386 }
 387 
 388 
 389 static inline bool
 390 tbitset_equal_p (bitset dst, bitset src)
     /*  */
 391 {
 392   if (src == dst)
 393     return true;
 394 
 395   tbitset_weed (dst);
 396   tbitset_weed (src);
 397 
 398   if (TBITSET_SIZE (src) != TBITSET_SIZE (dst))
 399     return false;
 400 
 401   tbitset_elts *selts = TBITSET_ELTS (src);
 402   tbitset_elts *delts = TBITSET_ELTS (dst);
 403 
 404   for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
 405     {
 406       tbitset_elt *selt = selts[j];
 407       tbitset_elt *delt = delts[j];
 408 
 409       if (!selt && !delt)
 410         continue;
 411       if ((selt && !delt) || (!selt && delt))
 412         return false;
 413 
 414       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 415         if (TBITSET_WORDS (selt)[i] != TBITSET_WORDS (delt)[i])
 416           return false;
 417     }
 418   return true;
 419 }
 420 
 421 
 422 /* Copy bits from bitset SRC to bitset DST.  */
 423 static inline void
 424 tbitset_copy_ (bitset dst, bitset src)
     /*  */
 425 {
 426   if (src == dst)
 427     return;
 428 
 429   tbitset_zero (dst);
 430 
 431   if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
 432     tbitset_resize (dst, BITSET_NBITS_ (src));
 433 
 434   tbitset_elts *selts = TBITSET_ELTS (src);
 435   tbitset_elts *delts = TBITSET_ELTS (dst);
 436   for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
 437     {
 438       tbitset_elt *selt = selts[j];
 439       if (selt)
 440         {
 441           tbitset_elt *tmp = tbitset_elt_alloc ();
 442           delts[j] = tmp;
 443           memcpy (TBITSET_WORDS (tmp), TBITSET_WORDS (selt),
 444                   sizeof (TBITSET_WORDS (selt)));
 445         }
 446     }
 447   TBITSET_NONZERO_SET (dst);
 448 }
 449 
 450 
 451 /* Copy bits from bitset SRC to bitset DST.  Return true if
 452    bitsets different.  */
 453 static inline bool
 454 tbitset_copy_cmp (bitset dst, bitset src)
     /*  */
 455 {
 456   if (src == dst)
 457     return false;
 458 
 459   if (TBITSET_ZERO_P (dst))
 460     {
 461       tbitset_copy_ (dst, src);
 462       return !TBITSET_ZERO_P (src);
 463     }
 464 
 465   if (tbitset_equal_p (dst, src))
 466     return false;
 467 
 468   tbitset_copy_ (dst, src);
 469   return true;
 470 }
 471 
 472 
 473 /* Set bit BITNO in bitset DST.  */
 474 static void
 475 tbitset_set (bitset dst, bitset_bindex bitno)
     /*  */
 476 {
 477   bitset_windex windex = bitno / BITSET_WORD_BITS;
 478 
 479   tbitset_elt_find (dst, bitno, TBITSET_CREATE);
 480 
 481   dst->b.cdata[windex - dst->b.cindex] |=
 482     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
 483 }
 484 
 485 
 486 /* Reset bit BITNO in bitset DST.  */
 487 static void
 488 tbitset_reset (bitset dst, bitset_bindex bitno)
     /*  */
 489 {
 490   bitset_windex windex = bitno / BITSET_WORD_BITS;
 491 
 492   if (!tbitset_elt_find (dst, bitno, TBITSET_FIND))
 493     return;
 494 
 495   dst->b.cdata[windex - dst->b.cindex] &=
 496     ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 497 
 498   /* If all the data is zero, perhaps we should remove it now...
 499      However, there is a good chance that the element will be needed
 500      again soon.  */
 501 }
 502 
 503 
 504 /* Test bit BITNO in bitset SRC.  */
 505 static bool
 506 tbitset_test (bitset src, bitset_bindex bitno)
     /*  */
 507 {
 508   bitset_windex windex = bitno / BITSET_WORD_BITS;
 509 
 510   return (tbitset_elt_find (src, bitno, TBITSET_FIND)
 511           && ((src->b.cdata[windex - src->b.cindex]
 512                >> (bitno % BITSET_WORD_BITS))
 513               & 1));
 514 }
 515 
 516 
 517 static void
 518 tbitset_free (bitset bset)
     /*  */
 519 {
 520   tbitset_zero (bset);
 521   free (TBITSET_ELTS (bset));
 522 }
 523 
 524 
 525 /* Find list of up to NUM bits set in BSET starting from and including
 526  *NEXT and store in array LIST.  Return with actual number of bits
 527  found and with *NEXT indicating where search stopped.  */
 528 static bitset_bindex
 529 tbitset_list_reverse (bitset bset, bitset_bindex *list,
     /*  */
 530                       bitset_bindex num, bitset_bindex *next)
 531 {
 532   if (TBITSET_ZERO_P (bset))
 533     return 0;
 534 
 535   bitset_windex size = TBITSET_SIZE (bset);
 536   bitset_bindex n_bits = size * TBITSET_ELT_BITS;
 537   bitset_bindex rbitno = *next;
 538 
 539   if (rbitno >= n_bits)
 540     return 0;
 541 
 542   tbitset_elts *elts = TBITSET_ELTS (bset);
 543 
 544   bitset_bindex bitno = n_bits - (rbitno + 1);
 545 
 546   bitset_windex windex = bitno / BITSET_WORD_BITS;
 547   bitset_windex eindex = bitno / TBITSET_ELT_BITS;
 548   bitset_windex woffset = windex - eindex * TBITSET_ELT_WORDS;
 549 
 550   /* If num is 1, we could speed things up with a binary search
 551      of the word of interest.  */
 552   bitset_bindex count = 0;
 553   unsigned bitcnt = bitno % BITSET_WORD_BITS;
 554   bitset_bindex bitoff = windex * BITSET_WORD_BITS;
 555 
 556   do
 557     {
 558       tbitset_elt *elt = elts[eindex];
 559       if (elt)
 560         {
 561           bitset_word *srcp = TBITSET_WORDS (elt);
 562 
 563           do
 564             {
 565               bitset_word word = srcp[woffset];
 566               if (bitcnt + 1 < BITSET_WORD_BITS)
 567                 /* We're starting in the middle of a word: smash bits to ignore.  */
 568                 word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
 569               BITSET_FOR_EACH_BIT_REVERSE(pos, word)
 570                 {
 571                   list[count++] = bitoff + pos;
 572                   if (count >= num)
 573                     {
 574                       *next = n_bits - (bitoff + pos);
 575                       return count;
 576                     }
 577                 }
 578               bitoff -= BITSET_WORD_BITS;
 579               bitcnt = BITSET_WORD_BITS - 1;
 580             }
 581           while (woffset--);
 582         }
 583 
 584       woffset = TBITSET_ELT_WORDS - 1;
 585       bitoff = eindex * TBITSET_ELT_BITS - BITSET_WORD_BITS;
 586     }
 587   while (eindex--);
 588 
 589   *next = n_bits - (bitoff + 1);
 590   return count;
 591 }
 592 
 593 
 594 /* Find list of up to NUM bits set in BSET starting from and including
 595    *NEXT and store in array LIST.  Return with actual number of bits
 596    found and with *NEXT indicating where search stopped.  */
 597 static bitset_bindex
 598 tbitset_list (bitset bset, bitset_bindex *list,
     /*  */
 599               bitset_bindex num, bitset_bindex *next)
 600 {
 601   if (TBITSET_ZERO_P (bset))
 602     return 0;
 603 
 604   bitset_bindex bitno = *next;
 605   bitset_bindex count = 0;
 606 
 607   tbitset_elts *elts = TBITSET_ELTS (bset);
 608   bitset_windex size = TBITSET_SIZE (bset);
 609   bitset_windex eindex = bitno / TBITSET_ELT_BITS;
 610 
 611   if (bitno % TBITSET_ELT_BITS)
 612     {
 613       /* We need to start within an element.  This is not very common.  */
 614       tbitset_elt *elt = elts[eindex];
 615       if (elt)
 616         {
 617           bitset_word *srcp = TBITSET_WORDS (elt);
 618           bitset_windex woffset = eindex * TBITSET_ELT_WORDS;
 619 
 620           for (bitset_windex windex = bitno / BITSET_WORD_BITS;
 621                (windex - woffset) < TBITSET_ELT_WORDS; windex++)
 622             {
 623               bitset_word word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
 624 
 625               BITSET_FOR_EACH_BIT (pos, word)
 626                 {
 627                   list[count++] = bitno + pos;
 628                   if (count >= num)
 629                     {
 630                       *next = bitno + pos + 1;
 631                       return count;
 632                     }
 633                 }
 634               bitno = (windex + 1) * BITSET_WORD_BITS;
 635             }
 636         }
 637 
 638       /* Skip to next element.  */
 639       eindex++;
 640     }
 641 
 642   /* If num is 1, we could speed things up with a binary search
 643      of the word of interest.  */
 644 
 645   for (; eindex < size; eindex++)
 646     {
 647       tbitset_elt *elt = elts[eindex];
 648       if (!elt)
 649         continue;
 650 
 651       bitset_word *srcp = TBITSET_WORDS (elt);
 652       bitset_windex windex = eindex * TBITSET_ELT_WORDS;
 653       bitno = windex * BITSET_WORD_BITS;
 654 
 655       /* Is there enough room to avoid checking in each iteration? */
 656       if ((count + TBITSET_ELT_BITS) < num)
 657         {
 658           /* The coast is clear, plant boot!  */
 659 
 660 #if TBITSET_ELT_WORDS == 2
 661           bitset_word word = srcp[0];
 662           if (word)
 663             BITSET_FOR_EACH_BIT (pos, word)
 664               list[count++] = bitno + pos;
 665           windex++;
 666           bitno = windex * BITSET_WORD_BITS;
 667 
 668           word = srcp[1];
 669           if (word)
 670             BITSET_FOR_EACH_BIT (pos, word)
 671               list[count++] = bitno + pos;
 672           windex++;
 673           bitno = windex * BITSET_WORD_BITS;
 674 #else
 675           for (int i = 0; i < TBITSET_ELT_WORDS; i++, windex++)
 676             {
 677               bitset_word word = srcp[i];
 678               if (word)
 679                 BITSET_FOR_EACH_BIT (pos, word)
 680                   list[count++] = bitno + pos;
 681               bitno = windex * BITSET_WORD_BITS;
 682             }
 683 #endif
 684         }
 685       else
 686         {
 687           /* Tread more carefully since we need to check
 688              if array overflows.  */
 689           for (int i = 0; i < TBITSET_ELT_WORDS; i++)
 690             {
 691               bitset_word word = srcp[i];
 692               if (word)
 693                 BITSET_FOR_EACH_BIT (pos, word)
 694                   {
 695                     list[count++] = bitno + pos;
 696                     if (count >= num)
 697                       {
 698                         *next = bitno + pos + 1;
 699                         return count;
 700                       }
 701                   }
 702               windex++;
 703               bitno = windex * BITSET_WORD_BITS;
 704             }
 705         }
 706     }
 707 
 708   *next = bitno;
 709   return count;
 710 }
 711 
 712 
 713 /* Ensure that any unused bits within the last element are clear.  */
 714 static inline void
 715 tbitset_unused_clear (bitset dst)
     /*  */
 716 {
 717   bitset_bindex n_bits = BITSET_NBITS_ (dst);
 718   unsigned last_bit = n_bits % TBITSET_ELT_BITS;
 719 
 720   if (last_bit)
 721     {
 722       tbitset_elts *elts = TBITSET_ELTS (dst);
 723 
 724       bitset_windex eindex = n_bits / TBITSET_ELT_BITS;
 725 
 726       tbitset_elt *elt = elts[eindex];
 727       if (elt)
 728         {
 729           bitset_word *srcp = TBITSET_WORDS (elt);
 730 
 731           bitset_windex windex = n_bits / BITSET_WORD_BITS;
 732           bitset_windex woffset = eindex * TBITSET_ELT_WORDS;
 733 
 734           srcp[windex - woffset]
 735             &= ((bitset_word) 1 << (last_bit % BITSET_WORD_BITS)) - 1;
 736           windex++;
 737           for (; (windex - woffset) < TBITSET_ELT_WORDS; windex++)
 738             srcp[windex - woffset] = 0;
 739         }
 740     }
 741 }
 742 
 743 
 744 static void
 745 tbitset_ones (bitset dst)
     /*  */
 746 {
 747   for (bitset_windex j = 0; j < TBITSET_SIZE (dst); j++)
 748     {
 749       /* Create new elements if they cannot be found.  Perhaps
 750          we should just add pointers to a ones element?  */
 751       tbitset_elt *elt =
 752         tbitset_elt_find (dst, j * TBITSET_ELT_BITS, TBITSET_CREATE);
 753       memset (TBITSET_WORDS (elt), -1, sizeof (TBITSET_WORDS (elt)));
 754     }
 755   TBITSET_NONZERO_SET (dst);
 756   tbitset_unused_clear (dst);
 757 }
 758 
 759 
 760 static bool
 761 tbitset_empty_p (bitset dst)
     /*  */
 762 {
 763   if (TBITSET_ZERO_P (dst))
 764     return true;
 765 
 766   tbitset_elts *elts = TBITSET_ELTS (dst);
 767   for (bitset_windex j = 0; j < TBITSET_SIZE (dst); j++)
 768     {
 769       tbitset_elt *elt = elts[j];
 770 
 771       if (elt)
 772         {
 773           if (!tbitset_elt_zero_p (elt))
 774             return false;
 775           /* Do some weeding as we go.  */
 776           tbitset_elt_remove (dst, j);
 777         }
 778     }
 779 
 780   /* All the bits are zero.  We could shrink the elts.
 781      For now just mark DST as known to be zero.  */
 782   TBITSET_ZERO_SET (dst);
 783   return true;
 784 }
 785 
 786 
 787 static void
 788 tbitset_not (bitset dst, bitset src)
     /*  */
 789 {
 790   tbitset_resize (dst, BITSET_NBITS_ (src));
 791 
 792   for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
 793     {
 794       /* Create new elements for dst if they cannot be found
 795          or substitute zero elements if src elements not found.  */
 796       tbitset_elt *selt =
 797         tbitset_elt_find (src, j * TBITSET_ELT_BITS, TBITSET_SUBST);
 798       tbitset_elt *delt =
 799         tbitset_elt_find (dst, j * TBITSET_ELT_BITS, TBITSET_CREATE);
 800 
 801       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 802         TBITSET_WORDS (delt)[i] = ~TBITSET_WORDS (selt)[i];
 803     }
 804   TBITSET_NONZERO_SET (dst);
 805   tbitset_unused_clear (dst);
 806 }
 807 
 808 
 809 /* Is DST == DST | SRC?  */
 810 static bool
 811 tbitset_subset_p (bitset dst, bitset src)
     /*  */
 812 {
 813   tbitset_elts *selts = TBITSET_ELTS (src);
 814   tbitset_elts *delts = TBITSET_ELTS (dst);
 815 
 816   bitset_windex ssize = TBITSET_SIZE (src);
 817   bitset_windex dsize = TBITSET_SIZE (dst);
 818 
 819   for (bitset_windex j = 0; j < ssize; j++)
 820     {
 821       tbitset_elt *selt = j < ssize ? selts[j] : 0;
 822       tbitset_elt *delt = j < dsize ? delts[j] : 0;
 823 
 824       if (!selt && !delt)
 825         continue;
 826 
 827       if (!selt)
 828         selt = &tbitset_zero_elts[0];
 829       if (!delt)
 830         delt = &tbitset_zero_elts[0];
 831 
 832       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 833         if (TBITSET_WORDS (delt)[i]
 834             != (TBITSET_WORDS (selt)[i] | TBITSET_WORDS (delt)[i]))
 835           return false;
 836     }
 837   return true;
 838 }
 839 
 840 
 841 /* Is DST & SRC == 0?  */
 842 static bool
 843 tbitset_disjoint_p (bitset dst, bitset src)
     /*  */
 844 {
 845   tbitset_elts *selts = TBITSET_ELTS (src);
 846   tbitset_elts *delts = TBITSET_ELTS (dst);
 847 
 848   bitset_windex ssize = TBITSET_SIZE (src);
 849   bitset_windex dsize = TBITSET_SIZE (dst);
 850 
 851   for (bitset_windex j = 0; j < ssize; j++)
 852     {
 853       tbitset_elt *selt = j < ssize ? selts[j] : 0;
 854       tbitset_elt *delt = j < dsize ? delts[j] : 0;
 855 
 856       if (!selt || !delt)
 857         continue;
 858 
 859       for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
 860         if ((TBITSET_WORDS (selt)[i] & TBITSET_WORDS (delt)[i]))
 861           return false;
 862     }
 863   return true;
 864 }
 865 
 866 
 867 
 868 static bool
 869 tbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
     /*  */
 870 {
 871   bool changed = false;
 872 
 873   tbitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
 874 
 875   bitset_windex ssize1 = TBITSET_SIZE (src1);
 876   bitset_windex ssize2 = TBITSET_SIZE (src2);
 877   bitset_windex dsize = TBITSET_SIZE (dst);
 878   bitset_windex size = ssize1;
 879   if (size < ssize2)
 880     size = ssize2;
 881 
 882   tbitset_elts *selts1 = TBITSET_ELTS (src1);
 883   tbitset_elts *selts2 = TBITSET_ELTS (src2);
 884   tbitset_elts *delts = TBITSET_ELTS (dst);
 885 
 886   bitset_windex j = 0;
 887   for (j = 0; j < size; j++)
 888     {
 889       tbitset_elt *selt1 = j < ssize1 ? selts1[j] : 0;
 890       tbitset_elt *selt2 = j < ssize2 ? selts2[j] : 0;
 891       tbitset_elt *delt = j < dsize ? delts[j] : 0;
 892 
 893       if (!selt1 && !selt2)
 894         {
 895           if (delt)
 896             {
 897               changed = true;
 898               tbitset_elt_remove (dst, j);
 899             }
 900           continue;
 901         }
 902 
 903       if (!selt1)
 904         selt1 = &tbitset_zero_elts[0];
 905       if (!selt2)
 906         selt2 = &tbitset_zero_elts[0];
 907       if (!delt)
 908         delt = tbitset_elt_calloc ();
 909       else
 910         delts[j] = 0;
 911 
 912       bitset_word *srcp1 = TBITSET_WORDS (selt1);
 913       bitset_word *srcp2 = TBITSET_WORDS (selt2);
 914       bitset_word *dstp = TBITSET_WORDS (delt);
 915       switch (op)
 916         {
 917         default:
 918           abort ();
 919 
 920         case BITSET_OP_OR:
 921           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 922             {
 923               bitset_word tmp = *srcp1++ | *srcp2++;
 924 
 925               if (*dstp != tmp)
 926                 {
 927                   changed = true;
 928                   *dstp = tmp;
 929                 }
 930             }
 931           break;
 932 
 933         case BITSET_OP_AND:
 934           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 935             {
 936               bitset_word tmp = *srcp1++ & *srcp2++;
 937 
 938               if (*dstp != tmp)
 939                 {
 940                   changed = true;
 941                   *dstp = tmp;
 942                 }
 943             }
 944           break;
 945 
 946         case BITSET_OP_XOR:
 947           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 948             {
 949               bitset_word tmp = *srcp1++ ^ *srcp2++;
 950 
 951               if (*dstp != tmp)
 952                 {
 953                   changed = true;
 954                   *dstp = tmp;
 955                 }
 956             }
 957           break;
 958 
 959         case BITSET_OP_ANDN:
 960           for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
 961             {
 962               bitset_word tmp = *srcp1++ & ~(*srcp2++);
 963 
 964               if (*dstp != tmp)
 965                 {
 966                   changed = true;
 967                   *dstp = tmp;
 968                 }
 969             }
 970           break;
 971         }
 972 
 973       if (!tbitset_elt_zero_p (delt))
 974         tbitset_elt_add (dst, delt, j);
 975       else
 976         tbitset_elt_free (delt);
 977     }
 978 
 979   /* If we have elements of DST left over, free them all.  */
 980   for (; j < dsize; j++)
 981     {
 982       changed = true;
 983 
 984       tbitset_elt *delt = delts[j];
 985       if (delt)
 986         tbitset_elt_remove (dst, j);
 987     }
 988 
 989   TBITSET_NONZERO_SET (dst);
 990   return changed;
 991 }
 992 
 993 
 994 static bool
 995 tbitset_and_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
 996 {
 997   if (TBITSET_ZERO_P (src2))
 998     {
 999       tbitset_weed (dst);
1000       bool changed = TBITSET_ZERO_P (dst);
1001       tbitset_zero (dst);
1002       return changed;
1003     }
1004   else if (TBITSET_ZERO_P (src1))
1005     {
1006       tbitset_weed (dst);
1007       bool changed = TBITSET_ZERO_P (dst);
1008       tbitset_zero (dst);
1009       return changed;
1010     }
1011   else
1012     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1013 }
1014 
1015 
1016 static void
1017 tbitset_and (bitset dst, bitset src1, bitset src2)
     /*  */
1018 {
1019   tbitset_and_cmp (dst, src1, src2);
1020 }
1021 
1022 
1023 static bool
1024 tbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
1025 {
1026   if (TBITSET_ZERO_P (src2))
1027     return tbitset_copy_cmp (dst, src1);
1028   else if (TBITSET_ZERO_P (src1))
1029     {
1030       tbitset_weed (dst);
1031       bool changed = TBITSET_ZERO_P (dst);
1032       tbitset_zero (dst);
1033       return changed;
1034     }
1035   else
1036     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1037 }
1038 
1039 
1040 static void
1041 tbitset_andn (bitset dst, bitset src1, bitset src2)
     /*  */
1042 {
1043   tbitset_andn_cmp (dst, src1, src2);
1044 }
1045 
1046 
1047 static bool
1048 tbitset_or_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
1049 {
1050   if (TBITSET_ZERO_P (src2))
1051     return tbitset_copy_cmp (dst, src1);
1052   else if (TBITSET_ZERO_P (src1))
1053     return tbitset_copy_cmp (dst, src2);
1054   else
1055     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1056 }
1057 
1058 
1059 static void
1060 tbitset_or (bitset dst, bitset src1, bitset src2)
     /*  */
1061 {
1062   tbitset_or_cmp (dst, src1, src2);
1063 }
1064 
1065 
1066 static bool
1067 tbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
1068 {
1069   if (TBITSET_ZERO_P (src2))
1070     return tbitset_copy_cmp (dst, src1);
1071   else if (TBITSET_ZERO_P (src1))
1072     return tbitset_copy_cmp (dst, src2);
1073   else
1074     return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1075 }
1076 
1077 
1078 static void
1079 tbitset_xor (bitset dst, bitset src1, bitset src2)
     /*  */
1080 {
1081   tbitset_xor_cmp (dst, src1, src2);
1082 }
1083 
1084 
1085 static void
1086 tbitset_copy (bitset dst, bitset src)
     /*  */
1087 {
1088   if (BITSET_COMPATIBLE_ (dst, src))
1089     tbitset_copy_ (dst, src);
1090   else
1091     bitset_copy_ (dst, src);
1092 }
1093 
1094 
1095 /* Vector of operations for linked-list bitsets.  */
1096 struct bitset_vtable tbitset_vtable = {
1097   tbitset_set,
1098   tbitset_reset,
1099   bitset_toggle_,
1100   tbitset_test,
1101   tbitset_resize,
1102   bitset_size_,
1103   bitset_count_,
1104   tbitset_empty_p,
1105   tbitset_ones,
1106   tbitset_zero,
1107   tbitset_copy,
1108   tbitset_disjoint_p,
1109   tbitset_equal_p,
1110   tbitset_not,
1111   tbitset_subset_p,
1112   tbitset_and,
1113   tbitset_and_cmp,
1114   tbitset_andn,
1115   tbitset_andn_cmp,
1116   tbitset_or,
1117   tbitset_or_cmp,
1118   tbitset_xor,
1119   tbitset_xor_cmp,
1120   bitset_and_or_,
1121   bitset_and_or_cmp_,
1122   bitset_andn_or_,
1123   bitset_andn_or_cmp_,
1124   bitset_or_and_,
1125   bitset_or_and_cmp_,
1126   tbitset_list,
1127   tbitset_list_reverse,
1128   tbitset_free,
1129   BITSET_TABLE
1130 };
1131 
1132 
1133 /* Return size of initial structure.  */
1134 size_t
1135 tbitset_bytes (MAYBE_UNUSED bitset_bindex n_bits)
     /*  */
1136 {
1137   return sizeof (struct tbitset_struct);
1138 }
1139 
1140 
1141 /* Initialize a bitset.  */
1142 
1143 bitset
1144 tbitset_init (bitset bset, bitset_bindex n_bits)
     /*  */
1145 {
1146   bset->b.vtable = &tbitset_vtable;
1147 
1148   bset->b.csize = TBITSET_ELT_WORDS;
1149 
1150   TBITSET_ZERO_SET (bset);
1151 
1152   TBITSET_ASIZE (bset) = 0;
1153   TBITSET_ELTS (bset) = 0;
1154   tbitset_resize (bset, n_bits);
1155 
1156   return bset;
1157 }
1158 
1159 
1160 void
1161 tbitset_release_memory (void)
     /*  */
1162 {
1163   tbitset_free_list = 0;
1164   if (tbitset_obstack_init)
1165     {
1166       tbitset_obstack_init = false;
1167       obstack_free (&tbitset_obstack, NULL);
1168     }
1169 }
/* */
root/maint/gnulib/lib/bitset/table.c

DEFINITIONS
