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 1410481215 : static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
32 : {
33 1410481215 : 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 1015759799 : sbitmap_alloc (unsigned int n_elms)
43 : {
44 1015759799 : unsigned int bytes, size, amt;
45 1015759799 : sbitmap bmap;
46 :
47 1015759799 : size = SBITMAP_SET_SIZE (n_elms);
48 1015759799 : bytes = size * sizeof (SBITMAP_ELT_TYPE);
49 1015759799 : amt = (sizeof (struct simple_bitmap_def)
50 : + bytes - sizeof (SBITMAP_ELT_TYPE));
51 1015759799 : bmap = (sbitmap) xmalloc (amt);
52 1015759799 : bmap->n_bits = n_elms;
53 1015759799 : bmap->size = size;
54 1015759799 : 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 1652641 : sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
63 : {
64 1652641 : unsigned int bytes, size, amt;
65 1652641 : unsigned int last_bit;
66 :
67 1652641 : size = SBITMAP_SET_SIZE (n_elms);
68 1652641 : bytes = size * sizeof (SBITMAP_ELT_TYPE);
69 1652641 : if (bytes > sbitmap_size_bytes (bmap))
70 : {
71 365879 : amt = (sizeof (struct simple_bitmap_def)
72 : + bytes - sizeof (SBITMAP_ELT_TYPE));
73 365879 : bmap = (sbitmap) xrealloc (bmap, amt);
74 : }
75 :
76 1652641 : if (n_elms > bmap->n_bits)
77 : {
78 1652641 : 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 1652641 : 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 1652641 : bmap->n_bits = n_elms;
108 1652641 : bmap->size = size;
109 1652641 : 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 12454435 : sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
141 : {
142 12454435 : unsigned int i, size;
143 12454435 : size_t amt, bytes, vector_bytes, elm_bytes, offset;
144 12454435 : sbitmap *bitmap_vector;
145 :
146 12454435 : size = SBITMAP_SET_SIZE (n_elms);
147 12454435 : bytes = size * sizeof (SBITMAP_ELT_TYPE);
148 12454435 : elm_bytes = (sizeof (struct simple_bitmap_def)
149 : + bytes - sizeof (SBITMAP_ELT_TYPE));
150 12454435 : 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 12454435 : {
158 : /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
159 12454435 : struct { char x; SBITMAP_ELT_TYPE y; } align;
160 12454435 : int alignment = (char *) & align.y - & align.x;
161 12454435 : vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
162 : }
163 :
164 12454435 : amt = vector_bytes + (n_vecs * elm_bytes);
165 12454435 : bitmap_vector = (sbitmap *) xmalloc (amt);
166 :
167 328386142 : for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
168 : {
169 315931707 : sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
170 :
171 315931707 : bitmap_vector[i] = b;
172 315931707 : b->n_bits = n_elms;
173 315931707 : b->size = size;
174 : }
175 :
176 12454435 : return bitmap_vector;
177 : }
178 :
179 : /* Copy sbitmap SRC to DST. */
180 :
181 : void
182 122935043 : bitmap_copy (sbitmap dst, const_sbitmap src)
183 : {
184 122935043 : gcc_checking_assert (src->size <= dst->size);
185 :
186 122935043 : memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
187 122935043 : }
188 :
189 : /* Determine if a == b. */
190 : bool
191 20851279 : bitmap_equal_p (const_sbitmap a, const_sbitmap b)
192 : {
193 20851279 : bitmap_check_sizes (a, b);
194 :
195 20851279 : 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 243264781 : bitmap_empty_p (const_sbitmap bmap)
202 : {
203 243264781 : unsigned int i;
204 334588329 : for (i=0; i<bmap->size; i++)
205 292463990 : 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 2610490 : bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
215 : {
216 2610490 : if (count == 0)
217 : return;
218 :
219 1037166 : bitmap_check_index (bmap, start + count - 1);
220 :
221 1037166 : unsigned int start_word = start / SBITMAP_ELT_BITS;
222 1037166 : unsigned int start_bitno = start % SBITMAP_ELT_BITS;
223 :
224 : /* Clearing less than a full word, starting at the beginning of a word. */
225 1037166 : if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
226 : {
227 236703 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
228 236703 : bmap->elms[start_word] &= ~mask;
229 236703 : return;
230 : }
231 :
232 800463 : unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
233 800463 : 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 800463 : if (start_bitno != 0)
239 : {
240 799906 : unsigned int nbits = ((start_word == end_word)
241 799906 : ? end_bitno - start_bitno
242 : : SBITMAP_ELT_BITS - start_bitno);
243 799906 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
244 799906 : mask <<= start_bitno;
245 799906 : bmap->elms[start_word] &= ~mask;
246 799906 : start_word++;
247 799906 : count -= nbits;
248 : }
249 :
250 800463 : if (count == 0)
251 : return;
252 :
253 : /* Now clear words at a time until we hit a partial word. */
254 2455 : unsigned int nwords = (end_word - start_word);
255 2455 : if (nwords)
256 : {
257 653 : memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
258 653 : count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
259 653 : start_word += nwords;
260 : }
261 :
262 2455 : if (count == 0)
263 : return;
264 :
265 : /* Now handle residuals in the last word. */
266 2089 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
267 2089 : bmap->elms[start_word] &= ~mask;
268 : }
269 :
270 : /* Set COUNT bits from START in BMAP. */
271 : void
272 30712435 : bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
273 : {
274 30712435 : if (count == 0)
275 : return;
276 :
277 30712435 : bitmap_check_index (bmap, start + count - 1);
278 :
279 30712435 : unsigned int start_word = start / SBITMAP_ELT_BITS;
280 30712435 : unsigned int start_bitno = start % SBITMAP_ELT_BITS;
281 :
282 : /* Setting less than a full word, starting at the beginning of a word. */
283 30712435 : if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
284 : {
285 30183401 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
286 30183401 : bmap->elms[start_word] |= mask;
287 30183401 : return;
288 : }
289 :
290 529034 : unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
291 529034 : 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 529034 : if (start_bitno != 0)
297 : {
298 61 : unsigned int nbits = ((start_word == end_word)
299 61 : ? end_bitno - start_bitno
300 : : SBITMAP_ELT_BITS - start_bitno);
301 61 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
302 61 : mask <<= start_bitno;
303 61 : bmap->elms[start_word] |= mask;
304 61 : start_word++;
305 61 : count -= nbits;
306 : }
307 :
308 529034 : if (count == 0)
309 : return;
310 :
311 : /* Now set words at a time until we hit a partial word. */
312 528973 : unsigned int nwords = (end_word - start_word);
313 528973 : if (nwords)
314 : {
315 528973 : memset (&bmap->elms[start_word], 0xff,
316 528973 : nwords * sizeof (SBITMAP_ELT_TYPE));
317 528973 : count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
318 528973 : start_word += nwords;
319 : }
320 :
321 528973 : if (count == 0)
322 : return;
323 :
324 : /* Now handle residuals in the last word. */
325 302872 : SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
326 302872 : 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 980382 : bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start,
335 : unsigned int end, bool any_inverted)
336 : {
337 980382 : gcc_checking_assert (start <= end);
338 980382 : bitmap_check_index (bmap, end);
339 :
340 980382 : unsigned int start_word = start / SBITMAP_ELT_BITS;
341 980382 : unsigned int start_bitno = start % SBITMAP_ELT_BITS;
342 :
343 980382 : unsigned int end_word = end / SBITMAP_ELT_BITS;
344 980382 : unsigned int end_bitno = end % SBITMAP_ELT_BITS;
345 :
346 : /* Check beginning of first word if different from zero. */
347 980382 : if (start_bitno != 0)
348 : {
349 709869 : SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0;
350 709869 : if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS)
351 700693 : high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
352 :
353 709869 : SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1;
354 709869 : SBITMAP_ELT_TYPE mask = high_mask - low_mask;
355 709869 : const SBITMAP_ELT_TYPE expected_partial = any_inverted ? mask : 0;
356 709869 : if ((bmap->elms[start_word] & mask) != expected_partial)
357 : return true;
358 1092 : start_word++;
359 : }
360 :
361 271605 : if (start_word > end_word)
362 : return false;
363 :
364 : /* Now test words at a time until we hit a partial word. */
365 270548 : unsigned int nwords = (end_word - start_word);
366 270548 : const SBITMAP_ELT_TYPE expected = any_inverted ? ~(SBITMAP_ELT_TYPE)0 : 0;
367 270896 : while (nwords)
368 : {
369 9098 : 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 261798 : SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0;
377 261798 : if (end_bitno + 1 < SBITMAP_ELT_BITS)
378 254993 : mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
379 261798 : const SBITMAP_ELT_TYPE expected_partial = any_inverted ? mask : 0;
380 261798 : 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 980382 : bitmap_any_bit_in_range_p (const_sbitmap bmap, unsigned int start,
398 : unsigned int end)
399 : {
400 980382 : 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 588 : bitmap_count_bits (const_sbitmap bmap)
434 : {
435 588 : unsigned int count = 0;
436 1178 : for (unsigned int i = 0; i < bmap->size; i++)
437 590 : 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 590 : 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 588 : return count;
452 : }
453 :
454 : /* Zero all elements in a bitmap. */
455 :
456 : void
457 1308667370 : bitmap_clear (sbitmap bmap)
458 : {
459 1308667370 : memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
460 1308667370 : }
461 :
462 : /* Set all elements in a bitmap to ones. */
463 :
464 : void
465 98508563 : bitmap_ones (sbitmap bmap)
466 : {
467 98508563 : unsigned int last_bit;
468 :
469 98508563 : memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
470 :
471 98508563 : last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
472 98508563 : if (last_bit)
473 97822367 : bmap->elms[bmap->size - 1]
474 97822367 : = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
475 98508563 : }
476 :
477 : /* Zero a vector of N_VECS bitmaps. */
478 :
479 : void
480 5642754 : bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
481 : {
482 5642754 : unsigned int i;
483 :
484 150936891 : for (i = 0; i < n_vecs; i++)
485 145294137 : bitmap_clear (bmap[i]);
486 5642754 : }
487 :
488 : /* Set a vector of N_VECS bitmaps to ones. */
489 :
490 : void
491 3398976 : bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
492 : {
493 3398976 : unsigned int i;
494 :
495 88819333 : for (i = 0; i < n_vecs; i++)
496 85420357 : bitmap_ones (bmap[i]);
497 3398976 : }
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 73749550 : bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
505 : {
506 73749550 : bitmap_check_sizes (a, b);
507 73749550 : bitmap_check_sizes (b, c);
508 :
509 73749550 : unsigned int i, n = dst->size;
510 73749550 : sbitmap_ptr dstp = dst->elms;
511 73749550 : const_sbitmap_ptr ap = a->elms;
512 73749550 : const_sbitmap_ptr bp = b->elms;
513 73749550 : const_sbitmap_ptr cp = c->elms;
514 73749550 : SBITMAP_ELT_TYPE changed = 0;
515 :
516 307525627 : for (i = 0; i < n; i++)
517 : {
518 233776077 : const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
519 233776077 : changed |= *dstp ^ tmp;
520 233776077 : *dstp++ = tmp;
521 : }
522 :
523 73749550 : return changed != 0;
524 : }
525 :
526 : /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
527 :
528 : void
529 23235060 : bitmap_not (sbitmap dst, const_sbitmap src)
530 : {
531 23235060 : bitmap_check_sizes (src, dst);
532 :
533 23235060 : unsigned int i, n = dst->size;
534 23235060 : sbitmap_ptr dstp = dst->elms;
535 23235060 : const_sbitmap_ptr srcp = src->elms;
536 23235060 : unsigned int last_bit;
537 :
538 85973123 : for (i = 0; i < n; i++)
539 62738063 : *dstp++ = ~*srcp++;
540 :
541 : /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */
542 23235060 : last_bit = src->n_bits % SBITMAP_ELT_BITS;
543 23235060 : if (last_bit)
544 23042918 : dst->elms[n-1] = dst->elms[n-1]
545 23042918 : & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
546 23235060 : }
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 119729690 : bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
553 : {
554 119729690 : bitmap_check_sizes (a, b);
555 119729690 : bitmap_check_sizes (b, dst);
556 :
557 119729690 : unsigned int i, dst_size = dst->size;
558 119729690 : unsigned int min_size = dst->size;
559 119729690 : sbitmap_ptr dstp = dst->elms;
560 119729690 : const_sbitmap_ptr ap = a->elms;
561 119729690 : const_sbitmap_ptr bp = b->elms;
562 :
563 : /* A should be at least as large as DEST, to have a defined source. */
564 119729690 : 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 119729690 : if (b->size < min_size)
568 : min_size = b->size;
569 384772876 : for (i = 0; i < min_size; i++)
570 265043186 : *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 119729690 : if (dst != a && i != dst_size)
574 0 : for (; i < dst_size; i++)
575 0 : *dstp++ = *ap++;
576 119729690 : }
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 46923515 : bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
603 : {
604 46923515 : bitmap_check_sizes (a, b);
605 46923515 : bitmap_check_sizes (b, dst);
606 :
607 46923515 : unsigned int i, n = dst->size;
608 46923515 : sbitmap_ptr dstp = dst->elms;
609 46923515 : const_sbitmap_ptr ap = a->elms;
610 46923515 : const_sbitmap_ptr bp = b->elms;
611 46923515 : SBITMAP_ELT_TYPE changed = 0;
612 :
613 152041877 : for (i = 0; i < n; i++)
614 : {
615 105118362 : const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
616 105118362 : SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
617 105118362 : *dstp++ = tmp;
618 105118362 : changed |= wordchanged;
619 : }
620 46923515 : 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 36566129 : bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
653 : {
654 36566129 : bitmap_check_sizes (a, b);
655 36566129 : bitmap_check_sizes (b, dst);
656 :
657 36566129 : unsigned int i, n = dst->size;
658 36566129 : sbitmap_ptr dstp = dst->elms;
659 36566129 : const_sbitmap_ptr ap = a->elms;
660 36566129 : const_sbitmap_ptr bp = b->elms;
661 36566129 : SBITMAP_ELT_TYPE changed = 0;
662 :
663 119764171 : for (i = 0; i < n; i++)
664 : {
665 83198042 : const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
666 83198042 : SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
667 83198042 : *dstp++ = tmp;
668 83198042 : changed |= wordchanged;
669 : }
670 36566129 : 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 11405293 : bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
695 : {
696 11405293 : bitmap_check_sizes (a, b);
697 11405293 : bitmap_check_sizes (b, c);
698 11405293 : bitmap_check_sizes (c, dst);
699 :
700 11405293 : unsigned int i, n = dst->size;
701 11405293 : sbitmap_ptr dstp = dst->elms;
702 11405293 : const_sbitmap_ptr ap = a->elms;
703 11405293 : const_sbitmap_ptr bp = b->elms;
704 11405293 : const_sbitmap_ptr cp = c->elms;
705 11405293 : SBITMAP_ELT_TYPE changed = 0;
706 :
707 42750921 : for (i = 0; i < n; i++)
708 : {
709 31345628 : const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
710 31345628 : changed |= *dstp ^ tmp;
711 31345628 : *dstp++ = tmp;
712 : }
713 :
714 11405293 : 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 13670972 : bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
722 : {
723 13670972 : bitmap_check_sizes (a, b);
724 13670972 : bitmap_check_sizes (b, c);
725 13670972 : bitmap_check_sizes (c, dst);
726 :
727 13670972 : unsigned int i, n = dst->size;
728 13670972 : sbitmap_ptr dstp = dst->elms;
729 13670972 : const_sbitmap_ptr ap = a->elms;
730 13670972 : const_sbitmap_ptr bp = b->elms;
731 13670972 : const_sbitmap_ptr cp = c->elms;
732 13670972 : SBITMAP_ELT_TYPE changed = 0;
733 :
734 51335499 : for (i = 0; i < n; i++)
735 : {
736 37664527 : const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
737 37664527 : changed |= *dstp ^ tmp;
738 37664527 : *dstp++ = tmp;
739 : }
740 :
741 13670972 : return changed != 0;
742 : }
743 :
744 : /* Return number of first bit set in the bitmap, -1 if none. */
745 :
746 : int
747 3451614 : bitmap_first_set_bit (const_sbitmap bmap)
748 : {
749 3451614 : unsigned int n = 0;
750 3451614 : sbitmap_iterator sbi;
751 :
752 6903228 : EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
753 3451614 : return n;
754 : return -1;
755 : }
756 :
757 : /* Return number of last bit set in the bitmap, -1 if none. */
758 :
759 : int
760 59609238 : bitmap_last_set_bit (const_sbitmap bmap)
761 : {
762 59609238 : int i;
763 59609238 : const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
764 :
765 90385066 : for (i = bmap->size - 1; i >= 0; i--)
766 : {
767 69880330 : const SBITMAP_ELT_TYPE word = ptr[i];
768 :
769 69880330 : if (word != 0)
770 : {
771 39104502 : unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
772 39104502 : SBITMAP_ELT_TYPE mask
773 : = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
774 :
775 4649353142 : while (1)
776 : {
777 2344228822 : if ((word & mask) != 0)
778 39104502 : return index;
779 :
780 2305124320 : mask >>= 1;
781 2305124320 : 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 */
|
