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