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