1 | /* Simple bitmaps. |
2 | Copyright (C) 1999-2023 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 | 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 |
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 |
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 (map: 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 (s: bmap->elms + bmap->size, c: -1, |
81 | n: bytes - sbitmap_size_bytes (map: 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 (s: bmap->elms + bmap->size, c: 0, n: bytes - sbitmap_size_bytes (map: 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 |
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 (map: 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 * |
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 |
182 | bitmap_copy (sbitmap dst, const_sbitmap src) |
183 | { |
184 | gcc_checking_assert (src->size <= dst->size); |
185 | |
186 | memcpy (dest: dst->elms, src: src->elms, n: sizeof (SBITMAP_ELT_TYPE) * dst->size); |
187 | } |
188 | |
189 | /* Determine if a == b. */ |
190 | bool |
191 | bitmap_equal_p (const_sbitmap a, const_sbitmap b) |
192 | { |
193 | bitmap_check_sizes (a, b); |
194 | |
195 | return !memcmp (s1: a->elms, s2: b->elms, n: sizeof (SBITMAP_ELT_TYPE) * a->size); |
196 | } |
197 | |
198 | /* Return true if the bitmap is empty. */ |
199 | |
200 | bool |
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 |
214 | bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count) |
215 | { |
216 | if (count == 0) |
217 | return; |
218 | |
219 | bitmap_check_index (map: bmap, index: 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 (s: &bmap->elms[start_word], c: 0, n: 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 |
272 | bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count) |
273 | { |
274 | if (count == 0) |
275 | return; |
276 | |
277 | bitmap_check_index (map: bmap, index: 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 (s: &bmap->elms[start_word], c: 0xff, |
316 | n: 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 |
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 (map: bmap, index: 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 |
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 |
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 |
432 | bitmap_clear (sbitmap bmap) |
433 | { |
434 | memset (s: bmap->elms, c: 0, n: sbitmap_size_bytes (map: bmap)); |
435 | } |
436 | |
437 | /* Set all elements in a bitmap to ones. */ |
438 | |
439 | void |
440 | bitmap_ones (sbitmap bmap) |
441 | { |
442 | unsigned int last_bit; |
443 | |
444 | memset (s: bmap->elms, c: -1, n: sbitmap_size_bytes (map: 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 |
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: bmap[i]); |
461 | } |
462 | |
463 | /* Set a vector of N_VECS bitmaps to ones. */ |
464 | |
465 | void |
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: 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 |
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 (a: b, 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 |
504 | bitmap_not (sbitmap dst, const_sbitmap src) |
505 | { |
506 | bitmap_check_sizes (a: src, b: 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 |
527 | bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b) |
528 | { |
529 | bitmap_check_sizes (a, b); |
530 | bitmap_check_sizes (a: b, 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 |
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 |
577 | bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b) |
578 | { |
579 | bitmap_check_sizes (a, b); |
580 | bitmap_check_sizes (a: b, 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 |
602 | bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b) |
603 | { |
604 | bitmap_check_sizes (a, b); |
605 | bitmap_check_sizes (a: b, 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 |
627 | bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b) |
628 | { |
629 | bitmap_check_sizes (a, b); |
630 | bitmap_check_sizes (a: b, 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 |
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 |
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 (a: b, b: c); |
673 | bitmap_check_sizes (a: c, b: 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 |
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 (a: b, b: c); |
700 | bitmap_check_sizes (a: c, b: 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 |
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 |
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 |
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 (stream: file, format: " " ); |
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 (stream: file, format: " " ); |
777 | |
778 | fprintf (stream: file, format: "%d" , |
779 | (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); |
780 | } |
781 | |
782 | fprintf (stream: file, format: "\n" ); |
783 | } |
784 | |
785 | DEBUG_FUNCTION void |
786 | debug_raw (simple_bitmap_def &ref) |
787 | { |
788 | dump_bitmap (stderr, bmap: &ref); |
789 | } |
790 | |
791 | DEBUG_FUNCTION void |
792 | debug_raw (simple_bitmap_def *ptr) |
793 | { |
794 | if (ptr) |
795 | debug_raw (ref&: *ptr); |
796 | else |
797 | fprintf (stderr, format: "<nil>\n" ); |
798 | } |
799 | |
800 | void |
801 | dump_bitmap_file (FILE *file, const_sbitmap bmap) |
802 | { |
803 | unsigned int i, pos; |
804 | |
805 | fprintf (stream: file, format: "n_bits = %d, set = {" , bmap->n_bits); |
806 | |
807 | for (pos = 30, i = 0; i < bmap->n_bits; i++) |
808 | if (bitmap_bit_p (map: bmap, bitno: i)) |
809 | { |
810 | if (pos > 70) |
811 | { |
812 | fprintf (stream: file, format: "\n " ); |
813 | pos = 0; |
814 | } |
815 | |
816 | fprintf (stream: file, format: "%d " , i); |
817 | pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000); |
818 | } |
819 | |
820 | fprintf (stream: file, format: "}\n" ); |
821 | } |
822 | |
823 | DEBUG_FUNCTION void |
824 | debug_bitmap (const_sbitmap bmap) |
825 | { |
826 | dump_bitmap_file (stderr, bmap); |
827 | } |
828 | |
829 | DEBUG_FUNCTION void |
830 | debug (simple_bitmap_def &ref) |
831 | { |
832 | dump_bitmap_file (stderr, bmap: &ref); |
833 | } |
834 | |
835 | DEBUG_FUNCTION void |
836 | debug (simple_bitmap_def *ptr) |
837 | { |
838 | if (ptr) |
839 | debug (ref&: *ptr); |
840 | else |
841 | fprintf (stderr, format: "<nil>\n" ); |
842 | } |
843 | |
844 | void |
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 (stream: file, format: "%s\n" , title); |
851 | for (i = 0; i < n_maps; i++) |
852 | { |
853 | fprintf (stream: file, format: "%s %d\n" , subtitle, i); |
854 | dump_bitmap (file, bmap: bmaps[i]); |
855 | } |
856 | |
857 | fprintf (stream: file, format: "\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 |
870 | bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start, |
871 | unsigned end) |
872 | { |
873 | bool r1 = bitmap_bit_in_range_p (bmap: s, start, end); |
874 | bool r2 = false; |
875 | |
876 | for (unsigned int i = start; i <= end; i++) |
877 | if (bitmap_bit_p (map: s, bitno: 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 |
890 | test_set_range () |
891 | { |
892 | sbitmap s = sbitmap_alloc (n_elms: 16); |
893 | bitmap_clear (bmap: s); |
894 | |
895 | bitmap_set_range (bmap: s, start: 0, count: 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 (bmap: s, start: 15, count: 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 (map: s); |
902 | |
903 | s = sbitmap_alloc (n_elms: 1024); |
904 | bitmap_clear (bmap: s); |
905 | bitmap_set_range (bmap: s, start: 512, count: 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 (bmap: s); |
914 | bitmap_set_range (bmap: s, start: 512, count: 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 (map: s); |
920 | } |
921 | |
922 | /* Verify bitmap_bit_in_range_p functions for sbitmap. */ |
923 | |
924 | static void |
925 | test_bit_in_range () |
926 | { |
927 | sbitmap s = sbitmap_alloc (n_elms: 1024); |
928 | bitmap_clear (bmap: s); |
929 | |
930 | ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023)); |
931 | bitmap_set_bit (map: s, bitno: 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 (map: s); |
942 | |
943 | s = sbitmap_alloc (n_elms: 64); |
944 | bitmap_clear (bmap: s); |
945 | bitmap_set_bit (map: s, bitno: 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 (map: s); |
951 | |
952 | s = sbitmap_alloc (n_elms: 1024); |
953 | bitmap_clear (bmap: s); |
954 | bitmap_set_bit (map: s, bitno: 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 (bmap: s); |
965 | bitmap_set_bit (map: s, bitno: 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 (bmap: 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 (map: s, bitno: 0); |
982 | bitmap_set_bit (map: s, bitno: 16); |
983 | bitmap_set_bit (map: s, bitno: 32); |
984 | bitmap_set_bit (map: s, bitno: 48); |
985 | bitmap_set_bit (map: s, bitno: 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 (map: s); |
995 | } |
996 | |
997 | /* Run all of the selftests within this file. */ |
998 | |
999 | void |
1000 | sbitmap_cc_tests () |
1001 | { |
1002 | test_set_range (); |
1003 | test_bit_in_range (); |
1004 | } |
1005 | |
1006 | } // namespace selftest |
1007 | #endif /* CHECKING_P */ |
1008 | |