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