|
0
|
1 /* SparseSet implementation.
|
|
|
2 Copyright (C) 2007, 2008 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
|
|
|
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 /* We use xcalloc rather than xmalloc to silence some valgrind uninitialized
|
|
|
34 read errors when accessing set->sparse[n] when "n" is not, and never has
|
|
|
35 been, in the set. These uninitialized reads are expected, by design and
|
|
|
36 harmless. If this turns into a performance problem due to some future
|
|
|
37 additional users of sparseset, we can revisit this decision. */
|
|
|
38 sparseset set = (sparseset) xcalloc (1, n_bytes);
|
|
|
39 set->dense = &(set->elms[0]);
|
|
|
40 set->sparse = &(set->elms[n_elms]);
|
|
|
41 set->size = n_elms;
|
|
|
42 sparseset_clear (set);
|
|
|
43 return set;
|
|
|
44 }
|
|
|
45
|
|
|
46 /* Low level routine not meant for use outside of sparseset.[ch].
|
|
|
47 Assumes idx1 < s->members and idx2 < s->members. */
|
|
|
48
|
|
|
49 static inline void
|
|
|
50 sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
|
|
|
51 {
|
|
|
52 SPARSESET_ELT_TYPE tmp = s->dense[idx2];
|
|
|
53 sparseset_insert_bit (s, s->dense[idx1], idx2);
|
|
|
54 sparseset_insert_bit (s, tmp, idx1);
|
|
|
55 }
|
|
|
56
|
|
|
57 /* Operation: S = S - {e}
|
|
|
58 Delete e from the set S if it is a member of S. */
|
|
|
59
|
|
|
60 void
|
|
|
61 sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
|
|
|
62 {
|
|
|
63 if (sparseset_bit_p (s, e))
|
|
|
64 {
|
|
|
65 SPARSESET_ELT_TYPE idx = s->sparse[e];
|
|
|
66 SPARSESET_ELT_TYPE iter = s->iter;
|
|
|
67 SPARSESET_ELT_TYPE mem = s->members - 1;
|
|
|
68
|
|
|
69 /* If we are iterating over this set and we want to delete a
|
|
|
70 member we've already visited, then we swap the element we
|
|
|
71 want to delete with the element at the current iteration
|
|
|
72 index so that it plays well together with the code below
|
|
|
73 that actually removes the element. */
|
|
|
74 if (s->iterating && idx <= iter)
|
|
|
75 {
|
|
|
76 if (idx < iter)
|
|
|
77 {
|
|
|
78 sparseset_swap (s, idx, iter);
|
|
|
79 idx = iter;
|
|
|
80 }
|
|
|
81 s->iter_inc = 0;
|
|
|
82 }
|
|
|
83
|
|
|
84 /* Replace the element we want to delete with the last element
|
|
|
85 in the dense array and then decrement s->members, effectively
|
|
|
86 removing the element we want to delete. */
|
|
|
87 sparseset_insert_bit (s, s->dense[mem], idx);
|
|
|
88 s->members = mem;
|
|
|
89 }
|
|
|
90 }
|
|
|
91
|
|
|
92 /* Operation: D = S
|
|
|
93 Restrictions: none. */
|
|
|
94
|
|
|
95 void
|
|
|
96 sparseset_copy (sparseset d, sparseset s)
|
|
|
97 {
|
|
|
98 SPARSESET_ELT_TYPE i;
|
|
|
99
|
|
|
100 if (d == s)
|
|
|
101 return;
|
|
|
102
|
|
|
103 sparseset_clear (d);
|
|
|
104 for (i = 0; i < s->members; i++)
|
|
|
105 sparseset_insert_bit (d, s->dense[i], i);
|
|
|
106 d->members = s->members;
|
|
|
107 }
|
|
|
108
|
|
|
109 /* Operation: D = A & B.
|
|
|
110 Restrictions: none. */
|
|
|
111
|
|
|
112 void
|
|
|
113 sparseset_and (sparseset d, sparseset a, sparseset b)
|
|
|
114 {
|
|
|
115 SPARSESET_ELT_TYPE e;
|
|
|
116
|
|
|
117 if (a == b)
|
|
|
118 {
|
|
|
119 if (d != a)
|
|
|
120 sparseset_copy (d, a);
|
|
|
121 return;
|
|
|
122 }
|
|
|
123
|
|
|
124 if (d == a || d == b)
|
|
|
125 {
|
|
|
126 sparseset s = (d == a) ? b : a;
|
|
|
127
|
|
|
128 EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
|
|
129 if (!sparseset_bit_p (s, e))
|
|
|
130 sparseset_clear_bit (d, e);
|
|
|
131 }
|
|
|
132 else
|
|
|
133 {
|
|
|
134 sparseset sml, lrg;
|
|
|
135
|
|
|
136 if (sparseset_cardinality (a) < sparseset_cardinality (b))
|
|
|
137 {
|
|
|
138 sml = a;
|
|
|
139 lrg = b;
|
|
|
140 }
|
|
|
141 else
|
|
|
142 {
|
|
|
143 sml = b;
|
|
|
144 lrg = a;
|
|
|
145 }
|
|
|
146
|
|
|
147 sparseset_clear (d);
|
|
|
148 EXECUTE_IF_SET_IN_SPARSESET (sml, e)
|
|
|
149 if (sparseset_bit_p (lrg, e))
|
|
|
150 sparseset_set_bit (d, e);
|
|
|
151 }
|
|
|
152 }
|
|
|
153
|
|
|
154 /* Operation: D = A & ~B.
|
|
|
155 Restrictions: D != B, unless D == A == B. */
|
|
|
156
|
|
|
157 void
|
|
|
158 sparseset_and_compl (sparseset d, sparseset a, sparseset b)
|
|
|
159 {
|
|
|
160 SPARSESET_ELT_TYPE e;
|
|
|
161
|
|
|
162 if (a == b)
|
|
|
163 {
|
|
|
164 sparseset_clear (d);
|
|
|
165 return;
|
|
|
166 }
|
|
|
167
|
|
|
168 gcc_assert (d != b);
|
|
|
169
|
|
|
170 if (d == a)
|
|
|
171 {
|
|
|
172 if (sparseset_cardinality (d) < sparseset_cardinality (b))
|
|
|
173 {
|
|
|
174 EXECUTE_IF_SET_IN_SPARSESET (d, e)
|
|
|
175 if (sparseset_bit_p (b, e))
|
|
|
176 sparseset_clear_bit (d, e);
|
|
|
177 }
|
|
|
178 else
|
|
|
179 {
|
|
|
180 EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
|
|
181 sparseset_clear_bit (d, e);
|
|
|
182 }
|
|
|
183 }
|
|
|
184 else
|
|
|
185 {
|
|
|
186 sparseset_clear (d);
|
|
|
187 EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
|
|
188 if (!sparseset_bit_p (b, e))
|
|
|
189 sparseset_set_bit (d, e);
|
|
|
190 }
|
|
|
191 }
|
|
|
192
|
|
|
193 /* Operation: D = A | B.
|
|
|
194 Restrictions: none. */
|
|
|
195
|
|
|
196 void
|
|
|
197 sparseset_ior (sparseset d, sparseset a, sparseset b)
|
|
|
198 {
|
|
|
199 SPARSESET_ELT_TYPE e;
|
|
|
200
|
|
|
201 if (a == b)
|
|
|
202 sparseset_copy (d, a);
|
|
|
203 else if (d == b)
|
|
|
204 {
|
|
|
205 EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
|
|
206 sparseset_set_bit (d, e);
|
|
|
207 }
|
|
|
208 else
|
|
|
209 {
|
|
|
210 if (d != a)
|
|
|
211 sparseset_copy (d, a);
|
|
|
212 EXECUTE_IF_SET_IN_SPARSESET (b, e)
|
|
|
213 sparseset_set_bit (d, e);
|
|
|
214 }
|
|
|
215 }
|
|
|
216
|
|
|
217 /* Operation: A == B
|
|
|
218 Restrictions: none. */
|
|
|
219
|
|
|
220 bool
|
|
|
221 sparseset_equal_p (sparseset a, sparseset b)
|
|
|
222 {
|
|
|
223 SPARSESET_ELT_TYPE e;
|
|
|
224
|
|
|
225 if (a == b)
|
|
|
226 return true;
|
|
|
227
|
|
|
228 if (sparseset_cardinality (a) != sparseset_cardinality (b))
|
|
|
229 return false;
|
|
|
230
|
|
|
231 EXECUTE_IF_SET_IN_SPARSESET (a, e)
|
|
|
232 if (!sparseset_bit_p (b, e))
|
|
|
233 return false;
|
|
|
234
|
|
|
235 return true;
|
|
|
236 }
|
|
|
237
|
