1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
/* Sparse array based bitmaps.
Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#ifndef GCC_EBITMAP_H
#define GCC_EBITMAP_H
#include "sbitmap.h"
#define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
#define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
typedef struct ebitmap_def
{
unsigned int n_elts; /* number of elements in the array. */
sbitmap wordmask; /* wordmask saying which words are
nonzero. */
unsigned int numwords; /* number of nonzero words. */
unsigned int cacheindex; /* which word cache is. */
EBITMAP_ELT_TYPE *elts; /* nonzero element array. */
EBITMAP_ELT_TYPE *cache; /* last tested element, or NULL. */
} *ebitmap;
#define ebitmap_empty_p(MAP) ((MAP)->numwords == 0)
#define ebitmap_free(MAP) (free((MAP)->elts), \
sbitmap_free ((MAP)->wordmask), \
free((MAP)))
extern void ebitmap_set_bit (ebitmap, unsigned int);
extern void ebitmap_clear_bit (ebitmap, unsigned int);
extern bool ebitmap_bit_p (ebitmap, unsigned int);
extern void dump_ebitmap (FILE *, ebitmap);
extern void dump_ebitmap_file (FILE *, ebitmap);
extern void dump_ebitmap_vector (FILE *, const char *, const char *, ebitmap *,
int);
extern ebitmap ebitmap_alloc (unsigned int);
extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int);
extern void ebitmap_copy (ebitmap, ebitmap);
extern void ebitmap_and (ebitmap, ebitmap, ebitmap);
extern void ebitmap_and_into (ebitmap, ebitmap);
extern bool ebitmap_and_compl (ebitmap, ebitmap, ebitmap);
extern bool ebitmap_and_compl_into (ebitmap, ebitmap);
extern bool ebitmap_ior_into (ebitmap, ebitmap);
extern bool ebitmap_ior (ebitmap, ebitmap, ebitmap);
extern bool ebitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap);
extern bool ebitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap);
extern bool ebitmap_equal_p (ebitmap, ebitmap);
extern void ebitmap_clear (ebitmap);
extern int ebitmap_last_set_bit (ebitmap);
extern void debug_ebitmap (ebitmap);
extern void dump_ebitmap (FILE *, ebitmap);
extern unsigned long ebitmap_popcount(ebitmap, unsigned long);
/* The iterator for ebitmap. */
typedef struct {
/* The pointer to the first word of the bitmap. */
EBITMAP_ELT_TYPE *ptr;
/* Element number inside ptr that we are at. */
unsigned int eltnum;
/* The size of the bitmap. */
unsigned int size;
/* Current bit index. */
unsigned int bit_num;
/* The words currently visited. */
EBITMAP_ELT_TYPE word;
/* The word mask iterator. */
sbitmap_iterator maskiter;
} ebitmap_iterator;
static inline void
ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min)
{
sbitmap_iter_init (&i->maskiter, bmp->wordmask,
min / EBITMAP_ELT_BITS);
i->size = bmp->numwords;
if (i->size == 0)
{
i->ptr = NULL;
i->eltnum = 0;
i->bit_num = 0;
i->word = 0;
return;
}
i->ptr = bmp->elts;
i->bit_num = min;
i->eltnum = 0;
if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits)
{
i->word = 0;
}
else
{
if (TEST_BIT (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0)
i->word = 0;
else
{
unsigned int wordindex = min / EBITMAP_ELT_BITS;
unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex);
i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS);
i->eltnum = count + 1;
}
}
}
static inline bool
ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n)
{
unsigned int ourn = 0;
if (i->size == 0)
return false;
if (i->word == 0)
{
sbitmap_iter_next (&i->maskiter);
if (!sbitmap_iter_cond (&i->maskiter, &ourn))
return false;
i->bit_num = ourn * EBITMAP_ELT_BITS;
i->word = i->ptr[i->eltnum++];
}
/* Skip bits that are zero. */
for (; (i->word & 1) == 0; i->word >>= 1)
i->bit_num++;
*n = i->bit_num;
return true;
}
static inline void
ebitmap_iter_next (ebitmap_iterator *i)
{
i->word >>= 1;
i->bit_num++;
}
/* Loop over all elements of EBITMAP, starting with MIN. In each
iteration, N is set to the index of the bit being visited. ITER is
an instance of ebitmap_iterator used to iterate the bitmap. */
#define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER) \
for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN)); \
ebitmap_iter_cond (&(ITER), &(N)); \
ebitmap_iter_next (&(ITER)))
#endif /* ! GCC_EBITMAP_H */
|
