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#ifndef GCC_SPARSESET_H
22#define GCC_SPARSESET_H
23
24/* Implementation of the Briggs and Torczon sparse set representation.
25 The sparse set representation was first published in:
26
27 "An Efficient Representation for Sparse Sets",
28 ACM LOPLAS, Vol. 2, Nos. 1-4, March-December 1993, Pages 59-69.
29
30 The sparse set representation is suitable for integer sets with a
31 fixed-size universe. Two vectors are used to store the members of
32 the set. If an element I is in the set, then sparse[I] is the
33 index of I in the dense vector, and dense[sparse[I]] == I. The dense
34 vector works like a stack. The size of the stack is the cardinality
35 of the set.
36
37 The following operations can be performed in O(1) time:
38
39 * clear : sparseset_clear
40 * cardinality : sparseset_cardinality
41 * set_size : sparseset_size
42 * member_p : sparseset_bit_p
43 * add_member : sparseset_set_bit
44 * remove_member : sparseset_clear_bit
45 * choose_one : sparseset_pop
46
47 Additionally, the sparse set representation supports enumeration of
48 the members in O(N) time, where n is the number of members in the set.
49 The members of the set are stored cache-friendly in the dense vector.
50 This makes it a competitive choice for iterating over relatively sparse
51 sets requiring operations:
52
53 * forall : EXECUTE_IF_SET_IN_SPARSESET
54 * set_copy : sparseset_copy
55 * set_intersection : sparseset_and
56 * set_union : sparseset_ior
57 * set_difference : sparseset_and_compl
58 * set_disjuction : (not implemented)
59 * set_compare : sparseset_equal_p
60
61 NB: It is OK to use remove_member during EXECUTE_IF_SET_IN_SPARSESET.
62 The iterator is updated for it.
63
64 Based on the efficiency of these operations, this representation of
65 sparse sets will often be superior to alternatives such as simple
66 bitmaps, linked-list bitmaps, array bitmaps, balanced binary trees,
67 hash tables, linked lists, etc., if the set is sufficiently sparse.
68 In the LOPLAS paper the cut-off point where sparse sets became faster
69 than simple bitmaps (see sbitmap.h) when N / U < 64 (where U is the
70 size of the universe of the set).
71
72 Because the set universe is fixed, the set cannot be resized. For
73 sparse sets with initially unknown size, linked-list bitmaps are a
74 better choice, see bitmap.h.
75
76 Sparse sets storage requirements are relatively large: O(U) with a
77 larger constant than sbitmaps (if the storage requirement for an
78 sbitmap with universe U is S, then the storage required for a sparse
79 set for the same universe are 2 * sizeof (SPARSESET_ELT_TYPE) * 8 * S).
80 Accessing the sparse vector is not very cache-friendly, but iterating
81 over the members in the set is cache-friendly because only the dense
82 vector is used. */
83
84/* Data Structure used for the SparseSet representation. */
85
86#define SPARSESET_ELT_TYPE unsigned int
87
88typedef struct sparseset_def
89{
90 SPARSESET_ELT_TYPE *dense; /* Dense array. */
91 SPARSESET_ELT_TYPE *sparse; /* Sparse array. */
92 SPARSESET_ELT_TYPE members; /* Number of elements. */
93 SPARSESET_ELT_TYPE size; /* Maximum number of elements. */
94 SPARSESET_ELT_TYPE iter; /* Iterator index. */
95 unsigned char iter_inc; /* Iteration increment amount. */
96 bool iterating;
97 SPARSESET_ELT_TYPE elms[2]; /* Combined dense and sparse arrays. */
98} *sparseset;
99
100#define sparseset_free(MAP) free(MAP)
101extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
102extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
103extern void sparseset_copy (sparseset, sparseset);
104extern void sparseset_and (sparseset, sparseset, sparseset);
105extern void sparseset_and_compl (sparseset, sparseset, sparseset);
106extern void sparseset_ior (sparseset, sparseset, sparseset);
107extern bool sparseset_equal_p (sparseset, sparseset);
108
109/* Operation: S = {}
110 Clear the set of all elements. */
111
112inline void
113sparseset_clear (sparseset s)
114{
115 s->members = 0;
116 s->iterating = false;
117}
118
119/* Return the number of elements currently in the set. */
120
121inline SPARSESET_ELT_TYPE
122sparseset_cardinality (sparseset s)
123{
124 return s->members;
125}
126
127/* Return the maximum number of elements this set can hold. */
128
129inline SPARSESET_ELT_TYPE
130sparseset_size (sparseset s)
131{
132 return s->size;
133}
134
135/* Return true if e is a member of the set S, otherwise return false. */
136
137inline bool
138sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e)
139{
140 SPARSESET_ELT_TYPE idx;
141
142 gcc_checking_assert (e < s->size);
143
144 idx = s->sparse[e];
145
146 return idx < s->members && s->dense[idx] == e;
147}
148
149/* Low level insertion routine not meant for use outside of sparseset.[ch].
150 Assumes E is valid and not already a member of the set S. */
151
152inline void
153sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx)
154{
155 s->sparse[e] = idx;
156 s->dense[idx] = e;
157}
158
159/* Operation: S = S + {e}
160 Insert E into the set S, if it isn't already a member. */
161
162inline void
163sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e)
164{
165 if (!sparseset_bit_p (s, e))
166 sparseset_insert_bit (s, e, idx: s->members++);
167}
168
169/* Return and remove the last member added to the set S. */
170
171inline SPARSESET_ELT_TYPE
172sparseset_pop (sparseset s)
173{
174 SPARSESET_ELT_TYPE mem = s->members;
175
176 gcc_checking_assert (mem != 0);
177
178 s->members = mem - 1;
179 return s->dense[s->members];
180}
181
182inline void
183sparseset_iter_init (sparseset s)
184{
185 s->iter = 0;
186 s->iter_inc = 1;
187 s->iterating = true;
188}
189
190inline bool
191sparseset_iter_p (sparseset s)
192{
193 if (s->iterating && s->iter < s->members)
194 return true;
195 else
196 return s->iterating = false;
197}
198
199inline SPARSESET_ELT_TYPE
200sparseset_iter_elm (sparseset s)
201{
202 return s->dense[s->iter];
203}
204
205inline void
206sparseset_iter_next (sparseset s)
207{
208 s->iter += s->iter_inc;
209 s->iter_inc = 1;
210}
211
212#define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER) \
213 for (sparseset_iter_init (SPARSESET); \
214 sparseset_iter_p (SPARSESET) \
215 && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1); \
216 sparseset_iter_next (SPARSESET))
217
218#endif /* GCC_SPARSESET_H */
219

source code of gcc/sparseset.h