Daily bump.
[official-gcc.git] / gcc / sparseset.c
blobc8a9a301b593d61e37dad02a96ef4810983ed184
1 /* SparseSet implementation.
2 Copyright (C) 2007 Free Software Foundation, Inc.
3 Contributed by Peter Bergner <bergner@vnet.ibm.com>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "sparseset.h"
25 /* Allocate and clear a n_elms SparseSet. */
27 sparseset
28 sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
30 unsigned int n_bytes = sizeof (struct sparseset_def)
31 + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
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;
46 /* Low level routine not meant for use outside of sparseset.[ch].
47 Assumes idx1 < s->members and idx2 < s->members. */
49 static inline void
50 sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
52 SPARSESET_ELT_TYPE tmp = s->dense[idx2];
53 sparseset_insert_bit (s, s->dense[idx1], idx2);
54 sparseset_insert_bit (s, tmp, idx1);
57 /* Operation: S = S - {e}
58 Delete e from the set S if it is a member of S. */
60 void
61 sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
63 if (sparseset_bit_p (s, e))
65 SPARSESET_ELT_TYPE idx = s->sparse[e];
66 SPARSESET_ELT_TYPE iter = s->iter;
67 SPARSESET_ELT_TYPE mem = s->members - 1;
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)
76 if (idx < iter)
78 sparseset_swap (s, idx, iter);
79 idx = iter;
81 s->iter_inc = 0;
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;
92 /* Operation: D = S
93 Restrictions: none. */
95 void
96 sparseset_copy (sparseset d, sparseset s)
98 SPARSESET_ELT_TYPE i;
100 if (d == s)
101 return;
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;
109 /* Operation: D = A & B.
110 Restrictions: none. */
112 void
113 sparseset_and (sparseset d, sparseset a, sparseset b)
115 SPARSESET_ELT_TYPE e;
117 if (a == b)
119 if (d != a)
120 sparseset_copy (d, a);
121 return;
124 if (d == a || d == b)
126 sparseset s = (d == a) ? b : a;
128 EXECUTE_IF_SET_IN_SPARSESET (d, e)
129 if (!sparseset_bit_p (s, e))
130 sparseset_clear_bit (d, e);
132 else
134 sparseset sml, lrg;
136 if (sparseset_cardinality (a) < sparseset_cardinality (b))
138 sml = a;
139 lrg = b;
141 else
143 sml = b;
144 lrg = a;
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);
154 /* Operation: D = A & ~B.
155 Restrictions: D != B, unless D == A == B. */
157 void
158 sparseset_and_compl (sparseset d, sparseset a, sparseset b)
160 SPARSESET_ELT_TYPE e;
162 if (a == b)
164 sparseset_clear (d);
165 return;
168 gcc_assert (d != b);
170 if (d == a)
172 if (sparseset_cardinality (d) < sparseset_cardinality (b))
174 EXECUTE_IF_SET_IN_SPARSESET (d, e)
175 if (sparseset_bit_p (b, e))
176 sparseset_clear_bit (d, e);
178 else
180 EXECUTE_IF_SET_IN_SPARSESET (b, e)
181 sparseset_clear_bit (d, e);
184 else
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);
193 /* Operation: D = A | B.
194 Restrictions: none. */
196 void
197 sparseset_ior (sparseset d, sparseset a, sparseset b)
199 SPARSESET_ELT_TYPE e;
201 if (a == b)
202 sparseset_copy (d, a);
203 else if (d == b)
205 EXECUTE_IF_SET_IN_SPARSESET (a, e)
206 sparseset_set_bit (d, e);
208 else
210 if (d != a)
211 sparseset_copy (d, a);
212 EXECUTE_IF_SET_IN_SPARSESET (b, e)
213 sparseset_set_bit (d, e);
217 /* Operation: A == B
218 Restrictions: none. */
220 bool
221 sparseset_equal_p (sparseset a, sparseset b)
223 SPARSESET_ELT_TYPE e;
225 if (a == b)
226 return true;
228 if (sparseset_cardinality (a) != sparseset_cardinality (b))
229 return false;
231 EXECUTE_IF_SET_IN_SPARSESET (a, e)
232 if (!sparseset_bit_p (b, e))
233 return false;
235 return true;