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