1/* Functions to support expandable bitsets.
2
3   Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc.
4
5   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
6
7   This program is free software: you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation, either version 3 of the License, or
10   (at your option) any later version.
11
12   This program is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
19
20#include <config.h>
21
22#include "ebitset.h"
23
24#include "obstack.h"
25#include <stdlib.h>
26#include <string.h>
27
28/* This file implements expandable bitsets.  These bitsets can be of
29   arbitrary length and are more efficient than arrays of bits for
30   large sparse sets.
31
32   Empty elements are represented by a NULL pointer in the table of
33   element pointers.  An alternative is to point to a special zero
34   element.  Similarly, we could represent an all 1's element with
35   another special ones element pointer.
36
37   Bitsets are commonly empty so we need to ensure that this special
38   case is fast.  A zero bitset is indicated when cdata is 0.  This is
39   conservative since cdata may be non zero and the bitset may still
40   be zero.
41
42   The bitset cache can be disabled either by setting cindex to
43   BITSET_WINDEX_MAX or by setting csize to 0.  Here
44   we use the former approach since cindex needs to be updated whenever
45   cdata is changed.
46*/
47
48
49/* Number of words to use for each element.  */
50#define EBITSET_ELT_WORDS 2
51
52/* Number of bits stored in each element.  */
53#define EBITSET_ELT_BITS \
54  ((unsigned int) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
55
56/* Ebitset element.  We use an array of bits.  */
57typedef struct ebitset_elt_struct
58{
59  union
60  {
61    bitset_word words[EBITSET_ELT_WORDS];	/* Bits that are set.  */
62    struct ebitset_elt_struct *next;
63  }
64  u;
65}
66ebitset_elt;
67
68
69typedef ebitset_elt *ebitset_elts;
70
71
72/* Number of elements to initially allocate.  */
73
74#ifndef EBITSET_INITIAL_SIZE
75#define EBITSET_INITIAL_SIZE 2
76#endif
77
78
79enum ebitset_find_mode
80  { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
81
82static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits.  */
83
84/* Obstack to allocate bitset elements from.  */
85static struct obstack ebitset_obstack;
86static bool ebitset_obstack_init = false;
87static ebitset_elt *ebitset_free_list;	/* Free list of bitset elements.  */
88
89#define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS)
90#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
91#define EBITSET_SIZE(BSET) EBITSET_N_ELTS (BITSET_NBITS_ (BSET))
92#define EBITSET_ASIZE(BSET) ((BSET)->e.size)
93
94#define EBITSET_NEXT(ELT) ((ELT)->u.next)
95#define EBITSET_WORDS(ELT) ((ELT)->u.words)
96
97/* Disable bitset cache and mark BSET as being zero.  */
98#define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
99	(BSET)->b.cdata = 0)
100
101#define EBITSET_CACHE_DISABLE(BSET)  ((BSET)->b.cindex = BITSET_WINDEX_MAX)
102
103/* Disable bitset cache and mark BSET as being possibly non-zero.  */
104#define EBITSET_NONZERO_SET(BSET) \
105 (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
106
107/* A conservative estimate of whether the bitset is zero.
108   This is non-zero only if we know for sure that the bitset is zero.  */
109#define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
110
111/* Enable cache to point to element with table index EINDEX.
112   The element must exist.  */
113#define EBITSET_CACHE_SET(BSET, EINDEX) \
114 ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
115  (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
116
117#undef min
118#undef max
119#define min(a, b) ((a) > (b) ? (b) : (a))
120#define max(a, b) ((a) > (b) ? (a) : (b))
121
122static bitset_bindex
123ebitset_resize (bitset src, bitset_bindex n_bits)
124{
125  bitset_windex oldsize;
126  bitset_windex newsize;
127
128  if (n_bits == BITSET_NBITS_ (src))
129    return n_bits;
130
131  oldsize = EBITSET_SIZE (src);
132  newsize = EBITSET_N_ELTS (n_bits);
133
134  if (oldsize < newsize)
135    {
136      bitset_windex size;
137
138      /* The bitset needs to grow.  If we already have enough memory
139	 allocated, then just zero what we need.  */
140      if (newsize > EBITSET_ASIZE (src))
141	{
142	  /* We need to allocate more memory.  When oldsize is
143	     non-zero this means that we are changing the size, so
144	     grow the bitset 25% larger than requested to reduce
145	     number of reallocations.  */
146
147	  if (oldsize == 0)
148	    size = newsize;
149	  else
150	    size = newsize + newsize / 4;
151
152	  EBITSET_ELTS (src)
153	    = realloc (EBITSET_ELTS (src), size * sizeof (ebitset_elt *));
154	  EBITSET_ASIZE (src) = size;
155	}
156
157      memset (EBITSET_ELTS (src) + oldsize, 0,
158	      (newsize - oldsize) * sizeof (ebitset_elt *));
159    }
160  else
161    {
162      /* The bitset needs to shrink.  There's no point deallocating
163	 the memory unless it is shrinking by a reasonable amount.  */
164      if ((oldsize - newsize) >= oldsize / 2)
165	{
166	  EBITSET_ELTS (src)
167	    = realloc (EBITSET_ELTS (src), newsize * sizeof (ebitset_elt *));
168	  EBITSET_ASIZE (src) = newsize;
169	}
170
171      /* Need to prune any excess bits.  FIXME.  */
172    }
173
174  BITSET_NBITS_ (src) = n_bits;
175  return n_bits;
176}
177
178
179/* Allocate a ebitset element.  The bits are not cleared.  */
180static inline ebitset_elt *
181ebitset_elt_alloc (void)
182{
183  ebitset_elt *elt;
184
185  if (ebitset_free_list != 0)
186    {
187      elt = ebitset_free_list;
188      ebitset_free_list = EBITSET_NEXT (elt);
189    }
190  else
191    {
192      if (!ebitset_obstack_init)
193	{
194	  ebitset_obstack_init = true;
195
196	  /* Let particular systems override the size of a chunk.  */
197
198#ifndef OBSTACK_CHUNK_SIZE
199#define OBSTACK_CHUNK_SIZE 0
200#endif
201
202	  /* Let them override the alloc and free routines too.  */
203
204#ifndef OBSTACK_CHUNK_ALLOC
205#define OBSTACK_CHUNK_ALLOC xmalloc
206#endif
207
208#ifndef OBSTACK_CHUNK_FREE
209#define OBSTACK_CHUNK_FREE free
210#endif
211
212#if ! defined __GNUC__ || __GNUC__ < 2
213#define __alignof__(type) 0
214#endif
215
216	  obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
217				      __alignof__ (ebitset_elt),
218				      OBSTACK_CHUNK_ALLOC,
219				      OBSTACK_CHUNK_FREE);
220	}
221
222      /* Perhaps we should add a number of new elements to the free
223	 list.  */
224      elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,
225					   sizeof (ebitset_elt));
226    }
227
228  return elt;
229}
230
231
232/* Allocate a ebitset element.  The bits are cleared.  */
233static inline ebitset_elt *
234ebitset_elt_calloc (void)
235{
236  ebitset_elt *elt;
237
238  elt = ebitset_elt_alloc ();
239  memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt)));
240  return elt;
241}
242
243
244static inline void
245ebitset_elt_free (ebitset_elt *elt)
246{
247  EBITSET_NEXT (elt) = ebitset_free_list;
248  ebitset_free_list = elt;
249}
250
251
252/* Remove element with index EINDEX from bitset BSET.  */
253static inline void
254ebitset_elt_remove (bitset bset, bitset_windex eindex)
255{
256  ebitset_elts *elts;
257  ebitset_elt *elt;
258
259  elts = EBITSET_ELTS (bset);
260
261  elt = elts[eindex];
262
263  elts[eindex] = 0;
264  ebitset_elt_free (elt);
265}
266
267
268/* Add ELT into elts at index EINDEX of bitset BSET.  */
269static inline void
270ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex)
271{
272  ebitset_elts *elts;
273
274  elts = EBITSET_ELTS (bset);
275  /* Assume that the elts entry not allocated.  */
276  elts[eindex] = elt;
277}
278
279
280/* Are all bits in an element zero?  */
281static inline bool
282ebitset_elt_zero_p (ebitset_elt *elt)
283{
284  int i;
285
286  for (i = 0; i < EBITSET_ELT_WORDS; i++)
287    if (EBITSET_WORDS (elt)[i])
288      return false;
289
290  return true;
291}
292
293
294static ebitset_elt *
295ebitset_elt_find (bitset bset, bitset_bindex bindex,
296		  enum ebitset_find_mode mode)
297{
298  ebitset_elt *elt;
299  bitset_windex size;
300  bitset_windex eindex;
301  ebitset_elts *elts;
302
303  eindex = bindex / EBITSET_ELT_BITS;
304
305  elts = EBITSET_ELTS (bset);
306  size = EBITSET_SIZE (bset);
307
308  if (eindex < size)
309    {
310      if ((elt = elts[eindex]))
311	{
312	  if (EBITSET_WORDS (elt) == bset->b.cdata)
313	    return elt;
314
315	  EBITSET_CACHE_SET (bset, eindex);
316	  return elt;
317	}
318    }
319
320  /* The element could not be found.  */
321
322  switch (mode)
323    {
324    default:
325      abort ();
326
327    case EBITSET_FIND:
328      return 0;
329
330    case EBITSET_CREATE:
331      if (eindex >= size)
332	ebitset_resize (bset, bindex);
333
334      /* Create a new element.  */
335      elt = ebitset_elt_calloc ();
336      ebitset_elt_add (bset, elt, eindex);
337      EBITSET_CACHE_SET (bset, eindex);
338      return elt;
339
340    case EBITSET_SUBST:
341      return &ebitset_zero_elts[0];
342    }
343}
344
345
346/* Weed out the zero elements from the elts.  */
347static inline bitset_windex
348ebitset_weed (bitset bset)
349{
350  ebitset_elts *elts;
351  bitset_windex j;
352  bitset_windex count;
353
354  if (EBITSET_ZERO_P (bset))
355    return 0;
356
357  elts = EBITSET_ELTS (bset);
358  count = 0;
359  for (j = 0; j < EBITSET_SIZE (bset); j++)
360    {
361      ebitset_elt *elt = elts[j];
362
363      if (elt)
364	{
365	  if (ebitset_elt_zero_p (elt))
366	    {
367	      ebitset_elt_remove (bset, j);
368	      count++;
369	    }
370	}
371      else
372	count++;
373    }
374
375  count = j - count;
376  if (!count)
377    {
378      /* All the bits are zero.  We could shrink the elts.
379	 For now just mark BSET as known to be zero.  */
380      EBITSET_ZERO_SET (bset);
381    }
382  else
383    EBITSET_NONZERO_SET (bset);
384
385  return count;
386}
387
388
389/* Set all bits in the bitset to zero.  */
390static inline void
391ebitset_zero (bitset bset)
392{
393  ebitset_elts *elts;
394  bitset_windex j;
395
396  if (EBITSET_ZERO_P (bset))
397    return;
398
399  elts = EBITSET_ELTS (bset);
400  for (j = 0; j < EBITSET_SIZE (bset); j++)
401    {
402      ebitset_elt *elt = elts[j];
403
404      if (elt)
405	ebitset_elt_remove (bset, j);
406    }
407
408  /* All the bits are zero.  We could shrink the elts.
409     For now just mark BSET as known to be zero.  */
410  EBITSET_ZERO_SET (bset);
411}
412
413
414static inline bool
415ebitset_equal_p (bitset dst, bitset src)
416{
417  ebitset_elts *selts;
418  ebitset_elts *delts;
419  bitset_windex j;
420
421  if (src == dst)
422    return true;
423
424  ebitset_weed (dst);
425  ebitset_weed (src);
426
427  if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
428    return false;
429
430  selts = EBITSET_ELTS (src);
431  delts = EBITSET_ELTS (dst);
432
433  for (j = 0; j < EBITSET_SIZE (src); j++)
434    {
435      unsigned int i;
436      ebitset_elt *selt = selts[j];
437      ebitset_elt *delt = delts[j];
438
439      if (!selt && !delt)
440	continue;
441      if ((selt && !delt) || (!selt && delt))
442	return false;
443
444      for (i = 0; i < EBITSET_ELT_WORDS; i++)
445	if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
446	  return false;
447    }
448  return true;
449}
450
451
452/* Copy bits from bitset SRC to bitset DST.  */
453static inline void
454ebitset_copy_ (bitset dst, bitset src)
455{
456  ebitset_elts *selts;
457  ebitset_elts *delts;
458  bitset_windex j;
459
460  if (src == dst)
461    return;
462
463  ebitset_zero (dst);
464
465  if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
466    ebitset_resize (dst, BITSET_NBITS_ (src));
467
468  selts = EBITSET_ELTS (src);
469  delts = EBITSET_ELTS (dst);
470  for (j = 0; j < EBITSET_SIZE (src); j++)
471    {
472      ebitset_elt *selt = selts[j];
473
474      if (selt)
475	{
476	  ebitset_elt *tmp;
477
478	  tmp = ebitset_elt_alloc ();
479	  delts[j] = tmp;
480	  memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
481		  sizeof (EBITSET_WORDS (selt)));
482	}
483    }
484  EBITSET_NONZERO_SET (dst);
485}
486
487
488/* Copy bits from bitset SRC to bitset DST.  Return true if
489   bitsets different.  */
490static inline bool
491ebitset_copy_cmp (bitset dst, bitset src)
492{
493  if (src == dst)
494    return false;
495
496  if (EBITSET_ZERO_P (dst))
497    {
498      ebitset_copy_ (dst, src);
499      return !EBITSET_ZERO_P (src);
500    }
501
502  if (ebitset_equal_p (dst, src))
503    return false;
504
505  ebitset_copy_ (dst, src);
506  return true;
507}
508
509
510/* Set bit BITNO in bitset DST.  */
511static void
512ebitset_set (bitset dst, bitset_bindex bitno)
513{
514  bitset_windex windex = bitno / BITSET_WORD_BITS;
515
516  ebitset_elt_find (dst, bitno, EBITSET_CREATE);
517
518  dst->b.cdata[windex - dst->b.cindex] |=
519    (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
520}
521
522
523/* Reset bit BITNO in bitset DST.  */
524static void
525ebitset_reset (bitset dst, bitset_bindex bitno)
526{
527  bitset_windex windex = bitno / BITSET_WORD_BITS;
528
529  if (!ebitset_elt_find (dst, bitno, EBITSET_FIND))
530    return;
531
532  dst->b.cdata[windex - dst->b.cindex] &=
533    ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
534
535  /* If all the data is zero, perhaps we should remove it now...
536     However, there is a good chance that the element will be needed
537     again soon.  */
538}
539
540
541/* Test bit BITNO in bitset SRC.  */
542static bool
543ebitset_test (bitset src, bitset_bindex bitno)
544{
545  bitset_windex windex = bitno / BITSET_WORD_BITS;
546
547  return (ebitset_elt_find (src, bitno, EBITSET_FIND)
548	  && ((src->b.cdata[windex - src->b.cindex]
549	       >> (bitno % BITSET_WORD_BITS))
550	      & 1));
551}
552
553
554static void
555ebitset_free (bitset bset)
556{
557  ebitset_zero (bset);
558  free (EBITSET_ELTS (bset));
559}
560
561
562/* Find list of up to NUM bits set in BSET starting from and including
563 *NEXT and store in array LIST.  Return with actual number of bits
564 found and with *NEXT indicating where search stopped.  */
565static bitset_bindex
566ebitset_list_reverse (bitset bset, bitset_bindex *list,
567		      bitset_bindex num, bitset_bindex *next)
568{
569  bitset_bindex n_bits;
570  bitset_bindex bitno;
571  bitset_bindex rbitno;
572  unsigned int bcount;
573  bitset_bindex boffset;
574  bitset_windex windex;
575  bitset_windex eindex;
576  bitset_windex woffset;
577  bitset_bindex count;
578  bitset_windex size;
579  ebitset_elts *elts;
580
581  if (EBITSET_ZERO_P (bset))
582    return 0;
583
584  size = EBITSET_SIZE (bset);
585  n_bits = size * EBITSET_ELT_BITS;
586  rbitno = *next;
587
588  if (rbitno >= n_bits)
589    return 0;
590
591  elts = EBITSET_ELTS (bset);
592
593  bitno = n_bits - (rbitno + 1);
594
595  windex = bitno / BITSET_WORD_BITS;
596  eindex = bitno / EBITSET_ELT_BITS;
597  woffset = windex - eindex * EBITSET_ELT_WORDS;
598
599  /* If num is 1, we could speed things up with a binary search
600     of the word of interest.  */
601
602  count = 0;
603  bcount = bitno % BITSET_WORD_BITS;
604  boffset = windex * BITSET_WORD_BITS;
605
606  do
607    {
608      ebitset_elt *elt;
609      bitset_word *srcp;
610
611      elt = elts[eindex];
612      if (elt)
613	{
614	  srcp = EBITSET_WORDS (elt);
615
616	  do
617	    {
618	      bitset_word word;
619
620	      word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
621
622	      for (; word; bcount--)
623		{
624		  if (word & BITSET_MSB)
625		    {
626		      list[count++] = boffset + bcount;
627		      if (count >= num)
628			{
629			  *next = n_bits - (boffset + bcount);
630			  return count;
631			}
632		    }
633		  word <<= 1;
634		}
635	      boffset -= BITSET_WORD_BITS;
636	      bcount = BITSET_WORD_BITS - 1;
637	    }
638	  while (woffset--);
639	}
640
641      woffset = EBITSET_ELT_WORDS - 1;
642      boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
643    }
644  while (eindex--);
645
646  *next = n_bits - (boffset + 1);
647  return count;
648}
649
650
651/* Find list of up to NUM bits set in BSET starting from and including
652 *NEXT and store in array LIST.  Return with actual number of bits
653 found and with *NEXT indicating where search stopped.  */
654static bitset_bindex
655ebitset_list (bitset bset, bitset_bindex *list,
656	      bitset_bindex num, bitset_bindex *next)
657{
658  bitset_bindex bitno;
659  bitset_windex windex;
660  bitset_windex eindex;
661  bitset_bindex count;
662  bitset_windex size;
663  ebitset_elt *elt;
664  bitset_word word;
665  ebitset_elts *elts;
666
667  if (EBITSET_ZERO_P (bset))
668    return 0;
669
670  bitno = *next;
671  count = 0;
672
673  elts = EBITSET_ELTS (bset);
674  size = EBITSET_SIZE (bset);
675  eindex = bitno / EBITSET_ELT_BITS;
676
677  if (bitno % EBITSET_ELT_BITS)
678    {
679      /* We need to start within an element.  This is not very common.  */
680
681      elt = elts[eindex];
682      if (elt)
683	{
684	  bitset_windex woffset;
685	  bitset_word *srcp = EBITSET_WORDS (elt);
686
687	  windex = bitno / BITSET_WORD_BITS;
688	  woffset = eindex * EBITSET_ELT_WORDS;
689
690	  for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
691	    {
692	      word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
693
694	      for (; word; bitno++)
695		{
696		  if (word & 1)
697		    {
698		      list[count++] = bitno;
699		      if (count >= num)
700			{
701			  *next = bitno + 1;
702			  return count;
703			}
704		    }
705		  word >>= 1;
706		}
707	      bitno = (windex + 1) * BITSET_WORD_BITS;
708	    }
709	}
710
711      /* Skip to next element.  */
712      eindex++;
713    }
714
715  /* If num is 1, we could speed things up with a binary search
716     of the word of interest.  */
717
718  for (; eindex < size; eindex++)
719    {
720      int i;
721      bitset_word *srcp;
722
723      elt = elts[eindex];
724      if (!elt)
725	continue;
726
727      srcp = EBITSET_WORDS (elt);
728      windex = eindex * EBITSET_ELT_WORDS;
729
730      if ((count + EBITSET_ELT_BITS) < num)
731	{
732	  /* The coast is clear, plant boot!  */
733
734#if EBITSET_ELT_WORDS == 2
735	  word = srcp[0];
736	  if (word)
737	    {
738	      if (!(word & 0xffff))
739		{
740		  word >>= 16;
741		  bitno += 16;
742		}
743	      if (!(word & 0xff))
744		{
745		  word >>= 8;
746		  bitno += 8;
747		}
748	      for (; word; bitno++)
749		{
750		  if (word & 1)
751		    list[count++] = bitno;
752		  word >>= 1;
753		}
754	    }
755	  windex++;
756	  bitno = windex * BITSET_WORD_BITS;
757
758	  word = srcp[1];
759	  if (word)
760	    {
761	      if (!(word & 0xffff))
762		{
763		  word >>= 16;
764		  bitno += 16;
765		}
766	      for (; word; bitno++)
767		{
768		  if (word & 1)
769		    list[count++] = bitno;
770		  word >>= 1;
771		}
772	    }
773	  windex++;
774	  bitno = windex * BITSET_WORD_BITS;
775#else
776	  for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
777	    {
778	      bitno = windex * BITSET_WORD_BITS;
779
780	      word = srcp[i];
781	      if (word)
782		{
783		  if (!(word & 0xffff))
784		    {
785		      word >>= 16;
786		      bitno += 16;
787		    }
788		  if (!(word & 0xff))
789		    {
790		      word >>= 8;
791		      bitno += 8;
792		    }
793		  for (; word; bitno++)
794		    {
795		      if (word & 1)
796			list[count++] = bitno;
797		      word >>= 1;
798		    }
799		}
800	    }
801#endif
802	}
803      else
804	{
805	  /* Tread more carefully since we need to check
806	     if array overflows.  */
807
808	  for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
809	    {
810	      bitno = windex * BITSET_WORD_BITS;
811
812	      for (word = srcp[i]; word; bitno++)
813		{
814		  if (word & 1)
815		    {
816		      list[count++] = bitno;
817		      if (count >= num)
818			{
819			  *next = bitno + 1;
820			  return count;
821			}
822		    }
823		  word >>= 1;
824		}
825	    }
826	}
827    }
828
829  *next = bitno;
830  return count;
831}
832
833
834/* Ensure that any unused bits within the last element are clear.  */
835static inline void
836ebitset_unused_clear (bitset dst)
837{
838  unsigned int last_bit;
839  bitset_bindex n_bits;
840
841  n_bits = BITSET_NBITS_ (dst);
842  last_bit = n_bits % EBITSET_ELT_BITS;
843
844  if (last_bit)
845    {
846      bitset_windex eindex;
847      ebitset_elts *elts;
848      ebitset_elt *elt;
849
850      elts = EBITSET_ELTS (dst);
851
852      eindex = n_bits / EBITSET_ELT_BITS;
853
854      elt = elts[eindex];
855      if (elt)
856	{
857	  bitset_windex windex;
858	  bitset_windex woffset;
859	  bitset_word *srcp = EBITSET_WORDS (elt);
860
861	  windex = n_bits / BITSET_WORD_BITS;
862	  woffset = eindex * EBITSET_ELT_WORDS;
863
864	  srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1;
865	  windex++;
866	  for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
867	    srcp[windex - woffset] = 0;
868	}
869    }
870}
871
872
873static void
874ebitset_ones (bitset dst)
875{
876  bitset_windex j;
877  ebitset_elt *elt;
878
879  for (j = 0; j < EBITSET_SIZE (dst); j++)
880    {
881      /* Create new elements if they cannot be found.  Perhaps
882	 we should just add pointers to a ones element?  */
883      elt =
884	ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
885      memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
886    }
887  EBITSET_NONZERO_SET (dst);
888  ebitset_unused_clear (dst);
889}
890
891
892static bool
893ebitset_empty_p (bitset dst)
894{
895  ebitset_elts *elts;
896  bitset_windex j;
897
898  if (EBITSET_ZERO_P (dst))
899    return 1;
900
901  elts = EBITSET_ELTS (dst);
902  for (j = 0; j < EBITSET_SIZE (dst); j++)
903    {
904      ebitset_elt *elt = elts[j];
905
906      if (elt)
907	{
908	  if (!ebitset_elt_zero_p (elt))
909	    return 0;
910	  /* Do some weeding as we go.  */
911	  ebitset_elt_remove (dst, j);
912	}
913    }
914
915  /* All the bits are zero.  We could shrink the elts.
916     For now just mark DST as known to be zero.  */
917  EBITSET_ZERO_SET (dst);
918  return 1;
919}
920
921
922static void
923ebitset_not (bitset dst, bitset src)
924{
925  unsigned int i;
926  ebitset_elt *selt;
927  ebitset_elt *delt;
928  bitset_windex j;
929
930  ebitset_resize (dst, BITSET_NBITS_ (src));
931
932  for (j = 0; j < EBITSET_SIZE (src); j++)
933    {
934      /* Create new elements for dst if they cannot be found
935	 or substitute zero elements if src elements not found.  */
936      selt =
937	ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST);
938      delt =
939	ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
940
941      for (i = 0; i < EBITSET_ELT_WORDS; i++)
942	EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
943    }
944  EBITSET_NONZERO_SET (dst);
945  ebitset_unused_clear (dst);
946}
947
948
949/* Is DST == DST | SRC?  */
950static bool
951ebitset_subset_p (bitset dst, bitset src)
952{
953  bitset_windex j;
954  ebitset_elts *selts;
955  ebitset_elts *delts;
956  bitset_windex ssize;
957  bitset_windex dsize;
958
959  selts = EBITSET_ELTS (src);
960  delts = EBITSET_ELTS (dst);
961
962  ssize = EBITSET_SIZE (src);
963  dsize = EBITSET_SIZE (dst);
964
965  for (j = 0; j < ssize; j++)
966    {
967      unsigned int i;
968      ebitset_elt *selt;
969      ebitset_elt *delt;
970
971      selt = j < ssize ? selts[j] : 0;
972      delt = j < dsize ? delts[j] : 0;
973
974      if (!selt && !delt)
975	continue;
976
977      if (!selt)
978	selt = &ebitset_zero_elts[0];
979      if (!delt)
980	delt = &ebitset_zero_elts[0];
981
982      for (i = 0; i < EBITSET_ELT_WORDS; i++)
983	if (EBITSET_WORDS (delt)[i]
984	    != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
985	  return false;
986    }
987  return true;
988}
989
990
991/* Is DST & SRC == 0?  */
992static bool
993ebitset_disjoint_p (bitset dst, bitset src)
994{
995  bitset_windex j;
996  ebitset_elts *selts;
997  ebitset_elts *delts;
998  bitset_windex ssize;
999  bitset_windex dsize;
1000
1001  selts = EBITSET_ELTS (src);
1002  delts = EBITSET_ELTS (dst);
1003
1004  ssize = EBITSET_SIZE (src);
1005  dsize = EBITSET_SIZE (dst);
1006
1007  for (j = 0; j < ssize; j++)
1008    {
1009      unsigned int i;
1010      ebitset_elt *selt;
1011      ebitset_elt *delt;
1012
1013      selt = j < ssize ? selts[j] : 0;
1014      delt = j < dsize ? delts[j] : 0;
1015
1016      if (!selt || !delt)
1017	continue;
1018
1019      for (i = 0; i < EBITSET_ELT_WORDS; i++)
1020	if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
1021	  return false;
1022    }
1023  return true;
1024}
1025
1026
1027
1028static bool
1029ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
1030{
1031  bitset_windex ssize1;
1032  bitset_windex ssize2;
1033  bitset_windex dsize;
1034  bitset_windex size;
1035  ebitset_elts *selts1;
1036  ebitset_elts *selts2;
1037  ebitset_elts *delts;
1038  bitset_word *srcp1;
1039  bitset_word *srcp2;
1040  bitset_word *dstp;
1041  bool changed = false;
1042  unsigned int i;
1043  bitset_windex j;
1044
1045  ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
1046
1047  ssize1 = EBITSET_SIZE (src1);
1048  ssize2 = EBITSET_SIZE (src2);
1049  dsize = EBITSET_SIZE (dst);
1050  size = ssize1;
1051  if (size < ssize2)
1052    size = ssize2;
1053
1054  selts1 = EBITSET_ELTS (src1);
1055  selts2 = EBITSET_ELTS (src2);
1056  delts = EBITSET_ELTS (dst);
1057
1058  for (j = 0; j < size; j++)
1059    {
1060      ebitset_elt *selt1;
1061      ebitset_elt *selt2;
1062      ebitset_elt *delt;
1063
1064      selt1 = j < ssize1 ? selts1[j] : 0;
1065      selt2 = j < ssize2 ? selts2[j] : 0;
1066      delt = j < dsize ? delts[j] : 0;
1067
1068      if (!selt1 && !selt2)
1069	{
1070	  if (delt)
1071	    {
1072	      changed = true;
1073	      ebitset_elt_remove (dst, j);
1074	    }
1075	  continue;
1076	}
1077
1078      if (!selt1)
1079	selt1 = &ebitset_zero_elts[0];
1080      if (!selt2)
1081	selt2 = &ebitset_zero_elts[0];
1082      if (!delt)
1083	delt = ebitset_elt_calloc ();
1084      else
1085	delts[j] = 0;
1086
1087      srcp1 = EBITSET_WORDS (selt1);
1088      srcp2 = EBITSET_WORDS (selt2);
1089      dstp = EBITSET_WORDS (delt);
1090      switch (op)
1091	{
1092	default:
1093	  abort ();
1094
1095	case BITSET_OP_OR:
1096	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1097	    {
1098	      bitset_word tmp = *srcp1++ | *srcp2++;
1099
1100	      if (*dstp != tmp)
1101		{
1102		  changed = true;
1103		  *dstp = tmp;
1104		}
1105	    }
1106	  break;
1107
1108	case BITSET_OP_AND:
1109	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1110	    {
1111	      bitset_word tmp = *srcp1++ & *srcp2++;
1112
1113	      if (*dstp != tmp)
1114		{
1115		  changed = true;
1116		  *dstp = tmp;
1117		}
1118	    }
1119	  break;
1120
1121	case BITSET_OP_XOR:
1122	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1123	    {
1124	      bitset_word tmp = *srcp1++ ^ *srcp2++;
1125
1126	      if (*dstp != tmp)
1127		{
1128		  changed = true;
1129		  *dstp = tmp;
1130		}
1131	    }
1132	  break;
1133
1134	case BITSET_OP_ANDN:
1135	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1136	    {
1137	      bitset_word tmp = *srcp1++ & ~(*srcp2++);
1138
1139	      if (*dstp != tmp)
1140		{
1141		  changed = true;
1142		  *dstp = tmp;
1143		}
1144	    }
1145	  break;
1146	}
1147
1148      if (!ebitset_elt_zero_p (delt))
1149	{
1150	  ebitset_elt_add (dst, delt, j);
1151	}
1152      else
1153	{
1154	  ebitset_elt_free (delt);
1155	}
1156    }
1157
1158  /* If we have elements of DST left over, free them all.  */
1159  for (; j < dsize; j++)
1160    {
1161      ebitset_elt *delt;
1162
1163      changed = true;
1164
1165      delt = delts[j];
1166
1167      if (delt)
1168	ebitset_elt_remove (dst, j);
1169    }
1170
1171  EBITSET_NONZERO_SET (dst);
1172  return changed;
1173}
1174
1175
1176static bool
1177ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
1178{
1179  bool changed;
1180
1181  if (EBITSET_ZERO_P (src2))
1182    {
1183      ebitset_weed (dst);
1184      changed = EBITSET_ZERO_P (dst);
1185      ebitset_zero (dst);
1186      return changed;
1187    }
1188  else if (EBITSET_ZERO_P (src1))
1189    {
1190      ebitset_weed (dst);
1191      changed = EBITSET_ZERO_P (dst);
1192      ebitset_zero (dst);
1193      return changed;
1194    }
1195  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1196}
1197
1198
1199static void
1200ebitset_and (bitset dst, bitset src1, bitset src2)
1201{
1202  ebitset_and_cmp (dst, src1, src2);
1203}
1204
1205
1206static bool
1207ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
1208{
1209  bool changed;
1210
1211  if (EBITSET_ZERO_P (src2))
1212    {
1213      return ebitset_copy_cmp (dst, src1);
1214    }
1215  else if (EBITSET_ZERO_P (src1))
1216    {
1217      ebitset_weed (dst);
1218      changed = EBITSET_ZERO_P (dst);
1219      ebitset_zero (dst);
1220      return changed;
1221    }
1222  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1223}
1224
1225
1226static void
1227ebitset_andn (bitset dst, bitset src1, bitset src2)
1228{
1229  ebitset_andn_cmp (dst, src1, src2);
1230}
1231
1232
1233static bool
1234ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
1235{
1236  if (EBITSET_ZERO_P (src2))
1237    {
1238      return ebitset_copy_cmp (dst, src1);
1239    }
1240  else if (EBITSET_ZERO_P (src1))
1241    {
1242      return ebitset_copy_cmp (dst, src2);
1243    }
1244  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1245}
1246
1247
1248static void
1249ebitset_or (bitset dst, bitset src1, bitset src2)
1250{
1251  ebitset_or_cmp (dst, src1, src2);
1252}
1253
1254
1255static bool
1256ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1257{
1258  if (EBITSET_ZERO_P (src2))
1259    {
1260      return ebitset_copy_cmp (dst, src1);
1261    }
1262  else if (EBITSET_ZERO_P (src1))
1263    {
1264      return ebitset_copy_cmp (dst, src2);
1265    }
1266  return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1267}
1268
1269
1270static void
1271ebitset_xor (bitset dst, bitset src1, bitset src2)
1272{
1273  ebitset_xor_cmp (dst, src1, src2);
1274}
1275
1276
1277static void
1278ebitset_copy (bitset dst, bitset src)
1279{
1280  if (BITSET_COMPATIBLE_ (dst, src))
1281      ebitset_copy_ (dst, src);
1282  else
1283      bitset_copy_ (dst, src);
1284}
1285
1286
1287/* Vector of operations for linked-list bitsets.  */
1288struct bitset_vtable ebitset_vtable = {
1289  ebitset_set,
1290  ebitset_reset,
1291  bitset_toggle_,
1292  ebitset_test,
1293  ebitset_resize,
1294  bitset_size_,
1295  bitset_count_,
1296  ebitset_empty_p,
1297  ebitset_ones,
1298  ebitset_zero,
1299  ebitset_copy,
1300  ebitset_disjoint_p,
1301  ebitset_equal_p,
1302  ebitset_not,
1303  ebitset_subset_p,
1304  ebitset_and,
1305  ebitset_and_cmp,
1306  ebitset_andn,
1307  ebitset_andn_cmp,
1308  ebitset_or,
1309  ebitset_or_cmp,
1310  ebitset_xor,
1311  ebitset_xor_cmp,
1312  bitset_and_or_,
1313  bitset_and_or_cmp_,
1314  bitset_andn_or_,
1315  bitset_andn_or_cmp_,
1316  bitset_or_and_,
1317  bitset_or_and_cmp_,
1318  ebitset_list,
1319  ebitset_list_reverse,
1320  ebitset_free,
1321  BITSET_TABLE
1322};
1323
1324
1325/* Return size of initial structure.  */
1326size_t
1327ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
1328{
1329  return sizeof (struct ebitset_struct);
1330}
1331
1332
1333/* Initialize a bitset.  */
1334
1335bitset
1336ebitset_init (bitset bset, bitset_bindex n_bits)
1337{
1338  bset->b.vtable = &ebitset_vtable;
1339
1340  bset->b.csize = EBITSET_ELT_WORDS;
1341
1342  EBITSET_ZERO_SET (bset);
1343
1344  EBITSET_ASIZE (bset) = 0;
1345  EBITSET_ELTS (bset) = 0;
1346  ebitset_resize (bset, n_bits);
1347
1348  return bset;
1349}
1350
1351
1352void
1353ebitset_release_memory (void)
1354{
1355  ebitset_free_list = 0;
1356  if (ebitset_obstack_init)
1357    {
1358      ebitset_obstack_init = false;
1359      obstack_free (&ebitset_obstack, NULL);
1360    }
1361}
1362