Branch data Line data Source code
1 : : /* SparseSet implementation.
2 : : Copyright (C) 2007-2024 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 : 18583835 : sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
29 : : {
30 : 18583835 : unsigned int n_bytes = sizeof (struct sparseset_def)
31 : : + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
32 : :
33 : 18583835 : 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 : 18583835 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
40 : :
41 : 18583835 : set->dense = &(set->elms[0]);
42 : 18583835 : set->sparse = &(set->elms[n_elms]);
43 : 18583835 : set->size = n_elms;
44 : 18583835 : sparseset_clear (set);
45 : 18583835 : 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 : 492558 : sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
53 : : {
54 : 492558 : SPARSESET_ELT_TYPE tmp = s->dense[idx2];
55 : 492558 : sparseset_insert_bit (s, s->dense[idx1], idx2);
56 : 492558 : sparseset_insert_bit (s, tmp, idx1);
57 : 492558 : }
58 : :
59 : : /* Operation: S = S - {e}
60 : : Delete e from the set S if it is a member of S. */
61 : :
62 : : void
63 : 991510052 : sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
64 : : {
65 : 991510052 : if (sparseset_bit_p (s, e))
66 : : {
67 : 984614590 : SPARSESET_ELT_TYPE idx = s->sparse[e];
68 : 984614590 : SPARSESET_ELT_TYPE iter = s->iter;
69 : 984614590 : 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 : 984614590 : if (s->iterating && idx <= iter)
77 : : {
78 : 643072627 : if (idx < iter)
79 : : {
80 : 492558 : sparseset_swap (s, idx, iter);
81 : 492558 : idx = iter;
82 : : }
83 : 643072627 : 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 : 984614590 : sparseset_insert_bit (s, s->dense[mem], idx);
90 : 984614590 : s->members = mem;
91 : : }
92 : 991510052 : }
93 : :
94 : : /* Operation: D = S
95 : : Restrictions: none. */
96 : :
97 : : void
98 : 197981667 : sparseset_copy (sparseset d, sparseset s)
99 : : {
100 : 197981667 : SPARSESET_ELT_TYPE i;
101 : :
102 : 197981667 : if (d == s)
103 : : return;
104 : :
105 : 197981667 : sparseset_clear (d);
106 : 223993347 : for (i = 0; i < s->members; i++)
107 : 26011680 : sparseset_insert_bit (d, s->dense[i], i);
108 : 197981667 : 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 : 197981667 : sparseset_and_compl (sparseset d, sparseset a, sparseset b)
161 : : {
162 : 197981667 : SPARSESET_ELT_TYPE e;
163 : :
164 : 197981667 : if (a == b)
165 : : {
166 : 0 : sparseset_clear (d);
167 : 0 : return;
168 : : }
169 : :
170 : 197981667 : gcc_assert (d != b);
171 : :
172 : 197981667 : 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 : 197981667 : sparseset_clear (d);
189 : 342102693 : EXECUTE_IF_SET_IN_SPARSESET (a, e)
190 : 144121026 : if (!sparseset_bit_p (b, e))
191 : 124396236 : sparseset_set_bit (d, e);
192 : : }
193 : : }
194 : :
195 : : /* Operation: D = A | B.
196 : : Restrictions: none. */
197 : :
198 : : void
199 : 11094386 : sparseset_ior (sparseset d, sparseset a, sparseset b)
200 : : {
201 : 11094386 : SPARSESET_ELT_TYPE e;
202 : :
203 : 11094386 : if (a == b)
204 : 0 : sparseset_copy (d, a);
205 : 11094386 : 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 : 11094386 : if (d != a)
213 : 0 : sparseset_copy (d, a);
214 : 270321530 : EXECUTE_IF_SET_IN_SPARSESET (b, e)
215 : 259227144 : sparseset_set_bit (d, e);
216 : : }
217 : 11094386 : }
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 : :
|
