[32/77] Check is_a <scalar_int_mode> before calling valid_pointer_mode
[gcc.git] / gcc / sbitmap.c
1 /* Simple bitmaps.
2 Copyright (C) 1999-2017 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
25 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
26 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
27
28 /* Return the size in bytes of a bitmap MAP. */
29
30 static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
31 {
32 return map->size * sizeof (SBITMAP_ELT_TYPE);
33 }
34
35
36 /* Bitmap manipulation routines. */
37
38 /* Allocate a simple bitmap of N_ELMS bits. */
39
40 sbitmap
41 sbitmap_alloc (unsigned int n_elms)
42 {
43 unsigned int bytes, size, amt;
44 sbitmap bmap;
45
46 size = SBITMAP_SET_SIZE (n_elms);
47 bytes = size * sizeof (SBITMAP_ELT_TYPE);
48 amt = (sizeof (struct simple_bitmap_def)
49 + bytes - sizeof (SBITMAP_ELT_TYPE));
50 bmap = (sbitmap) xmalloc (amt);
51 bmap->n_bits = n_elms;
52 bmap->size = size;
53 return bmap;
54 }
55
56 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
57 size of BMAP, clear the new bits to zero if the DEF argument
58 is zero, and set them to one otherwise. */
59
60 sbitmap
61 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
62 {
63 unsigned int bytes, size, amt;
64 unsigned int last_bit;
65
66 size = SBITMAP_SET_SIZE (n_elms);
67 bytes = size * sizeof (SBITMAP_ELT_TYPE);
68 if (bytes > sbitmap_size_bytes (bmap))
69 {
70 amt = (sizeof (struct simple_bitmap_def)
71 + bytes - sizeof (SBITMAP_ELT_TYPE));
72 bmap = (sbitmap) xrealloc (bmap, amt);
73 }
74
75 if (n_elms > bmap->n_bits)
76 {
77 if (def)
78 {
79 memset (bmap->elms + bmap->size, -1,
80 bytes - sbitmap_size_bytes (bmap));
81
82 /* Set the new bits if the original last element. */
83 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
84 if (last_bit)
85 bmap->elms[bmap->size - 1]
86 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
87
88 /* Clear the unused bit in the new last element. */
89 last_bit = n_elms % SBITMAP_ELT_BITS;
90 if (last_bit)
91 bmap->elms[size - 1]
92 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
93 }
94 else
95 memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
96 }
97 else if (n_elms < bmap->n_bits)
98 {
99 /* Clear the surplus bits in the last word. */
100 last_bit = n_elms % SBITMAP_ELT_BITS;
101 if (last_bit)
102 bmap->elms[size - 1]
103 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
104 }
105
106 bmap->n_bits = n_elms;
107 bmap->size = size;
108 return bmap;
109 }
110
111 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
112
113 sbitmap
114 sbitmap_realloc (sbitmap src, unsigned int n_elms)
115 {
116 unsigned int bytes, size, amt;
117 sbitmap bmap;
118
119 size = SBITMAP_SET_SIZE (n_elms);
120 bytes = size * sizeof (SBITMAP_ELT_TYPE);
121 amt = (sizeof (struct simple_bitmap_def)
122 + bytes - sizeof (SBITMAP_ELT_TYPE));
123
124 if (sbitmap_size_bytes (src) >= bytes)
125 {
126 src->n_bits = n_elms;
127 return src;
128 }
129
130 bmap = (sbitmap) xrealloc (src, amt);
131 bmap->n_bits = n_elms;
132 bmap->size = size;
133 return bmap;
134 }
135
136 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
137
138 sbitmap *
139 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
140 {
141 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
142 sbitmap *bitmap_vector;
143
144 size = SBITMAP_SET_SIZE (n_elms);
145 bytes = size * sizeof (SBITMAP_ELT_TYPE);
146 elm_bytes = (sizeof (struct simple_bitmap_def)
147 + bytes - sizeof (SBITMAP_ELT_TYPE));
148 vector_bytes = n_vecs * sizeof (sbitmap *);
149
150 /* Round up `vector_bytes' to account for the alignment requirements
151 of an sbitmap. One could allocate the vector-table and set of sbitmaps
152 separately, but that requires maintaining two pointers or creating
153 a cover struct to hold both pointers (so our result is still just
154 one pointer). Neither is a bad idea, but this is simpler for now. */
155 {
156 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
157 struct { char x; SBITMAP_ELT_TYPE y; } align;
158 int alignment = (char *) & align.y - & align.x;
159 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
160 }
161
162 amt = vector_bytes + (n_vecs * elm_bytes);
163 bitmap_vector = (sbitmap *) xmalloc (amt);
164
165 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
166 {
167 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
168
169 bitmap_vector[i] = b;
170 b->n_bits = n_elms;
171 b->size = size;
172 }
173
174 return bitmap_vector;
175 }
176
177 /* Copy sbitmap SRC to DST. */
178
179 void
180 bitmap_copy (sbitmap dst, const_sbitmap src)
181 {
182 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
183 }
184
185 /* Determine if a == b. */
186 int
187 bitmap_equal_p (const_sbitmap a, const_sbitmap b)
188 {
189 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
190 }
191
192 /* Return true if the bitmap is empty. */
193
194 bool
195 bitmap_empty_p (const_sbitmap bmap)
196 {
197 unsigned int i;
198 for (i=0; i<bmap->size; i++)
199 if (bmap->elms[i])
200 return false;
201
202 return true;
203 }
204
205 /* Clear COUNT bits from START in BMAP. */
206
207 void
208 bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
209 {
210 if (count == 0)
211 return;
212
213 unsigned int start_word = start / SBITMAP_ELT_BITS;
214 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
215
216 /* Clearing less than a full word, starting at the beginning of a word. */
217 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
218 {
219 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
220 bmap->elms[start_word] &= ~mask;
221 return;
222 }
223
224 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
225 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
226
227 /* Clearing starts somewhere in the middle of the first word. Clear up to
228 the end of the first word or the end of the requested region, whichever
229 comes first. */
230 if (start_bitno != 0)
231 {
232 unsigned int nbits = ((start_word == end_word)
233 ? end_bitno - start_bitno
234 : SBITMAP_ELT_BITS - start_bitno);
235 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
236 mask <<= start_bitno;
237 bmap->elms[start_word] &= ~mask;
238 start_word++;
239 count -= nbits;
240 }
241
242 if (count == 0)
243 return;
244
245 /* Now clear words at a time until we hit a partial word. */
246 unsigned int nwords = (end_word - start_word);
247 if (nwords)
248 {
249 memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
250 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
251 start_word += nwords;
252 }
253
254 if (count == 0)
255 return;
256
257 /* Now handle residuals in the last word. */
258 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
259 bmap->elms[start_word] &= ~mask;
260 }
261
262 /* Set COUNT bits from START in BMAP. */
263 void
264 bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
265 {
266 if (count == 0)
267 return;
268
269 unsigned int start_word = start / SBITMAP_ELT_BITS;
270 unsigned int start_bitno = start % SBITMAP_ELT_BITS;
271
272 /* Setting less than a full word, starting at the beginning of a word. */
273 if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
274 {
275 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
276 bmap->elms[start_word] |= mask;
277 return;
278 }
279
280 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
281 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
282
283 /* Setting starts somewhere in the middle of the first word. Set up to
284 the end of the first word or the end of the requested region, whichever
285 comes first. */
286 if (start_bitno != 0)
287 {
288 unsigned int nbits = ((start_word == end_word)
289 ? end_bitno - start_bitno
290 : SBITMAP_ELT_BITS - start_bitno);
291 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
292 mask <<= start_bitno;
293 bmap->elms[start_word] |= mask;
294 start_word++;
295 count -= nbits;
296 }
297
298 if (count == 0)
299 return;
300
301 /* Now set words at a time until we hit a partial word. */
302 unsigned int nwords = (end_word - start_word);
303 if (nwords)
304 {
305 memset (&bmap->elms[start_word], 0xff,
306 nwords * sizeof (SBITMAP_ELT_TYPE));
307 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
308 start_word += nwords;
309 }
310
311 if (count == 0)
312 return;
313
314 /* Now handle residuals in the last word. */
315 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
316 bmap->elms[start_word] |= mask;
317 }
318
319 #if GCC_VERSION < 3400
320 /* Table of number of set bits in a character, indexed by value of char. */
321 static const unsigned char popcount_table[] =
322 {
323 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,
324 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,
325 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,
326 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,
327 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,
328 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,
329 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,
330 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,
331 };
332
333 static unsigned long
334 sbitmap_popcount (SBITMAP_ELT_TYPE a)
335 {
336 unsigned long ret = 0;
337 unsigned i;
338
339 /* Just do this the table way for now */
340 for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
341 ret += popcount_table[(a >> i) & 0xff];
342 return ret;
343 }
344 #endif
345
346 /* Count and return the number of bits set in the bitmap BMAP. */
347
348 unsigned int
349 bitmap_count_bits (const_sbitmap bmap)
350 {
351 unsigned int count = 0;
352 for (unsigned int i = 0; i < bmap->size; i++)
353 if (bmap->elms[i])
354 {
355 #if GCC_VERSION < 3400
356 count += sbitmap_popcount (bmap->elms[i]);
357 #else
358 # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
359 count += __builtin_popcountl (bmap->elms[i]);
360 # elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
361 count += __builtin_popcountll (bmap->elms[i]);
362 # else
363 count += __builtin_popcount (bmap->elms[i]);
364 # endif
365 #endif
366 }
367 return count;
368 }
369
370 /* Zero all elements in a bitmap. */
371
372 void
373 bitmap_clear (sbitmap bmap)
374 {
375 memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
376 }
377
378 /* Set all elements in a bitmap to ones. */
379
380 void
381 bitmap_ones (sbitmap bmap)
382 {
383 unsigned int last_bit;
384
385 memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
386
387 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
388 if (last_bit)
389 bmap->elms[bmap->size - 1]
390 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
391 }
392
393 /* Zero a vector of N_VECS bitmaps. */
394
395 void
396 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
397 {
398 unsigned int i;
399
400 for (i = 0; i < n_vecs; i++)
401 bitmap_clear (bmap[i]);
402 }
403
404 /* Set a vector of N_VECS bitmaps to ones. */
405
406 void
407 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
408 {
409 unsigned int i;
410
411 for (i = 0; i < n_vecs; i++)
412 bitmap_ones (bmap[i]);
413 }
414
415 /* Set DST to be A union (B - C).
416 DST = A | (B & ~C).
417 Returns true if any change is made. */
418
419 bool
420 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
421 {
422 unsigned int i, n = dst->size;
423 sbitmap_ptr dstp = dst->elms;
424 const_sbitmap_ptr ap = a->elms;
425 const_sbitmap_ptr bp = b->elms;
426 const_sbitmap_ptr cp = c->elms;
427 SBITMAP_ELT_TYPE changed = 0;
428
429 for (i = 0; i < n; i++)
430 {
431 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
432 changed |= *dstp ^ tmp;
433 *dstp++ = tmp;
434 }
435
436 return changed != 0;
437 }
438
439 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
440
441 void
442 bitmap_not (sbitmap dst, const_sbitmap src)
443 {
444 unsigned int i, n = dst->size;
445 sbitmap_ptr dstp = dst->elms;
446 const_sbitmap_ptr srcp = src->elms;
447 unsigned int last_bit;
448
449 for (i = 0; i < n; i++)
450 *dstp++ = ~*srcp++;
451
452 /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */
453 last_bit = src->n_bits % SBITMAP_ELT_BITS;
454 if (last_bit)
455 dst->elms[n-1] = dst->elms[n-1]
456 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
457 }
458
459 /* Set the bits in DST to be the difference between the bits
460 in A and the bits in B. i.e. dst = a & (~b). */
461
462 void
463 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
464 {
465 unsigned int i, dst_size = dst->size;
466 unsigned int min_size = dst->size;
467 sbitmap_ptr dstp = dst->elms;
468 const_sbitmap_ptr ap = a->elms;
469 const_sbitmap_ptr bp = b->elms;
470
471 /* A should be at least as large as DEST, to have a defined source. */
472 gcc_assert (a->size >= dst_size);
473 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
474 only copy the subtrahend into dest. */
475 if (b->size < min_size)
476 min_size = b->size;
477 for (i = 0; i < min_size; i++)
478 *dstp++ = *ap++ & (~*bp++);
479 /* Now fill the rest of dest from A, if B was too short.
480 This makes sense only when destination and A differ. */
481 if (dst != a && i != dst_size)
482 for (; i < dst_size; i++)
483 *dstp++ = *ap++;
484 }
485
486 /* Return true if there are any bits set in A are also set in B.
487 Return false otherwise. */
488
489 bool
490 bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
491 {
492 const_sbitmap_ptr ap = a->elms;
493 const_sbitmap_ptr bp = b->elms;
494 unsigned int i, n;
495
496 n = MIN (a->size, b->size);
497 for (i = 0; i < n; i++)
498 if ((*ap++ & *bp++) != 0)
499 return true;
500
501 return false;
502 }
503
504 /* Set DST to be (A and B).
505 Return nonzero if any change is made. */
506
507 bool
508 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
509 {
510 unsigned int i, n = dst->size;
511 sbitmap_ptr dstp = dst->elms;
512 const_sbitmap_ptr ap = a->elms;
513 const_sbitmap_ptr bp = b->elms;
514 SBITMAP_ELT_TYPE changed = 0;
515
516 for (i = 0; i < n; i++)
517 {
518 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
519 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
520 *dstp++ = tmp;
521 changed |= wordchanged;
522 }
523 return changed != 0;
524 }
525
526 /* Set DST to be (A xor B)).
527 Return nonzero if any change is made. */
528
529 bool
530 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
531 {
532 unsigned int i, n = dst->size;
533 sbitmap_ptr dstp = dst->elms;
534 const_sbitmap_ptr ap = a->elms;
535 const_sbitmap_ptr bp = b->elms;
536 SBITMAP_ELT_TYPE changed = 0;
537
538 for (i = 0; i < n; i++)
539 {
540 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
541 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
542 *dstp++ = tmp;
543 changed |= wordchanged;
544 }
545 return changed != 0;
546 }
547
548 /* Set DST to be (A or B)).
549 Return nonzero if any change is made. */
550
551 bool
552 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
553 {
554 unsigned int i, n = dst->size;
555 sbitmap_ptr dstp = dst->elms;
556 const_sbitmap_ptr ap = a->elms;
557 const_sbitmap_ptr bp = b->elms;
558 SBITMAP_ELT_TYPE changed = 0;
559
560 for (i = 0; i < n; i++)
561 {
562 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
563 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
564 *dstp++ = tmp;
565 changed |= wordchanged;
566 }
567 return changed != 0;
568 }
569
570 /* Return nonzero if A is a subset of B. */
571
572 bool
573 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
574 {
575 unsigned int i, n = a->size;
576 const_sbitmap_ptr ap, bp;
577
578 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
579 if ((*ap | *bp) != *bp)
580 return false;
581
582 return true;
583 }
584
585 /* Set DST to be (A or (B and C)).
586 Return nonzero if any change is made. */
587
588 bool
589 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
590 {
591 unsigned int i, n = dst->size;
592 sbitmap_ptr dstp = dst->elms;
593 const_sbitmap_ptr ap = a->elms;
594 const_sbitmap_ptr bp = b->elms;
595 const_sbitmap_ptr cp = c->elms;
596 SBITMAP_ELT_TYPE changed = 0;
597
598 for (i = 0; i < n; i++)
599 {
600 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
601 changed |= *dstp ^ tmp;
602 *dstp++ = tmp;
603 }
604
605 return changed != 0;
606 }
607
608 /* Set DST to be (A and (B or C)).
609 Return nonzero if any change is made. */
610
611 bool
612 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
613 {
614 unsigned int i, n = dst->size;
615 sbitmap_ptr dstp = dst->elms;
616 const_sbitmap_ptr ap = a->elms;
617 const_sbitmap_ptr bp = b->elms;
618 const_sbitmap_ptr cp = c->elms;
619 SBITMAP_ELT_TYPE changed = 0;
620
621 for (i = 0; i < n; i++)
622 {
623 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
624 changed |= *dstp ^ tmp;
625 *dstp++ = tmp;
626 }
627
628 return changed != 0;
629 }
630
631 /* Return number of first bit set in the bitmap, -1 if none. */
632
633 int
634 bitmap_first_set_bit (const_sbitmap bmap)
635 {
636 unsigned int n = 0;
637 sbitmap_iterator sbi;
638
639 EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
640 return n;
641 return -1;
642 }
643
644 /* Return number of last bit set in the bitmap, -1 if none. */
645
646 int
647 bitmap_last_set_bit (const_sbitmap bmap)
648 {
649 int i;
650 const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
651
652 for (i = bmap->size - 1; i >= 0; i--)
653 {
654 const SBITMAP_ELT_TYPE word = ptr[i];
655
656 if (word != 0)
657 {
658 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
659 SBITMAP_ELT_TYPE mask
660 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
661
662 while (1)
663 {
664 if ((word & mask) != 0)
665 return index;
666
667 mask >>= 1;
668 index--;
669 }
670 }
671 }
672
673 return -1;
674 }
675
676 void
677 dump_bitmap (FILE *file, const_sbitmap bmap)
678 {
679 unsigned int i, n, j;
680 unsigned int set_size = bmap->size;
681 unsigned int total_bits = bmap->n_bits;
682
683 fprintf (file, " ");
684 for (i = n = 0; i < set_size && n < total_bits; i++)
685 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
686 {
687 if (n != 0 && n % 10 == 0)
688 fprintf (file, " ");
689
690 fprintf (file, "%d",
691 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
692 }
693
694 fprintf (file, "\n");
695 }
696
697 DEBUG_FUNCTION void
698 debug_raw (simple_bitmap_def &ref)
699 {
700 dump_bitmap (stderr, &ref);
701 }
702
703 DEBUG_FUNCTION void
704 debug_raw (simple_bitmap_def *ptr)
705 {
706 if (ptr)
707 debug_raw (*ptr);
708 else
709 fprintf (stderr, "<nil>\n");
710 }
711
712 void
713 dump_bitmap_file (FILE *file, const_sbitmap bmap)
714 {
715 unsigned int i, pos;
716
717 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
718
719 for (pos = 30, i = 0; i < bmap->n_bits; i++)
720 if (bitmap_bit_p (bmap, i))
721 {
722 if (pos > 70)
723 {
724 fprintf (file, "\n ");
725 pos = 0;
726 }
727
728 fprintf (file, "%d ", i);
729 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
730 }
731
732 fprintf (file, "}\n");
733 }
734
735 DEBUG_FUNCTION void
736 debug_bitmap (const_sbitmap bmap)
737 {
738 dump_bitmap_file (stderr, bmap);
739 }
740
741 DEBUG_FUNCTION void
742 debug (simple_bitmap_def &ref)
743 {
744 dump_bitmap_file (stderr, &ref);
745 }
746
747 DEBUG_FUNCTION void
748 debug (simple_bitmap_def *ptr)
749 {
750 if (ptr)
751 debug (*ptr);
752 else
753 fprintf (stderr, "<nil>\n");
754 }
755
756 void
757 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
758 sbitmap *bmaps, int n_maps)
759 {
760 int i;
761
762 fprintf (file, "%s\n", title);
763 for (i = 0; i < n_maps; i++)
764 {
765 fprintf (file, "%s %d\n", subtitle, i);
766 dump_bitmap (file, bmaps[i]);
767 }
768
769 fprintf (file, "\n");
770 }