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