1/* SparseSet implementation.
2 Copyright (C) 2007-2023 Free Software Foundation, Inc.
3 Contributed by Peter Bergner <bergner@vnet.ibm.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
27sparseset
28sparseset_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 (s: 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
51static inline void
52sparseset_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, e: s->dense[idx1], idx: idx2);
56 sparseset_insert_bit (s, e: tmp, idx: idx1);
57}
58
59/* Operation: S = S - {e}
60 Delete e from the set S if it is a member of S. */
61
62void
63sparseset_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, idx1: idx, idx2: 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, e: s->dense[mem], idx);
90 s->members = mem;
91 }
92}
93
94/* Operation: D = S
95 Restrictions: none. */
96
97void
98sparseset_copy (sparseset d, sparseset s)
99{
100 SPARSESET_ELT_TYPE i;
101
102 if (d == s)
103 return;
104
105 sparseset_clear (s: d);
106 for (i = 0; i < s->members; i++)
107 sparseset_insert_bit (s: d, e: s->dense[i], idx: i);
108 d->members = s->members;
109}
110
111/* Operation: D = A & B.
112 Restrictions: none. */
113
114void
115sparseset_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, s: 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 (s: d, e);
133 }
134 else
135 {
136 sparseset sml, lrg;
137
138 if (sparseset_cardinality (s: a) < sparseset_cardinality (s: b))
139 {
140 sml = a;
141 lrg = b;
142 }
143 else
144 {
145 sml = b;
146 lrg = a;
147 }
148
149 sparseset_clear (s: d);
150 EXECUTE_IF_SET_IN_SPARSESET (sml, e)
151 if (sparseset_bit_p (s: lrg, e))
152 sparseset_set_bit (s: d, e);
153 }
154}
155
156/* Operation: D = A & ~B.
157 Restrictions: D != B, unless D == A == B. */
158
159void
160sparseset_and_compl (sparseset d, sparseset a, sparseset b)
161{
162 SPARSESET_ELT_TYPE e;
163
164 if (a == b)
165 {
166 sparseset_clear (s: d);
167 return;
168 }
169
170 gcc_assert (d != b);
171
172 if (d == a)
173 {
174 if (sparseset_cardinality (s: d) < sparseset_cardinality (s: b))
175 {
176 EXECUTE_IF_SET_IN_SPARSESET (d, e)
177 if (sparseset_bit_p (s: b, e))
178 sparseset_clear_bit (s: d, e);
179 }
180 else
181 {
182 EXECUTE_IF_SET_IN_SPARSESET (b, e)
183 sparseset_clear_bit (s: d, e);
184 }
185 }
186 else
187 {
188 sparseset_clear (s: d);
189 EXECUTE_IF_SET_IN_SPARSESET (a, e)
190 if (!sparseset_bit_p (s: b, e))
191 sparseset_set_bit (s: d, e);
192 }
193}
194
195/* Operation: D = A | B.
196 Restrictions: none. */
197
198void
199sparseset_ior (sparseset d, sparseset a, sparseset b)
200{
201 SPARSESET_ELT_TYPE e;
202
203 if (a == b)
204 sparseset_copy (d, s: a);
205 else if (d == b)
206 {
207 EXECUTE_IF_SET_IN_SPARSESET (a, e)
208 sparseset_set_bit (s: d, e);
209 }
210 else
211 {
212 if (d != a)
213 sparseset_copy (d, s: a);
214 EXECUTE_IF_SET_IN_SPARSESET (b, e)
215 sparseset_set_bit (s: d, e);
216 }
217}
218
219/* Operation: A == B
220 Restrictions: none. */
221
222bool
223sparseset_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 (s: a) != sparseset_cardinality (s: b))
231 return false;
232
233 EXECUTE_IF_SET_IN_SPARSESET (a, e)
234 if (!sparseset_bit_p (s: b, e))
235 return false;
236
237 return true;
238}
239
240

source code of gcc/sparseset.cc