lib/lbitset.c

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