1 /* SparseSet implementation.
2 Copyright (C) 2007-2019 Free Software Foundation, Inc.
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
sparseset_alloc(SPARSESET_ELT_TYPE n_elms)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
33 sparseset set = XNEWVAR (struct sparseset_def, n_bytes);
34
35 /* Mark the sparseset as defined to silence some valgrind uninitialized
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
38 harmless. */
39 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
40
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
sparseset_swap(sparseset s,SPARSESET_ELT_TYPE idx1,SPARSESET_ELT_TYPE idx2)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
sparseset_clear_bit(sparseset s,SPARSESET_ELT_TYPE e)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
sparseset_copy(sparseset d,sparseset s)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
sparseset_and(sparseset d,sparseset a,sparseset b)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
sparseset_and_compl(sparseset d,sparseset a,sparseset b)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
sparseset_ior(sparseset d,sparseset a,sparseset b)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
sparseset_equal_p(sparseset a,sparseset b)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
240