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