1 /* Simple bitmaps.
2 Copyright (C) 1999-2020 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 "sbitmap.h"
24 #include "selftest.h"
25
26 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
27 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
28
29 /* Return the size in bytes of a bitmap MAP. */
30
sbitmap_size_bytes(const_sbitmap map)31 static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
32 {
33 return map->size * sizeof (SBITMAP_ELT_TYPE);
34 }
35
36
37 /* Bitmap manipulation routines. */
38
39 /* Allocate a simple bitmap of N_ELMS bits. */
40
41 sbitmap
sbitmap_alloc(unsigned int n_elms)42 sbitmap_alloc (unsigned int n_elms)
43 {
44 unsigned int bytes, size, amt;
45 sbitmap bmap;
46
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;
55 }
56
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. */
60
61 sbitmap
sbitmap_resize(sbitmap bmap,unsigned int n_elms,int def)62 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
63 {
64 unsigned int bytes, size, amt;
65 unsigned int last_bit;
66
67 size = SBITMAP_SET_SIZE (n_elms);
68 bytes = size * sizeof (SBITMAP_ELT_TYPE);
69 if (bytes > sbitmap_size_bytes (bmap))
70 {
71 amt = (sizeof (struct simple_bitmap_def)
72 + bytes - sizeof (SBITMAP_ELT_TYPE));
73 bmap = (sbitmap) xrealloc (bmap, amt);
74 }
75
76 if (n_elms > bmap->n_bits)
77 {
78 if (def)
79 {
80 memset (bmap->elms + bmap->size, -1,
81 bytes - sbitmap_size_bytes (bmap));
82
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));
88
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);
94 }
95 else
96 memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
97 }
98 else if (n_elms < bmap->n_bits)
99 {
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);
105 }
106
107 bmap->n_bits = n_elms;
108 bmap->size = size;
109 return bmap;
110 }
111
112 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
113
114 sbitmap
sbitmap_realloc(sbitmap src,unsigned int n_elms)115 sbitmap_realloc (sbitmap src, unsigned int n_elms)
116 {
117 unsigned int bytes, size, amt;
118 sbitmap bmap;
119
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));
124
125 if (sbitmap_size_bytes (src) >= bytes)
126 {
127 src->n_bits = n_elms;
128 return src;
129 }
130
131 bmap = (sbitmap) xrealloc (src, amt);
132 bmap->n_bits = n_elms;
133 bmap->size = size;
134 return bmap;
135 }
136
137 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
138
139 sbitmap *
sbitmap_vector_alloc(unsigned int n_vecs,unsigned int n_elms)140 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
141 {
142 unsigned int i, size;
143 size_t amt, bytes, vector_bytes, elm_bytes, offset;
144 sbitmap *bitmap_vector;
145
146 size = SBITMAP_SET_SIZE (n_elms);
147 bytes = size * sizeof (SBITMAP_ELT_TYPE);
148 elm_bytes = (sizeof (struct simple_bitmap_def)
149 + bytes - sizeof (SBITMAP_ELT_TYPE));
150 vector_bytes = n_vecs * sizeof (sbitmap *);
151
152 /* Round up `vector_bytes' to account for the alignment requirements
153 of an sbitmap. One could allocate the vector-table and set of sbitmaps
154 separately, but that requires maintaining two pointers or creating
155 a cover struct to hold both pointers (so our result is still just
156 one pointer). Neither is a bad idea, but this is simpler for now. */
157 {
158 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
159 struct { char x; SBITMAP_ELT_TYPE y; } align;
160 int alignment = (char *) & align.y - & align.x;
161 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
162 }
163
164 amt = vector_bytes + (n_vecs * elm_bytes);
165 bitmap_vector = (sbitmap *) xmalloc (amt);
166
167 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
168 {
169 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
170
171 bitmap_vector[i] = b;
172 b->n_bits = n_elms;
173 b->size = size;
174 }
175
176 return bitmap_vector;
177 }
178
179 /* Copy sbitmap SRC to DST. */
180
181 void
bitmap_copy(sbitmap dst,const_sbitmap src)182 bitmap_copy (sbitmap dst, const_sbitmap src)
183 {
184 gcc_checking_assert (src->size <= dst->size);
185
186 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
187 }
188
189 /* Determine if a == b. */
190 int
bitmap_equal_p(const_sbitmap a,const_sbitmap b)191 bitmap_equal_p (const_sbitmap a, const_sbitmap b)
192 {
193 bitmap_check_sizes (a, b);
194
195 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
196 }
197
198 /* Return true if the bitmap is empty. */
199
200 bool
bitmap_empty_p(const_sbitmap bmap)201 bitmap_empty_p (const_sbitmap bmap)
202 {
203 unsigned int i;
204 for (i=0; i<bmap->size; i++)
205 if (bmap->elms[i])
206 return false;
207
208 return true;
209 }
210
211 /* Clear COUNT bits from START in BMAP. */
212
213 void
bitmap_clear_range(sbitmap bmap,unsigned int start,unsigned int count)214 bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
215 {
216 if (count == 0)
217 return;
218
219 bitmap_check_index (bmap, start + count - 1);
220
221 unsigned int start_word = start / SBITMAP_ELT_BITS;
222 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
223
224 /* Clearing less than a full word, starting at the beginning of a word. */
225 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
226 {
227 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
228 bmap->elms[start_word] &= ~mask;
229 return;
230 }
231
232 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
233 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
234
235 /* Clearing starts somewhere in the middle of the first word. Clear up to
236 the end of the first word or the end of the requested region, whichever
237 comes first. */
238 if (start_bitno != 0)
239 {
240 unsigned int nbits = ((start_word == end_word)
241 ? end_bitno - start_bitno
242 : SBITMAP_ELT_BITS - start_bitno);
243 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
244 mask <<= start_bitno;
245 bmap->elms[start_word] &= ~mask;
246 start_word++;
247 count -= nbits;
248 }
249
250 if (count == 0)
251 return;
252
253 /* Now clear words at a time until we hit a partial word. */
254 unsigned int nwords = (end_word - start_word);
255 if (nwords)
256 {
257 memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
258 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
259 start_word += nwords;
260 }
261
262 if (count == 0)
263 return;
264
265 /* Now handle residuals in the last word. */
266 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
267 bmap->elms[start_word] &= ~mask;
268 }
269
270 /* Set COUNT bits from START in BMAP. */
271 void
bitmap_set_range(sbitmap bmap,unsigned int start,unsigned int count)272 bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
273 {
274 if (count == 0)
275 return;
276
277 bitmap_check_index (bmap, start + count - 1);
278
279 unsigned int start_word = start / SBITMAP_ELT_BITS;
280 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
281
282 /* Setting less than a full word, starting at the beginning of a word. */
283 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
284 {
285 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
286 bmap->elms[start_word] |= mask;
287 return;
288 }
289
290 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
291 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
292
293 /* Setting starts somewhere in the middle of the first word. Set up to
294 the end of the first word or the end of the requested region, whichever
295 comes first. */
296 if (start_bitno != 0)
297 {
298 unsigned int nbits = ((start_word == end_word)
299 ? end_bitno - start_bitno
300 : SBITMAP_ELT_BITS - start_bitno);
301 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
302 mask <<= start_bitno;
303 bmap->elms[start_word] |= mask;
304 start_word++;
305 count -= nbits;
306 }
307
308 if (count == 0)
309 return;
310
311 /* Now set words at a time until we hit a partial word. */
312 unsigned int nwords = (end_word - start_word);
313 if (nwords)
314 {
315 memset (&bmap->elms[start_word], 0xff,
316 nwords * sizeof (SBITMAP_ELT_TYPE));
317 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
318 start_word += nwords;
319 }
320
321 if (count == 0)
322 return;
323
324 /* Now handle residuals in the last word. */
325 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
326 bmap->elms[start_word] |= mask;
327 }
328
329 /* Return TRUE if any bit between START and END inclusive is set within
330 the simple bitmap BMAP. Return FALSE otherwise. */
331
332 bool
bitmap_bit_in_range_p(const_sbitmap bmap,unsigned int start,unsigned int end)333 bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
334 {
335 gcc_checking_assert (start <= end);
336 bitmap_check_index (bmap, end);
337
338 unsigned int start_word = start / SBITMAP_ELT_BITS;
339 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
340
341 unsigned int end_word = end / SBITMAP_ELT_BITS;
342 unsigned int end_bitno = end % SBITMAP_ELT_BITS;
343
344 /* Check beginning of first word if different from zero. */
345 if (start_bitno != 0)
346 {
347 SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0;
348 if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS)
349 high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
350
351 SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1;
352 SBITMAP_ELT_TYPE mask = high_mask - low_mask;
353 if (bmap->elms[start_word] & mask)
354 return true;
355 start_word++;
356 }
357
358 if (start_word > end_word)
359 return false;
360
361 /* Now test words at a time until we hit a partial word. */
362 unsigned int nwords = (end_word - start_word);
363 while (nwords)
364 {
365 if (bmap->elms[start_word])
366 return true;
367 start_word++;
368 nwords--;
369 }
370
371 /* Now handle residuals in the last word. */
372 SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0;
373 if (end_bitno + 1 < SBITMAP_ELT_BITS)
374 mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
375 return (bmap->elms[start_word] & mask) != 0;
376 }
377
378 #if GCC_VERSION < 3400
379 /* Table of number of set bits in a character, indexed by value of char. */
380 static const unsigned char popcount_table[] =
381 {
382 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,
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 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,
385 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,
386 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,
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 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,
389 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,
390 };
391
392 static unsigned long
sbitmap_popcount(SBITMAP_ELT_TYPE a)393 sbitmap_popcount (SBITMAP_ELT_TYPE a)
394 {
395 unsigned long ret = 0;
396 unsigned i;
397
398 /* Just do this the table way for now */
399 for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
400 ret += popcount_table[(a >> i) & 0xff];
401 return ret;
402 }
403 #endif
404
405 /* Count and return the number of bits set in the bitmap BMAP. */
406
407 unsigned int
bitmap_count_bits(const_sbitmap bmap)408 bitmap_count_bits (const_sbitmap bmap)
409 {
410 unsigned int count = 0;
411 for (unsigned int i = 0; i < bmap->size; i++)
412 if (bmap->elms[i])
413 {
414 #if GCC_VERSION < 3400
415 count += sbitmap_popcount (bmap->elms[i]);
416 #else
417 # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
418 count += __builtin_popcountl (bmap->elms[i]);
419 # elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
420 count += __builtin_popcountll (bmap->elms[i]);
421 # else
422 count += __builtin_popcount (bmap->elms[i]);
423 # endif
424 #endif
425 }
426 return count;
427 }
428
429 /* Zero all elements in a bitmap. */
430
431 void
bitmap_clear(sbitmap bmap)432 bitmap_clear (sbitmap bmap)
433 {
434 memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
435 }
436
437 /* Set all elements in a bitmap to ones. */
438
439 void
bitmap_ones(sbitmap bmap)440 bitmap_ones (sbitmap bmap)
441 {
442 unsigned int last_bit;
443
444 memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
445
446 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
447 if (last_bit)
448 bmap->elms[bmap->size - 1]
449 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
450 }
451
452 /* Zero a vector of N_VECS bitmaps. */
453
454 void
bitmap_vector_clear(sbitmap * bmap,unsigned int n_vecs)455 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
456 {
457 unsigned int i;
458
459 for (i = 0; i < n_vecs; i++)
460 bitmap_clear (bmap[i]);
461 }
462
463 /* Set a vector of N_VECS bitmaps to ones. */
464
465 void
bitmap_vector_ones(sbitmap * bmap,unsigned int n_vecs)466 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
467 {
468 unsigned int i;
469
470 for (i = 0; i < n_vecs; i++)
471 bitmap_ones (bmap[i]);
472 }
473
474 /* Set DST to be A union (B - C).
475 DST = A | (B & ~C).
476 Returns true if any change is made. */
477
478 bool
bitmap_ior_and_compl(sbitmap dst,const_sbitmap a,const_sbitmap b,const_sbitmap c)479 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
480 {
481 bitmap_check_sizes (a, b);
482 bitmap_check_sizes (b, c);
483
484 unsigned int i, n = dst->size;
485 sbitmap_ptr dstp = dst->elms;
486 const_sbitmap_ptr ap = a->elms;
487 const_sbitmap_ptr bp = b->elms;
488 const_sbitmap_ptr cp = c->elms;
489 SBITMAP_ELT_TYPE changed = 0;
490
491 for (i = 0; i < n; i++)
492 {
493 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
494 changed |= *dstp ^ tmp;
495 *dstp++ = tmp;
496 }
497
498 return changed != 0;
499 }
500
501 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
502
503 void
bitmap_not(sbitmap dst,const_sbitmap src)504 bitmap_not (sbitmap dst, const_sbitmap src)
505 {
506 bitmap_check_sizes (src, dst);
507
508 unsigned int i, n = dst->size;
509 sbitmap_ptr dstp = dst->elms;
510 const_sbitmap_ptr srcp = src->elms;
511 unsigned int last_bit;
512
513 for (i = 0; i < n; i++)
514 *dstp++ = ~*srcp++;
515
516 /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */
517 last_bit = src->n_bits % SBITMAP_ELT_BITS;
518 if (last_bit)
519 dst->elms[n-1] = dst->elms[n-1]
520 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
521 }
522
523 /* Set the bits in DST to be the difference between the bits
524 in A and the bits in B. i.e. dst = a & (~b). */
525
526 void
bitmap_and_compl(sbitmap dst,const_sbitmap a,const_sbitmap b)527 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
528 {
529 bitmap_check_sizes (a, b);
530 bitmap_check_sizes (b, dst);
531
532 unsigned int i, dst_size = dst->size;
533 unsigned int min_size = dst->size;
534 sbitmap_ptr dstp = dst->elms;
535 const_sbitmap_ptr ap = a->elms;
536 const_sbitmap_ptr bp = b->elms;
537
538 /* A should be at least as large as DEST, to have a defined source. */
539 gcc_assert (a->size >= dst_size);
540 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
541 only copy the subtrahend into dest. */
542 if (b->size < min_size)
543 min_size = b->size;
544 for (i = 0; i < min_size; i++)
545 *dstp++ = *ap++ & (~*bp++);
546 /* Now fill the rest of dest from A, if B was too short.
547 This makes sense only when destination and A differ. */
548 if (dst != a && i != dst_size)
549 for (; i < dst_size; i++)
550 *dstp++ = *ap++;
551 }
552
553 /* Return true if there are any bits set in A are also set in B.
554 Return false otherwise. */
555
556 bool
bitmap_intersect_p(const_sbitmap a,const_sbitmap b)557 bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
558 {
559 bitmap_check_sizes (a, b);
560
561 const_sbitmap_ptr ap = a->elms;
562 const_sbitmap_ptr bp = b->elms;
563 unsigned int i, n;
564
565 n = MIN (a->size, b->size);
566 for (i = 0; i < n; i++)
567 if ((*ap++ & *bp++) != 0)
568 return true;
569
570 return false;
571 }
572
573 /* Set DST to be (A and B).
574 Return nonzero if any change is made. */
575
576 bool
bitmap_and(sbitmap dst,const_sbitmap a,const_sbitmap b)577 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
578 {
579 bitmap_check_sizes (a, b);
580 bitmap_check_sizes (b, dst);
581
582 unsigned int i, n = dst->size;
583 sbitmap_ptr dstp = dst->elms;
584 const_sbitmap_ptr ap = a->elms;
585 const_sbitmap_ptr bp = b->elms;
586 SBITMAP_ELT_TYPE changed = 0;
587
588 for (i = 0; i < n; i++)
589 {
590 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
591 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
592 *dstp++ = tmp;
593 changed |= wordchanged;
594 }
595 return changed != 0;
596 }
597
598 /* Set DST to be (A xor B)).
599 Return nonzero if any change is made. */
600
601 bool
bitmap_xor(sbitmap dst,const_sbitmap a,const_sbitmap b)602 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
603 {
604 bitmap_check_sizes (a, b);
605 bitmap_check_sizes (b, dst);
606
607 unsigned int i, n = dst->size;
608 sbitmap_ptr dstp = dst->elms;
609 const_sbitmap_ptr ap = a->elms;
610 const_sbitmap_ptr bp = b->elms;
611 SBITMAP_ELT_TYPE changed = 0;
612
613 for (i = 0; i < n; i++)
614 {
615 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
616 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
617 *dstp++ = tmp;
618 changed |= wordchanged;
619 }
620 return changed != 0;
621 }
622
623 /* Set DST to be (A or B)).
624 Return nonzero if any change is made. */
625
626 bool
bitmap_ior(sbitmap dst,const_sbitmap a,const_sbitmap b)627 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
628 {
629 bitmap_check_sizes (a, b);
630 bitmap_check_sizes (b, dst);
631
632 unsigned int i, n = dst->size;
633 sbitmap_ptr dstp = dst->elms;
634 const_sbitmap_ptr ap = a->elms;
635 const_sbitmap_ptr bp = b->elms;
636 SBITMAP_ELT_TYPE changed = 0;
637
638 for (i = 0; i < n; i++)
639 {
640 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
641 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
642 *dstp++ = tmp;
643 changed |= wordchanged;
644 }
645 return changed != 0;
646 }
647
648 /* Return nonzero if A is a subset of B. */
649
650 bool
bitmap_subset_p(const_sbitmap a,const_sbitmap b)651 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
652 {
653 bitmap_check_sizes (a, b);
654
655 unsigned int i, n = a->size;
656 const_sbitmap_ptr ap, bp;
657
658 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
659 if ((*ap | *bp) != *bp)
660 return false;
661
662 return true;
663 }
664
665 /* Set DST to be (A or (B and C)).
666 Return nonzero if any change is made. */
667
668 bool
bitmap_or_and(sbitmap dst,const_sbitmap a,const_sbitmap b,const_sbitmap c)669 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
670 {
671 bitmap_check_sizes (a, b);
672 bitmap_check_sizes (b, c);
673 bitmap_check_sizes (c, dst);
674
675 unsigned int i, n = dst->size;
676 sbitmap_ptr dstp = dst->elms;
677 const_sbitmap_ptr ap = a->elms;
678 const_sbitmap_ptr bp = b->elms;
679 const_sbitmap_ptr cp = c->elms;
680 SBITMAP_ELT_TYPE changed = 0;
681
682 for (i = 0; i < n; i++)
683 {
684 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
685 changed |= *dstp ^ tmp;
686 *dstp++ = tmp;
687 }
688
689 return changed != 0;
690 }
691
692 /* Set DST to be (A and (B or C)).
693 Return nonzero if any change is made. */
694
695 bool
bitmap_and_or(sbitmap dst,const_sbitmap a,const_sbitmap b,const_sbitmap c)696 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
697 {
698 bitmap_check_sizes (a, b);
699 bitmap_check_sizes (b, c);
700 bitmap_check_sizes (c, dst);
701
702 unsigned int i, n = dst->size;
703 sbitmap_ptr dstp = dst->elms;
704 const_sbitmap_ptr ap = a->elms;
705 const_sbitmap_ptr bp = b->elms;
706 const_sbitmap_ptr cp = c->elms;
707 SBITMAP_ELT_TYPE changed = 0;
708
709 for (i = 0; i < n; i++)
710 {
711 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
712 changed |= *dstp ^ tmp;
713 *dstp++ = tmp;
714 }
715
716 return changed != 0;
717 }
718
719 /* Return number of first bit set in the bitmap, -1 if none. */
720
721 int
bitmap_first_set_bit(const_sbitmap bmap)722 bitmap_first_set_bit (const_sbitmap bmap)
723 {
724 unsigned int n = 0;
725 sbitmap_iterator sbi;
726
727 EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
728 return n;
729 return -1;
730 }
731
732 /* Return number of last bit set in the bitmap, -1 if none. */
733
734 int
bitmap_last_set_bit(const_sbitmap bmap)735 bitmap_last_set_bit (const_sbitmap bmap)
736 {
737 int i;
738 const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
739
740 for (i = bmap->size - 1; i >= 0; i--)
741 {
742 const SBITMAP_ELT_TYPE word = ptr[i];
743
744 if (word != 0)
745 {
746 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
747 SBITMAP_ELT_TYPE mask
748 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
749
750 while (1)
751 {
752 if ((word & mask) != 0)
753 return index;
754
755 mask >>= 1;
756 index--;
757 }
758 }
759 }
760
761 return -1;
762 }
763
764 void
dump_bitmap(FILE * file,const_sbitmap bmap)765 dump_bitmap (FILE *file, const_sbitmap bmap)
766 {
767 unsigned int i, n, j;
768 unsigned int set_size = bmap->size;
769 unsigned int total_bits = bmap->n_bits;
770
771 fprintf (file, " ");
772 for (i = n = 0; i < set_size && n < total_bits; i++)
773 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
774 {
775 if (n != 0 && n % 10 == 0)
776 fprintf (file, " ");
777
778 fprintf (file, "%d",
779 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
780 }
781
782 fprintf (file, "\n");
783 }
784
785 DEBUG_FUNCTION void
debug_raw(simple_bitmap_def & ref)786 debug_raw (simple_bitmap_def &ref)
787 {
788 dump_bitmap (stderr, &ref);
789 }
790
791 DEBUG_FUNCTION void
debug_raw(simple_bitmap_def * ptr)792 debug_raw (simple_bitmap_def *ptr)
793 {
794 if (ptr)
795 debug_raw (*ptr);
796 else
797 fprintf (stderr, "<nil>\n");
798 }
799
800 void
dump_bitmap_file(FILE * file,const_sbitmap bmap)801 dump_bitmap_file (FILE *file, const_sbitmap bmap)
802 {
803 unsigned int i, pos;
804
805 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
806
807 for (pos = 30, i = 0; i < bmap->n_bits; i++)
808 if (bitmap_bit_p (bmap, i))
809 {
810 if (pos > 70)
811 {
812 fprintf (file, "\n ");
813 pos = 0;
814 }
815
816 fprintf (file, "%d ", i);
817 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
818 }
819
820 fprintf (file, "}\n");
821 }
822
823 DEBUG_FUNCTION void
debug_bitmap(const_sbitmap bmap)824 debug_bitmap (const_sbitmap bmap)
825 {
826 dump_bitmap_file (stderr, bmap);
827 }
828
829 DEBUG_FUNCTION void
debug(simple_bitmap_def & ref)830 debug (simple_bitmap_def &ref)
831 {
832 dump_bitmap_file (stderr, &ref);
833 }
834
835 DEBUG_FUNCTION void
debug(simple_bitmap_def * ptr)836 debug (simple_bitmap_def *ptr)
837 {
838 if (ptr)
839 debug (*ptr);
840 else
841 fprintf (stderr, "<nil>\n");
842 }
843
844 void
dump_bitmap_vector(FILE * file,const char * title,const char * subtitle,sbitmap * bmaps,int n_maps)845 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
846 sbitmap *bmaps, int n_maps)
847 {
848 int i;
849
850 fprintf (file, "%s\n", title);
851 for (i = 0; i < n_maps; i++)
852 {
853 fprintf (file, "%s %d\n", subtitle, i);
854 dump_bitmap (file, bmaps[i]);
855 }
856
857 fprintf (file, "\n");
858 }
859
860 #if CHECKING_P
861
862 namespace selftest {
863
864 /* Selftests for sbitmaps. */
865
866 /* Checking function that uses both bitmap_bit_in_range_p and
867 loop of bitmap_bit_p and verifies consistent results. */
868
869 static bool
bitmap_bit_in_range_p_checking(sbitmap s,unsigned int start,unsigned end)870 bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start,
871 unsigned end)
872 {
873 bool r1 = bitmap_bit_in_range_p (s, start, end);
874 bool r2 = false;
875
876 for (unsigned int i = start; i <= end; i++)
877 if (bitmap_bit_p (s, i))
878 {
879 r2 = true;
880 break;
881 }
882
883 ASSERT_EQ (r1, r2);
884 return r1;
885 }
886
887 /* Verify bitmap_set_range functions for sbitmap. */
888
889 static void
test_set_range()890 test_set_range ()
891 {
892 sbitmap s = sbitmap_alloc (16);
893 bitmap_clear (s);
894
895 bitmap_set_range (s, 0, 1);
896 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 0, 0));
897 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 15));
898 bitmap_set_range (s, 15, 1);
899 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 14));
900 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 15, 15));
901 sbitmap_free (s);
902
903 s = sbitmap_alloc (1024);
904 bitmap_clear (s);
905 bitmap_set_range (s, 512, 1);
906 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
907 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 513, 1023));
908 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
909 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 512));
910 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 513));
911 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 508, 511));
912
913 bitmap_clear (s);
914 bitmap_set_range (s, 512, 64);
915 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
916 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 512 + 64, 1023));
917 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
918 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512 + 63, 512 + 63));
919 sbitmap_free (s);
920 }
921
922 /* Verify bitmap_bit_in_range_p functions for sbitmap. */
923
924 static void
test_bit_in_range()925 test_bit_in_range ()
926 {
927 sbitmap s = sbitmap_alloc (1024);
928 bitmap_clear (s);
929
930 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
931 bitmap_set_bit (s, 100);
932
933 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
934 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99));
935 ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023));
936 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100));
937 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100));
938 ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100));
939 ASSERT_TRUE (bitmap_bit_p (s, 100));
940
941 sbitmap_free (s);
942
943 s = sbitmap_alloc (64);
944 bitmap_clear (s);
945 bitmap_set_bit (s, 63);
946 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
947 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63));
948 ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63));
949 ASSERT_TRUE (bitmap_bit_p (s, 63));
950 sbitmap_free (s);
951
952 s = sbitmap_alloc (1024);
953 bitmap_clear (s);
954 bitmap_set_bit (s, 128);
955 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127));
956 ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023));
957
958 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128));
959 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128));
960 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255));
961 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254));
962 ASSERT_TRUE (bitmap_bit_p (s, 128));
963
964 bitmap_clear (s);
965 bitmap_set_bit (s, 8);
966 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8));
967 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12));
968 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
969 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127));
970 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512));
971 ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8));
972 ASSERT_TRUE (bitmap_bit_p (s, 8));
973
974 bitmap_clear (s);
975 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0));
976 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8));
977 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63));
978 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63));
979 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256));
980
981 bitmap_set_bit (s, 0);
982 bitmap_set_bit (s, 16);
983 bitmap_set_bit (s, 32);
984 bitmap_set_bit (s, 48);
985 bitmap_set_bit (s, 64);
986 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0));
987 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16));
988 ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63));
989 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64));
990 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15));
991 ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31));
992 ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63));
993 ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023));
994 sbitmap_free (s);
995 }
996
997 /* Run all of the selftests within this file. */
998
999 void
sbitmap_c_tests()1000 sbitmap_c_tests ()
1001 {
1002 test_set_range ();
1003 test_bit_in_range ();
1004 }
1005
1006 } // namespace selftest
1007 #endif /* CHECKING_P */
1008