Line data Source code
1 : /* SparseSet implementation.
2 : Copyright (C) 2007-2026 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 19572783 : sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
29 : {
30 19572783 : unsigned int n_bytes = sizeof (struct sparseset_def)
31 : + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
32 :
33 19572783 : 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 19572783 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
40 :
41 19572783 : set->dense = &(set->elms[0]);
42 19572783 : set->sparse = &(set->elms[n_elms]);
43 19572783 : set->size = n_elms;
44 19572783 : sparseset_clear (set);
45 19572783 : 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 653054 : sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
53 : {
54 653054 : SPARSESET_ELT_TYPE tmp = s->dense[idx2];
55 653054 : sparseset_insert_bit (s, s->dense[idx1], idx2);
56 653054 : sparseset_insert_bit (s, tmp, idx1);
57 653054 : }
58 :
59 : /* Operation: S = S - {e}
60 : Delete e from the set S if it is a member of S. */
61 :
62 : void
63 1056900895 : sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
64 : {
65 1056900895 : if (sparseset_bit_p (s, e))
66 : {
67 1048651154 : SPARSESET_ELT_TYPE idx = s->sparse[e];
68 1048651154 : SPARSESET_ELT_TYPE iter = s->iter;
69 1048651154 : 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 1048651154 : if (s->iterating && idx <= iter)
77 : {
78 686338323 : if (idx < iter)
79 : {
80 653054 : sparseset_swap (s, idx, iter);
81 653054 : idx = iter;
82 : }
83 686338323 : 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 1048651154 : sparseset_insert_bit (s, s->dense[mem], idx);
90 1048651154 : s->members = mem;
91 : }
92 1056900895 : }
93 :
94 : /* Operation: D = S
95 : Restrictions: none. */
96 :
97 : void
98 220416417 : sparseset_copy (sparseset d, sparseset s)
99 : {
100 220416417 : SPARSESET_ELT_TYPE i;
101 :
102 220416417 : if (d == s)
103 : return;
104 :
105 220416417 : sparseset_clear (d);
106 248415295 : for (i = 0; i < s->members; i++)
107 27998878 : sparseset_insert_bit (d, s->dense[i], i);
108 220416417 : d->members = s->members;
109 : }
110 :
111 : /* Operation: D = A & B.
112 : Restrictions: none. */
113 :
114 : void
115 0 : sparseset_and (sparseset d, sparseset a, sparseset b)
116 : {
117 0 : SPARSESET_ELT_TYPE e;
118 :
119 0 : if (a == b)
120 : {
121 0 : if (d != a)
122 0 : sparseset_copy (d, a);
123 0 : return;
124 : }
125 :
126 0 : if (d == a || d == b)
127 : {
128 0 : sparseset s = (d == a) ? b : a;
129 :
130 0 : EXECUTE_IF_SET_IN_SPARSESET (d, e)
131 0 : if (!sparseset_bit_p (s, e))
132 0 : sparseset_clear_bit (d, e);
133 : }
134 : else
135 : {
136 0 : sparseset sml, lrg;
137 :
138 0 : if (sparseset_cardinality (a) < sparseset_cardinality (b))
139 : {
140 : sml = a;
141 : lrg = b;
142 : }
143 : else
144 : {
145 0 : sml = b;
146 0 : lrg = a;
147 : }
148 :
149 0 : sparseset_clear (d);
150 0 : EXECUTE_IF_SET_IN_SPARSESET (sml, e)
151 0 : if (sparseset_bit_p (lrg, e))
152 0 : 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 220416417 : sparseset_and_compl (sparseset d, sparseset a, sparseset b)
161 : {
162 220416417 : SPARSESET_ELT_TYPE e;
163 :
164 220416417 : if (a == b)
165 : {
166 0 : sparseset_clear (d);
167 0 : return;
168 : }
169 :
170 220416417 : gcc_assert (d != b);
171 :
172 220416417 : if (d == a)
173 : {
174 0 : if (sparseset_cardinality (d) < sparseset_cardinality (b))
175 : {
176 0 : EXECUTE_IF_SET_IN_SPARSESET (d, e)
177 0 : if (sparseset_bit_p (b, e))
178 0 : sparseset_clear_bit (d, e);
179 : }
180 : else
181 : {
182 0 : EXECUTE_IF_SET_IN_SPARSESET (b, e)
183 0 : sparseset_clear_bit (d, e);
184 : }
185 : }
186 : else
187 : {
188 220416417 : sparseset_clear (d);
189 379453747 : EXECUTE_IF_SET_IN_SPARSESET (a, e)
190 159037330 : if (!sparseset_bit_p (b, e))
191 137668112 : sparseset_set_bit (d, e);
192 : }
193 : }
194 :
195 : /* Operation: D = A | B.
196 : Restrictions: none. */
197 :
198 : void
199 12093963 : sparseset_ior (sparseset d, sparseset a, sparseset b)
200 : {
201 12093963 : SPARSESET_ELT_TYPE e;
202 :
203 12093963 : if (a == b)
204 0 : sparseset_copy (d, a);
205 12093963 : else if (d == b)
206 : {
207 0 : EXECUTE_IF_SET_IN_SPARSESET (a, e)
208 0 : sparseset_set_bit (d, e);
209 : }
210 : else
211 : {
212 12093963 : if (d != a)
213 0 : sparseset_copy (d, a);
214 270198438 : EXECUTE_IF_SET_IN_SPARSESET (b, e)
215 258104475 : sparseset_set_bit (d, e);
216 : }
217 12093963 : }
218 :
219 : /* Operation: A == B
220 : Restrictions: none. */
221 :
222 : bool
223 0 : sparseset_equal_p (sparseset a, sparseset b)
224 : {
225 0 : SPARSESET_ELT_TYPE e;
226 :
227 0 : if (a == b)
228 : return true;
229 :
230 0 : if (sparseset_cardinality (a) != sparseset_cardinality (b))
231 : return false;
232 :
233 0 : EXECUTE_IF_SET_IN_SPARSESET (a, e)
234 0 : if (!sparseset_bit_p (b, e))
235 : return false;
236 :
237 : return true;
238 : }
239 :
|
