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