|
0
|
1 /* SparseSet implementation.
|
|
145
|
2 Copyright (C) 2007-2020 Free Software Foundation, Inc.
|
|
0
|
3 Contributed by Peter Bergner <bergner@vnet.ibm.com>
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify it under
|
|
|
8 the terms of the GNU General Public License as published by the Free
|
|
|
9 Software Foundation; either version 3, or (at your option) any later
|
|
|
10 version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
15 for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "sparseset.h"
|
|
|
24
|
|
|
25 /* Allocate and clear a n_elms SparseSet. */
|
|
|
26
|
|
|
27 sparseset
|
|
|
28 sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
|
|
|
29 {
|
|
|
30 unsigned int n_bytes = sizeof (struct sparseset_def)
|
|
|
31 + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
|
|
|
32
|
|
111
|
33 sparseset set = XNEWVAR (struct sparseset_def, n_bytes);
|
|
|
34
|
|
|
35 /* Mark the sparseset as defined to silence some valgrind uninitialized
|
|
0
|
36 read errors when accessing set->sparse[n] when "n" is not, and never has
|
|
|
37 been, in the set. These uninitialized reads are expected, by design and
|
|
111
|
38 harmless. */
|
|
|
39 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
|
|
|
40
|
|
0
|
41 set->dense = &(set->elms[0]);
|
|
|
42 set->sparse = &(set->elms[n_elms]);
|
|
|
43 set->size = n_elms;
|
|
|
44 sparseset_clear (set);
|
|
|
45 return set;
|
|
|
46 }
|
|
|
47
|
|
|
48 /* Low level routine not meant for use outside of sparseset.[ch].
|
|
|
49 Assumes idx1 < s->members and idx2 < s->members. */
|
|
|
50
|
|
|
51 static inline void
|
|
|
52 sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
|
|
|
53 {
|
|
|
54 SPARSESET_ELT_TYPE tmp = s->dense[idx2];
|
|
|
55 sparseset_insert_bit (s, s->dense[idx1], idx2);
|
|
|
56 sparseset_insert_bit (s, tmp, idx1);
|
|
|
57 }
|
|
|
58
|
|
|
59 /* Operation: S = S - {e}
|
|
|
60 Delete e from the set S if it is a member of S. */
|
|
|
61
|
|
|
62 void
|
|
|
63 sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
|
|
|
64 {
|
|
|
65 if (sparseset_bit_p (s, e))
|
|
|
66 {
|
|
|
67 SPARSESET_ELT_TYPE idx = s->sparse[e];
|
|
|
68 SPARSESET_ELT_TYPE iter = s->iter;
|
|
|
69 SPARSESET_ELT_TYPE mem = s->members - 1;
|
|
|
70
|
|
|
71 /* If we are iterating over this set and we want to delete a
|
|
|
72 member we've already visited, then we swap the element we
|
|
|
73 want to delete with the element at the current iteration
|
|
|
74 index so that it plays well together with the code below
|
|
|
75 that actually removes the element. */
|
|
|
76 if (s->iterating && idx <= iter)
|
|
|
77 {
|
|
|
78 if (idx < iter)
|
|
|
79 {
|
|
|
80 sparseset_swap (s, idx, iter);
|
|
|
81 idx = iter;
|
|
|
82 }
|
|
|
83 s->iter_inc = 0;
|
|
|
84 }
|
|
|
85
|
|
|
86 /* Replace the element we want to delete with the last element
|
|
|
87 in the dense array and then decrement s->members, effectively
|
|
|
88 removing the element we want to delete. */
|
|
|
89 sparseset_insert_bit (s, s->dense[mem], idx);
|
|
|
90 s->members = mem;
|
|
|
91 }
|
|
|
92 }
|
|
|
93
|
|
|
94 /* Operation: D = S
|
|
|
95 Restrictions: none. */
|
|
|
96
|
|
|
97 void
|
|
|
98 sparseset_copy (sparseset d, sparseset s)
|
|
|
99 {
|
|
|
100 SPARSESET_ELT_TYPE i;
|
|
|
101
|
|
|
102 if (d == s)
|
|
|
103 return;
|
|
|
104
|
|
|
105 sparseset_clear (d);
|
|
|
106 for (i = 0; i < s->members; i++)
|
|
|
107 sparseset_insert_bit (d, s->dense[i], i);
|
|
|
108 d->members = s->members;
|
|
|
109 }
|
|
|
110
|
|
|
111 /* Operation: D = A & B.
|
|
|
112 Restrictions: none. */
|
|
|
113
|
|
|
114 void
|
|
|
115 sparseset_and (sparseset d, sparseset a, sparseset b)
|
|
|
116 {
|
|
|
117 SPARSESET_ELT_TYPE e;
|
|
|
118
|
|
|
119 if (a == b)
|
|
|
120 {
|
|
|
121 if (d != a)
|
|
|
122 sparseset_copy (d, a);
|
|
|
123 return;
|
|
|
124 }
|
|
|
125
|
|
|
126 if (d == a || d == b)
|
|
|
127 {
|
|
|
128 sparseset s = (d == a) ? b : a;
|
|
|
129
|
|
|
130 EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
|
|
131 if (!sparseset_bit_p (s, e))
|
|
|
132 sparseset_clear_bit (d, e);
|
|
|
133 }
|
|
|
134 else
|
|
|
135 {
|
|
|
136 sparseset sml, lrg;
|
|
|
137
|
|
|
138 if (sparseset_cardinality (a) < sparseset_cardinality (b))
|
|
|
139 {
|
|
|
140 sml = a;
|
|
|
141 lrg = b;
|
|
|
142 }
|
|
|
143 else
|
|
|
144 {
|
|
|
145 sml = b;
|
|
|
146 lrg = a;
|
|
|
147 }
|
|
|
148
|
|
|
149 sparseset_clear (d);
|
|
|
150 EXECUTE_IF_SET_IN_SPARSESET (sml, e)
|
|
|
151 if (sparseset_bit_p (lrg, e))
|
|
|
152 sparseset_set_bit (d, e);
|
|
|
153 }
|
|
|
154 }
|
|
|
155
|
|
|
156 /* Operation: D = A & ~B.
|
|
|
157 Restrictions: D != B, unless D == A == B. */
|
|
|
158
|
|
|
159 void
|
|
|
160 sparseset_and_compl (sparseset d, sparseset a, sparseset b)
|
|
|
161 {
|
|
|
162 SPARSESET_ELT_TYPE e;
|
|
|
163
|
|
|
164 if (a == b)
|
|
|
165 {
|
|
|
166 sparseset_clear (d);
|
|
|
167 return;
|
|
|
168 }
|
|
|
169
|
|
|
170 gcc_assert (d != b);
|
|
|
171
|
|
|
172 if (d == a)
|
|
|
173 {
|
|
|
174 if (sparseset_cardinality (d) < sparseset_cardinality (b))
|
|
|
175 {
|
|
|
176 EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
|
|
177 if (sparseset_bit_p (b, e))
|
|
|
178 sparseset_clear_bit (d, e);
|
|
|
179 }
|
|
|
180 else
|
|
|
181 {
|
|
|
182 EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
|
|
183 sparseset_clear_bit (d, e);
|
|
|
184 }
|
|
|
185 }
|
|
|
186 else
|
|
|
187 {
|
|
|
188 sparseset_clear (d);
|
|
|
189 EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
|
|
190 if (!sparseset_bit_p (b, e))
|
|
|
191 sparseset_set_bit (d, e);
|
|
|
192 }
|
|
|
193 }
|
|
|
194
|
|
|
195 /* Operation: D = A | B.
|
|
|
196 Restrictions: none. */
|
|
|
197
|
|
|
198 void
|
|
|
199 sparseset_ior (sparseset d, sparseset a, sparseset b)
|
|
|
200 {
|
|
|
201 SPARSESET_ELT_TYPE e;
|
|
|
202
|
|
|
203 if (a == b)
|
|
|
204 sparseset_copy (d, a);
|
|
|
205 else if (d == b)
|
|
|
206 {
|
|
|
207 EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
|
|
208 sparseset_set_bit (d, e);
|
|
|
209 }
|
|
|
210 else
|
|
|
211 {
|
|
|
212 if (d != a)
|
|
|
213 sparseset_copy (d, a);
|
|
|
214 EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
|
|
215 sparseset_set_bit (d, e);
|
|
|
216 }
|
|
|
217 }
|
|
|
218
|
|
|
219 /* Operation: A == B
|
|
|
220 Restrictions: none. */
|
|
|
221
|
|
|
222 bool
|
|
|
223 sparseset_equal_p (sparseset a, sparseset b)
|
|
|
224 {
|
|
|
225 SPARSESET_ELT_TYPE e;
|
|
|
226
|
|
|
227 if (a == b)
|
|
|
228 return true;
|
|
|
229
|
|
|
230 if (sparseset_cardinality (a) != sparseset_cardinality (b))
|
|
|
231 return false;
|
|
|
232
|
|
|
233 EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
|
|
234 if (!sparseset_bit_p (b, e))
|
|
|
235 return false;
|
|
|
236
|
|
|
237 return true;
|
|
|
238 }
|
|
|
239
|
