1*38fd1498Szrj /* SparseSet implementation.
2*38fd1498Szrj Copyright (C) 2007-2018 Free Software Foundation, Inc.
3*38fd1498Szrj Contributed by Peter Bergner <bergner@vnet.ibm.com>
4*38fd1498Szrj
5*38fd1498Szrj This file is part of GCC.
6*38fd1498Szrj
7*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
8*38fd1498Szrj the terms of the GNU General Public License as published by the Free
9*38fd1498Szrj Software Foundation; either version 3, or (at your option) any later
10*38fd1498Szrj version.
11*38fd1498Szrj
12*38fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*38fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*38fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*38fd1498Szrj for more details.
16*38fd1498Szrj
17*38fd1498Szrj You should have received a copy of the GNU General Public License
18*38fd1498Szrj along with GCC; see the file COPYING3. If not see
19*38fd1498Szrj <http://www.gnu.org/licenses/>. */
20*38fd1498Szrj
21*38fd1498Szrj #include "config.h"
22*38fd1498Szrj #include "system.h"
23*38fd1498Szrj #include "sparseset.h"
24*38fd1498Szrj
25*38fd1498Szrj /* Allocate and clear a n_elms SparseSet. */
26*38fd1498Szrj
27*38fd1498Szrj sparseset
sparseset_alloc(SPARSESET_ELT_TYPE n_elms)28*38fd1498Szrj sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
29*38fd1498Szrj {
30*38fd1498Szrj unsigned int n_bytes = sizeof (struct sparseset_def)
31*38fd1498Szrj + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
32*38fd1498Szrj
33*38fd1498Szrj sparseset set = XNEWVAR (struct sparseset_def, n_bytes);
34*38fd1498Szrj
35*38fd1498Szrj /* Mark the sparseset as defined to silence some valgrind uninitialized
36*38fd1498Szrj read errors when accessing set->sparse[n] when "n" is not, and never has
37*38fd1498Szrj been, in the set. These uninitialized reads are expected, by design and
38*38fd1498Szrj harmless. */
39*38fd1498Szrj VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
40*38fd1498Szrj
41*38fd1498Szrj set->dense = &(set->elms[0]);
42*38fd1498Szrj set->sparse = &(set->elms[n_elms]);
43*38fd1498Szrj set->size = n_elms;
44*38fd1498Szrj sparseset_clear (set);
45*38fd1498Szrj return set;
46*38fd1498Szrj }
47*38fd1498Szrj
48*38fd1498Szrj /* Low level routine not meant for use outside of sparseset.[ch].
49*38fd1498Szrj Assumes idx1 < s->members and idx2 < s->members. */
50*38fd1498Szrj
51*38fd1498Szrj static inline void
sparseset_swap(sparseset s,SPARSESET_ELT_TYPE idx1,SPARSESET_ELT_TYPE idx2)52*38fd1498Szrj sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
53*38fd1498Szrj {
54*38fd1498Szrj SPARSESET_ELT_TYPE tmp = s->dense[idx2];
55*38fd1498Szrj sparseset_insert_bit (s, s->dense[idx1], idx2);
56*38fd1498Szrj sparseset_insert_bit (s, tmp, idx1);
57*38fd1498Szrj }
58*38fd1498Szrj
59*38fd1498Szrj /* Operation: S = S - {e}
60*38fd1498Szrj Delete e from the set S if it is a member of S. */
61*38fd1498Szrj
62*38fd1498Szrj void
sparseset_clear_bit(sparseset s,SPARSESET_ELT_TYPE e)63*38fd1498Szrj sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
64*38fd1498Szrj {
65*38fd1498Szrj if (sparseset_bit_p (s, e))
66*38fd1498Szrj {
67*38fd1498Szrj SPARSESET_ELT_TYPE idx = s->sparse[e];
68*38fd1498Szrj SPARSESET_ELT_TYPE iter = s->iter;
69*38fd1498Szrj SPARSESET_ELT_TYPE mem = s->members - 1;
70*38fd1498Szrj
71*38fd1498Szrj /* If we are iterating over this set and we want to delete a
72*38fd1498Szrj member we've already visited, then we swap the element we
73*38fd1498Szrj want to delete with the element at the current iteration
74*38fd1498Szrj index so that it plays well together with the code below
75*38fd1498Szrj that actually removes the element. */
76*38fd1498Szrj if (s->iterating && idx <= iter)
77*38fd1498Szrj {
78*38fd1498Szrj if (idx < iter)
79*38fd1498Szrj {
80*38fd1498Szrj sparseset_swap (s, idx, iter);
81*38fd1498Szrj idx = iter;
82*38fd1498Szrj }
83*38fd1498Szrj s->iter_inc = 0;
84*38fd1498Szrj }
85*38fd1498Szrj
86*38fd1498Szrj /* Replace the element we want to delete with the last element
87*38fd1498Szrj in the dense array and then decrement s->members, effectively
88*38fd1498Szrj removing the element we want to delete. */
89*38fd1498Szrj sparseset_insert_bit (s, s->dense[mem], idx);
90*38fd1498Szrj s->members = mem;
91*38fd1498Szrj }
92*38fd1498Szrj }
93*38fd1498Szrj
94*38fd1498Szrj /* Operation: D = S
95*38fd1498Szrj Restrictions: none. */
96*38fd1498Szrj
97*38fd1498Szrj void
sparseset_copy(sparseset d,sparseset s)98*38fd1498Szrj sparseset_copy (sparseset d, sparseset s)
99*38fd1498Szrj {
100*38fd1498Szrj SPARSESET_ELT_TYPE i;
101*38fd1498Szrj
102*38fd1498Szrj if (d == s)
103*38fd1498Szrj return;
104*38fd1498Szrj
105*38fd1498Szrj sparseset_clear (d);
106*38fd1498Szrj for (i = 0; i < s->members; i++)
107*38fd1498Szrj sparseset_insert_bit (d, s->dense[i], i);
108*38fd1498Szrj d->members = s->members;
109*38fd1498Szrj }
110*38fd1498Szrj
111*38fd1498Szrj /* Operation: D = A & B.
112*38fd1498Szrj Restrictions: none. */
113*38fd1498Szrj
114*38fd1498Szrj void
sparseset_and(sparseset d,sparseset a,sparseset b)115*38fd1498Szrj sparseset_and (sparseset d, sparseset a, sparseset b)
116*38fd1498Szrj {
117*38fd1498Szrj SPARSESET_ELT_TYPE e;
118*38fd1498Szrj
119*38fd1498Szrj if (a == b)
120*38fd1498Szrj {
121*38fd1498Szrj if (d != a)
122*38fd1498Szrj sparseset_copy (d, a);
123*38fd1498Szrj return;
124*38fd1498Szrj }
125*38fd1498Szrj
126*38fd1498Szrj if (d == a || d == b)
127*38fd1498Szrj {
128*38fd1498Szrj sparseset s = (d == a) ? b : a;
129*38fd1498Szrj
130*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (d, e)
131*38fd1498Szrj if (!sparseset_bit_p (s, e))
132*38fd1498Szrj sparseset_clear_bit (d, e);
133*38fd1498Szrj }
134*38fd1498Szrj else
135*38fd1498Szrj {
136*38fd1498Szrj sparseset sml, lrg;
137*38fd1498Szrj
138*38fd1498Szrj if (sparseset_cardinality (a) < sparseset_cardinality (b))
139*38fd1498Szrj {
140*38fd1498Szrj sml = a;
141*38fd1498Szrj lrg = b;
142*38fd1498Szrj }
143*38fd1498Szrj else
144*38fd1498Szrj {
145*38fd1498Szrj sml = b;
146*38fd1498Szrj lrg = a;
147*38fd1498Szrj }
148*38fd1498Szrj
149*38fd1498Szrj sparseset_clear (d);
150*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (sml, e)
151*38fd1498Szrj if (sparseset_bit_p (lrg, e))
152*38fd1498Szrj sparseset_set_bit (d, e);
153*38fd1498Szrj }
154*38fd1498Szrj }
155*38fd1498Szrj
156*38fd1498Szrj /* Operation: D = A & ~B.
157*38fd1498Szrj Restrictions: D != B, unless D == A == B. */
158*38fd1498Szrj
159*38fd1498Szrj void
sparseset_and_compl(sparseset d,sparseset a,sparseset b)160*38fd1498Szrj sparseset_and_compl (sparseset d, sparseset a, sparseset b)
161*38fd1498Szrj {
162*38fd1498Szrj SPARSESET_ELT_TYPE e;
163*38fd1498Szrj
164*38fd1498Szrj if (a == b)
165*38fd1498Szrj {
166*38fd1498Szrj sparseset_clear (d);
167*38fd1498Szrj return;
168*38fd1498Szrj }
169*38fd1498Szrj
170*38fd1498Szrj gcc_assert (d != b);
171*38fd1498Szrj
172*38fd1498Szrj if (d == a)
173*38fd1498Szrj {
174*38fd1498Szrj if (sparseset_cardinality (d) < sparseset_cardinality (b))
175*38fd1498Szrj {
176*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (d, e)
177*38fd1498Szrj if (sparseset_bit_p (b, e))
178*38fd1498Szrj sparseset_clear_bit (d, e);
179*38fd1498Szrj }
180*38fd1498Szrj else
181*38fd1498Szrj {
182*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (b, e)
183*38fd1498Szrj sparseset_clear_bit (d, e);
184*38fd1498Szrj }
185*38fd1498Szrj }
186*38fd1498Szrj else
187*38fd1498Szrj {
188*38fd1498Szrj sparseset_clear (d);
189*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (a, e)
190*38fd1498Szrj if (!sparseset_bit_p (b, e))
191*38fd1498Szrj sparseset_set_bit (d, e);
192*38fd1498Szrj }
193*38fd1498Szrj }
194*38fd1498Szrj
195*38fd1498Szrj /* Operation: D = A | B.
196*38fd1498Szrj Restrictions: none. */
197*38fd1498Szrj
198*38fd1498Szrj void
sparseset_ior(sparseset d,sparseset a,sparseset b)199*38fd1498Szrj sparseset_ior (sparseset d, sparseset a, sparseset b)
200*38fd1498Szrj {
201*38fd1498Szrj SPARSESET_ELT_TYPE e;
202*38fd1498Szrj
203*38fd1498Szrj if (a == b)
204*38fd1498Szrj sparseset_copy (d, a);
205*38fd1498Szrj else if (d == b)
206*38fd1498Szrj {
207*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (a, e)
208*38fd1498Szrj sparseset_set_bit (d, e);
209*38fd1498Szrj }
210*38fd1498Szrj else
211*38fd1498Szrj {
212*38fd1498Szrj if (d != a)
213*38fd1498Szrj sparseset_copy (d, a);
214*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (b, e)
215*38fd1498Szrj sparseset_set_bit (d, e);
216*38fd1498Szrj }
217*38fd1498Szrj }
218*38fd1498Szrj
219*38fd1498Szrj /* Operation: A == B
220*38fd1498Szrj Restrictions: none. */
221*38fd1498Szrj
222*38fd1498Szrj bool
sparseset_equal_p(sparseset a,sparseset b)223*38fd1498Szrj sparseset_equal_p (sparseset a, sparseset b)
224*38fd1498Szrj {
225*38fd1498Szrj SPARSESET_ELT_TYPE e;
226*38fd1498Szrj
227*38fd1498Szrj if (a == b)
228*38fd1498Szrj return true;
229*38fd1498Szrj
230*38fd1498Szrj if (sparseset_cardinality (a) != sparseset_cardinality (b))
231*38fd1498Szrj return false;
232*38fd1498Szrj
233*38fd1498Szrj EXECUTE_IF_SET_IN_SPARSESET (a, e)
234*38fd1498Szrj if (!sparseset_bit_p (b, e))
235*38fd1498Szrj return false;
236*38fd1498Szrj
237*38fd1498Szrj return true;
238*38fd1498Szrj }
239*38fd1498Szrj
240