[gcc]
[official-gcc.git] / gcc / sbitmap.c
blob10b4347d65b906ffe5ec488f3e9f28f1a345fec0
1 /* Simple bitmaps.
2 Copyright (C) 1999-2016 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "sbitmap.h"
25 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
26 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
28 /* Return the size in bytes of a bitmap MAP. */
30 static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
32 return map->size * sizeof (SBITMAP_ELT_TYPE);
36 /* Bitmap manipulation routines. */
38 /* Allocate a simple bitmap of N_ELMS bits. */
40 sbitmap
41 sbitmap_alloc (unsigned int n_elms)
43 unsigned int bytes, size, amt;
44 sbitmap bmap;
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;
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. */
60 sbitmap
61 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
63 unsigned int bytes, size, amt;
64 unsigned int last_bit;
66 size = SBITMAP_SET_SIZE (n_elms);
67 bytes = size * sizeof (SBITMAP_ELT_TYPE);
68 if (bytes > sbitmap_size_bytes (bmap))
70 amt = (sizeof (struct simple_bitmap_def)
71 + bytes - sizeof (SBITMAP_ELT_TYPE));
72 bmap = (sbitmap) xrealloc (bmap, amt);
75 if (n_elms > bmap->n_bits)
77 if (def)
79 memset (bmap->elms + bmap->size, -1,
80 bytes - sbitmap_size_bytes (bmap));
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));
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);
94 else
95 memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
97 else if (n_elms < bmap->n_bits)
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);
106 bmap->n_bits = n_elms;
107 bmap->size = size;
108 return bmap;
111 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
113 sbitmap
114 sbitmap_realloc (sbitmap src, unsigned int n_elms)
116 unsigned int bytes, size, amt;
117 sbitmap bmap;
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));
124 if (sbitmap_size_bytes (src) >= bytes)
126 src->n_bits = n_elms;
127 return src;
130 bmap = (sbitmap) xrealloc (src, amt);
131 bmap->n_bits = n_elms;
132 bmap->size = size;
133 return bmap;
136 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
138 sbitmap *
139 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
141 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
142 sbitmap *bitmap_vector;
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 *);
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. */
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);
162 amt = vector_bytes + (n_vecs * elm_bytes);
163 bitmap_vector = (sbitmap *) xmalloc (amt);
165 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
167 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
169 bitmap_vector[i] = b;
170 b->n_bits = n_elms;
171 b->size = size;
174 return bitmap_vector;
177 /* Copy sbitmap SRC to DST. */
179 void
180 bitmap_copy (sbitmap dst, const_sbitmap src)
182 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
185 /* Determine if a == b. */
187 bitmap_equal_p (const_sbitmap a, const_sbitmap b)
189 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
192 /* Return true if the bitmap is empty. */
194 bool
195 bitmap_empty_p (const_sbitmap bmap)
197 unsigned int i;
198 for (i=0; i<bmap->size; i++)
199 if (bmap->elms[i])
200 return false;
202 return true;
206 /* Zero all elements in a bitmap. */
208 void
209 bitmap_clear (sbitmap bmap)
211 memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
214 /* Set all elements in a bitmap to ones. */
216 void
217 bitmap_ones (sbitmap bmap)
219 unsigned int last_bit;
221 memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
223 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
224 if (last_bit)
225 bmap->elms[bmap->size - 1]
226 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
229 /* Zero a vector of N_VECS bitmaps. */
231 void
232 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
234 unsigned int i;
236 for (i = 0; i < n_vecs; i++)
237 bitmap_clear (bmap[i]);
240 /* Set a vector of N_VECS bitmaps to ones. */
242 void
243 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
245 unsigned int i;
247 for (i = 0; i < n_vecs; i++)
248 bitmap_ones (bmap[i]);
251 /* Set DST to be A union (B - C).
252 DST = A | (B & ~C).
253 Returns true if any change is made. */
255 bool
256 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
258 unsigned int i, n = dst->size;
259 sbitmap_ptr dstp = dst->elms;
260 const_sbitmap_ptr ap = a->elms;
261 const_sbitmap_ptr bp = b->elms;
262 const_sbitmap_ptr cp = c->elms;
263 SBITMAP_ELT_TYPE changed = 0;
265 for (i = 0; i < n; i++)
267 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
268 changed |= *dstp ^ tmp;
269 *dstp++ = tmp;
272 return changed != 0;
275 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
277 void
278 bitmap_not (sbitmap dst, const_sbitmap src)
280 unsigned int i, n = dst->size;
281 sbitmap_ptr dstp = dst->elms;
282 const_sbitmap_ptr srcp = src->elms;
283 unsigned int last_bit;
285 for (i = 0; i < n; i++)
286 *dstp++ = ~*srcp++;
288 /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */
289 last_bit = src->n_bits % SBITMAP_ELT_BITS;
290 if (last_bit)
291 dst->elms[n-1] = dst->elms[n-1]
292 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
295 /* Set the bits in DST to be the difference between the bits
296 in A and the bits in B. i.e. dst = a & (~b). */
298 void
299 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
301 unsigned int i, dst_size = dst->size;
302 unsigned int min_size = dst->size;
303 sbitmap_ptr dstp = dst->elms;
304 const_sbitmap_ptr ap = a->elms;
305 const_sbitmap_ptr bp = b->elms;
307 /* A should be at least as large as DEST, to have a defined source. */
308 gcc_assert (a->size >= dst_size);
309 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
310 only copy the subtrahend into dest. */
311 if (b->size < min_size)
312 min_size = b->size;
313 for (i = 0; i < min_size; i++)
314 *dstp++ = *ap++ & (~*bp++);
315 /* Now fill the rest of dest from A, if B was too short.
316 This makes sense only when destination and A differ. */
317 if (dst != a && i != dst_size)
318 for (; i < dst_size; i++)
319 *dstp++ = *ap++;
322 /* Return true if there are any bits set in A are also set in B.
323 Return false otherwise. */
325 bool
326 bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
328 const_sbitmap_ptr ap = a->elms;
329 const_sbitmap_ptr bp = b->elms;
330 unsigned int i, n;
332 n = MIN (a->size, b->size);
333 for (i = 0; i < n; i++)
334 if ((*ap++ & *bp++) != 0)
335 return true;
337 return false;
340 /* Set DST to be (A and B).
341 Return nonzero if any change is made. */
343 bool
344 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
346 unsigned int i, n = dst->size;
347 sbitmap_ptr dstp = dst->elms;
348 const_sbitmap_ptr ap = a->elms;
349 const_sbitmap_ptr bp = b->elms;
350 SBITMAP_ELT_TYPE changed = 0;
352 for (i = 0; i < n; i++)
354 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
355 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
356 *dstp++ = tmp;
357 changed |= wordchanged;
359 return changed != 0;
362 /* Set DST to be (A xor B)).
363 Return nonzero if any change is made. */
365 bool
366 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
368 unsigned int i, n = dst->size;
369 sbitmap_ptr dstp = dst->elms;
370 const_sbitmap_ptr ap = a->elms;
371 const_sbitmap_ptr bp = b->elms;
372 SBITMAP_ELT_TYPE changed = 0;
374 for (i = 0; i < n; i++)
376 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
377 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
378 *dstp++ = tmp;
379 changed |= wordchanged;
381 return changed != 0;
384 /* Set DST to be (A or B)).
385 Return nonzero if any change is made. */
387 bool
388 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
390 unsigned int i, n = dst->size;
391 sbitmap_ptr dstp = dst->elms;
392 const_sbitmap_ptr ap = a->elms;
393 const_sbitmap_ptr bp = b->elms;
394 SBITMAP_ELT_TYPE changed = 0;
396 for (i = 0; i < n; i++)
398 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
399 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
400 *dstp++ = tmp;
401 changed |= wordchanged;
403 return changed != 0;
406 /* Return nonzero if A is a subset of B. */
408 bool
409 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
411 unsigned int i, n = a->size;
412 const_sbitmap_ptr ap, bp;
414 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
415 if ((*ap | *bp) != *bp)
416 return false;
418 return true;
421 /* Set DST to be (A or (B and C)).
422 Return nonzero if any change is made. */
424 bool
425 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
427 unsigned int i, n = dst->size;
428 sbitmap_ptr dstp = dst->elms;
429 const_sbitmap_ptr ap = a->elms;
430 const_sbitmap_ptr bp = b->elms;
431 const_sbitmap_ptr cp = c->elms;
432 SBITMAP_ELT_TYPE changed = 0;
434 for (i = 0; i < n; i++)
436 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
437 changed |= *dstp ^ tmp;
438 *dstp++ = tmp;
441 return changed != 0;
444 /* Set DST to be (A and (B or C)).
445 Return nonzero if any change is made. */
447 bool
448 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
450 unsigned int i, n = dst->size;
451 sbitmap_ptr dstp = dst->elms;
452 const_sbitmap_ptr ap = a->elms;
453 const_sbitmap_ptr bp = b->elms;
454 const_sbitmap_ptr cp = c->elms;
455 SBITMAP_ELT_TYPE changed = 0;
457 for (i = 0; i < n; i++)
459 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
460 changed |= *dstp ^ tmp;
461 *dstp++ = tmp;
464 return changed != 0;
467 /* Return number of first bit set in the bitmap, -1 if none. */
470 bitmap_first_set_bit (const_sbitmap bmap)
472 unsigned int n = 0;
473 sbitmap_iterator sbi;
475 EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
476 return n;
477 return -1;
480 /* Return number of last bit set in the bitmap, -1 if none. */
483 bitmap_last_set_bit (const_sbitmap bmap)
485 int i;
486 const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
488 for (i = bmap->size - 1; i >= 0; i--)
490 const SBITMAP_ELT_TYPE word = ptr[i];
492 if (word != 0)
494 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
495 SBITMAP_ELT_TYPE mask
496 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
498 while (1)
500 if ((word & mask) != 0)
501 return index;
503 mask >>= 1;
504 index--;
509 return -1;
512 void
513 dump_bitmap (FILE *file, const_sbitmap bmap)
515 unsigned int i, n, j;
516 unsigned int set_size = bmap->size;
517 unsigned int total_bits = bmap->n_bits;
519 fprintf (file, " ");
520 for (i = n = 0; i < set_size && n < total_bits; i++)
521 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
523 if (n != 0 && n % 10 == 0)
524 fprintf (file, " ");
526 fprintf (file, "%d",
527 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
530 fprintf (file, "\n");
533 DEBUG_FUNCTION void
534 debug_raw (simple_bitmap_def &ref)
536 dump_bitmap (stderr, &ref);
539 DEBUG_FUNCTION void
540 debug_raw (simple_bitmap_def *ptr)
542 if (ptr)
543 debug_raw (*ptr);
544 else
545 fprintf (stderr, "<nil>\n");
548 void
549 dump_bitmap_file (FILE *file, const_sbitmap bmap)
551 unsigned int i, pos;
553 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
555 for (pos = 30, i = 0; i < bmap->n_bits; i++)
556 if (bitmap_bit_p (bmap, i))
558 if (pos > 70)
560 fprintf (file, "\n ");
561 pos = 0;
564 fprintf (file, "%d ", i);
565 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
568 fprintf (file, "}\n");
571 DEBUG_FUNCTION void
572 debug_bitmap (const_sbitmap bmap)
574 dump_bitmap_file (stderr, bmap);
577 DEBUG_FUNCTION void
578 debug (simple_bitmap_def &ref)
580 dump_bitmap_file (stderr, &ref);
583 DEBUG_FUNCTION void
584 debug (simple_bitmap_def *ptr)
586 if (ptr)
587 debug (*ptr);
588 else
589 fprintf (stderr, "<nil>\n");
592 void
593 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
594 sbitmap *bmaps, int n_maps)
596 int i;
598 fprintf (file, "%s\n", title);
599 for (i = 0; i < n_maps; i++)
601 fprintf (file, "%s %d\n", subtitle, i);
602 dump_bitmap (file, bmaps[i]);
605 fprintf (file, "\n");