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