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