maint/gnulib/lib/bitset/list.c

/* */
This source file includes following definitions.
lbitset_elt_alloc
lbitset_elt_calloc
lbitset_elt_free
lbitset_elt_unlink
lbitset_prune
lbitset_elt_zero_p
lbitset_elt_link
lbitset_elt_find
lbitset_weed
lbitset_zero
lbitset_equal_p
lbitset_copy_
lbitset_copy
lbitset_copy_cmp
lbitset_resize
lbitset_set
lbitset_reset
lbitset_test
lbitset_free
lbitset_list_reverse
lbitset_list
lbitset_empty_p
lbitset_unused_clear
lbitset_ones
lbitset_not
lbitset_subset_p
lbitset_disjoint_p
lbitset_op3_cmp
lbitset_and_cmp
lbitset_and
lbitset_andn_cmp
lbitset_andn
lbitset_or_cmp
lbitset_or
lbitset_xor_cmp
lbitset_xor
lbitset_bytes
lbitset_init
lbitset_release_memory
debug_lbitset
   1 /* Functions to support link list bitsets.
   2 
   3    Copyright (C) 2002-2004, 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/list.h"
  24 
  25 #include <stddef.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 
  30 #include "obstack.h"
  31 
  32 /* This file implements linked-list bitsets.  These bitsets can be of
  33    arbitrary length and are more efficient than arrays of bits for
  34    large sparse sets.
  35 
  36    Usually if all the bits in an element are zero we remove the element
  37    from the list.  However, a side effect of the bit caching is that we
  38    do not always notice when an element becomes zero.  Hence the
  39    lbitset_weed function which removes zero elements.  */
  40 
  41 
  42 /* Number of words to use for each element.  The larger the value the
  43    greater the size of the cache and the shorter the time to find a given bit
  44    but the more memory wasted for sparse bitsets and the longer the time
  45    to search for set bits.
  46 
  47    The routines that dominate timing profiles are lbitset_elt_find
  48    and lbitset_elt_link, especially when accessing the bits randomly.  */
  49 
  50 #define LBITSET_ELT_WORDS 2
  51 
  52 typedef bitset_word lbitset_word;
  53 
  54 #define LBITSET_WORD_BITS BITSET_WORD_BITS
  55 
  56 /* Number of bits stored in each element.  */
  57 #define LBITSET_ELT_BITS \
  58   ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
  59 
  60 /* Lbitset element.   We use an array of bits for each element.
  61    These are linked together in a doubly-linked list.  */
  62 typedef struct lbitset_elt_struct
  63 {
  64   struct lbitset_elt_struct *next;      /* Next element.  */
  65   struct lbitset_elt_struct *prev;      /* Previous element.  */
  66   bitset_windex index;  /* bitno / BITSET_WORD_BITS.  */
  67   bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set.  */
  68 }
  69 lbitset_elt;
  70 
  71 
  72 enum lbitset_find_mode
  73   { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
  74 
  75 static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits.  */
  76 
  77 /* Obstack to allocate bitset elements from.  */
  78 static struct obstack lbitset_obstack;
  79 static bool lbitset_obstack_init = false;
  80 static lbitset_elt *lbitset_free_list;  /* Free list of bitset elements.  */
  81 
  82 extern void debug_lbitset (bitset);
  83 
  84 #define LBITSET_CURRENT1(X) \
  85   ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
  86 
  87 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
  88 
  89 #define LBITSET_HEAD(X) ((X)->l.head)
  90 #define LBITSET_TAIL(X) ((X)->l.tail)
  91 
  92 /* Allocate a lbitset element.  The bits are not cleared.  */
  93 static inline lbitset_elt *
  94 lbitset_elt_alloc (void)
     /*  */
  95 {
  96   lbitset_elt *elt;
  97 
  98   if (lbitset_free_list != 0)
  99     {
 100       elt = lbitset_free_list;
 101       lbitset_free_list = elt->next;
 102     }
 103   else
 104     {
 105       if (!lbitset_obstack_init)
 106         {
 107           lbitset_obstack_init = true;
 108 
 109           /* Let particular systems override the size of a chunk.  */
 110 
 111 #ifndef OBSTACK_CHUNK_SIZE
 112 # define OBSTACK_CHUNK_SIZE 0
 113 #endif
 114 
 115           /* Let them override the alloc and free routines too.  */
 116 
 117 #ifndef OBSTACK_CHUNK_ALLOC
 118 # define OBSTACK_CHUNK_ALLOC xmalloc
 119 #endif
 120 
 121 #ifndef OBSTACK_CHUNK_FREE
 122 # define OBSTACK_CHUNK_FREE free
 123 #endif
 124 
 125 #if !(defined __GNUC__ || defined __clang__)
 126 # define __alignof__(type) 0
 127 #endif
 128 
 129           obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
 130                                       __alignof__ (lbitset_elt),
 131                                       OBSTACK_CHUNK_ALLOC,
 132                                       OBSTACK_CHUNK_FREE);
 133         }
 134 
 135       /* Perhaps we should add a number of new elements to the free
 136          list.  */
 137       elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack,
 138                                            sizeof (lbitset_elt));
 139     }
 140 
 141   return elt;
 142 }
 143 
 144 
 145 /* Allocate a lbitset element.  The bits are cleared.  */
 146 static inline lbitset_elt *
 147 lbitset_elt_calloc (void)
     /*  */
 148 {
 149   lbitset_elt *elt = lbitset_elt_alloc ();
 150   memset (elt->words, 0, sizeof (elt->words));
 151   return elt;
 152 }
 153 
 154 
 155 static inline void
 156 lbitset_elt_free (lbitset_elt *elt)
     /*  */
 157 {
 158   elt->next = lbitset_free_list;
 159   lbitset_free_list = elt;
 160 }
 161 
 162 
 163 /* Unlink element ELT from bitset BSET.  */
 164 static inline void
 165 lbitset_elt_unlink (bitset bset, lbitset_elt *elt)
     /*  */
 166 {
 167   lbitset_elt *next = elt->next;
 168   lbitset_elt *prev = elt->prev;
 169 
 170   if (prev)
 171     prev->next = next;
 172 
 173   if (next)
 174     next->prev = prev;
 175 
 176   if (LBITSET_HEAD (bset) == elt)
 177     LBITSET_HEAD (bset) = next;
 178   if (LBITSET_TAIL (bset) == elt)
 179     LBITSET_TAIL (bset) = prev;
 180 
 181   /* Update cache pointer.  Since the first thing we try is to insert
 182      before current, make current the next entry in preference to the
 183      previous.  */
 184   if (LBITSET_CURRENT (bset) == elt)
 185     {
 186       if (next)
 187         {
 188           bset->b.cdata = next->words;
 189           bset->b.cindex = next->index;
 190         }
 191       else if (prev)
 192         {
 193           bset->b.cdata = prev->words;
 194           bset->b.cindex = prev->index;
 195         }
 196       else
 197         {
 198           bset->b.csize = 0;
 199           bset->b.cdata = 0;
 200         }
 201     }
 202 
 203   lbitset_elt_free (elt);
 204 }
 205 
 206 
 207 /* Cut the chain of bitset BSET before element ELT and free the
 208    elements.  */
 209 static inline void
 210 lbitset_prune (bitset bset, lbitset_elt *elt)
     /*  */
 211 {
 212   if (!elt)
 213     return;
 214 
 215   if (elt->prev)
 216     {
 217       LBITSET_TAIL (bset) = elt->prev;
 218       bset->b.cdata = elt->prev->words;
 219       bset->b.cindex = elt->prev->index;
 220       elt->prev->next = 0;
 221     }
 222   else
 223     {
 224       LBITSET_HEAD (bset) = 0;
 225       LBITSET_TAIL (bset) = 0;
 226       bset->b.cdata = 0;
 227       bset->b.csize = 0;
 228     }
 229 
 230   lbitset_elt *next;
 231   for (; elt; elt = next)
 232     {
 233       next = elt->next;
 234       lbitset_elt_free (elt);
 235     }
 236 }
 237 
 238 
 239 /* Are all bits in an element zero?  */
 240 static inline bool
 241 lbitset_elt_zero_p (lbitset_elt *elt)
     /*  */
 242 {
 243   for (int i = 0; i < LBITSET_ELT_WORDS; i++)
 244     if (elt->words[i])
 245       return false;
 246   return true;
 247 }
 248 
 249 
 250 /* Link the bitset element into the current bitset linked list.  */
 251 static inline void
 252 lbitset_elt_link (bitset bset, lbitset_elt *elt)
     /*  */
 253 {
 254   bitset_windex windex = elt->index;
 255 
 256   lbitset_elt *current = bset->b.csize ? LBITSET_CURRENT (bset) : LBITSET_HEAD (bset);
 257 
 258   /* If this is the first and only element, add it in.  */
 259   if (LBITSET_HEAD (bset) == 0)
 260     {
 261       elt->next = elt->prev = 0;
 262       LBITSET_HEAD (bset) = elt;
 263       LBITSET_TAIL (bset) = elt;
 264     }
 265 
 266   /* If this index is less than that of the current element, it goes
 267      somewhere before the current element.  */
 268   else if (windex < bset->b.cindex)
 269     {
 270       lbitset_elt *ptr;
 271       for (ptr = current;
 272            ptr->prev && ptr->prev->index > windex; ptr = ptr->prev)
 273         continue;
 274 
 275       if (ptr->prev)
 276         ptr->prev->next = elt;
 277       else
 278         LBITSET_HEAD (bset) = elt;
 279 
 280       elt->prev = ptr->prev;
 281       elt->next = ptr;
 282       ptr->prev = elt;
 283     }
 284 
 285   /* Otherwise, it must go somewhere after the current element.  */
 286   else
 287     {
 288       lbitset_elt *ptr;
 289       for (ptr = current;
 290            ptr->next && ptr->next->index < windex; ptr = ptr->next)
 291         continue;
 292 
 293       if (ptr->next)
 294         ptr->next->prev = elt;
 295       else
 296         LBITSET_TAIL (bset) = elt;
 297 
 298       elt->next = ptr->next;
 299       elt->prev = ptr;
 300       ptr->next = elt;
 301     }
 302 
 303   /* Set up so this is the first element searched.  */
 304   bset->b.cindex = windex;
 305   bset->b.csize = LBITSET_ELT_WORDS;
 306   bset->b.cdata = elt->words;
 307 }
 308 
 309 
 310 static lbitset_elt *
 311 lbitset_elt_find (bitset bset, bitset_windex windex,
     /*  */
 312                   enum lbitset_find_mode mode)
 313 {
 314   lbitset_elt *current;
 315 
 316   if (bset->b.csize)
 317     {
 318       current = LBITSET_CURRENT (bset);
 319       /* Check if element is the cached element.  */
 320       if ((windex - bset->b.cindex) < bset->b.csize)
 321         return current;
 322     }
 323   else
 324     {
 325       current = LBITSET_HEAD (bset);
 326     }
 327 
 328   if (current)
 329     {
 330       lbitset_elt *elt;
 331       if (windex < bset->b.cindex)
 332         {
 333           for (elt = current;
 334                elt->prev && elt->index > windex; elt = elt->prev)
 335             continue;
 336         }
 337       else
 338         {
 339           for (elt = current;
 340                elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
 341                elt = elt->next)
 342             continue;
 343         }
 344 
 345       /* ELT is the nearest to the one we want.  If it's not the one
 346          we want, the one we want does not exist.  */
 347       if (windex - elt->index < LBITSET_ELT_WORDS)
 348         {
 349           bset->b.cindex = elt->index;
 350           bset->b.csize = LBITSET_ELT_WORDS;
 351           bset->b.cdata = elt->words;
 352           return elt;
 353         }
 354     }
 355 
 356   switch (mode)
 357     {
 358     default:
 359       abort ();
 360 
 361     case LBITSET_FIND:
 362       return 0;
 363 
 364     case LBITSET_CREATE:
 365       windex -= windex % LBITSET_ELT_WORDS;
 366       lbitset_elt *elt = lbitset_elt_calloc ();
 367       elt->index = windex;
 368       lbitset_elt_link (bset, elt);
 369       return elt;
 370 
 371     case LBITSET_SUBST:
 372       return &lbitset_zero_elts[0];
 373     }
 374 }
 375 
 376 
 377 /* Weed out the zero elements from the list.  */
 378 static inline void
 379 lbitset_weed (bitset bset)
     /*  */
 380 {
 381   lbitset_elt *next;
 382   for (lbitset_elt *elt = LBITSET_HEAD (bset); elt; elt = next)
 383     {
 384       next = elt->next;
 385       if (lbitset_elt_zero_p (elt))
 386         lbitset_elt_unlink (bset, elt);
 387     }
 388 }
 389 
 390 
 391 /* Set all bits in the bitset to zero.  */
 392 static void
 393 lbitset_zero (bitset bset)
     /*  */
 394 {
 395   lbitset_elt *head = LBITSET_HEAD (bset);
 396   if (!head)
 397     return;
 398 
 399   /* Clear a bitset by freeing the linked list at the head element.  */
 400   lbitset_prune (bset, head);
 401 }
 402 
 403 
 404 /* Is DST == SRC?  */
 405 static inline bool
 406 lbitset_equal_p (bitset dst, bitset src)
     /*  */
 407 {
 408   if (src == dst)
 409     return true;
 410 
 411   lbitset_weed (src);
 412   lbitset_weed (dst);
 413   lbitset_elt *selt;
 414   lbitset_elt *delt;
 415   for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
 416        selt && delt; selt = selt->next, delt = delt->next)
 417     {
 418       if (selt->index != delt->index)
 419         return false;
 420 
 421       for (int j = 0; j < LBITSET_ELT_WORDS; j++)
 422         if (delt->words[j] != selt->words[j])
 423           return false;
 424     }
 425   return !selt && !delt;
 426 }
 427 
 428 
 429 /* Copy bits from bitset SRC to bitset DST.  */
 430 static inline void
 431 lbitset_copy_ (bitset dst, bitset src)
     /*  */
 432 {
 433   if (src == dst)
 434     return;
 435 
 436   lbitset_zero (dst);
 437 
 438   lbitset_elt *head = LBITSET_HEAD (src);
 439   if (!head)
 440     return;
 441 
 442   lbitset_elt *prev = 0;
 443   lbitset_elt *tmp;
 444   for (lbitset_elt *elt = head; elt; elt = elt->next)
 445     {
 446       tmp = lbitset_elt_alloc ();
 447       tmp->index = elt->index;
 448       tmp->prev = prev;
 449       tmp->next = 0;
 450       if (prev)
 451         prev->next = tmp;
 452       else
 453         LBITSET_HEAD (dst) = tmp;
 454       prev = tmp;
 455 
 456       memcpy (tmp->words, elt->words, sizeof (elt->words));
 457     }
 458   LBITSET_TAIL (dst) = tmp;
 459 
 460   dst->b.csize = LBITSET_ELT_WORDS;
 461   dst->b.cdata = LBITSET_HEAD (dst)->words;
 462   dst->b.cindex = LBITSET_HEAD (dst)->index;
 463 }
 464 
 465 
 466 static void
 467 lbitset_copy (bitset dst, bitset src)
     /*  */
 468 {
 469   if (BITSET_COMPATIBLE_ (dst, src))
 470     lbitset_copy_ (dst, src);
 471   else
 472     bitset_copy_ (dst, src);
 473 }
 474 
 475 /* Copy bits from bitset SRC to bitset DST.  Return true if
 476    bitsets different.  */
 477 static inline bool
 478 lbitset_copy_cmp (bitset dst, bitset src)
     /*  */
 479 {
 480   if (src == dst)
 481     return false;
 482 
 483   if (!LBITSET_HEAD (dst))
 484     {
 485       lbitset_copy (dst, src);
 486       return LBITSET_HEAD (src) != 0;
 487     }
 488 
 489   if (lbitset_equal_p (dst, src))
 490     return false;
 491 
 492   lbitset_copy (dst, src);
 493   return true;
 494 }
 495 
 496 
 497 static bitset_bindex
 498 lbitset_resize (bitset src, bitset_bindex size)
     /*  */
 499 {
 500   BITSET_NBITS_ (src) = size;
 501 
 502   /* Need to prune any excess bits.  FIXME.  */
 503   return size;
 504 }
 505 
 506 /* Set bit BITNO in bitset DST.  */
 507 static void
 508 lbitset_set (bitset dst, bitset_bindex bitno)
     /*  */
 509 {
 510   bitset_windex windex = bitno / BITSET_WORD_BITS;
 511 
 512   lbitset_elt_find (dst, windex, LBITSET_CREATE);
 513 
 514   dst->b.cdata[windex - dst->b.cindex] |=
 515     (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
 516 }
 517 
 518 
 519 /* Reset bit BITNO in bitset DST.  */
 520 static void
 521 lbitset_reset (bitset dst, bitset_bindex bitno)
     /*  */
 522 {
 523   bitset_windex windex = bitno / BITSET_WORD_BITS;
 524 
 525   if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
 526     return;
 527 
 528   dst->b.cdata[windex - dst->b.cindex] &=
 529     ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
 530 
 531   /* If all the data is zero, perhaps we should unlink it now...  */
 532 }
 533 
 534 
 535 /* Test bit BITNO in bitset SRC.  */
 536 static bool
 537 lbitset_test (bitset src, bitset_bindex bitno)
     /*  */
 538 {
 539   bitset_windex windex = bitno / BITSET_WORD_BITS;
 540 
 541   return (lbitset_elt_find (src, windex, LBITSET_FIND)
 542           && ((src->b.cdata[windex - src->b.cindex]
 543                >> (bitno % BITSET_WORD_BITS))
 544               & 1));
 545 }
 546 
 547 
 548 static void
 549 lbitset_free (bitset bset)
     /*  */
 550 {
 551   lbitset_zero (bset);
 552 }
 553 
 554 
 555 /* Find list of up to NUM bits set in BSET starting from and including
 556  *NEXT and store in array LIST.  Return with actual number of bits
 557  found and with *NEXT indicating where search stopped.  */
 558 static bitset_bindex
 559 lbitset_list_reverse (bitset bset, bitset_bindex *list,
     /*  */
 560                       bitset_bindex num, bitset_bindex *next)
 561 {
 562   lbitset_elt *elt = LBITSET_TAIL (bset);
 563   if (!elt)
 564     return 0;
 565 
 566   bitset_bindex n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
 567   bitset_bindex rbitno = *next;
 568 
 569   if (rbitno >= n_bits)
 570     return 0;
 571 
 572   bitset_bindex bitno = n_bits - (rbitno + 1);
 573 
 574   bitset_windex windex = bitno / BITSET_WORD_BITS;
 575 
 576   /* Skip back to starting element.  */
 577   for (; elt && elt->index > windex; elt = elt->prev)
 578     continue;
 579 
 580   if (!elt)
 581     return 0;
 582 
 583   unsigned bitcnt;
 584   if (windex >= elt->index + LBITSET_ELT_WORDS)
 585     {
 586       /* We are trying to start in no-mans land so start
 587          at end of current elt.  */
 588       bitcnt = BITSET_WORD_BITS - 1;
 589       windex = elt->index + LBITSET_ELT_WORDS - 1;
 590     }
 591   else
 592     {
 593       bitcnt = bitno % BITSET_WORD_BITS;
 594     }
 595 
 596   bitset_bindex count = 0;
 597   bitset_bindex bitoff = windex * BITSET_WORD_BITS;
 598 
 599   /* If num is 1, we could speed things up with a binary search
 600      of the word of interest.  */
 601 
 602   while (elt)
 603     {
 604       bitset_word *srcp = elt->words;
 605 
 606       for (; (windex - elt->index) < LBITSET_ELT_WORDS;
 607            windex--)
 608         {
 609           bitset_word word = srcp[windex - elt->index];
 610           if (bitcnt + 1 < BITSET_WORD_BITS)
 611             /* We're starting in the middle of a word: smash bits to ignore.  */
 612             word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
 613           BITSET_FOR_EACH_BIT_REVERSE(pos, word)
 614             {
 615               list[count++] = bitoff + pos;
 616               if (count >= num)
 617                 {
 618                   *next = n_bits - (bitoff + pos);
 619                   return count;
 620                 }
 621             }
 622           bitoff -= BITSET_WORD_BITS;
 623           bitcnt = BITSET_WORD_BITS - 1;
 624         }
 625 
 626       elt = elt->prev;
 627       if (elt)
 628         {
 629           windex = elt->index + LBITSET_ELT_WORDS - 1;
 630           bitoff = windex * BITSET_WORD_BITS;
 631         }
 632     }
 633 
 634   *next = n_bits - (bitoff + 1);
 635   return count;
 636 }
 637 
 638 
 639 /* Find list of up to NUM bits set in BSET starting from and including
 640    *NEXT and store in array LIST.  Return with actual number of bits
 641    found and with *NEXT indicating where search stopped.  */
 642 static bitset_bindex
 643 lbitset_list (bitset bset, bitset_bindex *list,
     /*  */
 644               bitset_bindex num, bitset_bindex *next)
 645 {
 646   lbitset_elt *head = LBITSET_HEAD (bset);
 647   if (!head)
 648     return 0;
 649 
 650   bitset_windex windex;
 651   lbitset_elt *elt;
 652 
 653   bitset_bindex bitno = *next;
 654   bitset_bindex count = 0;
 655 
 656   if (!bitno)
 657     {
 658       /* This is the most common case.  */
 659 
 660       /* Start with the first element.  */
 661       elt = head;
 662       windex = elt->index;
 663       bitno = windex * BITSET_WORD_BITS;
 664     }
 665   else
 666     {
 667       windex = bitno / BITSET_WORD_BITS;
 668 
 669       /* Skip to starting element.  */
 670       for (elt = head;
 671            elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
 672            elt = elt->next)
 673         continue;
 674 
 675       if (!elt)
 676         return 0;
 677 
 678       if (windex < elt->index)
 679         {
 680           windex = elt->index;
 681           bitno = windex * BITSET_WORD_BITS;
 682         }
 683       else
 684         {
 685           bitset_word *srcp = elt->words;
 686 
 687           /* We are starting within an element.  */
 688 
 689           for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
 690             {
 691               bitset_word word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS);
 692               BITSET_FOR_EACH_BIT (pos, word)
 693                 {
 694                   list[count++] = bitno + pos;
 695                   if (count >= num)
 696                     {
 697                       *next = bitno + pos + 1;
 698                       return count;
 699                     }
 700                 }
 701               bitno = (windex + 1) * BITSET_WORD_BITS;
 702             }
 703 
 704           elt = elt->next;
 705           if (elt)
 706             {
 707               windex = elt->index;
 708               bitno = windex * BITSET_WORD_BITS;
 709             }
 710         }
 711     }
 712 
 713   while (elt)
 714     {
 715       bitset_word *srcp = elt->words;
 716 
 717       /* Is there enough room to avoid checking in each iteration? */
 718       if ((count + LBITSET_ELT_BITS) < num)
 719         {
 720           /* The coast is clear, plant boot!  */
 721 
 722 #if LBITSET_ELT_WORDS == 2
 723           bitset_word word = srcp[0];
 724           if (word)
 725             BITSET_FOR_EACH_BIT (pos, word)
 726               list[count++] = bitno + pos;
 727           windex++;
 728           bitno = windex * BITSET_WORD_BITS;
 729 
 730           word = srcp[1];
 731           if (word)
 732             BITSET_FOR_EACH_BIT (pos, word)
 733               list[count++] = bitno + pos;
 734           windex++;
 735           bitno = windex * BITSET_WORD_BITS;
 736 #else
 737           for (int i = 0; i < LBITSET_ELT_WORDS; i++)
 738             {
 739               bitset_word word = srcp[i];
 740               if (word)
 741                 BITSET_FOR_EACH_BIT (pos, word)
 742                   list[count++] = bitno + pos;
 743               windex++;
 744               bitno = windex * BITSET_WORD_BITS;
 745             }
 746 #endif
 747         }
 748       else
 749         {
 750           /* Tread more carefully since we need to check
 751              if array overflows.  */
 752           for (int i = 0; i < LBITSET_ELT_WORDS; i++)
 753             {
 754               bitset_word word = srcp[i];
 755               if (word)
 756                 BITSET_FOR_EACH_BIT (pos, word)
 757                   {
 758                     list[count++] = bitno + pos;
 759                     if (count >= num)
 760                       {
 761                         *next = bitno + pos + 1;
 762                         return count;
 763                       }
 764                   }
 765               windex++;
 766               bitno = windex * BITSET_WORD_BITS;
 767             }
 768         }
 769 
 770       elt = elt->next;
 771       if (elt)
 772         {
 773           windex = elt->index;
 774           bitno = windex * BITSET_WORD_BITS;
 775         }
 776     }
 777 
 778   *next = bitno;
 779   return count;
 780 }
 781 
 782 
 783 static bool
 784 lbitset_empty_p (bitset dst)
     /*  */
 785 {
 786   lbitset_elt *elt;
 787   lbitset_elt *next;
 788 
 789   for (elt = LBITSET_HEAD (dst); elt; elt = next)
 790     {
 791       next = elt->next;
 792       if (!lbitset_elt_zero_p (elt))
 793         return false;
 794       /* Weed as we go.  */
 795       lbitset_elt_unlink (dst, elt);
 796     }
 797 
 798   return true;
 799 }
 800 
 801 
 802 /* Ensure that any unused bits within the last element are clear.  */
 803 static inline void
 804 lbitset_unused_clear (bitset dst)
     /*  */
 805 {
 806   bitset_bindex n_bits = BITSET_SIZE_ (dst);
 807   unsigned last_bit = n_bits % LBITSET_ELT_BITS;
 808 
 809   if (last_bit)
 810     {
 811       lbitset_elt *elt = LBITSET_TAIL (dst);
 812       bitset_word *srcp = elt->words;
 813       bitset_windex windex = n_bits / BITSET_WORD_BITS;
 814 
 815       srcp[windex - elt->index]
 816         &= ((bitset_word) 1 << (last_bit % BITSET_WORD_BITS)) - 1;
 817       windex++;
 818 
 819       for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
 820         srcp[windex - elt->index] = 0;
 821     }
 822 }
 823 
 824 
 825 static void
 826 lbitset_ones (bitset dst)
     /*  */
 827 {
 828   /* This is a decidedly unfriendly operation for a linked list
 829      bitset!  It makes a sparse bitset become dense.  An alternative
 830      is to have a flag that indicates that the bitset stores the
 831      complement of what it indicates.  */
 832 
 833   bitset_windex windex
 834     = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
 835 
 836   for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
 837     {
 838       /* Create new elements if they cannot be found.  */
 839       lbitset_elt *elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 840       memset (elt->words, -1, sizeof (elt->words));
 841     }
 842 
 843   lbitset_unused_clear (dst);
 844 }
 845 
 846 
 847 static void
 848 lbitset_not (bitset dst, bitset src)
     /*  */
 849 {
 850   bitset_windex windex
 851     = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
 852 
 853   for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
 854     {
 855       /* Create new elements for dst if they cannot be found
 856          or substitute zero elements if src elements not found.  */
 857       lbitset_elt *selt = lbitset_elt_find (src, i, LBITSET_SUBST);
 858       lbitset_elt *delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
 859 
 860       for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
 861         delt->words[j] = ~selt->words[j];
 862     }
 863   lbitset_unused_clear (dst);
 864   lbitset_weed (dst);
 865 }
 866 
 867 
 868 /* Is DST == DST | SRC?  */
 869 static bool
 870 lbitset_subset_p (bitset dst, bitset src)
     /*  */
 871 {
 872   for (lbitset_elt *selt = LBITSET_HEAD (src), *delt = LBITSET_HEAD (dst);
 873        selt || delt; selt = selt->next, delt = delt->next)
 874     {
 875       if (!selt)
 876         selt = &lbitset_zero_elts[0];
 877       else if (!delt)
 878         delt = &lbitset_zero_elts[0];
 879       else if (selt->index != delt->index)
 880         {
 881           if (selt->index < delt->index)
 882             {
 883               lbitset_zero_elts[2].next = delt;
 884               delt = &lbitset_zero_elts[2];
 885             }
 886           else
 887             {
 888               lbitset_zero_elts[1].next = selt;
 889               selt = &lbitset_zero_elts[1];
 890             }
 891         }
 892 
 893       for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
 894         if (delt->words[j] != (selt->words[j] | delt->words[j]))
 895           return false;
 896     }
 897   return true;
 898 }
 899 
 900 
 901 /* Is DST & SRC == 0?  */
 902 static bool
 903 lbitset_disjoint_p (bitset dst, bitset src)
     /*  */
 904 {
 905   for (lbitset_elt *selt = LBITSET_HEAD (src), *delt = LBITSET_HEAD (dst);
 906        selt && delt; selt = selt->next, delt = delt->next)
 907     {
 908       if (selt->index != delt->index)
 909         {
 910           if (selt->index < delt->index)
 911             {
 912               lbitset_zero_elts[2].next = delt;
 913               delt = &lbitset_zero_elts[2];
 914             }
 915           else
 916             {
 917               lbitset_zero_elts[1].next = selt;
 918               selt = &lbitset_zero_elts[1];
 919             }
 920           /* Since the elements are different, there is no
 921              intersection of these elements.  */
 922           continue;
 923         }
 924 
 925       for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
 926         if (selt->words[j] & delt->words[j])
 927           return false;
 928     }
 929   return true;
 930 }
 931 
 932 
 933 static bool
 934 lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
     /*  */
 935 {
 936   lbitset_elt *selt1 = LBITSET_HEAD (src1);
 937   lbitset_elt *selt2 = LBITSET_HEAD (src2);
 938   lbitset_elt *delt = LBITSET_HEAD (dst);
 939   bool changed = false;
 940 
 941   LBITSET_HEAD (dst) = 0;
 942   dst->b.csize = 0;
 943 
 944   bitset_windex windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
 945   bitset_windex windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
 946 
 947   while (selt1 || selt2)
 948     {
 949       bitset_windex windex;
 950       lbitset_elt *stmp1;
 951       lbitset_elt *stmp2;
 952 
 953       /* Figure out whether we need to substitute zero elements for
 954          missing links.  */
 955       if (windex1 == windex2)
 956         {
 957           windex = windex1;
 958           stmp1 = selt1;
 959           stmp2 = selt2;
 960           selt1 = selt1->next;
 961           windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
 962           selt2 = selt2->next;
 963           windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
 964         }
 965       else if (windex1 < windex2)
 966         {
 967           windex = windex1;
 968           stmp1 = selt1;
 969           stmp2 = &lbitset_zero_elts[0];
 970           selt1 = selt1->next;
 971           windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
 972         }
 973       else
 974         {
 975           windex = windex2;
 976           stmp1 = &lbitset_zero_elts[0];
 977           stmp2 = selt2;
 978           selt2 = selt2->next;
 979           windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
 980         }
 981 
 982       /* Find the appropriate element from DST.  Begin by discarding
 983          elements that we've skipped.  */
 984       lbitset_elt *dtmp;
 985       while (delt && delt->index < windex)
 986         {
 987           changed = true;
 988           dtmp = delt;
 989           delt = delt->next;
 990           lbitset_elt_free (dtmp);
 991         }
 992       if (delt && delt->index == windex)
 993         {
 994           dtmp = delt;
 995           delt = delt->next;
 996         }
 997       else
 998         dtmp = lbitset_elt_calloc ();
 999 
1000       /* Do the operation, and if any bits are set, link it into the
1001          linked list.  */
1002       bitset_word *srcp1 = stmp1->words;
1003       bitset_word *srcp2 = stmp2->words;
1004       bitset_word *dstp = dtmp->words;
1005       switch (op)
1006         {
1007         default:
1008           abort ();
1009 
1010         case BITSET_OP_OR:
1011           for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1012             {
1013               bitset_word tmp = *srcp1++ | *srcp2++;
1014 
1015               if (*dstp != tmp)
1016                 {
1017                   changed = true;
1018                   *dstp = tmp;
1019                 }
1020             }
1021           break;
1022 
1023         case BITSET_OP_AND:
1024           for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1025             {
1026               bitset_word tmp = *srcp1++ & *srcp2++;
1027 
1028               if (*dstp != tmp)
1029                 {
1030                   changed = true;
1031                   *dstp = tmp;
1032                 }
1033             }
1034           break;
1035 
1036         case BITSET_OP_XOR:
1037           for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1038             {
1039               bitset_word tmp = *srcp1++ ^ *srcp2++;
1040 
1041               if (*dstp != tmp)
1042                 {
1043                   changed = true;
1044                   *dstp = tmp;
1045                 }
1046             }
1047           break;
1048 
1049         case BITSET_OP_ANDN:
1050           for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1051             {
1052               bitset_word tmp = *srcp1++ & ~(*srcp2++);
1053 
1054               if (*dstp != tmp)
1055                 {
1056                   changed = true;
1057                   *dstp = tmp;
1058                 }
1059             }
1060           break;
1061         }
1062 
1063       if (!lbitset_elt_zero_p (dtmp))
1064         {
1065           dtmp->index = windex;
1066           /* Perhaps this could be optimised...  */
1067           lbitset_elt_link (dst, dtmp);
1068         }
1069       else
1070         {
1071           lbitset_elt_free (dtmp);
1072         }
1073     }
1074 
1075   /* If we have elements of DST left over, free them all.  */
1076   if (delt)
1077     {
1078       changed = true;
1079       lbitset_prune (dst, delt);
1080     }
1081 
1082   return changed;
1083 }
1084 
1085 
1086 static bool
1087 lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
1088 {
1089   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1090   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1091 
1092   if (!selt2)
1093     {
1094       lbitset_weed (dst);
1095       bool changed = !LBITSET_HEAD (dst);
1096       lbitset_zero (dst);
1097       return changed;
1098     }
1099   else if (!selt1)
1100     {
1101       lbitset_weed (dst);
1102       bool changed = !LBITSET_HEAD (dst);
1103       lbitset_zero (dst);
1104       return changed;
1105     }
1106   else
1107     return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1108 }
1109 
1110 
1111 static void
1112 lbitset_and (bitset dst, bitset src1, bitset src2)
     /*  */
1113 {
1114   lbitset_and_cmp (dst, src1, src2);
1115 }
1116 
1117 
1118 static bool
1119 lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
1120 {
1121   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1122   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1123 
1124   if (!selt2)
1125     {
1126       return lbitset_copy_cmp (dst, src1);
1127     }
1128   else if (!selt1)
1129     {
1130       lbitset_weed (dst);
1131       bool changed = !LBITSET_HEAD (dst);
1132       lbitset_zero (dst);
1133       return changed;
1134     }
1135   else
1136     return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1137 }
1138 
1139 
1140 static void
1141 lbitset_andn (bitset dst, bitset src1, bitset src2)
     /*  */
1142 {
1143   lbitset_andn_cmp (dst, src1, src2);
1144 }
1145 
1146 
1147 static bool
1148 lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
1149 {
1150   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1151   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1152 
1153   if (!selt2)
1154     return lbitset_copy_cmp (dst, src1);
1155   else if (!selt1)
1156     return lbitset_copy_cmp (dst, src2);
1157   else
1158     return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1159 }
1160 
1161 
1162 static void
1163 lbitset_or (bitset dst, bitset src1, bitset src2)
     /*  */
1164 {
1165   lbitset_or_cmp (dst, src1, src2);
1166 }
1167 
1168 
1169 static bool
1170 lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
     /*  */
1171 {
1172   lbitset_elt *selt1 = LBITSET_HEAD (src1);
1173   lbitset_elt *selt2 = LBITSET_HEAD (src2);
1174 
1175   if (!selt2)
1176     return lbitset_copy_cmp (dst, src1);
1177   else if (!selt1)
1178     return lbitset_copy_cmp (dst, src2);
1179   else
1180     return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1181 }
1182 
1183 
1184 static void
1185 lbitset_xor (bitset dst, bitset src1, bitset src2)
     /*  */
1186 {
1187   lbitset_xor_cmp (dst, src1, src2);
1188 }
1189 
1190 
1191 
1192 /* Vector of operations for linked-list bitsets.  */
1193 struct bitset_vtable lbitset_vtable = {
1194   lbitset_set,
1195   lbitset_reset,
1196   bitset_toggle_,
1197   lbitset_test,
1198   lbitset_resize,
1199   bitset_size_,
1200   bitset_count_,
1201   lbitset_empty_p,
1202   lbitset_ones,
1203   lbitset_zero,
1204   lbitset_copy,
1205   lbitset_disjoint_p,
1206   lbitset_equal_p,
1207   lbitset_not,
1208   lbitset_subset_p,
1209   lbitset_and,
1210   lbitset_and_cmp,
1211   lbitset_andn,
1212   lbitset_andn_cmp,
1213   lbitset_or,
1214   lbitset_or_cmp,
1215   lbitset_xor,
1216   lbitset_xor_cmp,
1217   bitset_and_or_,
1218   bitset_and_or_cmp_,
1219   bitset_andn_or_,
1220   bitset_andn_or_cmp_,
1221   bitset_or_and_,
1222   bitset_or_and_cmp_,
1223   lbitset_list,
1224   lbitset_list_reverse,
1225   lbitset_free,
1226   BITSET_LIST
1227 };
1228 
1229 
1230 /* Return size of initial structure.  */
1231 size_t
1232 lbitset_bytes (MAYBE_UNUSED bitset_bindex n_bits)
     /*  */
1233 {
1234   return sizeof (struct lbitset_struct);
1235 }
1236 
1237 
1238 /* Initialize a bitset.  */
1239 bitset
1240 lbitset_init (bitset bset, MAYBE_UNUSED bitset_bindex n_bits)
     /*  */
1241 {
1242   BITSET_NBITS_ (bset) = n_bits;
1243   bset->b.vtable = &lbitset_vtable;
1244   return bset;
1245 }
1246 
1247 
1248 void
1249 lbitset_release_memory (void)
     /*  */
1250 {
1251   lbitset_free_list = 0;
1252   if (lbitset_obstack_init)
1253     {
1254       lbitset_obstack_init = false;
1255       obstack_free (&lbitset_obstack, NULL);
1256     }
1257 }
1258 
1259 
1260 /* Function to be called from debugger to debug lbitset.  */
1261 void
1262 debug_lbitset (bitset bset)
     /*  */
1263 {
1264   if (!bset)
1265     return;
1266 
1267   for (lbitset_elt *elt = LBITSET_HEAD (bset); elt; elt = elt->next)
1268     {
1269       fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index);
1270       for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++)
1271         {
1272           bitset_word word = elt->words[i];
1273 
1274           fprintf (stderr, "  Word %u:", i);
1275           for (unsigned j = 0; j < LBITSET_WORD_BITS; j++)
1276             if ((word & ((bitset_word) 1 << j)))
1277               fprintf (stderr, " %u", j);
1278           fprintf (stderr, "\n");
1279         }
1280     }
1281 }
/* */
root/maint/gnulib/lib/bitset/list.c

DEFINITIONS
