1 /* Sparse array based bitmaps.
2 Copyright (C) 2007 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 2, or (at your option) any later
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
27 #define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
29 typedef struct ebitmap_def
31 unsigned int n_elts
; /* number of elements in the array. */
32 sbitmap wordmask
; /* wordmask saying which words are
34 unsigned int numwords
; /* number of nonzero words. */
35 unsigned int cacheindex
; /* which word cache is. */
36 EBITMAP_ELT_TYPE
*elts
; /* nonzero element array. */
37 EBITMAP_ELT_TYPE
*cache
; /* last tested element, or NULL. */
41 #define ebitmap_empty_p(MAP) ((MAP)->numwords == 0)
42 #define ebitmap_free(MAP) (free((MAP)->elts), \
43 sbitmap_free ((MAP)->wordmask), \
46 extern void ebitmap_set_bit (ebitmap
, unsigned int);
47 extern void ebitmap_clear_bit (ebitmap
, unsigned int);
48 extern bool ebitmap_bit_p (ebitmap
, unsigned int);
49 extern void dump_ebitmap (FILE *, ebitmap
);
50 extern void dump_ebitmap_file (FILE *, ebitmap
);
51 extern void dump_ebitmap_vector (FILE *, const char *, const char *, ebitmap
*,
53 extern ebitmap
ebitmap_alloc (unsigned int);
54 extern ebitmap
*ebitmap_vector_alloc (unsigned int, unsigned int);
55 extern void ebitmap_copy (ebitmap
, ebitmap
);
56 extern void ebitmap_and (ebitmap
, ebitmap
, ebitmap
);
57 extern void ebitmap_and_into (ebitmap
, ebitmap
);
58 extern bool ebitmap_and_compl (ebitmap
, ebitmap
, ebitmap
);
59 extern bool ebitmap_and_compl_into (ebitmap
, ebitmap
);
60 extern bool ebitmap_ior_into (ebitmap
, ebitmap
);
61 extern bool ebitmap_ior (ebitmap
, ebitmap
, ebitmap
);
62 extern bool ebitmap_ior_and_compl (ebitmap
, ebitmap
, ebitmap
, ebitmap
);
63 extern bool ebitmap_ior_and_compl_into (ebitmap
, ebitmap
, ebitmap
);
64 extern bool ebitmap_equal_p (ebitmap
, ebitmap
);
65 extern void ebitmap_clear (ebitmap
);
66 extern int ebitmap_last_set_bit (ebitmap
);
67 extern void debug_ebitmap (ebitmap
);
68 extern void dump_ebitmap (FILE *, ebitmap
);
69 extern unsigned long ebitmap_popcount(ebitmap
, unsigned long);
71 /* The iterator for ebitmap. */
73 /* The pointer to the first word of the bitmap. */
74 EBITMAP_ELT_TYPE
*ptr
;
76 /* Element number inside ptr that we are at. */
79 /* The size of the bitmap. */
82 /* Current bit index. */
85 /* The words currently visited. */
86 EBITMAP_ELT_TYPE word
;
88 /* The word mask iterator. */
89 sbitmap_iterator maskiter
;
93 ebitmap_iter_init (ebitmap_iterator
*i
, ebitmap bmp
, unsigned int min
)
95 sbitmap_iter_init (&i
->maskiter
, bmp
->wordmask
,
96 min
/ EBITMAP_ELT_BITS
);
97 i
->size
= bmp
->numwords
;
104 if ((min
/ EBITMAP_ELT_BITS
) >= bmp
->wordmask
->n_bits
)
110 if (TEST_BIT (bmp
->wordmask
, min
/ EBITMAP_ELT_BITS
) == 0)
114 unsigned int wordindex
= min
/ EBITMAP_ELT_BITS
;
115 unsigned int count
= sbitmap_popcount (bmp
->wordmask
, wordindex
);
116 i
->word
= i
->ptr
[count
] >> (i
->bit_num
% (unsigned int)EBITMAP_ELT_BITS
);
117 i
->eltnum
= count
+ 1;
123 ebitmap_iter_cond (ebitmap_iterator
*i
, unsigned int *n
)
132 sbitmap_iter_next (&i
->maskiter
);
133 if (!sbitmap_iter_cond (&i
->maskiter
, &ourn
))
135 i
->bit_num
= ourn
* EBITMAP_ELT_BITS
;
136 i
->word
= i
->ptr
[i
->eltnum
++];
139 /* Skip bits that are zero. */
141 for (; (i
->word
& 1) == 0; i
->word
>>= 1)
149 ebitmap_iter_next (ebitmap_iterator
*i
)
155 /* Loop over all elements of EBITMAP, starting with MIN. In each
156 iteration, N is set to the index of the bit being visited. ITER is
157 an instance of ebitmap_iterator used to iterate the bitmap. */
159 #define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER) \
160 for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN)); \
161 ebitmap_iter_cond (&(ITER), &(N)); \
162 ebitmap_iter_next (&(ITER)))
165 #endif /* ! GCC_EBITMAP_H */