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