[testsuite]
[official-gcc.git] / gcc / sbitmap.c
blob967868ad118f83ef2d43ea1abda888cf7bd24ed6
1 /* Simple bitmaps.
2 Copyright (C) 1999-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "sbitmap.h"
24 #include "selftest.h"
26 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
27 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
29 /* Return the size in bytes of a bitmap MAP. */
31 static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
33 return map->size * sizeof (SBITMAP_ELT_TYPE);
37 /* Bitmap manipulation routines. */
39 /* Allocate a simple bitmap of N_ELMS bits. */
41 sbitmap
42 sbitmap_alloc (unsigned int n_elms)
44 unsigned int bytes, size, amt;
45 sbitmap bmap;
47 size = SBITMAP_SET_SIZE (n_elms);
48 bytes = size * sizeof (SBITMAP_ELT_TYPE);
49 amt = (sizeof (struct simple_bitmap_def)
50 + bytes - sizeof (SBITMAP_ELT_TYPE));
51 bmap = (sbitmap) xmalloc (amt);
52 bmap->n_bits = n_elms;
53 bmap->size = size;
54 return bmap;
57 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
58 size of BMAP, clear the new bits to zero if the DEF argument
59 is zero, and set them to one otherwise. */
61 sbitmap
62 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
64 unsigned int bytes, size, amt;
65 unsigned int last_bit;
67 size = SBITMAP_SET_SIZE (n_elms);
68 bytes = size * sizeof (SBITMAP_ELT_TYPE);
69 if (bytes > sbitmap_size_bytes (bmap))
71 amt = (sizeof (struct simple_bitmap_def)
72 + bytes - sizeof (SBITMAP_ELT_TYPE));
73 bmap = (sbitmap) xrealloc (bmap, amt);
76 if (n_elms > bmap->n_bits)
78 if (def)
80 memset (bmap->elms + bmap->size, -1,
81 bytes - sbitmap_size_bytes (bmap));
83 /* Set the new bits if the original last element. */
84 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
85 if (last_bit)
86 bmap->elms[bmap->size - 1]
87 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
89 /* Clear the unused bit in the new last element. */
90 last_bit = n_elms % SBITMAP_ELT_BITS;
91 if (last_bit)
92 bmap->elms[size - 1]
93 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
95 else
96 memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
98 else if (n_elms < bmap->n_bits)
100 /* Clear the surplus bits in the last word. */
101 last_bit = n_elms % SBITMAP_ELT_BITS;
102 if (last_bit)
103 bmap->elms[size - 1]
104 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
107 bmap->n_bits = n_elms;
108 bmap->size = size;
109 return bmap;
112 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
114 sbitmap
115 sbitmap_realloc (sbitmap src, unsigned int n_elms)
117 unsigned int bytes, size, amt;
118 sbitmap bmap;
120 size = SBITMAP_SET_SIZE (n_elms);
121 bytes = size * sizeof (SBITMAP_ELT_TYPE);
122 amt = (sizeof (struct simple_bitmap_def)
123 + bytes - sizeof (SBITMAP_ELT_TYPE));
125 if (sbitmap_size_bytes (src) >= bytes)
127 src->n_bits = n_elms;
128 return src;
131 bmap = (sbitmap) xrealloc (src, amt);
132 bmap->n_bits = n_elms;
133 bmap->size = size;
134 return bmap;
137 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
139 sbitmap *
140 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
142 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
143 sbitmap *bitmap_vector;
145 size = SBITMAP_SET_SIZE (n_elms);
146 bytes = size * sizeof (SBITMAP_ELT_TYPE);
147 elm_bytes = (sizeof (struct simple_bitmap_def)
148 + bytes - sizeof (SBITMAP_ELT_TYPE));
149 vector_bytes = n_vecs * sizeof (sbitmap *);
151 /* Round up `vector_bytes' to account for the alignment requirements
152 of an sbitmap. One could allocate the vector-table and set of sbitmaps
153 separately, but that requires maintaining two pointers or creating
154 a cover struct to hold both pointers (so our result is still just
155 one pointer). Neither is a bad idea, but this is simpler for now. */
157 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
158 struct { char x; SBITMAP_ELT_TYPE y; } align;
159 int alignment = (char *) & align.y - & align.x;
160 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
163 amt = vector_bytes + (n_vecs * elm_bytes);
164 bitmap_vector = (sbitmap *) xmalloc (amt);
166 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
168 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
170 bitmap_vector[i] = b;
171 b->n_bits = n_elms;
172 b->size = size;
175 return bitmap_vector;
178 /* Copy sbitmap SRC to DST. */
180 void
181 bitmap_copy (sbitmap dst, const_sbitmap src)
183 gcc_checking_assert (src->size <= dst->size);
185 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
188 /* Determine if a == b. */
190 bitmap_equal_p (const_sbitmap a, const_sbitmap b)
192 bitmap_check_sizes (a, b);
194 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
197 /* Return true if the bitmap is empty. */
199 bool
200 bitmap_empty_p (const_sbitmap bmap)
202 unsigned int i;
203 for (i=0; i<bmap->size; i++)
204 if (bmap->elms[i])
205 return false;
207 return true;
210 /* Clear COUNT bits from START in BMAP. */
212 void
213 bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
215 if (count == 0)
216 return;
218 bitmap_check_index (bmap, start + count - 1);
220 unsigned int start_word = start / SBITMAP_ELT_BITS;
221 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
223 /* Clearing less than a full word, starting at the beginning of a word. */
224 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
226 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
227 bmap->elms[start_word] &= ~mask;
228 return;
231 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
232 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
234 /* Clearing starts somewhere in the middle of the first word. Clear up to
235 the end of the first word or the end of the requested region, whichever
236 comes first. */
237 if (start_bitno != 0)
239 unsigned int nbits = ((start_word == end_word)
240 ? end_bitno - start_bitno
241 : SBITMAP_ELT_BITS - start_bitno);
242 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
243 mask <<= start_bitno;
244 bmap->elms[start_word] &= ~mask;
245 start_word++;
246 count -= nbits;
249 if (count == 0)
250 return;
252 /* Now clear words at a time until we hit a partial word. */
253 unsigned int nwords = (end_word - start_word);
254 if (nwords)
256 memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
257 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
258 start_word += nwords;
261 if (count == 0)
262 return;
264 /* Now handle residuals in the last word. */
265 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
266 bmap->elms[start_word] &= ~mask;
269 /* Set COUNT bits from START in BMAP. */
270 void
271 bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
273 if (count == 0)
274 return;
276 bitmap_check_index (bmap, start + count - 1);
278 unsigned int start_word = start / SBITMAP_ELT_BITS;
279 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
281 /* Setting less than a full word, starting at the beginning of a word. */
282 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
284 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
285 bmap->elms[start_word] |= mask;
286 return;
289 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
290 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
292 /* Setting starts somewhere in the middle of the first word. Set up to
293 the end of the first word or the end of the requested region, whichever
294 comes first. */
295 if (start_bitno != 0)
297 unsigned int nbits = ((start_word == end_word)
298 ? end_bitno - start_bitno
299 : SBITMAP_ELT_BITS - start_bitno);
300 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
301 mask <<= start_bitno;
302 bmap->elms[start_word] |= mask;
303 start_word++;
304 count -= nbits;
307 if (count == 0)
308 return;
310 /* Now set words at a time until we hit a partial word. */
311 unsigned int nwords = (end_word - start_word);
312 if (nwords)
314 memset (&bmap->elms[start_word], 0xff,
315 nwords * sizeof (SBITMAP_ELT_TYPE));
316 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
317 start_word += nwords;
320 if (count == 0)
321 return;
323 /* Now handle residuals in the last word. */
324 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
325 bmap->elms[start_word] |= mask;
328 /* Return TRUE if any bit between START and END inclusive is set within
329 the simple bitmap BMAP. Return FALSE otherwise. */
331 bool
332 bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
334 gcc_checking_assert (start <= end);
335 bitmap_check_index (bmap, end);
337 unsigned int start_word = start / SBITMAP_ELT_BITS;
338 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
340 unsigned int end_word = end / SBITMAP_ELT_BITS;
341 unsigned int end_bitno = end % SBITMAP_ELT_BITS;
343 /* Check beginning of first word if different from zero. */
344 if (start_bitno != 0)
346 SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0;
347 if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS)
348 high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
350 SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1;
351 SBITMAP_ELT_TYPE mask = high_mask - low_mask;
352 if (bmap->elms[start_word] & mask)
353 return true;
354 start_word++;
357 if (start_word > end_word)
358 return false;
360 /* Now test words at a time until we hit a partial word. */
361 unsigned int nwords = (end_word - start_word);
362 while (nwords)
364 if (bmap->elms[start_word])
365 return true;
366 start_word++;
367 nwords--;
370 /* Now handle residuals in the last word. */
371 SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0;
372 if (end_bitno + 1 < SBITMAP_ELT_BITS)
373 mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
374 return (bmap->elms[start_word] & mask) != 0;
377 #if GCC_VERSION < 3400
378 /* Table of number of set bits in a character, indexed by value of char. */
379 static const unsigned char popcount_table[] =
381 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,
382 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,
383 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,
384 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,
385 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,
386 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,
387 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,
388 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,
391 static unsigned long
392 sbitmap_popcount (SBITMAP_ELT_TYPE a)
394 unsigned long ret = 0;
395 unsigned i;
397 /* Just do this the table way for now */
398 for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
399 ret += popcount_table[(a >> i) & 0xff];
400 return ret;
402 #endif
404 /* Count and return the number of bits set in the bitmap BMAP. */
406 unsigned int
407 bitmap_count_bits (const_sbitmap bmap)
409 unsigned int count = 0;
410 for (unsigned int i = 0; i < bmap->size; i++)
411 if (bmap->elms[i])
413 #if GCC_VERSION < 3400
414 count += sbitmap_popcount (bmap->elms[i]);
415 #else
416 # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
417 count += __builtin_popcountl (bmap->elms[i]);
418 # elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
419 count += __builtin_popcountll (bmap->elms[i]);
420 # else
421 count += __builtin_popcount (bmap->elms[i]);
422 # endif
423 #endif
425 return count;
428 /* Zero all elements in a bitmap. */
430 void
431 bitmap_clear (sbitmap bmap)
433 memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
436 /* Set all elements in a bitmap to ones. */
438 void
439 bitmap_ones (sbitmap bmap)
441 unsigned int last_bit;
443 memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
445 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
446 if (last_bit)
447 bmap->elms[bmap->size - 1]
448 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
451 /* Zero a vector of N_VECS bitmaps. */
453 void
454 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
456 unsigned int i;
458 for (i = 0; i < n_vecs; i++)
459 bitmap_clear (bmap[i]);
462 /* Set a vector of N_VECS bitmaps to ones. */
464 void
465 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
467 unsigned int i;
469 for (i = 0; i < n_vecs; i++)
470 bitmap_ones (bmap[i]);
473 /* Set DST to be A union (B - C).
474 DST = A | (B & ~C).
475 Returns true if any change is made. */
477 bool
478 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
480 bitmap_check_sizes (a, b);
481 bitmap_check_sizes (b, c);
483 unsigned int i, n = dst->size;
484 sbitmap_ptr dstp = dst->elms;
485 const_sbitmap_ptr ap = a->elms;
486 const_sbitmap_ptr bp = b->elms;
487 const_sbitmap_ptr cp = c->elms;
488 SBITMAP_ELT_TYPE changed = 0;
490 for (i = 0; i < n; i++)
492 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
493 changed |= *dstp ^ tmp;
494 *dstp++ = tmp;
497 return changed != 0;
500 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
502 void
503 bitmap_not (sbitmap dst, const_sbitmap src)
505 bitmap_check_sizes (src, dst);
507 unsigned int i, n = dst->size;
508 sbitmap_ptr dstp = dst->elms;
509 const_sbitmap_ptr srcp = src->elms;
510 unsigned int last_bit;
512 for (i = 0; i < n; i++)
513 *dstp++ = ~*srcp++;
515 /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */
516 last_bit = src->n_bits % SBITMAP_ELT_BITS;
517 if (last_bit)
518 dst->elms[n-1] = dst->elms[n-1]
519 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
522 /* Set the bits in DST to be the difference between the bits
523 in A and the bits in B. i.e. dst = a & (~b). */
525 void
526 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
528 bitmap_check_sizes (a, b);
529 bitmap_check_sizes (b, dst);
531 unsigned int i, dst_size = dst->size;
532 unsigned int min_size = dst->size;
533 sbitmap_ptr dstp = dst->elms;
534 const_sbitmap_ptr ap = a->elms;
535 const_sbitmap_ptr bp = b->elms;
537 /* A should be at least as large as DEST, to have a defined source. */
538 gcc_assert (a->size >= dst_size);
539 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
540 only copy the subtrahend into dest. */
541 if (b->size < min_size)
542 min_size = b->size;
543 for (i = 0; i < min_size; i++)
544 *dstp++ = *ap++ & (~*bp++);
545 /* Now fill the rest of dest from A, if B was too short.
546 This makes sense only when destination and A differ. */
547 if (dst != a && i != dst_size)
548 for (; i < dst_size; i++)
549 *dstp++ = *ap++;
552 /* Return true if there are any bits set in A are also set in B.
553 Return false otherwise. */
555 bool
556 bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
558 bitmap_check_sizes (a, b);
560 const_sbitmap_ptr ap = a->elms;
561 const_sbitmap_ptr bp = b->elms;
562 unsigned int i, n;
564 n = MIN (a->size, b->size);
565 for (i = 0; i < n; i++)
566 if ((*ap++ & *bp++) != 0)
567 return true;
569 return false;
572 /* Set DST to be (A and B).
573 Return nonzero if any change is made. */
575 bool
576 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
578 bitmap_check_sizes (a, b);
579 bitmap_check_sizes (b, dst);
581 unsigned int i, n = dst->size;
582 sbitmap_ptr dstp = dst->elms;
583 const_sbitmap_ptr ap = a->elms;
584 const_sbitmap_ptr bp = b->elms;
585 SBITMAP_ELT_TYPE changed = 0;
587 for (i = 0; i < n; i++)
589 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
590 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
591 *dstp++ = tmp;
592 changed |= wordchanged;
594 return changed != 0;
597 /* Set DST to be (A xor B)).
598 Return nonzero if any change is made. */
600 bool
601 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
603 bitmap_check_sizes (a, b);
604 bitmap_check_sizes (b, dst);
606 unsigned int i, n = dst->size;
607 sbitmap_ptr dstp = dst->elms;
608 const_sbitmap_ptr ap = a->elms;
609 const_sbitmap_ptr bp = b->elms;
610 SBITMAP_ELT_TYPE changed = 0;
612 for (i = 0; i < n; i++)
614 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
615 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
616 *dstp++ = tmp;
617 changed |= wordchanged;
619 return changed != 0;
622 /* Set DST to be (A or B)).
623 Return nonzero if any change is made. */
625 bool
626 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
628 bitmap_check_sizes (a, b);
629 bitmap_check_sizes (b, dst);
631 unsigned int i, n = dst->size;
632 sbitmap_ptr dstp = dst->elms;
633 const_sbitmap_ptr ap = a->elms;
634 const_sbitmap_ptr bp = b->elms;
635 SBITMAP_ELT_TYPE changed = 0;
637 for (i = 0; i < n; i++)
639 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
640 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
641 *dstp++ = tmp;
642 changed |= wordchanged;
644 return changed != 0;
647 /* Return nonzero if A is a subset of B. */
649 bool
650 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
652 bitmap_check_sizes (a, b);
654 unsigned int i, n = a->size;
655 const_sbitmap_ptr ap, bp;
657 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
658 if ((*ap | *bp) != *bp)
659 return false;
661 return true;
664 /* Set DST to be (A or (B and C)).
665 Return nonzero if any change is made. */
667 bool
668 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
670 bitmap_check_sizes (a, b);
671 bitmap_check_sizes (b, c);
672 bitmap_check_sizes (c, dst);
674 unsigned int i, n = dst->size;
675 sbitmap_ptr dstp = dst->elms;
676 const_sbitmap_ptr ap = a->elms;
677 const_sbitmap_ptr bp = b->elms;
678 const_sbitmap_ptr cp = c->elms;
679 SBITMAP_ELT_TYPE changed = 0;
681 for (i = 0; i < n; i++)
683 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
684 changed |= *dstp ^ tmp;
685 *dstp++ = tmp;
688 return changed != 0;
691 /* Set DST to be (A and (B or C)).
692 Return nonzero if any change is made. */
694 bool
695 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
697 bitmap_check_sizes (a, b);
698 bitmap_check_sizes (b, c);
699 bitmap_check_sizes (c, dst);
701 unsigned int i, n = dst->size;
702 sbitmap_ptr dstp = dst->elms;
703 const_sbitmap_ptr ap = a->elms;
704 const_sbitmap_ptr bp = b->elms;
705 const_sbitmap_ptr cp = c->elms;
706 SBITMAP_ELT_TYPE changed = 0;
708 for (i = 0; i < n; i++)
710 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
711 changed |= *dstp ^ tmp;
712 *dstp++ = tmp;
715 return changed != 0;
718 /* Return number of first bit set in the bitmap, -1 if none. */
721 bitmap_first_set_bit (const_sbitmap bmap)
723 unsigned int n = 0;
724 sbitmap_iterator sbi;
726 EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
727 return n;
728 return -1;
731 /* Return number of last bit set in the bitmap, -1 if none. */
734 bitmap_last_set_bit (const_sbitmap bmap)
736 int i;
737 const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
739 for (i = bmap->size - 1; i >= 0; i--)
741 const SBITMAP_ELT_TYPE word = ptr[i];
743 if (word != 0)
745 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
746 SBITMAP_ELT_TYPE mask
747 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
749 while (1)
751 if ((word & mask) != 0)
752 return index;
754 mask >>= 1;
755 index--;
760 return -1;
763 void
764 dump_bitmap (FILE *file, const_sbitmap bmap)
766 unsigned int i, n, j;
767 unsigned int set_size = bmap->size;
768 unsigned int total_bits = bmap->n_bits;
770 fprintf (file, " ");
771 for (i = n = 0; i < set_size && n < total_bits; i++)
772 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
774 if (n != 0 && n % 10 == 0)
775 fprintf (file, " ");
777 fprintf (file, "%d",
778 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
781 fprintf (file, "\n");
784 DEBUG_FUNCTION void
785 debug_raw (simple_bitmap_def &ref)
787 dump_bitmap (stderr, &ref);
790 DEBUG_FUNCTION void
791 debug_raw (simple_bitmap_def *ptr)
793 if (ptr)
794 debug_raw (*ptr);
795 else
796 fprintf (stderr, "<nil>\n");
799 void
800 dump_bitmap_file (FILE *file, const_sbitmap bmap)
802 unsigned int i, pos;
804 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
806 for (pos = 30, i = 0; i < bmap->n_bits; i++)
807 if (bitmap_bit_p (bmap, i))
809 if (pos > 70)
811 fprintf (file, "\n ");
812 pos = 0;
815 fprintf (file, "%d ", i);
816 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
819 fprintf (file, "}\n");
822 DEBUG_FUNCTION void
823 debug_bitmap (const_sbitmap bmap)
825 dump_bitmap_file (stderr, bmap);
828 DEBUG_FUNCTION void
829 debug (simple_bitmap_def &ref)
831 dump_bitmap_file (stderr, &ref);
834 DEBUG_FUNCTION void
835 debug (simple_bitmap_def *ptr)
837 if (ptr)
838 debug (*ptr);
839 else
840 fprintf (stderr, "<nil>\n");
843 void
844 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
845 sbitmap *bmaps, int n_maps)
847 int i;
849 fprintf (file, "%s\n", title);
850 for (i = 0; i < n_maps; i++)
852 fprintf (file, "%s %d\n", subtitle, i);
853 dump_bitmap (file, bmaps[i]);
856 fprintf (file, "\n");
859 #if CHECKING_P
861 namespace selftest {
863 /* Selftests for sbitmaps. */
865 /* Checking function that uses both bitmap_bit_in_range_p and
866 loop of bitmap_bit_p and verifies consistent results. */
868 static bool
869 bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start,
870 unsigned end)
872 bool r1 = bitmap_bit_in_range_p (s, start, end);
873 bool r2 = false;
875 for (unsigned int i = start; i <= end; i++)
876 if (bitmap_bit_p (s, i))
878 r2 = true;
879 break;
882 ASSERT_EQ (r1, r2);
883 return r1;
886 /* Verify bitmap_set_range functions for sbitmap. */
888 static void
889 test_set_range ()
891 sbitmap s = sbitmap_alloc (16);
892 bitmap_clear (s);
894 bitmap_set_range (s, 0, 1);
895 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 0, 0));
896 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 15));
897 bitmap_set_range (s, 15, 1);
898 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 14));
899 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 15, 15));
900 sbitmap_free (s);
902 s = sbitmap_alloc (1024);
903 bitmap_clear (s);
904 bitmap_set_range (s, 512, 1);
905 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
906 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 513, 1023));
907 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
908 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 512));
909 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 513));
910 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 508, 511));
912 bitmap_clear (s);
913 bitmap_set_range (s, 512, 64);
914 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
915 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 512 + 64, 1023));
916 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
917 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512 + 63, 512 + 63));
918 sbitmap_free (s);
921 /* Verify bitmap_bit_in_range_p functions for sbitmap. */
923 static void
924 test_bit_in_range ()
926 sbitmap s = sbitmap_alloc (1024);
927 bitmap_clear (s);
929 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
930 bitmap_set_bit (s, 100);
932 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
933 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99));
934 ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023));
935 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100));
936 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100));
937 ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100));
938 ASSERT_TRUE (bitmap_bit_p (s, 100));
940 sbitmap_free (s);
942 s = sbitmap_alloc (64);
943 bitmap_clear (s);
944 bitmap_set_bit (s, 63);
945 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
946 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63));
947 ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63));
948 ASSERT_TRUE (bitmap_bit_p (s, 63));
949 sbitmap_free (s);
951 s = sbitmap_alloc (1024);
952 bitmap_clear (s);
953 bitmap_set_bit (s, 128);
954 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127));
955 ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023));
957 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128));
958 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128));
959 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255));
960 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254));
961 ASSERT_TRUE (bitmap_bit_p (s, 128));
963 bitmap_clear (s);
964 bitmap_set_bit (s, 8);
965 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8));
966 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12));
967 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
968 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127));
969 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512));
970 ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8));
971 ASSERT_TRUE (bitmap_bit_p (s, 8));
973 bitmap_clear (s);
974 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0));
975 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8));
976 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63));
977 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63));
978 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256));
980 bitmap_set_bit (s, 0);
981 bitmap_set_bit (s, 16);
982 bitmap_set_bit (s, 32);
983 bitmap_set_bit (s, 48);
984 bitmap_set_bit (s, 64);
985 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0));
986 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16));
987 ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63));
988 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64));
989 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15));
990 ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31));
991 ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63));
992 ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023));
993 sbitmap_free (s);
996 /* Run all of the selftests within this file. */
998 void
999 sbitmap_c_tests ()
1001 test_set_range ();
1002 test_bit_in_range ();
1005 } // namespace selftest
1006 #endif /* CHECKING_P */