don't compare ARG_FRAME_POINTER_REGNUM and FRAME_POINTER_REGNUM with the preprocessor
[official-gcc.git] / gcc / sparseset.c
blob3c3a317940f64e598d4b7a85f843ef0e6943a44b
1 /* SparseSet implementation.
2 Copyright (C) 2007-2015 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 sparseset set = XNEWVAR (struct sparseset_def, n_bytes);
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));
41 set->dense = &(set->elms[0]);
42 set->sparse = &(set->elms[n_elms]);
43 set->size = n_elms;
44 sparseset_clear (set);
45 return set;
48 /* Low level routine not meant for use outside of sparseset.[ch].
49 Assumes idx1 < s->members and idx2 < s->members. */
51 static inline void
52 sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
54 SPARSESET_ELT_TYPE tmp = s->dense[idx2];
55 sparseset_insert_bit (s, s->dense[idx1], idx2);
56 sparseset_insert_bit (s, tmp, idx1);
59 /* Operation: S = S - {e}
60 Delete e from the set S if it is a member of S. */
62 void
63 sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
65 if (sparseset_bit_p (s, e))
67 SPARSESET_ELT_TYPE idx = s->sparse[e];
68 SPARSESET_ELT_TYPE iter = s->iter;
69 SPARSESET_ELT_TYPE mem = s->members - 1;
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)
78 if (idx < iter)
80 sparseset_swap (s, idx, iter);
81 idx = iter;
83 s->iter_inc = 0;
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, s->dense[mem], idx);
90 s->members = mem;
94 /* Operation: D = S
95 Restrictions: none. */
97 void
98 sparseset_copy (sparseset d, sparseset s)
100 SPARSESET_ELT_TYPE i;
102 if (d == s)
103 return;
105 sparseset_clear (d);
106 for (i = 0; i < s->members; i++)
107 sparseset_insert_bit (d, s->dense[i], i);
108 d->members = s->members;
111 /* Operation: D = A & B.
112 Restrictions: none. */
114 void
115 sparseset_and (sparseset d, sparseset a, sparseset b)
117 SPARSESET_ELT_TYPE e;
119 if (a == b)
121 if (d != a)
122 sparseset_copy (d, a);
123 return;
126 if (d == a || d == b)
128 sparseset s = (d == a) ? b : a;
130 EXECUTE_IF_SET_IN_SPARSESET (d, e)
131 if (!sparseset_bit_p (s, e))
132 sparseset_clear_bit (d, e);
134 else
136 sparseset sml, lrg;
138 if (sparseset_cardinality (a) < sparseset_cardinality (b))
140 sml = a;
141 lrg = b;
143 else
145 sml = b;
146 lrg = a;
149 sparseset_clear (d);
150 EXECUTE_IF_SET_IN_SPARSESET (sml, e)
151 if (sparseset_bit_p (lrg, e))
152 sparseset_set_bit (d, e);
156 /* Operation: D = A & ~B.
157 Restrictions: D != B, unless D == A == B. */
159 void
160 sparseset_and_compl (sparseset d, sparseset a, sparseset b)
162 SPARSESET_ELT_TYPE e;
164 if (a == b)
166 sparseset_clear (d);
167 return;
170 gcc_assert (d != b);
172 if (d == a)
174 if (sparseset_cardinality (d) < sparseset_cardinality (b))
176 EXECUTE_IF_SET_IN_SPARSESET (d, e)
177 if (sparseset_bit_p (b, e))
178 sparseset_clear_bit (d, e);
180 else
182 EXECUTE_IF_SET_IN_SPARSESET (b, e)
183 sparseset_clear_bit (d, e);
186 else
188 sparseset_clear (d);
189 EXECUTE_IF_SET_IN_SPARSESET (a, e)
190 if (!sparseset_bit_p (b, e))
191 sparseset_set_bit (d, e);
195 /* Operation: D = A | B.
196 Restrictions: none. */
198 void
199 sparseset_ior (sparseset d, sparseset a, sparseset b)
201 SPARSESET_ELT_TYPE e;
203 if (a == b)
204 sparseset_copy (d, a);
205 else if (d == b)
207 EXECUTE_IF_SET_IN_SPARSESET (a, e)
208 sparseset_set_bit (d, e);
210 else
212 if (d != a)
213 sparseset_copy (d, a);
214 EXECUTE_IF_SET_IN_SPARSESET (b, e)
215 sparseset_set_bit (d, e);
219 /* Operation: A == B
220 Restrictions: none. */
222 bool
223 sparseset_equal_p (sparseset a, sparseset b)
225 SPARSESET_ELT_TYPE e;
227 if (a == b)
228 return true;
230 if (sparseset_cardinality (a) != sparseset_cardinality (b))
231 return false;
233 EXECUTE_IF_SET_IN_SPARSESET (a, e)
234 if (!sparseset_bit_p (b, e))
235 return false;
237 return true;