• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.  */
57 typedef 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 }
66 ebitset_elt;
67 
68 
69 typedef 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 
79 enum ebitset_find_mode
80   { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
81 
82 static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits.  */
83 
84 /* Obstack to allocate bitset elements from.  */
85 static struct obstack ebitset_obstack;
86 static bool ebitset_obstack_init = false;
87 static 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 
122 static bitset_bindex
ebitset_resize(bitset src,bitset_bindex n_bits)123 ebitset_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.  */
180 static inline ebitset_elt *
ebitset_elt_alloc(void)181 ebitset_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.  */
233 static inline ebitset_elt *
ebitset_elt_calloc(void)234 ebitset_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 
244 static inline void
ebitset_elt_free(ebitset_elt * elt)245 ebitset_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.  */
253 static inline void
ebitset_elt_remove(bitset bset,bitset_windex eindex)254 ebitset_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.  */
269 static inline void
ebitset_elt_add(bitset bset,ebitset_elt * elt,bitset_windex eindex)270 ebitset_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?  */
281 static inline bool
ebitset_elt_zero_p(ebitset_elt * elt)282 ebitset_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 
294 static ebitset_elt *
ebitset_elt_find(bitset bset,bitset_bindex bindex,enum ebitset_find_mode mode)295 ebitset_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.  */
347 static inline bitset_windex
ebitset_weed(bitset bset)348 ebitset_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.  */
390 static inline void
ebitset_zero(bitset bset)391 ebitset_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 
414 static inline bool
ebitset_equal_p(bitset dst,bitset src)415 ebitset_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.  */
453 static inline void
ebitset_copy_(bitset dst,bitset src)454 ebitset_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.  */
490 static inline bool
ebitset_copy_cmp(bitset dst,bitset src)491 ebitset_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.  */
511 static void
ebitset_set(bitset dst,bitset_bindex bitno)512 ebitset_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.  */
524 static void
ebitset_reset(bitset dst,bitset_bindex bitno)525 ebitset_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.  */
542 static bool
ebitset_test(bitset src,bitset_bindex bitno)543 ebitset_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 
554 static void
ebitset_free(bitset bset)555 ebitset_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.  */
565 static bitset_bindex
ebitset_list_reverse(bitset bset,bitset_bindex * list,bitset_bindex num,bitset_bindex * next)566 ebitset_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.  */
654 static bitset_bindex
ebitset_list(bitset bset,bitset_bindex * list,bitset_bindex num,bitset_bindex * next)655 ebitset_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.  */
835 static inline void
ebitset_unused_clear(bitset dst)836 ebitset_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 
873 static void
ebitset_ones(bitset dst)874 ebitset_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 
892 static bool
ebitset_empty_p(bitset dst)893 ebitset_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 
922 static void
ebitset_not(bitset dst,bitset src)923 ebitset_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?  */
950 static bool
ebitset_subset_p(bitset dst,bitset src)951 ebitset_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?  */
992 static bool
ebitset_disjoint_p(bitset dst,bitset src)993 ebitset_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 
1028 static bool
ebitset_op3_cmp(bitset dst,bitset src1,bitset src2,enum bitset_ops op)1029 ebitset_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 
1176 static bool
ebitset_and_cmp(bitset dst,bitset src1,bitset src2)1177 ebitset_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 
1199 static void
ebitset_and(bitset dst,bitset src1,bitset src2)1200 ebitset_and (bitset dst, bitset src1, bitset src2)
1201 {
1202   ebitset_and_cmp (dst, src1, src2);
1203 }
1204 
1205 
1206 static bool
ebitset_andn_cmp(bitset dst,bitset src1,bitset src2)1207 ebitset_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 
1226 static void
ebitset_andn(bitset dst,bitset src1,bitset src2)1227 ebitset_andn (bitset dst, bitset src1, bitset src2)
1228 {
1229   ebitset_andn_cmp (dst, src1, src2);
1230 }
1231 
1232 
1233 static bool
ebitset_or_cmp(bitset dst,bitset src1,bitset src2)1234 ebitset_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 
1248 static void
ebitset_or(bitset dst,bitset src1,bitset src2)1249 ebitset_or (bitset dst, bitset src1, bitset src2)
1250 {
1251   ebitset_or_cmp (dst, src1, src2);
1252 }
1253 
1254 
1255 static bool
ebitset_xor_cmp(bitset dst,bitset src1,bitset src2)1256 ebitset_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 
1270 static void
ebitset_xor(bitset dst,bitset src1,bitset src2)1271 ebitset_xor (bitset dst, bitset src1, bitset src2)
1272 {
1273   ebitset_xor_cmp (dst, src1, src2);
1274 }
1275 
1276 
1277 static void
ebitset_copy(bitset dst,bitset src)1278 ebitset_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.  */
1288 struct 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.  */
1326 size_t
ebitset_bytes(bitset_bindex n_bits ATTRIBUTE_UNUSED)1327 ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
1328 {
1329   return sizeof (struct ebitset_struct);
1330 }
1331 
1332 
1333 /* Initialize a bitset.  */
1334 
1335 bitset
ebitset_init(bitset bset,bitset_bindex n_bits)1336 ebitset_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 
1352 void
ebitset_release_memory(void)1353 ebitset_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