1/* SparseSet implementation.
2   Copyright (C) 2007-2015 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 (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, s->dense[idx1], idx2);
56  sparseset_insert_bit (s, tmp, 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, idx, 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, 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 (d);
106  for (i = 0; i < s->members; i++)
107    sparseset_insert_bit (d, s->dense[i], 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, 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 (d, e);
133    }
134  else
135    {
136      sparseset sml, lrg;
137
138      if (sparseset_cardinality (a) < sparseset_cardinality (b))
139	{
140	  sml = a;
141	  lrg = b;
142	}
143      else
144	{
145	  sml = b;
146	  lrg = a;
147	}
148
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);
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 (d);
167      return;
168    }
169
170  gcc_assert (d != b);
171
172  if (d == a)
173    {
174      if (sparseset_cardinality (d) < sparseset_cardinality (b))
175	{
176	  EXECUTE_IF_SET_IN_SPARSESET (d, e)
177	    if (sparseset_bit_p (b, e))
178	      sparseset_clear_bit (d, e);
179	}
180      else
181	{
182	  EXECUTE_IF_SET_IN_SPARSESET (b, e)
183	    sparseset_clear_bit (d, e);
184	}
185    }
186  else
187    {
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);
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, a);
205  else if (d == b)
206    {
207      EXECUTE_IF_SET_IN_SPARSESET (a, e)
208	sparseset_set_bit (d, e);
209    }
210  else
211    {
212      if (d != a)
213        sparseset_copy (d, a);
214      EXECUTE_IF_SET_IN_SPARSESET (b, e)
215	sparseset_set_bit (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 (a) != sparseset_cardinality (b))
231    return false;
232
233  EXECUTE_IF_SET_IN_SPARSESET (a, e)
234    if (!sparseset_bit_p (b, e))
235      return false;
236
237  return true;
238}
239
240