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