lib/lbitset.c

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