1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "rtl.h"
27 #include "flags.h"
28 #include "obstack.h"
29 #include "ggc.h"
30 #include "bitmap.h"
31
32 /* Global data */
33 bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
34 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
35 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
36 GC'd elements. */
37
38 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
39 static void bitmap_element_free (bitmap, bitmap_element *);
40 static bitmap_element *bitmap_element_allocate (bitmap);
41 static int bitmap_element_zerop (bitmap_element *);
42 static void bitmap_element_link (bitmap, bitmap_element *);
43 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
44 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
45 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
46
47
48 /* Add ELEM to the appropriate freelist. */
49 static inline void
bitmap_elem_to_freelist(bitmap head,bitmap_element * elt)50 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
51 {
52 bitmap_obstack *bit_obstack = head->obstack;
53
54 elt->next = NULL;
55 if (bit_obstack)
56 {
57 elt->prev = bit_obstack->elements;
58 bit_obstack->elements = elt;
59 }
60 else
61 {
62 elt->prev = bitmap_ggc_free;
63 bitmap_ggc_free = elt;
64 }
65 }
66
67 /* Free a bitmap element. Since these are allocated off the
68 bitmap_obstack, "free" actually means "put onto the freelist". */
69
70 static inline void
bitmap_element_free(bitmap head,bitmap_element * elt)71 bitmap_element_free (bitmap head, bitmap_element *elt)
72 {
73 bitmap_element *next = elt->next;
74 bitmap_element *prev = elt->prev;
75
76 if (prev)
77 prev->next = next;
78
79 if (next)
80 next->prev = prev;
81
82 if (head->first == elt)
83 head->first = next;
84
85 /* Since the first thing we try is to insert before current,
86 make current the next entry in preference to the previous. */
87 if (head->current == elt)
88 {
89 head->current = next != 0 ? next : prev;
90 if (head->current)
91 head->indx = head->current->indx;
92 else
93 head->indx = 0;
94 }
95 bitmap_elem_to_freelist (head, elt);
96 }
97
98 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
99
100 static inline bitmap_element *
bitmap_element_allocate(bitmap head)101 bitmap_element_allocate (bitmap head)
102 {
103 bitmap_element *element;
104 bitmap_obstack *bit_obstack = head->obstack;
105
106 if (bit_obstack)
107 {
108 element = bit_obstack->elements;
109
110 if (element)
111 /* Use up the inner list first before looking at the next
112 element of the outer list. */
113 if (element->next)
114 {
115 bit_obstack->elements = element->next;
116 bit_obstack->elements->prev = element->prev;
117 }
118 else
119 /* Inner list was just a singleton. */
120 bit_obstack->elements = element->prev;
121 else
122 element = XOBNEW (&bit_obstack->obstack, bitmap_element);
123 }
124 else
125 {
126 element = bitmap_ggc_free;
127 if (element)
128 /* Use up the inner list first before looking at the next
129 element of the outer list. */
130 if (element->next)
131 {
132 bitmap_ggc_free = element->next;
133 bitmap_ggc_free->prev = element->prev;
134 }
135 else
136 /* Inner list was just a singleton. */
137 bitmap_ggc_free = element->prev;
138 else
139 element = GGC_NEW (bitmap_element);
140 }
141
142 memset (element->bits, 0, sizeof (element->bits));
143
144 return element;
145 }
146
147 /* Remove ELT and all following elements from bitmap HEAD. */
148
149 void
bitmap_elt_clear_from(bitmap head,bitmap_element * elt)150 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
151 {
152 bitmap_element *prev;
153 bitmap_obstack *bit_obstack = head->obstack;
154
155 if (!elt) return;
156
157 prev = elt->prev;
158 if (prev)
159 {
160 prev->next = NULL;
161 if (head->current->indx > prev->indx)
162 {
163 head->current = prev;
164 head->indx = prev->indx;
165 }
166 }
167 else
168 {
169 head->first = NULL;
170 head->current = NULL;
171 head->indx = 0;
172 }
173
174 /* Put the entire list onto the free list in one operation. */
175 if (bit_obstack)
176 {
177 elt->prev = bit_obstack->elements;
178 bit_obstack->elements = elt;
179 }
180 else
181 {
182 elt->prev = bitmap_ggc_free;
183 bitmap_ggc_free = elt;
184 }
185 }
186
187 /* Clear a bitmap by freeing the linked list. */
188
189 inline void
bitmap_clear(bitmap head)190 bitmap_clear (bitmap head)
191 {
192 if (head->first)
193 bitmap_elt_clear_from (head, head->first);
194 }
195
196 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
197 the default bitmap obstack. */
198
199 void
bitmap_obstack_initialize(bitmap_obstack * bit_obstack)200 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
201 {
202 if (!bit_obstack)
203 bit_obstack = &bitmap_default_obstack;
204
205 #if !defined(__GNUC__) || (__GNUC__ < 2)
206 #define __alignof__(type) 0
207 #endif
208
209 bit_obstack->elements = NULL;
210 bit_obstack->heads = NULL;
211 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
212 __alignof__ (bitmap_element),
213 obstack_chunk_alloc,
214 obstack_chunk_free);
215 }
216
217 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
218 release the default bitmap obstack. */
219
220 void
bitmap_obstack_release(bitmap_obstack * bit_obstack)221 bitmap_obstack_release (bitmap_obstack *bit_obstack)
222 {
223 if (!bit_obstack)
224 bit_obstack = &bitmap_default_obstack;
225
226 bit_obstack->elements = NULL;
227 bit_obstack->heads = NULL;
228 obstack_free (&bit_obstack->obstack, NULL);
229 }
230
231 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
232 it on the default bitmap obstack. */
233
234 bitmap
bitmap_obstack_alloc(bitmap_obstack * bit_obstack)235 bitmap_obstack_alloc (bitmap_obstack *bit_obstack)
236 {
237 bitmap map;
238
239 if (!bit_obstack)
240 bit_obstack = &bitmap_default_obstack;
241 map = bit_obstack->heads;
242 if (map)
243 bit_obstack->heads = (void *)map->first;
244 else
245 map = XOBNEW (&bit_obstack->obstack, bitmap_head);
246 bitmap_initialize (map, bit_obstack);
247
248 return map;
249 }
250
251 /* Create a new GCd bitmap. */
252
253 bitmap
bitmap_gc_alloc(void)254 bitmap_gc_alloc (void)
255 {
256 bitmap map;
257
258 map = GGC_NEW (struct bitmap_head_def);
259 bitmap_initialize (map, NULL);
260
261 return map;
262 }
263
264 /* Release an obstack allocated bitmap. */
265
266 void
bitmap_obstack_free(bitmap map)267 bitmap_obstack_free (bitmap map)
268 {
269 if (map)
270 {
271 bitmap_clear (map);
272 map->first = (void *)map->obstack->heads;
273 map->obstack->heads = map;
274 }
275 }
276
277
278 /* Return nonzero if all bits in an element are zero. */
279
280 static inline int
bitmap_element_zerop(bitmap_element * element)281 bitmap_element_zerop (bitmap_element *element)
282 {
283 #if BITMAP_ELEMENT_WORDS == 2
284 return (element->bits[0] | element->bits[1]) == 0;
285 #else
286 unsigned i;
287
288 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
289 if (element->bits[i] != 0)
290 return 0;
291
292 return 1;
293 #endif
294 }
295
296 /* Link the bitmap element into the current bitmap linked list. */
297
298 static inline void
bitmap_element_link(bitmap head,bitmap_element * element)299 bitmap_element_link (bitmap head, bitmap_element *element)
300 {
301 unsigned int indx = element->indx;
302 bitmap_element *ptr;
303
304 /* If this is the first and only element, set it in. */
305 if (head->first == 0)
306 {
307 element->next = element->prev = 0;
308 head->first = element;
309 }
310
311 /* If this index is less than that of the current element, it goes someplace
312 before the current element. */
313 else if (indx < head->indx)
314 {
315 for (ptr = head->current;
316 ptr->prev != 0 && ptr->prev->indx > indx;
317 ptr = ptr->prev)
318 ;
319
320 if (ptr->prev)
321 ptr->prev->next = element;
322 else
323 head->first = element;
324
325 element->prev = ptr->prev;
326 element->next = ptr;
327 ptr->prev = element;
328 }
329
330 /* Otherwise, it must go someplace after the current element. */
331 else
332 {
333 for (ptr = head->current;
334 ptr->next != 0 && ptr->next->indx < indx;
335 ptr = ptr->next)
336 ;
337
338 if (ptr->next)
339 ptr->next->prev = element;
340
341 element->next = ptr->next;
342 element->prev = ptr;
343 ptr->next = element;
344 }
345
346 /* Set up so this is the first element searched. */
347 head->current = element;
348 head->indx = indx;
349 }
350
351 /* Insert a new uninitialized element into bitmap HEAD after element
352 ELT. If ELT is NULL, insert the element at the start. Return the
353 new element. */
354
355 static bitmap_element *
bitmap_elt_insert_after(bitmap head,bitmap_element * elt,unsigned int indx)356 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
357 {
358 bitmap_element *node = bitmap_element_allocate (head);
359 node->indx = indx;
360
361 if (!elt)
362 {
363 if (!head->current)
364 {
365 head->current = node;
366 head->indx = indx;
367 }
368 node->next = head->first;
369 if (node->next)
370 node->next->prev = node;
371 head->first = node;
372 node->prev = NULL;
373 }
374 else
375 {
376 gcc_assert (head->current);
377 node->next = elt->next;
378 if (node->next)
379 node->next->prev = node;
380 elt->next = node;
381 node->prev = elt;
382 }
383 return node;
384 }
385
386 /* Copy a bitmap to another bitmap. */
387
388 void
bitmap_copy(bitmap to,bitmap from)389 bitmap_copy (bitmap to, bitmap from)
390 {
391 bitmap_element *from_ptr, *to_ptr = 0;
392
393 bitmap_clear (to);
394
395 /* Copy elements in forward direction one at a time. */
396 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
397 {
398 bitmap_element *to_elt = bitmap_element_allocate (to);
399
400 to_elt->indx = from_ptr->indx;
401 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
402
403 /* Here we have a special case of bitmap_element_link, for the case
404 where we know the links are being entered in sequence. */
405 if (to_ptr == 0)
406 {
407 to->first = to->current = to_elt;
408 to->indx = from_ptr->indx;
409 to_elt->next = to_elt->prev = 0;
410 }
411 else
412 {
413 to_elt->prev = to_ptr;
414 to_elt->next = 0;
415 to_ptr->next = to_elt;
416 }
417
418 to_ptr = to_elt;
419 }
420 }
421
422 /* Find a bitmap element that would hold a bitmap's bit.
423 Update the `current' field even if we can't find an element that
424 would hold the bitmap's bit to make eventual allocation
425 faster. */
426
427 static inline bitmap_element *
bitmap_find_bit(bitmap head,unsigned int bit)428 bitmap_find_bit (bitmap head, unsigned int bit)
429 {
430 bitmap_element *element;
431 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
432
433 if (head->current == 0
434 || head->indx == indx)
435 return head->current;
436
437 if (head->indx < indx)
438 /* INDX is beyond head->indx. Search from head->current
439 forward. */
440 for (element = head->current;
441 element->next != 0 && element->indx < indx;
442 element = element->next)
443 ;
444
445 else if (head->indx / 2 < indx)
446 /* INDX is less than head->indx and closer to head->indx than to
447 0. Search from head->current backward. */
448 for (element = head->current;
449 element->prev != 0 && element->indx > indx;
450 element = element->prev)
451 ;
452
453 else
454 /* INDX is less than head->indx and closer to 0 than to
455 head->indx. Search from head->first forward. */
456 for (element = head->first;
457 element->next != 0 && element->indx < indx;
458 element = element->next)
459 ;
460
461 /* `element' is the nearest to the one we want. If it's not the one we
462 want, the one we want doesn't exist. */
463 head->current = element;
464 head->indx = element->indx;
465 if (element != 0 && element->indx != indx)
466 element = 0;
467
468 return element;
469 }
470
471 /* Clear a single bit in a bitmap. */
472
473 void
bitmap_clear_bit(bitmap head,int bit)474 bitmap_clear_bit (bitmap head, int bit)
475 {
476 bitmap_element *ptr = bitmap_find_bit (head, bit);
477
478 if (ptr != 0)
479 {
480 unsigned bit_num = bit % BITMAP_WORD_BITS;
481 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
482 ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
483
484 /* If we cleared the entire word, free up the element. */
485 if (bitmap_element_zerop (ptr))
486 bitmap_element_free (head, ptr);
487 }
488 }
489
490 /* Set a single bit in a bitmap. */
491
492 void
bitmap_set_bit(bitmap head,int bit)493 bitmap_set_bit (bitmap head, int bit)
494 {
495 bitmap_element *ptr = bitmap_find_bit (head, bit);
496 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
497 unsigned bit_num = bit % BITMAP_WORD_BITS;
498 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
499
500 if (ptr == 0)
501 {
502 ptr = bitmap_element_allocate (head);
503 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
504 ptr->bits[word_num] = bit_val;
505 bitmap_element_link (head, ptr);
506 }
507 else
508 ptr->bits[word_num] |= bit_val;
509 }
510
511 /* Return whether a bit is set within a bitmap. */
512
513 int
bitmap_bit_p(bitmap head,int bit)514 bitmap_bit_p (bitmap head, int bit)
515 {
516 bitmap_element *ptr;
517 unsigned bit_num;
518 unsigned word_num;
519
520 ptr = bitmap_find_bit (head, bit);
521 if (ptr == 0)
522 return 0;
523
524 bit_num = bit % BITMAP_WORD_BITS;
525 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
526
527 return (ptr->bits[word_num] >> bit_num) & 1;
528 }
529
530 #if GCC_VERSION < 3400
531 /* Table of number of set bits in a character, indexed by value of char. */
532 static unsigned char popcount_table[] =
533 {
534 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
535 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
536 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
537 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
538 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
539 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
540 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
541 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
542 };
543
544 static unsigned long
bitmap_popcount(BITMAP_WORD a)545 bitmap_popcount (BITMAP_WORD a)
546 {
547 unsigned long ret = 0;
548 unsigned i;
549
550 /* Just do this the table way for now */
551 for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
552 ret += popcount_table[(a >> i) & 0xff];
553 return ret;
554 }
555 #endif
556 /* Count the number of bits set in the bitmap, and return it. */
557
558 unsigned long
bitmap_count_bits(bitmap a)559 bitmap_count_bits (bitmap a)
560 {
561 unsigned long count = 0;
562 bitmap_element *elt;
563 unsigned ix;
564
565 for (elt = a->first; elt; elt = elt->next)
566 {
567 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
568 {
569 #if GCC_VERSION >= 3400
570 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
571 of BITMAP_WORD is not material. */
572 count += __builtin_popcountl (elt->bits[ix]);
573 #else
574 count += bitmap_popcount (elt->bits[ix]);
575 #endif
576 }
577 }
578 return count;
579 }
580
581
582
583 /* Return the bit number of the first set bit in the bitmap. The
584 bitmap must be non-empty. */
585
586 unsigned
bitmap_first_set_bit(bitmap a)587 bitmap_first_set_bit (bitmap a)
588 {
589 bitmap_element *elt = a->first;
590 unsigned bit_no;
591 BITMAP_WORD word;
592 unsigned ix;
593
594 gcc_assert (elt);
595 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
596 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
597 {
598 word = elt->bits[ix];
599 if (word)
600 goto found_bit;
601 }
602 gcc_unreachable ();
603 found_bit:
604 bit_no += ix * BITMAP_WORD_BITS;
605
606 #if GCC_VERSION >= 3004
607 gcc_assert (sizeof(long) == sizeof (word));
608 bit_no += __builtin_ctzl (word);
609 #else
610 /* Binary search for the first set bit. */
611 #if BITMAP_WORD_BITS > 64
612 #error "Fill out the table."
613 #endif
614 #if BITMAP_WORD_BITS > 32
615 if (!(word & 0xffffffff))
616 word >>= 32, bit_no += 32;
617 #endif
618 if (!(word & 0xffff))
619 word >>= 16, bit_no += 16;
620 if (!(word & 0xff))
621 word >>= 8, bit_no += 8;
622 if (!(word & 0xf))
623 word >>= 4, bit_no += 4;
624 if (!(word & 0x3))
625 word >>= 2, bit_no += 2;
626 if (!(word & 0x1))
627 word >>= 1, bit_no += 1;
628
629 gcc_assert (word & 1);
630 #endif
631 return bit_no;
632 }
633
634
635 /* DST = A & B. */
636
637 void
bitmap_and(bitmap dst,bitmap a,bitmap b)638 bitmap_and (bitmap dst, bitmap a, bitmap b)
639 {
640 bitmap_element *dst_elt = dst->first;
641 bitmap_element *a_elt = a->first;
642 bitmap_element *b_elt = b->first;
643 bitmap_element *dst_prev = NULL;
644
645 gcc_assert (dst != a && dst != b);
646
647 if (a == b)
648 {
649 bitmap_copy (dst, a);
650 return;
651 }
652
653 while (a_elt && b_elt)
654 {
655 if (a_elt->indx < b_elt->indx)
656 a_elt = a_elt->next;
657 else if (b_elt->indx < a_elt->indx)
658 b_elt = b_elt->next;
659 else
660 {
661 /* Matching elts, generate A & B. */
662 unsigned ix;
663 BITMAP_WORD ior = 0;
664
665 if (!dst_elt)
666 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
667 else
668 dst_elt->indx = a_elt->indx;
669 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
670 {
671 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
672
673 dst_elt->bits[ix] = r;
674 ior |= r;
675 }
676 if (ior)
677 {
678 dst_prev = dst_elt;
679 dst_elt = dst_elt->next;
680 }
681 a_elt = a_elt->next;
682 b_elt = b_elt->next;
683 }
684 }
685 bitmap_elt_clear_from (dst, dst_elt);
686 gcc_assert (!dst->current == !dst->first);
687 if (dst->current)
688 dst->indx = dst->current->indx;
689 }
690
691 /* A &= B. */
692
693 void
bitmap_and_into(bitmap a,bitmap b)694 bitmap_and_into (bitmap a, bitmap b)
695 {
696 bitmap_element *a_elt = a->first;
697 bitmap_element *b_elt = b->first;
698 bitmap_element *next;
699
700 if (a == b)
701 return;
702
703 while (a_elt && b_elt)
704 {
705 if (a_elt->indx < b_elt->indx)
706 {
707 next = a_elt->next;
708 bitmap_element_free (a, a_elt);
709 a_elt = next;
710 }
711 else if (b_elt->indx < a_elt->indx)
712 b_elt = b_elt->next;
713 else
714 {
715 /* Matching elts, generate A &= B. */
716 unsigned ix;
717 BITMAP_WORD ior = 0;
718
719 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
720 {
721 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
722
723 a_elt->bits[ix] = r;
724 ior |= r;
725 }
726 next = a_elt->next;
727 if (!ior)
728 bitmap_element_free (a, a_elt);
729 a_elt = next;
730 b_elt = b_elt->next;
731 }
732 }
733 bitmap_elt_clear_from (a, a_elt);
734 gcc_assert (!a->current == !a->first);
735 gcc_assert (!a->current || a->indx == a->current->indx);
736 }
737
738 /* DST = A & ~B */
739
740 void
bitmap_and_compl(bitmap dst,bitmap a,bitmap b)741 bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
742 {
743 bitmap_element *dst_elt = dst->first;
744 bitmap_element *a_elt = a->first;
745 bitmap_element *b_elt = b->first;
746 bitmap_element *dst_prev = NULL;
747
748 gcc_assert (dst != a && dst != b);
749
750 if (a == b)
751 {
752 bitmap_clear (dst);
753 return;
754 }
755
756 while (a_elt)
757 {
758 if (!b_elt || a_elt->indx < b_elt->indx)
759 {
760 /* Copy a_elt. */
761 if (!dst_elt)
762 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
763 else
764 dst_elt->indx = a_elt->indx;
765 memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
766 dst_prev = dst_elt;
767 dst_elt = dst_elt->next;
768 a_elt = a_elt->next;
769 }
770 else if (b_elt->indx < a_elt->indx)
771 b_elt = b_elt->next;
772 else
773 {
774 /* Matching elts, generate A & ~B. */
775 unsigned ix;
776 BITMAP_WORD ior = 0;
777
778 if (!dst_elt)
779 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
780 else
781 dst_elt->indx = a_elt->indx;
782 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
783 {
784 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
785
786 dst_elt->bits[ix] = r;
787 ior |= r;
788 }
789 if (ior)
790 {
791 dst_prev = dst_elt;
792 dst_elt = dst_elt->next;
793 }
794 a_elt = a_elt->next;
795 b_elt = b_elt->next;
796 }
797 }
798 bitmap_elt_clear_from (dst, dst_elt);
799 gcc_assert (!dst->current == !dst->first);
800 if (dst->current)
801 dst->indx = dst->current->indx;
802 }
803
804 /* A &= ~B. Returns true if A changes */
805
806 bool
bitmap_and_compl_into(bitmap a,bitmap b)807 bitmap_and_compl_into (bitmap a, bitmap b)
808 {
809 bitmap_element *a_elt = a->first;
810 bitmap_element *b_elt = b->first;
811 bitmap_element *next;
812 BITMAP_WORD changed = 0;
813
814 if (a == b)
815 {
816 if (bitmap_empty_p (a))
817 return false;
818 else
819 {
820 bitmap_clear (a);
821 return true;
822 }
823 }
824
825 while (a_elt && b_elt)
826 {
827 if (a_elt->indx < b_elt->indx)
828 a_elt = a_elt->next;
829 else if (b_elt->indx < a_elt->indx)
830 b_elt = b_elt->next;
831 else
832 {
833 /* Matching elts, generate A &= ~B. */
834 unsigned ix;
835 BITMAP_WORD ior = 0;
836
837 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
838 {
839 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
840 BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
841
842 a_elt->bits[ix] = r;
843 changed |= cleared;
844 ior |= r;
845 }
846 next = a_elt->next;
847 if (!ior)
848 bitmap_element_free (a, a_elt);
849 a_elt = next;
850 b_elt = b_elt->next;
851 }
852 }
853 gcc_assert (!a->current == !a->first);
854 gcc_assert (!a->current || a->indx == a->current->indx);
855 return changed != 0;
856 }
857
858 /* Clear COUNT bits from START in HEAD. */
859 void
bitmap_clear_range(bitmap head,unsigned int start,unsigned int count)860 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
861 {
862 unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS;
863 unsigned int end_bit_plus1 = start + count;
864 unsigned int end_bit = end_bit_plus1 - 1;
865 unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS;
866 bitmap_element *elt = bitmap_find_bit (head, start);
867
868 /* If bitmap_find_bit returns zero, the current is the closest block
869 to the result. If the current is less than first index, find the
870 next one. Otherwise, just set elt to be current. */
871 if (!elt)
872 {
873 if (head->current)
874 {
875 if (head->indx < first_index)
876 {
877 elt = head->current->next;
878 if (!elt)
879 return;
880 }
881 else
882 elt = head->current;
883 }
884 else
885 return;
886 }
887
888 while (elt && (elt->indx <= last_index))
889 {
890 bitmap_element * next_elt = elt->next;
891 unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
892 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
893
894
895 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
896 /* Get rid of the entire elt and go to the next one. */
897 bitmap_element_free (head, elt);
898 else
899 {
900 /* Going to have to knock out some bits in this elt. */
901 unsigned int first_word_to_mod;
902 BITMAP_WORD first_mask;
903 unsigned int last_word_to_mod;
904 BITMAP_WORD last_mask;
905 unsigned int i;
906 bool clear = true;
907
908 if (elt_start_bit <= start)
909 {
910 /* The first bit to turn off is somewhere inside this
911 elt. */
912 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
913
914 /* This mask should have 1s in all bits >= start position. */
915 first_mask =
916 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
917 first_mask = ~first_mask;
918 }
919 else
920 {
921 /* The first bit to turn off is below this start of this elt. */
922 first_word_to_mod = 0;
923 first_mask = 0;
924 first_mask = ~first_mask;
925 }
926
927 if (elt_end_bit_plus1 <= end_bit_plus1)
928 {
929 /* The last bit to turn off is beyond this elt. */
930 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
931 last_mask = 0;
932 last_mask = ~last_mask;
933 }
934 else
935 {
936 /* The last bit to turn off is inside to this elt. */
937 last_word_to_mod =
938 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
939
940 /* The last mask should have 1s below the end bit. */
941 last_mask =
942 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
943 }
944
945
946 if (first_word_to_mod == last_word_to_mod)
947 {
948 BITMAP_WORD mask = first_mask & last_mask;
949 elt->bits[first_word_to_mod] &= ~mask;
950 }
951 else
952 {
953 elt->bits[first_word_to_mod] &= ~first_mask;
954 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
955 elt->bits[i] = 0;
956 elt->bits[last_word_to_mod] &= ~last_mask;
957 }
958 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
959 if (elt->bits[i])
960 {
961 clear = false;
962 break;
963 }
964 /* Check to see if there are any bits left. */
965 if (clear)
966 bitmap_element_free (head, elt);
967 }
968 elt = next_elt;
969 }
970
971 if (elt)
972 {
973 head->current = elt;
974 head->indx = head->current->indx;
975 }
976 }
977
978 /* A = ~A & B. */
979
980 void
bitmap_compl_and_into(bitmap a,bitmap b)981 bitmap_compl_and_into (bitmap a, bitmap b)
982 {
983 bitmap_element *a_elt = a->first;
984 bitmap_element *b_elt = b->first;
985 bitmap_element *a_prev = NULL;
986 bitmap_element *next;
987
988 gcc_assert (a != b);
989
990 if (bitmap_empty_p (a))
991 {
992 bitmap_copy (a, b);
993 return;
994 }
995 if (bitmap_empty_p (b))
996 {
997 bitmap_clear (a);
998 return;
999 }
1000
1001 while (a_elt || b_elt)
1002 {
1003 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1004 {
1005 /* A is before B. Remove A */
1006 next = a_elt->next;
1007 a_prev = a_elt->prev;
1008 bitmap_element_free (a, a_elt);
1009 a_elt = next;
1010 }
1011 else if (!a_elt || b_elt->indx < a_elt->indx)
1012 {
1013 /* B is before A. Copy B. */
1014 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1015 memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1016 a_prev = next;
1017 b_elt = b_elt->next;
1018 }
1019 else
1020 {
1021 /* Matching elts, generate A = ~A & B. */
1022 unsigned ix;
1023 BITMAP_WORD ior = 0;
1024
1025 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1026 {
1027 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1028 BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1029
1030 a_elt->bits[ix] = r;
1031 ior |= r;
1032 }
1033 next = a_elt->next;
1034 if (!ior)
1035 bitmap_element_free (a, a_elt);
1036 else
1037 a_prev = a_elt;
1038 a_elt = next;
1039 b_elt = b_elt->next;
1040 }
1041 }
1042 gcc_assert (!a->current == !a->first);
1043 gcc_assert (!a->current || a->indx == a->current->indx);
1044 return;
1045 }
1046
1047 /* DST = A | B. Return true if DST changes. */
1048
1049 bool
bitmap_ior(bitmap dst,bitmap a,bitmap b)1050 bitmap_ior (bitmap dst, bitmap a, bitmap b)
1051 {
1052 bitmap_element *dst_elt = dst->first;
1053 bitmap_element *a_elt = a->first;
1054 bitmap_element *b_elt = b->first;
1055 bitmap_element *dst_prev = NULL;
1056 bool changed = false;
1057
1058 gcc_assert (dst != a && dst != b);
1059
1060 while (a_elt || b_elt)
1061 {
1062 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1063 {
1064 /* Matching elts, generate A | B. */
1065 unsigned ix;
1066
1067 if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1068 {
1069 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1070 {
1071 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1072
1073 if (r != dst_elt->bits[ix])
1074 {
1075 dst_elt->bits[ix] = r;
1076 changed = true;
1077 }
1078 }
1079 }
1080 else
1081 {
1082 changed = true;
1083 if (!dst_elt)
1084 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1085 else
1086 dst_elt->indx = a_elt->indx;
1087 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1088 {
1089 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1090
1091 dst_elt->bits[ix] = r;
1092 }
1093 }
1094 a_elt = a_elt->next;
1095 b_elt = b_elt->next;
1096 dst_prev = dst_elt;
1097 dst_elt = dst_elt->next;
1098 }
1099 else
1100 {
1101 /* Copy a single element. */
1102 bitmap_element *src;
1103
1104 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1105 {
1106 src = a_elt;
1107 a_elt = a_elt->next;
1108 }
1109 else
1110 {
1111 src = b_elt;
1112 b_elt = b_elt->next;
1113 }
1114
1115 if (!changed && dst_elt && dst_elt->indx == src->indx)
1116 {
1117 unsigned ix;
1118
1119 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1120 if (src->bits[ix] != dst_elt->bits[ix])
1121 {
1122 dst_elt->bits[ix] = src->bits[ix];
1123 changed = true;
1124 }
1125 }
1126 else
1127 {
1128 changed = true;
1129 if (!dst_elt)
1130 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1131 else
1132 dst_elt->indx = src->indx;
1133 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1134 }
1135
1136 dst_prev = dst_elt;
1137 dst_elt = dst_elt->next;
1138 }
1139 }
1140
1141 if (dst_elt)
1142 {
1143 changed = true;
1144 bitmap_elt_clear_from (dst, dst_elt);
1145 }
1146 gcc_assert (!dst->current == !dst->first);
1147 if (dst->current)
1148 dst->indx = dst->current->indx;
1149 return changed;
1150 }
1151
1152 /* A |= B. Return true if A changes. */
1153
1154 bool
bitmap_ior_into(bitmap a,bitmap b)1155 bitmap_ior_into (bitmap a, bitmap b)
1156 {
1157 bitmap_element *a_elt = a->first;
1158 bitmap_element *b_elt = b->first;
1159 bitmap_element *a_prev = NULL;
1160 bool changed = false;
1161
1162 if (a == b)
1163 return false;
1164
1165 while (b_elt)
1166 {
1167 if (!a_elt || b_elt->indx < a_elt->indx)
1168 {
1169 /* Copy b_elt. */
1170 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1171 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1172 a_prev = dst;
1173 b_elt = b_elt->next;
1174 changed = true;
1175 }
1176 else if (a_elt->indx < b_elt->indx)
1177 {
1178 a_prev = a_elt;
1179 a_elt = a_elt->next;
1180 }
1181 else
1182 {
1183 /* Matching elts, generate A |= B. */
1184 unsigned ix;
1185
1186 if (changed)
1187 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1188 {
1189 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1190
1191 a_elt->bits[ix] = r;
1192 }
1193 else
1194 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1195 {
1196 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1197
1198 if (a_elt->bits[ix] != r)
1199 {
1200 changed = true;
1201 a_elt->bits[ix] = r;
1202 }
1203 }
1204 b_elt = b_elt->next;
1205 a_prev = a_elt;
1206 a_elt = a_elt->next;
1207 }
1208 }
1209 gcc_assert (!a->current == !a->first);
1210 if (a->current)
1211 a->indx = a->current->indx;
1212 return changed;
1213 }
1214
1215 /* DST = A ^ B */
1216
1217 void
bitmap_xor(bitmap dst,bitmap a,bitmap b)1218 bitmap_xor (bitmap dst, bitmap a, bitmap b)
1219 {
1220 bitmap_element *dst_elt = dst->first;
1221 bitmap_element *a_elt = a->first;
1222 bitmap_element *b_elt = b->first;
1223 bitmap_element *dst_prev = NULL;
1224
1225 gcc_assert (dst != a && dst != b);
1226 if (a == b)
1227 {
1228 bitmap_clear (dst);
1229 return;
1230 }
1231
1232 while (a_elt || b_elt)
1233 {
1234 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1235 {
1236 /* Matching elts, generate A ^ B. */
1237 unsigned ix;
1238 BITMAP_WORD ior = 0;
1239
1240 if (!dst_elt)
1241 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1242 else
1243 dst_elt->indx = a_elt->indx;
1244 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1245 {
1246 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1247
1248 ior |= r;
1249 dst_elt->bits[ix] = r;
1250 }
1251 a_elt = a_elt->next;
1252 b_elt = b_elt->next;
1253 if (ior)
1254 {
1255 dst_prev = dst_elt;
1256 dst_elt = dst_elt->next;
1257 }
1258 }
1259 else
1260 {
1261 /* Copy a single element. */
1262 bitmap_element *src;
1263
1264 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1265 {
1266 src = a_elt;
1267 a_elt = a_elt->next;
1268 }
1269 else
1270 {
1271 src = b_elt;
1272 b_elt = b_elt->next;
1273 }
1274
1275 if (!dst_elt)
1276 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1277 else
1278 dst_elt->indx = src->indx;
1279 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1280 dst_prev = dst_elt;
1281 dst_elt = dst_elt->next;
1282 }
1283 }
1284 bitmap_elt_clear_from (dst, dst_elt);
1285 gcc_assert (!dst->current == !dst->first);
1286 if (dst->current)
1287 dst->indx = dst->current->indx;
1288 }
1289
1290 /* A ^= B */
1291
1292 void
bitmap_xor_into(bitmap a,bitmap b)1293 bitmap_xor_into (bitmap a, bitmap b)
1294 {
1295 bitmap_element *a_elt = a->first;
1296 bitmap_element *b_elt = b->first;
1297 bitmap_element *a_prev = NULL;
1298
1299 if (a == b)
1300 {
1301 bitmap_clear (a);
1302 return;
1303 }
1304
1305 while (b_elt)
1306 {
1307 if (!a_elt || b_elt->indx < a_elt->indx)
1308 {
1309 /* Copy b_elt. */
1310 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1311 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1312 a_prev = dst;
1313 b_elt = b_elt->next;
1314 }
1315 else if (a_elt->indx < b_elt->indx)
1316 {
1317 a_prev = a_elt;
1318 a_elt = a_elt->next;
1319 }
1320 else
1321 {
1322 /* Matching elts, generate A ^= B. */
1323 unsigned ix;
1324 BITMAP_WORD ior = 0;
1325 bitmap_element *next = a_elt->next;
1326
1327 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1328 {
1329 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1330
1331 ior |= r;
1332 a_elt->bits[ix] = r;
1333 }
1334 b_elt = b_elt->next;
1335 if (ior)
1336 a_prev = a_elt;
1337 else
1338 bitmap_element_free (a, a_elt);
1339 a_elt = next;
1340 }
1341 }
1342 gcc_assert (!a->current == !a->first);
1343 if (a->current)
1344 a->indx = a->current->indx;
1345 }
1346
1347 /* Return true if two bitmaps are identical.
1348 We do not bother with a check for pointer equality, as that never
1349 occurs in practice. */
1350
1351 bool
bitmap_equal_p(bitmap a,bitmap b)1352 bitmap_equal_p (bitmap a, bitmap b)
1353 {
1354 bitmap_element *a_elt;
1355 bitmap_element *b_elt;
1356 unsigned ix;
1357
1358 for (a_elt = a->first, b_elt = b->first;
1359 a_elt && b_elt;
1360 a_elt = a_elt->next, b_elt = b_elt->next)
1361 {
1362 if (a_elt->indx != b_elt->indx)
1363 return false;
1364 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1365 if (a_elt->bits[ix] != b_elt->bits[ix])
1366 return false;
1367 }
1368 return !a_elt && !b_elt;
1369 }
1370
1371 /* Return true if A AND B is not empty. */
1372
1373 bool
bitmap_intersect_p(bitmap a,bitmap b)1374 bitmap_intersect_p (bitmap a, bitmap b)
1375 {
1376 bitmap_element *a_elt;
1377 bitmap_element *b_elt;
1378 unsigned ix;
1379
1380 for (a_elt = a->first, b_elt = b->first;
1381 a_elt && b_elt;)
1382 {
1383 if (a_elt->indx < b_elt->indx)
1384 a_elt = a_elt->next;
1385 else if (b_elt->indx < a_elt->indx)
1386 b_elt = b_elt->next;
1387 else
1388 {
1389 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1390 if (a_elt->bits[ix] & b_elt->bits[ix])
1391 return true;
1392 a_elt = a_elt->next;
1393 b_elt = b_elt->next;
1394 }
1395 }
1396 return false;
1397 }
1398
1399 /* Return true if A AND NOT B is not empty. */
1400
1401 bool
bitmap_intersect_compl_p(bitmap a,bitmap b)1402 bitmap_intersect_compl_p (bitmap a, bitmap b)
1403 {
1404 bitmap_element *a_elt;
1405 bitmap_element *b_elt;
1406 unsigned ix;
1407 for (a_elt = a->first, b_elt = b->first;
1408 a_elt && b_elt;)
1409 {
1410 if (a_elt->indx < b_elt->indx)
1411 return true;
1412 else if (b_elt->indx < a_elt->indx)
1413 b_elt = b_elt->next;
1414 else
1415 {
1416 for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1417 if (a_elt->bits[ix] & ~b_elt->bits[ix])
1418 return true;
1419 a_elt = a_elt->next;
1420 b_elt = b_elt->next;
1421 }
1422 }
1423 return a_elt != NULL;
1424 }
1425
1426
1427 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1428
1429 bool
bitmap_ior_and_compl(bitmap dst,bitmap a,bitmap from1,bitmap from2)1430 bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1431 {
1432 bitmap_head tmp;
1433 bool changed;
1434
1435 bitmap_initialize (&tmp, &bitmap_default_obstack);
1436 bitmap_and_compl (&tmp, from1, from2);
1437 changed = bitmap_ior (dst, a, &tmp);
1438 bitmap_clear (&tmp);
1439
1440 return changed;
1441 }
1442
1443 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1444
1445 bool
bitmap_ior_and_compl_into(bitmap a,bitmap from1,bitmap from2)1446 bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
1447 {
1448 bitmap_head tmp;
1449 bool changed;
1450
1451 bitmap_initialize (&tmp, &bitmap_default_obstack);
1452 bitmap_and_compl (&tmp, from1, from2);
1453 changed = bitmap_ior_into (a, &tmp);
1454 bitmap_clear (&tmp);
1455
1456 return changed;
1457 }
1458
1459 /* Debugging function to print out the contents of a bitmap. */
1460
1461 void
debug_bitmap_file(FILE * file,bitmap head)1462 debug_bitmap_file (FILE *file, bitmap head)
1463 {
1464 bitmap_element *ptr;
1465
1466 fprintf (file, "\nfirst = %p current = %p indx = %u\n",
1467 (void *) head->first, (void *) head->current, head->indx);
1468
1469 for (ptr = head->first; ptr; ptr = ptr->next)
1470 {
1471 unsigned int i, j, col = 26;
1472
1473 fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
1474 (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1475
1476 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1477 for (j = 0; j < BITMAP_WORD_BITS; j++)
1478 if ((ptr->bits[i] >> j) & 1)
1479 {
1480 if (col > 70)
1481 {
1482 fprintf (file, "\n\t\t\t");
1483 col = 24;
1484 }
1485
1486 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1487 + i * BITMAP_WORD_BITS + j));
1488 col += 4;
1489 }
1490
1491 fprintf (file, " }\n");
1492 }
1493 }
1494
1495 /* Function to be called from the debugger to print the contents
1496 of a bitmap. */
1497
1498 void
debug_bitmap(bitmap head)1499 debug_bitmap (bitmap head)
1500 {
1501 debug_bitmap_file (stdout, head);
1502 }
1503
1504 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
1505 it does not print anything but the bits. */
1506
1507 void
bitmap_print(FILE * file,bitmap head,const char * prefix,const char * suffix)1508 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1509 {
1510 const char *comma = "";
1511 unsigned i;
1512 bitmap_iterator bi;
1513
1514 fputs (prefix, file);
1515 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1516 {
1517 fprintf (file, "%s%d", comma, i);
1518 comma = ", ";
1519 }
1520 fputs (suffix, file);
1521 }
1522
1523 /* Compute hash of bitmap (for purposes of hashing). */
1524 hashval_t
bitmap_hash(bitmap head)1525 bitmap_hash (bitmap head)
1526 {
1527 bitmap_element *ptr;
1528 BITMAP_WORD hash = 0;
1529 int ix;
1530
1531 for (ptr = head->first; ptr; ptr = ptr->next)
1532 {
1533 hash ^= ptr->indx;
1534 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1535 hash ^= ptr->bits[ix];
1536 }
1537 return (hashval_t)hash;
1538 }
1539
1540 #include "gt-bitmap.h"
1541