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