1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997-2018 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "bitmap.h"
24 #include "selftest.h"
25
26 /* Memory allocation statistics purpose instance. */
27 mem_alloc_description<bitmap_usage> bitmap_mem_desc;
28
29 /* Register new bitmap. */
30 void
bitmap_register(bitmap b MEM_STAT_DECL)31 bitmap_register (bitmap b MEM_STAT_DECL)
32 {
33 bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false
34 FINAL_PASS_MEM_STAT);
35 }
36
37 /* Account the overhead. */
38 static void
register_overhead(bitmap b,size_t amount)39 register_overhead (bitmap b, size_t amount)
40 {
41 if (bitmap_mem_desc.contains_descriptor_for_instance (b))
42 bitmap_mem_desc.register_instance_overhead (amount, b);
43 }
44
45 /* Global data */
46 bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
47 bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */
48 static int bitmap_default_obstack_depth;
49 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
50 GC'd elements. */
51
52 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
53 static void bitmap_element_free (bitmap, bitmap_element *);
54 static bitmap_element *bitmap_element_allocate (bitmap);
55 static int bitmap_element_zerop (const bitmap_element *);
56 static void bitmap_element_link (bitmap, bitmap_element *);
57 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
58 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
59 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
60
61
62 /* Add ELEM to the appropriate freelist. */
63 static inline void
bitmap_elem_to_freelist(bitmap head,bitmap_element * elt)64 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
65 {
66 bitmap_obstack *bit_obstack = head->obstack;
67
68 elt->next = NULL;
69 elt->indx = -1;
70 if (bit_obstack)
71 {
72 elt->prev = bit_obstack->elements;
73 bit_obstack->elements = elt;
74 }
75 else
76 {
77 elt->prev = bitmap_ggc_free;
78 bitmap_ggc_free = elt;
79 }
80 }
81
82 /* Free a bitmap element. Since these are allocated off the
83 bitmap_obstack, "free" actually means "put onto the freelist". */
84
85 static inline void
bitmap_element_free(bitmap head,bitmap_element * elt)86 bitmap_element_free (bitmap head, bitmap_element *elt)
87 {
88 bitmap_element *next = elt->next;
89 bitmap_element *prev = elt->prev;
90
91 if (prev)
92 prev->next = next;
93
94 if (next)
95 next->prev = prev;
96
97 if (head->first == elt)
98 head->first = next;
99
100 /* Since the first thing we try is to insert before current,
101 make current the next entry in preference to the previous. */
102 if (head->current == elt)
103 {
104 head->current = next != 0 ? next : prev;
105 if (head->current)
106 head->indx = head->current->indx;
107 else
108 head->indx = 0;
109 }
110
111 if (GATHER_STATISTICS)
112 register_overhead (head, -((int)sizeof (bitmap_element)));
113
114 bitmap_elem_to_freelist (head, elt);
115 }
116
117 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
118
119 static inline bitmap_element *
bitmap_element_allocate(bitmap head)120 bitmap_element_allocate (bitmap head)
121 {
122 bitmap_element *element;
123 bitmap_obstack *bit_obstack = head->obstack;
124
125 if (bit_obstack)
126 {
127 element = bit_obstack->elements;
128
129 if (element)
130 /* Use up the inner list first before looking at the next
131 element of the outer list. */
132 if (element->next)
133 {
134 bit_obstack->elements = element->next;
135 bit_obstack->elements->prev = element->prev;
136 }
137 else
138 /* Inner list was just a singleton. */
139 bit_obstack->elements = element->prev;
140 else
141 element = XOBNEW (&bit_obstack->obstack, bitmap_element);
142 }
143 else
144 {
145 element = bitmap_ggc_free;
146 if (element)
147 /* Use up the inner list first before looking at the next
148 element of the outer list. */
149 if (element->next)
150 {
151 bitmap_ggc_free = element->next;
152 bitmap_ggc_free->prev = element->prev;
153 }
154 else
155 /* Inner list was just a singleton. */
156 bitmap_ggc_free = element->prev;
157 else
158 element = ggc_alloc<bitmap_element> ();
159 }
160
161 if (GATHER_STATISTICS)
162 register_overhead (head, sizeof (bitmap_element));
163
164 memset (element->bits, 0, sizeof (element->bits));
165
166 return element;
167 }
168
169 /* Remove ELT and all following elements from bitmap HEAD. */
170
171 void
bitmap_elt_clear_from(bitmap head,bitmap_element * elt)172 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
173 {
174 bitmap_element *prev;
175 bitmap_obstack *bit_obstack = head->obstack;
176
177 if (!elt) return;
178
179 if (GATHER_STATISTICS)
180 {
181 int n = 0;
182 for (prev = elt; prev; prev = prev->next)
183 n++;
184 register_overhead (head, -sizeof (bitmap_element) * n);
185 }
186
187 prev = elt->prev;
188 if (prev)
189 {
190 prev->next = NULL;
191 if (head->current->indx > prev->indx)
192 {
193 head->current = prev;
194 head->indx = prev->indx;
195 }
196 }
197 else
198 {
199 head->first = NULL;
200 head->current = NULL;
201 head->indx = 0;
202 }
203
204 /* Put the entire list onto the free list in one operation. */
205 if (bit_obstack)
206 {
207 elt->prev = bit_obstack->elements;
208 bit_obstack->elements = elt;
209 }
210 else
211 {
212 elt->prev = bitmap_ggc_free;
213 bitmap_ggc_free = elt;
214 }
215 }
216
217 /* Clear a bitmap by freeing the linked list. */
218
219 void
bitmap_clear(bitmap head)220 bitmap_clear (bitmap head)
221 {
222 if (head->first)
223 bitmap_elt_clear_from (head, head->first);
224 }
225
226 /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
227 the default bitmap obstack. */
228
229 void
bitmap_obstack_initialize(bitmap_obstack * bit_obstack)230 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
231 {
232 if (!bit_obstack)
233 {
234 if (bitmap_default_obstack_depth++)
235 return;
236 bit_obstack = &bitmap_default_obstack;
237 }
238
239 #if !defined(__GNUC__) || (__GNUC__ < 2)
240 #define __alignof__(type) 0
241 #endif
242
243 bit_obstack->elements = NULL;
244 bit_obstack->heads = NULL;
245 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
246 __alignof__ (bitmap_element),
247 obstack_chunk_alloc,
248 obstack_chunk_free);
249 }
250
251 /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL,
252 release the default bitmap obstack. */
253
254 void
bitmap_obstack_release(bitmap_obstack * bit_obstack)255 bitmap_obstack_release (bitmap_obstack *bit_obstack)
256 {
257 if (!bit_obstack)
258 {
259 if (--bitmap_default_obstack_depth)
260 {
261 gcc_assert (bitmap_default_obstack_depth > 0);
262 return;
263 }
264 bit_obstack = &bitmap_default_obstack;
265 }
266
267 bit_obstack->elements = NULL;
268 bit_obstack->heads = NULL;
269 obstack_free (&bit_obstack->obstack, NULL);
270 }
271
272 /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create
273 it on the default bitmap obstack. */
274
275 bitmap
bitmap_alloc(bitmap_obstack * bit_obstack MEM_STAT_DECL)276 bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL)
277 {
278 bitmap map;
279
280 if (!bit_obstack)
281 bit_obstack = &bitmap_default_obstack;
282 map = bit_obstack->heads;
283 if (map)
284 bit_obstack->heads = (struct bitmap_head *) map->first;
285 else
286 map = XOBNEW (&bit_obstack->obstack, bitmap_head);
287 bitmap_initialize (map, bit_obstack PASS_MEM_STAT);
288
289 if (GATHER_STATISTICS)
290 register_overhead (map, sizeof (bitmap_head));
291
292 return map;
293 }
294
295 /* Create a new GCd bitmap. */
296
297 bitmap
bitmap_gc_alloc(ALONE_MEM_STAT_DECL)298 bitmap_gc_alloc (ALONE_MEM_STAT_DECL)
299 {
300 bitmap map;
301
302 map = ggc_alloc<bitmap_head> ();
303 bitmap_initialize (map, NULL PASS_MEM_STAT);
304
305 if (GATHER_STATISTICS)
306 register_overhead (map, sizeof (bitmap_head));
307
308 return map;
309 }
310
311 /* Release an obstack allocated bitmap. */
312
313 void
bitmap_obstack_free(bitmap map)314 bitmap_obstack_free (bitmap map)
315 {
316 if (map)
317 {
318 bitmap_clear (map);
319 map->first = (bitmap_element *) map->obstack->heads;
320
321 if (GATHER_STATISTICS)
322 register_overhead (map, -((int)sizeof (bitmap_head)));
323
324 map->obstack->heads = map;
325 }
326 }
327
328
329 /* Return nonzero if all bits in an element are zero. */
330
331 static inline int
bitmap_element_zerop(const bitmap_element * element)332 bitmap_element_zerop (const bitmap_element *element)
333 {
334 #if BITMAP_ELEMENT_WORDS == 2
335 return (element->bits[0] | element->bits[1]) == 0;
336 #else
337 unsigned i;
338
339 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
340 if (element->bits[i] != 0)
341 return 0;
342
343 return 1;
344 #endif
345 }
346
347 /* Link the bitmap element into the current bitmap linked list. */
348
349 static inline void
bitmap_element_link(bitmap head,bitmap_element * element)350 bitmap_element_link (bitmap head, bitmap_element *element)
351 {
352 unsigned int indx = element->indx;
353 bitmap_element *ptr;
354
355 /* If this is the first and only element, set it in. */
356 if (head->first == 0)
357 {
358 element->next = element->prev = 0;
359 head->first = element;
360 }
361
362 /* If this index is less than that of the current element, it goes someplace
363 before the current element. */
364 else if (indx < head->indx)
365 {
366 for (ptr = head->current;
367 ptr->prev != 0 && ptr->prev->indx > indx;
368 ptr = ptr->prev)
369 ;
370
371 if (ptr->prev)
372 ptr->prev->next = element;
373 else
374 head->first = element;
375
376 element->prev = ptr->prev;
377 element->next = ptr;
378 ptr->prev = element;
379 }
380
381 /* Otherwise, it must go someplace after the current element. */
382 else
383 {
384 for (ptr = head->current;
385 ptr->next != 0 && ptr->next->indx < indx;
386 ptr = ptr->next)
387 ;
388
389 if (ptr->next)
390 ptr->next->prev = element;
391
392 element->next = ptr->next;
393 element->prev = ptr;
394 ptr->next = element;
395 }
396
397 /* Set up so this is the first element searched. */
398 head->current = element;
399 head->indx = indx;
400 }
401
402 /* Insert a new uninitialized element into bitmap HEAD after element
403 ELT. If ELT is NULL, insert the element at the start. Return the
404 new element. */
405
406 static bitmap_element *
bitmap_elt_insert_after(bitmap head,bitmap_element * elt,unsigned int indx)407 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
408 {
409 bitmap_element *node = bitmap_element_allocate (head);
410 node->indx = indx;
411
412 if (!elt)
413 {
414 if (!head->current)
415 {
416 head->current = node;
417 head->indx = indx;
418 }
419 node->next = head->first;
420 if (node->next)
421 node->next->prev = node;
422 head->first = node;
423 node->prev = NULL;
424 }
425 else
426 {
427 gcc_checking_assert (head->current);
428 node->next = elt->next;
429 if (node->next)
430 node->next->prev = node;
431 elt->next = node;
432 node->prev = elt;
433 }
434 return node;
435 }
436
437 /* Copy a bitmap to another bitmap. */
438
439 void
bitmap_copy(bitmap to,const_bitmap from)440 bitmap_copy (bitmap to, const_bitmap from)
441 {
442 const bitmap_element *from_ptr;
443 bitmap_element *to_ptr = 0;
444
445 bitmap_clear (to);
446
447 /* Copy elements in forward direction one at a time. */
448 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
449 {
450 bitmap_element *to_elt = bitmap_element_allocate (to);
451
452 to_elt->indx = from_ptr->indx;
453 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
454
455 /* Here we have a special case of bitmap_element_link, for the case
456 where we know the links are being entered in sequence. */
457 if (to_ptr == 0)
458 {
459 to->first = to->current = to_elt;
460 to->indx = from_ptr->indx;
461 to_elt->next = to_elt->prev = 0;
462 }
463 else
464 {
465 to_elt->prev = to_ptr;
466 to_elt->next = 0;
467 to_ptr->next = to_elt;
468 }
469
470 to_ptr = to_elt;
471 }
472 }
473
474 /* Move a bitmap to another bitmap. */
475
476 void
bitmap_move(bitmap to,bitmap from)477 bitmap_move (bitmap to, bitmap from)
478 {
479 gcc_assert (to->obstack == from->obstack);
480
481 bitmap_clear (to);
482
483 *to = *from;
484
485 if (GATHER_STATISTICS)
486 {
487 size_t sz = 0;
488 for (bitmap_element *e = to->first; e; e = e->next)
489 sz += sizeof (bitmap_element);
490 register_overhead (to, sz);
491 register_overhead (from, -sz);
492 }
493 }
494
495 /* Find a bitmap element that would hold a bitmap's bit.
496 Update the `current' field even if we can't find an element that
497 would hold the bitmap's bit to make eventual allocation
498 faster. */
499
500 static inline bitmap_element *
bitmap_find_bit(bitmap head,unsigned int bit)501 bitmap_find_bit (bitmap head, unsigned int bit)
502 {
503 bitmap_element *element;
504 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
505
506 if (head->current == NULL
507 || head->indx == indx)
508 return head->current;
509 if (head->current == head->first
510 && head->first->next == NULL)
511 return NULL;
512
513 /* Usage can be NULL due to allocated bitmaps for which we do not
514 call initialize function. */
515 bitmap_usage *usage = NULL;
516 if (GATHER_STATISTICS)
517 usage = bitmap_mem_desc.get_descriptor_for_instance (head);
518
519 /* This bitmap has more than one element, and we're going to look
520 through the elements list. Count that as a search. */
521 if (GATHER_STATISTICS && usage)
522 usage->m_nsearches++;
523
524 if (head->indx < indx)
525 /* INDX is beyond head->indx. Search from head->current
526 forward. */
527 for (element = head->current;
528 element->next != 0 && element->indx < indx;
529 element = element->next)
530 {
531 if (GATHER_STATISTICS && usage)
532 usage->m_search_iter++;
533 }
534
535 else if (head->indx / 2 < indx)
536 /* INDX is less than head->indx and closer to head->indx than to
537 0. Search from head->current backward. */
538 for (element = head->current;
539 element->prev != 0 && element->indx > indx;
540 element = element->prev)
541 {
542 if (GATHER_STATISTICS && usage)
543 usage->m_search_iter++;
544 }
545
546 else
547 /* INDX is less than head->indx and closer to 0 than to
548 head->indx. Search from head->first forward. */
549 for (element = head->first;
550 element->next != 0 && element->indx < indx;
551 element = element->next)
552 if (GATHER_STATISTICS && usage)
553 {
554 usage->m_search_iter++;
555 }
556
557 /* `element' is the nearest to the one we want. If it's not the one we
558 want, the one we want doesn't exist. */
559 head->current = element;
560 head->indx = element->indx;
561 if (element->indx != indx)
562 element = 0;
563
564 return element;
565 }
566
567 /* Clear a single bit in a bitmap. Return true if the bit changed. */
568
569 bool
bitmap_clear_bit(bitmap head,int bit)570 bitmap_clear_bit (bitmap head, int bit)
571 {
572 bitmap_element *const ptr = bitmap_find_bit (head, bit);
573
574 if (ptr != 0)
575 {
576 unsigned bit_num = bit % BITMAP_WORD_BITS;
577 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
578 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
579 bool res = (ptr->bits[word_num] & bit_val) != 0;
580 if (res)
581 {
582 ptr->bits[word_num] &= ~bit_val;
583 /* If we cleared the entire word, free up the element. */
584 if (!ptr->bits[word_num]
585 && bitmap_element_zerop (ptr))
586 bitmap_element_free (head, ptr);
587 }
588
589 return res;
590 }
591
592 return false;
593 }
594
595 /* Set a single bit in a bitmap. Return true if the bit changed. */
596
597 bool
bitmap_set_bit(bitmap head,int bit)598 bitmap_set_bit (bitmap head, int bit)
599 {
600 bitmap_element *ptr = bitmap_find_bit (head, bit);
601 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
602 unsigned bit_num = bit % BITMAP_WORD_BITS;
603 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
604
605 if (ptr == 0)
606 {
607 ptr = bitmap_element_allocate (head);
608 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
609 ptr->bits[word_num] = bit_val;
610 bitmap_element_link (head, ptr);
611 return true;
612 }
613 else
614 {
615 bool res = (ptr->bits[word_num] & bit_val) == 0;
616 if (res)
617 ptr->bits[word_num] |= bit_val;
618 return res;
619 }
620 }
621
622 /* Return whether a bit is set within a bitmap. */
623
624 int
bitmap_bit_p(bitmap head,int bit)625 bitmap_bit_p (bitmap head, int bit)
626 {
627 bitmap_element *ptr;
628 unsigned bit_num;
629 unsigned word_num;
630
631 ptr = bitmap_find_bit (head, bit);
632 if (ptr == 0)
633 return 0;
634
635 bit_num = bit % BITMAP_WORD_BITS;
636 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
637
638 return (ptr->bits[word_num] >> bit_num) & 1;
639 }
640
641 #if GCC_VERSION < 3400
642 /* Table of number of set bits in a character, indexed by value of char. */
643 static const unsigned char popcount_table[] =
644 {
645 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,
646 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,
647 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,
648 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,
649 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,
650 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,
651 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,
652 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,
653 };
654
655 static unsigned long
bitmap_popcount(BITMAP_WORD a)656 bitmap_popcount (BITMAP_WORD a)
657 {
658 unsigned long ret = 0;
659 unsigned i;
660
661 /* Just do this the table way for now */
662 for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
663 ret += popcount_table[(a >> i) & 0xff];
664 return ret;
665 }
666 #endif
667
668 /* Count and return the number of bits set in the bitmap word BITS. */
669 static unsigned long
bitmap_count_bits_in_word(const BITMAP_WORD * bits)670 bitmap_count_bits_in_word (const BITMAP_WORD *bits)
671 {
672 unsigned long count = 0;
673
674 for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
675 {
676 #if GCC_VERSION >= 3400
677 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
678 of BITMAP_WORD is not material. */
679 count += __builtin_popcountl (bits[ix]);
680 #else
681 count += bitmap_popcount (bits[ix]);
682 #endif
683 }
684 return count;
685 }
686
687 /* Count the number of bits set in the bitmap, and return it. */
688
689 unsigned long
bitmap_count_bits(const_bitmap a)690 bitmap_count_bits (const_bitmap a)
691 {
692 unsigned long count = 0;
693 const bitmap_element *elt;
694
695 for (elt = a->first; elt; elt = elt->next)
696 count += bitmap_count_bits_in_word (elt->bits);
697
698 return count;
699 }
700
701 /* Count the number of unique bits set in A and B and return it. */
702
703 unsigned long
bitmap_count_unique_bits(const_bitmap a,const_bitmap b)704 bitmap_count_unique_bits (const_bitmap a, const_bitmap b)
705 {
706 unsigned long count = 0;
707 const bitmap_element *elt_a, *elt_b;
708
709 for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; )
710 {
711 /* If we're at different indices, then count all the bits
712 in the lower element. If we're at the same index, then
713 count the bits in the IOR of the two elements. */
714 if (elt_a->indx < elt_b->indx)
715 {
716 count += bitmap_count_bits_in_word (elt_a->bits);
717 elt_a = elt_a->next;
718 }
719 else if (elt_b->indx < elt_a->indx)
720 {
721 count += bitmap_count_bits_in_word (elt_b->bits);
722 elt_b = elt_b->next;
723 }
724 else
725 {
726 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
727 for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
728 bits[ix] = elt_a->bits[ix] | elt_b->bits[ix];
729 count += bitmap_count_bits_in_word (bits);
730 elt_a = elt_a->next;
731 elt_b = elt_b->next;
732 }
733 }
734 return count;
735 }
736
737 /* Return true if the bitmap has a single bit set. Otherwise return
738 false. */
739
740 bool
bitmap_single_bit_set_p(const_bitmap a)741 bitmap_single_bit_set_p (const_bitmap a)
742 {
743 unsigned long count = 0;
744 const bitmap_element *elt;
745 unsigned ix;
746
747 if (bitmap_empty_p (a))
748 return false;
749
750 elt = a->first;
751 /* As there are no completely empty bitmap elements, a second one
752 means we have more than one bit set. */
753 if (elt->next != NULL)
754 return false;
755
756 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
757 {
758 #if GCC_VERSION >= 3400
759 /* Note that popcountl matches BITMAP_WORD in type, so the actual size
760 of BITMAP_WORD is not material. */
761 count += __builtin_popcountl (elt->bits[ix]);
762 #else
763 count += bitmap_popcount (elt->bits[ix]);
764 #endif
765 if (count > 1)
766 return false;
767 }
768
769 return count == 1;
770 }
771
772
773 /* Return the bit number of the first set bit in the bitmap. The
774 bitmap must be non-empty. */
775
776 unsigned
bitmap_first_set_bit(const_bitmap a)777 bitmap_first_set_bit (const_bitmap a)
778 {
779 const bitmap_element *elt = a->first;
780 unsigned bit_no;
781 BITMAP_WORD word;
782 unsigned ix;
783
784 gcc_checking_assert (elt);
785 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
786 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
787 {
788 word = elt->bits[ix];
789 if (word)
790 goto found_bit;
791 }
792 gcc_unreachable ();
793 found_bit:
794 bit_no += ix * BITMAP_WORD_BITS;
795
796 #if GCC_VERSION >= 3004
797 gcc_assert (sizeof (long) == sizeof (word));
798 bit_no += __builtin_ctzl (word);
799 #else
800 /* Binary search for the first set bit. */
801 #if BITMAP_WORD_BITS > 64
802 #error "Fill out the table."
803 #endif
804 #if BITMAP_WORD_BITS > 32
805 if (!(word & 0xffffffff))
806 word >>= 32, bit_no += 32;
807 #endif
808 if (!(word & 0xffff))
809 word >>= 16, bit_no += 16;
810 if (!(word & 0xff))
811 word >>= 8, bit_no += 8;
812 if (!(word & 0xf))
813 word >>= 4, bit_no += 4;
814 if (!(word & 0x3))
815 word >>= 2, bit_no += 2;
816 if (!(word & 0x1))
817 word >>= 1, bit_no += 1;
818
819 gcc_checking_assert (word & 1);
820 #endif
821 return bit_no;
822 }
823
824 /* Return the bit number of the first set bit in the bitmap. The
825 bitmap must be non-empty. */
826
827 unsigned
bitmap_last_set_bit(const_bitmap a)828 bitmap_last_set_bit (const_bitmap a)
829 {
830 const bitmap_element *elt = a->current ? a->current : a->first;
831 unsigned bit_no;
832 BITMAP_WORD word;
833 int ix;
834
835 gcc_checking_assert (elt);
836 while (elt->next)
837 elt = elt->next;
838 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
839 for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
840 {
841 word = elt->bits[ix];
842 if (word)
843 goto found_bit;
844 }
845 gcc_unreachable ();
846 found_bit:
847 bit_no += ix * BITMAP_WORD_BITS;
848 #if GCC_VERSION >= 3004
849 gcc_assert (sizeof (long) == sizeof (word));
850 bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
851 #else
852 /* Hopefully this is a twos-complement host... */
853 BITMAP_WORD x = word;
854 x |= (x >> 1);
855 x |= (x >> 2);
856 x |= (x >> 4);
857 x |= (x >> 8);
858 x |= (x >> 16);
859 #if BITMAP_WORD_BITS > 32
860 x |= (x >> 32);
861 #endif
862 bit_no += bitmap_popcount (x) - 1;
863 #endif
864
865 return bit_no;
866 }
867
868
869 /* DST = A & B. */
870
871 void
bitmap_and(bitmap dst,const_bitmap a,const_bitmap b)872 bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
873 {
874 bitmap_element *dst_elt = dst->first;
875 const bitmap_element *a_elt = a->first;
876 const bitmap_element *b_elt = b->first;
877 bitmap_element *dst_prev = NULL;
878
879 gcc_assert (dst != a && dst != b);
880
881 if (a == b)
882 {
883 bitmap_copy (dst, a);
884 return;
885 }
886
887 while (a_elt && b_elt)
888 {
889 if (a_elt->indx < b_elt->indx)
890 a_elt = a_elt->next;
891 else if (b_elt->indx < a_elt->indx)
892 b_elt = b_elt->next;
893 else
894 {
895 /* Matching elts, generate A & B. */
896 unsigned ix;
897 BITMAP_WORD ior = 0;
898
899 if (!dst_elt)
900 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
901 else
902 dst_elt->indx = a_elt->indx;
903 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
904 {
905 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
906
907 dst_elt->bits[ix] = r;
908 ior |= r;
909 }
910 if (ior)
911 {
912 dst_prev = dst_elt;
913 dst_elt = dst_elt->next;
914 }
915 a_elt = a_elt->next;
916 b_elt = b_elt->next;
917 }
918 }
919 /* Ensure that dst->current is valid. */
920 dst->current = dst->first;
921 bitmap_elt_clear_from (dst, dst_elt);
922 gcc_checking_assert (!dst->current == !dst->first);
923 if (dst->current)
924 dst->indx = dst->current->indx;
925 }
926
927 /* A &= B. Return true if A changed. */
928
929 bool
bitmap_and_into(bitmap a,const_bitmap b)930 bitmap_and_into (bitmap a, const_bitmap b)
931 {
932 bitmap_element *a_elt = a->first;
933 const bitmap_element *b_elt = b->first;
934 bitmap_element *next;
935 bool changed = false;
936
937 if (a == b)
938 return false;
939
940 while (a_elt && b_elt)
941 {
942 if (a_elt->indx < b_elt->indx)
943 {
944 next = a_elt->next;
945 bitmap_element_free (a, a_elt);
946 a_elt = next;
947 changed = true;
948 }
949 else if (b_elt->indx < a_elt->indx)
950 b_elt = b_elt->next;
951 else
952 {
953 /* Matching elts, generate A &= B. */
954 unsigned ix;
955 BITMAP_WORD ior = 0;
956
957 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
958 {
959 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
960 if (a_elt->bits[ix] != r)
961 changed = true;
962 a_elt->bits[ix] = r;
963 ior |= r;
964 }
965 next = a_elt->next;
966 if (!ior)
967 bitmap_element_free (a, a_elt);
968 a_elt = next;
969 b_elt = b_elt->next;
970 }
971 }
972
973 if (a_elt)
974 {
975 changed = true;
976 bitmap_elt_clear_from (a, a_elt);
977 }
978
979 gcc_checking_assert (!a->current == !a->first
980 && (!a->current || a->indx == a->current->indx));
981
982 return changed;
983 }
984
985
986 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
987 if non-NULL. CHANGED is true if the destination bitmap had already been
988 changed; the new value of CHANGED is returned. */
989
990 static inline bool
bitmap_elt_copy(bitmap dst,bitmap_element * dst_elt,bitmap_element * dst_prev,const bitmap_element * src_elt,bool changed)991 bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
992 const bitmap_element *src_elt, bool changed)
993 {
994 if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
995 {
996 unsigned ix;
997
998 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
999 if (src_elt->bits[ix] != dst_elt->bits[ix])
1000 {
1001 dst_elt->bits[ix] = src_elt->bits[ix];
1002 changed = true;
1003 }
1004 }
1005 else
1006 {
1007 changed = true;
1008 if (!dst_elt)
1009 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
1010 else
1011 dst_elt->indx = src_elt->indx;
1012 memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1013 }
1014 return changed;
1015 }
1016
1017
1018
1019 /* DST = A & ~B */
1020
1021 bool
bitmap_and_compl(bitmap dst,const_bitmap a,const_bitmap b)1022 bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1023 {
1024 bitmap_element *dst_elt = dst->first;
1025 const bitmap_element *a_elt = a->first;
1026 const bitmap_element *b_elt = b->first;
1027 bitmap_element *dst_prev = NULL;
1028 bitmap_element **dst_prev_pnext = &dst->first;
1029 bool changed = false;
1030
1031 gcc_assert (dst != a && dst != b);
1032
1033 if (a == b)
1034 {
1035 changed = !bitmap_empty_p (dst);
1036 bitmap_clear (dst);
1037 return changed;
1038 }
1039
1040 while (a_elt)
1041 {
1042 while (b_elt && b_elt->indx < a_elt->indx)
1043 b_elt = b_elt->next;
1044
1045 if (!b_elt || b_elt->indx > a_elt->indx)
1046 {
1047 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1048 dst_prev = *dst_prev_pnext;
1049 dst_prev_pnext = &dst_prev->next;
1050 dst_elt = *dst_prev_pnext;
1051 a_elt = a_elt->next;
1052 }
1053
1054 else
1055 {
1056 /* Matching elts, generate A & ~B. */
1057 unsigned ix;
1058 BITMAP_WORD ior = 0;
1059
1060 if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1061 {
1062 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1063 {
1064 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1065
1066 if (dst_elt->bits[ix] != r)
1067 {
1068 changed = true;
1069 dst_elt->bits[ix] = r;
1070 }
1071 ior |= r;
1072 }
1073 }
1074 else
1075 {
1076 bool new_element;
1077 if (!dst_elt || dst_elt->indx > a_elt->indx)
1078 {
1079 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1080 new_element = true;
1081 }
1082 else
1083 {
1084 dst_elt->indx = a_elt->indx;
1085 new_element = false;
1086 }
1087
1088 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1089 {
1090 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1091
1092 dst_elt->bits[ix] = r;
1093 ior |= r;
1094 }
1095
1096 if (ior)
1097 changed = true;
1098 else
1099 {
1100 changed |= !new_element;
1101 bitmap_element_free (dst, dst_elt);
1102 dst_elt = *dst_prev_pnext;
1103 }
1104 }
1105
1106 if (ior)
1107 {
1108 dst_prev = *dst_prev_pnext;
1109 dst_prev_pnext = &dst_prev->next;
1110 dst_elt = *dst_prev_pnext;
1111 }
1112 a_elt = a_elt->next;
1113 b_elt = b_elt->next;
1114 }
1115 }
1116
1117 /* Ensure that dst->current is valid. */
1118 dst->current = dst->first;
1119
1120 if (dst_elt)
1121 {
1122 changed = true;
1123 bitmap_elt_clear_from (dst, dst_elt);
1124 }
1125 gcc_checking_assert (!dst->current == !dst->first);
1126 if (dst->current)
1127 dst->indx = dst->current->indx;
1128
1129 return changed;
1130 }
1131
1132 /* A &= ~B. Returns true if A changes */
1133
1134 bool
bitmap_and_compl_into(bitmap a,const_bitmap b)1135 bitmap_and_compl_into (bitmap a, const_bitmap b)
1136 {
1137 bitmap_element *a_elt = a->first;
1138 const bitmap_element *b_elt = b->first;
1139 bitmap_element *next;
1140 BITMAP_WORD changed = 0;
1141
1142 if (a == b)
1143 {
1144 if (bitmap_empty_p (a))
1145 return false;
1146 else
1147 {
1148 bitmap_clear (a);
1149 return true;
1150 }
1151 }
1152
1153 while (a_elt && b_elt)
1154 {
1155 if (a_elt->indx < b_elt->indx)
1156 a_elt = a_elt->next;
1157 else if (b_elt->indx < a_elt->indx)
1158 b_elt = b_elt->next;
1159 else
1160 {
1161 /* Matching elts, generate A &= ~B. */
1162 unsigned ix;
1163 BITMAP_WORD ior = 0;
1164
1165 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1166 {
1167 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1168 BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1169
1170 a_elt->bits[ix] = r;
1171 changed |= cleared;
1172 ior |= r;
1173 }
1174 next = a_elt->next;
1175 if (!ior)
1176 bitmap_element_free (a, a_elt);
1177 a_elt = next;
1178 b_elt = b_elt->next;
1179 }
1180 }
1181 gcc_checking_assert (!a->current == !a->first
1182 && (!a->current || a->indx == a->current->indx));
1183 return changed != 0;
1184 }
1185
1186 /* Set COUNT bits from START in HEAD. */
1187 void
bitmap_set_range(bitmap head,unsigned int start,unsigned int count)1188 bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1189 {
1190 unsigned int first_index, end_bit_plus1, last_index;
1191 bitmap_element *elt, *elt_prev;
1192 unsigned int i;
1193
1194 if (!count)
1195 return;
1196
1197 if (count == 1)
1198 {
1199 bitmap_set_bit (head, start);
1200 return;
1201 }
1202
1203 first_index = start / BITMAP_ELEMENT_ALL_BITS;
1204 end_bit_plus1 = start + count;
1205 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1206 elt = bitmap_find_bit (head, start);
1207
1208 /* If bitmap_find_bit returns zero, the current is the closest block
1209 to the result. Otherwise, just use bitmap_element_allocate to
1210 ensure ELT is set; in the loop below, ELT == NULL means "insert
1211 at the end of the bitmap". */
1212 if (!elt)
1213 {
1214 elt = bitmap_element_allocate (head);
1215 elt->indx = first_index;
1216 bitmap_element_link (head, elt);
1217 }
1218
1219 gcc_checking_assert (elt->indx == first_index);
1220 elt_prev = elt->prev;
1221 for (i = first_index; i <= last_index; i++)
1222 {
1223 unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1224 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1225
1226 unsigned int first_word_to_mod;
1227 BITMAP_WORD first_mask;
1228 unsigned int last_word_to_mod;
1229 BITMAP_WORD last_mask;
1230 unsigned int ix;
1231
1232 if (!elt || elt->indx != i)
1233 elt = bitmap_elt_insert_after (head, elt_prev, i);
1234
1235 if (elt_start_bit <= start)
1236 {
1237 /* The first bit to turn on is somewhere inside this
1238 elt. */
1239 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1240
1241 /* This mask should have 1s in all bits >= start position. */
1242 first_mask =
1243 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1244 first_mask = ~first_mask;
1245 }
1246 else
1247 {
1248 /* The first bit to turn on is below this start of this elt. */
1249 first_word_to_mod = 0;
1250 first_mask = ~(BITMAP_WORD) 0;
1251 }
1252
1253 if (elt_end_bit_plus1 <= end_bit_plus1)
1254 {
1255 /* The last bit to turn on is beyond this elt. */
1256 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1257 last_mask = ~(BITMAP_WORD) 0;
1258 }
1259 else
1260 {
1261 /* The last bit to turn on is inside to this elt. */
1262 last_word_to_mod =
1263 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1264
1265 /* The last mask should have 1s below the end bit. */
1266 last_mask =
1267 (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1268 }
1269
1270 if (first_word_to_mod == last_word_to_mod)
1271 {
1272 BITMAP_WORD mask = first_mask & last_mask;
1273 elt->bits[first_word_to_mod] |= mask;
1274 }
1275 else
1276 {
1277 elt->bits[first_word_to_mod] |= first_mask;
1278 if (BITMAP_ELEMENT_WORDS > 2)
1279 for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1280 elt->bits[ix] = ~(BITMAP_WORD) 0;
1281 elt->bits[last_word_to_mod] |= last_mask;
1282 }
1283
1284 elt_prev = elt;
1285 elt = elt->next;
1286 }
1287
1288 head->current = elt ? elt : elt_prev;
1289 head->indx = head->current->indx;
1290 }
1291
1292 /* Clear COUNT bits from START in HEAD. */
1293 void
bitmap_clear_range(bitmap head,unsigned int start,unsigned int count)1294 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1295 {
1296 unsigned int first_index, end_bit_plus1, last_index;
1297 bitmap_element *elt;
1298
1299 if (!count)
1300 return;
1301
1302 if (count == 1)
1303 {
1304 bitmap_clear_bit (head, start);
1305 return;
1306 }
1307
1308 first_index = start / BITMAP_ELEMENT_ALL_BITS;
1309 end_bit_plus1 = start + count;
1310 last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1311 elt = bitmap_find_bit (head, start);
1312
1313 /* If bitmap_find_bit returns zero, the current is the closest block
1314 to the result. If the current is less than first index, find the
1315 next one. Otherwise, just set elt to be current. */
1316 if (!elt)
1317 {
1318 if (head->current)
1319 {
1320 if (head->indx < first_index)
1321 {
1322 elt = head->current->next;
1323 if (!elt)
1324 return;
1325 }
1326 else
1327 elt = head->current;
1328 }
1329 else
1330 return;
1331 }
1332
1333 while (elt && (elt->indx <= last_index))
1334 {
1335 bitmap_element * next_elt = elt->next;
1336 unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1337 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1338
1339
1340 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1341 /* Get rid of the entire elt and go to the next one. */
1342 bitmap_element_free (head, elt);
1343 else
1344 {
1345 /* Going to have to knock out some bits in this elt. */
1346 unsigned int first_word_to_mod;
1347 BITMAP_WORD first_mask;
1348 unsigned int last_word_to_mod;
1349 BITMAP_WORD last_mask;
1350 unsigned int i;
1351 bool clear = true;
1352
1353 if (elt_start_bit <= start)
1354 {
1355 /* The first bit to turn off is somewhere inside this
1356 elt. */
1357 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1358
1359 /* This mask should have 1s in all bits >= start position. */
1360 first_mask =
1361 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1362 first_mask = ~first_mask;
1363 }
1364 else
1365 {
1366 /* The first bit to turn off is below this start of this elt. */
1367 first_word_to_mod = 0;
1368 first_mask = 0;
1369 first_mask = ~first_mask;
1370 }
1371
1372 if (elt_end_bit_plus1 <= end_bit_plus1)
1373 {
1374 /* The last bit to turn off is beyond this elt. */
1375 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1376 last_mask = 0;
1377 last_mask = ~last_mask;
1378 }
1379 else
1380 {
1381 /* The last bit to turn off is inside to this elt. */
1382 last_word_to_mod =
1383 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1384
1385 /* The last mask should have 1s below the end bit. */
1386 last_mask =
1387 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1388 }
1389
1390
1391 if (first_word_to_mod == last_word_to_mod)
1392 {
1393 BITMAP_WORD mask = first_mask & last_mask;
1394 elt->bits[first_word_to_mod] &= ~mask;
1395 }
1396 else
1397 {
1398 elt->bits[first_word_to_mod] &= ~first_mask;
1399 if (BITMAP_ELEMENT_WORDS > 2)
1400 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1401 elt->bits[i] = 0;
1402 elt->bits[last_word_to_mod] &= ~last_mask;
1403 }
1404 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1405 if (elt->bits[i])
1406 {
1407 clear = false;
1408 break;
1409 }
1410 /* Check to see if there are any bits left. */
1411 if (clear)
1412 bitmap_element_free (head, elt);
1413 }
1414 elt = next_elt;
1415 }
1416
1417 if (elt)
1418 {
1419 head->current = elt;
1420 head->indx = head->current->indx;
1421 }
1422 }
1423
1424 /* A = ~A & B. */
1425
1426 void
bitmap_compl_and_into(bitmap a,const_bitmap b)1427 bitmap_compl_and_into (bitmap a, const_bitmap b)
1428 {
1429 bitmap_element *a_elt = a->first;
1430 const bitmap_element *b_elt = b->first;
1431 bitmap_element *a_prev = NULL;
1432 bitmap_element *next;
1433
1434 gcc_assert (a != b);
1435
1436 if (bitmap_empty_p (a))
1437 {
1438 bitmap_copy (a, b);
1439 return;
1440 }
1441 if (bitmap_empty_p (b))
1442 {
1443 bitmap_clear (a);
1444 return;
1445 }
1446
1447 while (a_elt || b_elt)
1448 {
1449 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1450 {
1451 /* A is before B. Remove A */
1452 next = a_elt->next;
1453 a_prev = a_elt->prev;
1454 bitmap_element_free (a, a_elt);
1455 a_elt = next;
1456 }
1457 else if (!a_elt || b_elt->indx < a_elt->indx)
1458 {
1459 /* B is before A. Copy B. */
1460 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1461 memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1462 a_prev = next;
1463 b_elt = b_elt->next;
1464 }
1465 else
1466 {
1467 /* Matching elts, generate A = ~A & B. */
1468 unsigned ix;
1469 BITMAP_WORD ior = 0;
1470
1471 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1472 {
1473 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1474 BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1475
1476 a_elt->bits[ix] = r;
1477 ior |= r;
1478 }
1479 next = a_elt->next;
1480 if (!ior)
1481 bitmap_element_free (a, a_elt);
1482 else
1483 a_prev = a_elt;
1484 a_elt = next;
1485 b_elt = b_elt->next;
1486 }
1487 }
1488 gcc_checking_assert (!a->current == !a->first
1489 && (!a->current || a->indx == a->current->indx));
1490 return;
1491 }
1492
1493
1494 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1495 overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
1496 had already been changed; the new value of CHANGED is returned. */
1497
1498 static inline bool
bitmap_elt_ior(bitmap dst,bitmap_element * dst_elt,bitmap_element * dst_prev,const bitmap_element * a_elt,const bitmap_element * b_elt,bool changed)1499 bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1500 const bitmap_element *a_elt, const bitmap_element *b_elt,
1501 bool changed)
1502 {
1503 gcc_assert (a_elt || b_elt);
1504
1505 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1506 {
1507 /* Matching elts, generate A | B. */
1508 unsigned ix;
1509
1510 if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1511 {
1512 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1513 {
1514 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1515 if (r != dst_elt->bits[ix])
1516 {
1517 dst_elt->bits[ix] = r;
1518 changed = true;
1519 }
1520 }
1521 }
1522 else
1523 {
1524 changed = true;
1525 if (!dst_elt)
1526 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1527 else
1528 dst_elt->indx = a_elt->indx;
1529 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1530 {
1531 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1532 dst_elt->bits[ix] = r;
1533 }
1534 }
1535 }
1536 else
1537 {
1538 /* Copy a single element. */
1539 const bitmap_element *src;
1540
1541 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1542 src = a_elt;
1543 else
1544 src = b_elt;
1545
1546 gcc_checking_assert (src);
1547 changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
1548 }
1549 return changed;
1550 }
1551
1552
1553 /* DST = A | B. Return true if DST changes. */
1554
1555 bool
bitmap_ior(bitmap dst,const_bitmap a,const_bitmap b)1556 bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
1557 {
1558 bitmap_element *dst_elt = dst->first;
1559 const bitmap_element *a_elt = a->first;
1560 const bitmap_element *b_elt = b->first;
1561 bitmap_element *dst_prev = NULL;
1562 bitmap_element **dst_prev_pnext = &dst->first;
1563 bool changed = false;
1564
1565 gcc_assert (dst != a && dst != b);
1566
1567 while (a_elt || b_elt)
1568 {
1569 changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
1570
1571 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1572 {
1573 a_elt = a_elt->next;
1574 b_elt = b_elt->next;
1575 }
1576 else
1577 {
1578 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1579 a_elt = a_elt->next;
1580 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1581 b_elt = b_elt->next;
1582 }
1583
1584 dst_prev = *dst_prev_pnext;
1585 dst_prev_pnext = &dst_prev->next;
1586 dst_elt = *dst_prev_pnext;
1587 }
1588
1589 if (dst_elt)
1590 {
1591 changed = true;
1592 /* Ensure that dst->current is valid. */
1593 dst->current = dst->first;
1594 bitmap_elt_clear_from (dst, dst_elt);
1595 }
1596 gcc_checking_assert (!dst->current == !dst->first);
1597 if (dst->current)
1598 dst->indx = dst->current->indx;
1599 return changed;
1600 }
1601
1602 /* A |= B. Return true if A changes. */
1603
1604 bool
bitmap_ior_into(bitmap a,const_bitmap b)1605 bitmap_ior_into (bitmap a, const_bitmap b)
1606 {
1607 bitmap_element *a_elt = a->first;
1608 const bitmap_element *b_elt = b->first;
1609 bitmap_element *a_prev = NULL;
1610 bitmap_element **a_prev_pnext = &a->first;
1611 bool changed = false;
1612
1613 if (a == b)
1614 return false;
1615
1616 while (b_elt)
1617 {
1618 /* If A lags behind B, just advance it. */
1619 if (!a_elt || a_elt->indx == b_elt->indx)
1620 {
1621 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
1622 b_elt = b_elt->next;
1623 }
1624 else if (a_elt->indx > b_elt->indx)
1625 {
1626 changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
1627 b_elt = b_elt->next;
1628 }
1629
1630 a_prev = *a_prev_pnext;
1631 a_prev_pnext = &a_prev->next;
1632 a_elt = *a_prev_pnext;
1633 }
1634
1635 gcc_checking_assert (!a->current == !a->first);
1636 if (a->current)
1637 a->indx = a->current->indx;
1638 return changed;
1639 }
1640
1641 /* DST = A ^ B */
1642
1643 void
bitmap_xor(bitmap dst,const_bitmap a,const_bitmap b)1644 bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
1645 {
1646 bitmap_element *dst_elt = dst->first;
1647 const bitmap_element *a_elt = a->first;
1648 const bitmap_element *b_elt = b->first;
1649 bitmap_element *dst_prev = NULL;
1650
1651 gcc_assert (dst != a && dst != b);
1652 if (a == b)
1653 {
1654 bitmap_clear (dst);
1655 return;
1656 }
1657
1658 while (a_elt || b_elt)
1659 {
1660 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1661 {
1662 /* Matching elts, generate A ^ B. */
1663 unsigned ix;
1664 BITMAP_WORD ior = 0;
1665
1666 if (!dst_elt)
1667 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1668 else
1669 dst_elt->indx = a_elt->indx;
1670 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1671 {
1672 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1673
1674 ior |= r;
1675 dst_elt->bits[ix] = r;
1676 }
1677 a_elt = a_elt->next;
1678 b_elt = b_elt->next;
1679 if (ior)
1680 {
1681 dst_prev = dst_elt;
1682 dst_elt = dst_elt->next;
1683 }
1684 }
1685 else
1686 {
1687 /* Copy a single element. */
1688 const bitmap_element *src;
1689
1690 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1691 {
1692 src = a_elt;
1693 a_elt = a_elt->next;
1694 }
1695 else
1696 {
1697 src = b_elt;
1698 b_elt = b_elt->next;
1699 }
1700
1701 if (!dst_elt)
1702 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1703 else
1704 dst_elt->indx = src->indx;
1705 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1706 dst_prev = dst_elt;
1707 dst_elt = dst_elt->next;
1708 }
1709 }
1710 /* Ensure that dst->current is valid. */
1711 dst->current = dst->first;
1712 bitmap_elt_clear_from (dst, dst_elt);
1713 gcc_checking_assert (!dst->current == !dst->first);
1714 if (dst->current)
1715 dst->indx = dst->current->indx;
1716 }
1717
1718 /* A ^= B */
1719
1720 void
bitmap_xor_into(bitmap a,const_bitmap b)1721 bitmap_xor_into (bitmap a, const_bitmap b)
1722 {
1723 bitmap_element *a_elt = a->first;
1724 const bitmap_element *b_elt = b->first;
1725 bitmap_element *a_prev = NULL;
1726
1727 if (a == b)
1728 {
1729 bitmap_clear (a);
1730 return;
1731 }
1732
1733 while (b_elt)
1734 {
1735 if (!a_elt || b_elt->indx < a_elt->indx)
1736 {
1737 /* Copy b_elt. */
1738 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1739 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1740 a_prev = dst;
1741 b_elt = b_elt->next;
1742 }
1743 else if (a_elt->indx < b_elt->indx)
1744 {
1745 a_prev = a_elt;
1746 a_elt = a_elt->next;
1747 }
1748 else
1749 {
1750 /* Matching elts, generate A ^= B. */
1751 unsigned ix;
1752 BITMAP_WORD ior = 0;
1753 bitmap_element *next = a_elt->next;
1754
1755 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1756 {
1757 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1758
1759 ior |= r;
1760 a_elt->bits[ix] = r;
1761 }
1762 b_elt = b_elt->next;
1763 if (ior)
1764 a_prev = a_elt;
1765 else
1766 bitmap_element_free (a, a_elt);
1767 a_elt = next;
1768 }
1769 }
1770 gcc_checking_assert (!a->current == !a->first);
1771 if (a->current)
1772 a->indx = a->current->indx;
1773 }
1774
1775 /* Return true if two bitmaps are identical.
1776 We do not bother with a check for pointer equality, as that never
1777 occurs in practice. */
1778
1779 bool
bitmap_equal_p(const_bitmap a,const_bitmap b)1780 bitmap_equal_p (const_bitmap a, const_bitmap b)
1781 {
1782 const bitmap_element *a_elt;
1783 const bitmap_element *b_elt;
1784 unsigned ix;
1785
1786 for (a_elt = a->first, b_elt = b->first;
1787 a_elt && b_elt;
1788 a_elt = a_elt->next, b_elt = b_elt->next)
1789 {
1790 if (a_elt->indx != b_elt->indx)
1791 return false;
1792 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1793 if (a_elt->bits[ix] != b_elt->bits[ix])
1794 return false;
1795 }
1796 return !a_elt && !b_elt;
1797 }
1798
1799 /* Return true if A AND B is not empty. */
1800
1801 bool
bitmap_intersect_p(const_bitmap a,const_bitmap b)1802 bitmap_intersect_p (const_bitmap a, const_bitmap b)
1803 {
1804 const bitmap_element *a_elt;
1805 const bitmap_element *b_elt;
1806 unsigned ix;
1807
1808 for (a_elt = a->first, b_elt = b->first;
1809 a_elt && b_elt;)
1810 {
1811 if (a_elt->indx < b_elt->indx)
1812 a_elt = a_elt->next;
1813 else if (b_elt->indx < a_elt->indx)
1814 b_elt = b_elt->next;
1815 else
1816 {
1817 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1818 if (a_elt->bits[ix] & b_elt->bits[ix])
1819 return true;
1820 a_elt = a_elt->next;
1821 b_elt = b_elt->next;
1822 }
1823 }
1824 return false;
1825 }
1826
1827 /* Return true if A AND NOT B is not empty. */
1828
1829 bool
bitmap_intersect_compl_p(const_bitmap a,const_bitmap b)1830 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
1831 {
1832 const bitmap_element *a_elt;
1833 const bitmap_element *b_elt;
1834 unsigned ix;
1835 for (a_elt = a->first, b_elt = b->first;
1836 a_elt && b_elt;)
1837 {
1838 if (a_elt->indx < b_elt->indx)
1839 return true;
1840 else if (b_elt->indx < a_elt->indx)
1841 b_elt = b_elt->next;
1842 else
1843 {
1844 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1845 if (a_elt->bits[ix] & ~b_elt->bits[ix])
1846 return true;
1847 a_elt = a_elt->next;
1848 b_elt = b_elt->next;
1849 }
1850 }
1851 return a_elt != NULL;
1852 }
1853
1854
1855 /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
1856
1857 bool
bitmap_ior_and_compl(bitmap dst,const_bitmap a,const_bitmap b,const_bitmap kill)1858 bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
1859 {
1860 bool changed = false;
1861
1862 bitmap_element *dst_elt = dst->first;
1863 const bitmap_element *a_elt = a->first;
1864 const bitmap_element *b_elt = b->first;
1865 const bitmap_element *kill_elt = kill->first;
1866 bitmap_element *dst_prev = NULL;
1867 bitmap_element **dst_prev_pnext = &dst->first;
1868
1869 gcc_assert (dst != a && dst != b && dst != kill);
1870
1871 /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
1872 if (b == kill || bitmap_empty_p (b))
1873 {
1874 changed = !bitmap_equal_p (dst, a);
1875 if (changed)
1876 bitmap_copy (dst, a);
1877 return changed;
1878 }
1879 if (bitmap_empty_p (kill))
1880 return bitmap_ior (dst, a, b);
1881 if (bitmap_empty_p (a))
1882 return bitmap_and_compl (dst, b, kill);
1883
1884 while (a_elt || b_elt)
1885 {
1886 bool new_element = false;
1887
1888 if (b_elt)
1889 while (kill_elt && kill_elt->indx < b_elt->indx)
1890 kill_elt = kill_elt->next;
1891
1892 if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
1893 && (!a_elt || a_elt->indx >= b_elt->indx))
1894 {
1895 bitmap_element tmp_elt;
1896 unsigned ix;
1897
1898 BITMAP_WORD ior = 0;
1899 tmp_elt.indx = b_elt->indx;
1900 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1901 {
1902 BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
1903 ior |= r;
1904 tmp_elt.bits[ix] = r;
1905 }
1906
1907 if (ior)
1908 {
1909 changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1910 a_elt, &tmp_elt, changed);
1911 new_element = true;
1912 if (a_elt && a_elt->indx == b_elt->indx)
1913 a_elt = a_elt->next;
1914 }
1915
1916 b_elt = b_elt->next;
1917 kill_elt = kill_elt->next;
1918 }
1919 else
1920 {
1921 changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1922 a_elt, b_elt, changed);
1923 new_element = true;
1924
1925 if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1926 {
1927 a_elt = a_elt->next;
1928 b_elt = b_elt->next;
1929 }
1930 else
1931 {
1932 if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1933 a_elt = a_elt->next;
1934 else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1935 b_elt = b_elt->next;
1936 }
1937 }
1938
1939 if (new_element)
1940 {
1941 dst_prev = *dst_prev_pnext;
1942 dst_prev_pnext = &dst_prev->next;
1943 dst_elt = *dst_prev_pnext;
1944 }
1945 }
1946
1947 if (dst_elt)
1948 {
1949 changed = true;
1950 /* Ensure that dst->current is valid. */
1951 dst->current = dst->first;
1952 bitmap_elt_clear_from (dst, dst_elt);
1953 }
1954 gcc_checking_assert (!dst->current == !dst->first);
1955 if (dst->current)
1956 dst->indx = dst->current->indx;
1957
1958 return changed;
1959 }
1960
1961 /* A |= (FROM1 & ~FROM2). Return true if A changes. */
1962
1963 bool
bitmap_ior_and_compl_into(bitmap a,const_bitmap from1,const_bitmap from2)1964 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
1965 {
1966 bitmap_head tmp;
1967 bool changed;
1968
1969 bitmap_initialize (&tmp, &bitmap_default_obstack);
1970 bitmap_and_compl (&tmp, from1, from2);
1971 changed = bitmap_ior_into (a, &tmp);
1972 bitmap_clear (&tmp);
1973
1974 return changed;
1975 }
1976
1977 /* A |= (B & C). Return true if A changes. */
1978
1979 bool
bitmap_ior_and_into(bitmap a,const_bitmap b,const_bitmap c)1980 bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
1981 {
1982 bitmap_element *a_elt = a->first;
1983 const bitmap_element *b_elt = b->first;
1984 const bitmap_element *c_elt = c->first;
1985 bitmap_element and_elt;
1986 bitmap_element *a_prev = NULL;
1987 bitmap_element **a_prev_pnext = &a->first;
1988 bool changed = false;
1989 unsigned ix;
1990
1991 if (b == c)
1992 return bitmap_ior_into (a, b);
1993 if (bitmap_empty_p (b) || bitmap_empty_p (c))
1994 return false;
1995
1996 and_elt.indx = -1;
1997 while (b_elt && c_elt)
1998 {
1999 BITMAP_WORD overall;
2000
2001 /* Find a common item of B and C. */
2002 while (b_elt->indx != c_elt->indx)
2003 {
2004 if (b_elt->indx < c_elt->indx)
2005 {
2006 b_elt = b_elt->next;
2007 if (!b_elt)
2008 goto done;
2009 }
2010 else
2011 {
2012 c_elt = c_elt->next;
2013 if (!c_elt)
2014 goto done;
2015 }
2016 }
2017
2018 overall = 0;
2019 and_elt.indx = b_elt->indx;
2020 for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2021 {
2022 and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2023 overall |= and_elt.bits[ix];
2024 }
2025
2026 b_elt = b_elt->next;
2027 c_elt = c_elt->next;
2028 if (!overall)
2029 continue;
2030
2031 /* Now find a place to insert AND_ELT. */
2032 do
2033 {
2034 ix = a_elt ? a_elt->indx : and_elt.indx;
2035 if (ix == and_elt.indx)
2036 changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2037 else if (ix > and_elt.indx)
2038 changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2039
2040 a_prev = *a_prev_pnext;
2041 a_prev_pnext = &a_prev->next;
2042 a_elt = *a_prev_pnext;
2043
2044 /* If A lagged behind B/C, we advanced it so loop once more. */
2045 }
2046 while (ix < and_elt.indx);
2047 }
2048
2049 done:
2050 gcc_checking_assert (!a->current == !a->first);
2051 if (a->current)
2052 a->indx = a->current->indx;
2053 return changed;
2054 }
2055
2056 /* Compute hash of bitmap (for purposes of hashing). */
2057 hashval_t
bitmap_hash(const_bitmap head)2058 bitmap_hash (const_bitmap head)
2059 {
2060 const bitmap_element *ptr;
2061 BITMAP_WORD hash = 0;
2062 int ix;
2063
2064 for (ptr = head->first; ptr; ptr = ptr->next)
2065 {
2066 hash ^= ptr->indx;
2067 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2068 hash ^= ptr->bits[ix];
2069 }
2070 return (hashval_t)hash;
2071 }
2072
2073
2074 /* Debugging function to print out the contents of a bitmap. */
2075
2076 DEBUG_FUNCTION void
debug_bitmap_file(FILE * file,const_bitmap head)2077 debug_bitmap_file (FILE *file, const_bitmap head)
2078 {
2079 const bitmap_element *ptr;
2080
2081 fprintf (file, "\nfirst = " HOST_PTR_PRINTF
2082 " current = " HOST_PTR_PRINTF " indx = %u\n",
2083 (void *) head->first, (void *) head->current, head->indx);
2084
2085 for (ptr = head->first; ptr; ptr = ptr->next)
2086 {
2087 unsigned int i, j, col = 26;
2088
2089 fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2090 " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2091 (const void*) ptr, (const void*) ptr->next,
2092 (const void*) ptr->prev, ptr->indx);
2093
2094 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2095 for (j = 0; j < BITMAP_WORD_BITS; j++)
2096 if ((ptr->bits[i] >> j) & 1)
2097 {
2098 if (col > 70)
2099 {
2100 fprintf (file, "\n\t\t\t");
2101 col = 24;
2102 }
2103
2104 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2105 + i * BITMAP_WORD_BITS + j));
2106 col += 4;
2107 }
2108
2109 fprintf (file, " }\n");
2110 }
2111 }
2112
2113 /* Function to be called from the debugger to print the contents
2114 of a bitmap. */
2115
2116 DEBUG_FUNCTION void
debug_bitmap(const_bitmap head)2117 debug_bitmap (const_bitmap head)
2118 {
2119 debug_bitmap_file (stderr, head);
2120 }
2121
2122 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
2123 it does not print anything but the bits. */
2124
2125 DEBUG_FUNCTION void
bitmap_print(FILE * file,const_bitmap head,const char * prefix,const char * suffix)2126 bitmap_print (FILE *file, const_bitmap head, const char *prefix,
2127 const char *suffix)
2128 {
2129 const char *comma = "";
2130 unsigned i;
2131 bitmap_iterator bi;
2132
2133 fputs (prefix, file);
2134 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2135 {
2136 fprintf (file, "%s%d", comma, i);
2137 comma = ", ";
2138 }
2139 fputs (suffix, file);
2140 }
2141
2142 /* Output per-bitmap memory usage statistics. */
2143 void
dump_bitmap_statistics(void)2144 dump_bitmap_statistics (void)
2145 {
2146 if (!GATHER_STATISTICS)
2147 return;
2148
2149 bitmap_mem_desc.dump (BITMAP_ORIGIN);
2150 }
2151
2152 DEBUG_FUNCTION void
debug(const bitmap_head & ref)2153 debug (const bitmap_head &ref)
2154 {
2155 dump_bitmap (stderr, &ref);
2156 }
2157
2158 DEBUG_FUNCTION void
debug(const bitmap_head * ptr)2159 debug (const bitmap_head *ptr)
2160 {
2161 if (ptr)
2162 debug (*ptr);
2163 else
2164 fprintf (stderr, "<nil>\n");
2165 }
2166
2167 #if CHECKING_P
2168
2169 namespace selftest {
2170
2171 /* Selftests for bitmaps. */
2172
2173 /* Freshly-created bitmaps ought to be empty. */
2174
2175 static void
test_gc_alloc()2176 test_gc_alloc ()
2177 {
2178 bitmap b = bitmap_gc_alloc ();
2179 ASSERT_TRUE (bitmap_empty_p (b));
2180 }
2181
2182 /* Verify bitmap_set_range. */
2183
2184 static void
test_set_range()2185 test_set_range ()
2186 {
2187 bitmap b = bitmap_gc_alloc ();
2188 ASSERT_TRUE (bitmap_empty_p (b));
2189
2190 bitmap_set_range (b, 7, 5);
2191 ASSERT_FALSE (bitmap_empty_p (b));
2192 ASSERT_EQ (5, bitmap_count_bits (b));
2193
2194 /* Verify bitmap_bit_p at the boundaries. */
2195 ASSERT_FALSE (bitmap_bit_p (b, 6));
2196 ASSERT_TRUE (bitmap_bit_p (b, 7));
2197 ASSERT_TRUE (bitmap_bit_p (b, 11));
2198 ASSERT_FALSE (bitmap_bit_p (b, 12));
2199 }
2200
2201 /* Verify splitting a range into two pieces using bitmap_clear_bit. */
2202
2203 static void
test_clear_bit_in_middle()2204 test_clear_bit_in_middle ()
2205 {
2206 bitmap b = bitmap_gc_alloc ();
2207
2208 /* Set b to [100..200]. */
2209 bitmap_set_range (b, 100, 100);
2210 ASSERT_EQ (100, bitmap_count_bits (b));
2211
2212 /* Clear a bit in the middle. */
2213 bool changed = bitmap_clear_bit (b, 150);
2214 ASSERT_TRUE (changed);
2215 ASSERT_EQ (99, bitmap_count_bits (b));
2216 ASSERT_TRUE (bitmap_bit_p (b, 149));
2217 ASSERT_FALSE (bitmap_bit_p (b, 150));
2218 ASSERT_TRUE (bitmap_bit_p (b, 151));
2219 }
2220
2221 /* Verify bitmap_copy. */
2222
2223 static void
test_copying()2224 test_copying ()
2225 {
2226 bitmap src = bitmap_gc_alloc ();
2227 bitmap_set_range (src, 40, 10);
2228
2229 bitmap dst = bitmap_gc_alloc ();
2230 ASSERT_FALSE (bitmap_equal_p (src, dst));
2231 bitmap_copy (dst, src);
2232 ASSERT_TRUE (bitmap_equal_p (src, dst));
2233
2234 /* Verify that we can make them unequal again... */
2235 bitmap_set_range (src, 70, 5);
2236 ASSERT_FALSE (bitmap_equal_p (src, dst));
2237
2238 /* ...and that changing src after the copy didn't affect
2239 the other: */
2240 ASSERT_FALSE (bitmap_bit_p (dst, 70));
2241 }
2242
2243 /* Verify bitmap_single_bit_set_p. */
2244
2245 static void
test_bitmap_single_bit_set_p()2246 test_bitmap_single_bit_set_p ()
2247 {
2248 bitmap b = bitmap_gc_alloc ();
2249
2250 ASSERT_FALSE (bitmap_single_bit_set_p (b));
2251
2252 bitmap_set_range (b, 42, 1);
2253 ASSERT_TRUE (bitmap_single_bit_set_p (b));
2254 ASSERT_EQ (42, bitmap_first_set_bit (b));
2255
2256 bitmap_set_range (b, 1066, 1);
2257 ASSERT_FALSE (bitmap_single_bit_set_p (b));
2258 ASSERT_EQ (42, bitmap_first_set_bit (b));
2259
2260 bitmap_clear_range (b, 0, 100);
2261 ASSERT_TRUE (bitmap_single_bit_set_p (b));
2262 ASSERT_EQ (1066, bitmap_first_set_bit (b));
2263 }
2264
2265 /* Run all of the selftests within this file. */
2266
2267 void
bitmap_c_tests()2268 bitmap_c_tests ()
2269 {
2270 test_gc_alloc ();
2271 test_set_range ();
2272 test_clear_bit_in_middle ();
2273 test_copying ();
2274 test_bitmap_single_bit_set_p ();
2275 }
2276
2277 } // namespace selftest
2278 #endif /* CHECKING_P */
2279
2280 #include "gt-bitmap.h"
2281