Line data Source code
1 : /* SparseSet implementation.
2 : Copyright (C) 2007-2026 Free Software Foundation, Inc.
3 : Contributed by Peter Bergner <bergner@vnet.ibm.com>
4 :
5 : This file is part of GCC.
6 :
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.
11 :
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.
16 :
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/>. */
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 :
88 : typedef 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)
101 : extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
102 : extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
103 : extern void sparseset_copy (sparseset, sparseset);
104 : extern void sparseset_and (sparseset, sparseset, sparseset);
105 : extern void sparseset_and_compl (sparseset, sparseset, sparseset);
106 : extern void sparseset_ior (sparseset, sparseset, sparseset);
107 : extern bool sparseset_equal_p (sparseset, sparseset);
108 :
109 : /* Operation: S = {}
110 : Clear the set of all elements. */
111 :
112 : inline void
113 1439912327 : sparseset_clear (sparseset s)
114 : {
115 1439912327 : s->members = 0;
116 1420339544 : s->iterating = false;
117 46662067 : }
118 :
119 : /* Return the number of elements currently in the set. */
120 :
121 : inline SPARSESET_ELT_TYPE
122 178166303 : sparseset_cardinality (sparseset s)
123 : {
124 146323589 : return s->members;
125 : }
126 :
127 : /* Return the maximum number of elements this set can hold. */
128 :
129 : inline SPARSESET_ELT_TYPE
130 : sparseset_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 :
137 : inline bool
138 9975118216 : sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e)
139 : {
140 9975118216 : SPARSESET_ELT_TYPE idx;
141 :
142 9975118216 : gcc_checking_assert (e < s->size);
143 :
144 9975118216 : idx = s->sparse[e];
145 :
146 9975118216 : 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 :
152 : inline void
153 5272393578 : sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx)
154 : {
155 5272393578 : s->sparse[e] = idx;
156 5038323561 : s->dense[idx] = e;
157 4195090492 : }
158 :
159 : /* Operation: S = S + {e}
160 : Insert E into the set S, if it isn't already a member. */
161 :
162 : inline void
163 4451969236 : sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e)
164 : {
165 4451969236 : if (!sparseset_bit_p (s, e))
166 4195090492 : sparseset_insert_bit (s, e, s->members++);
167 4451969236 : }
168 :
169 : /* Return and remove the last member added to the set S. */
170 :
171 : inline SPARSESET_ELT_TYPE
172 : sparseset_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 :
182 : inline void
183 1747512185 : sparseset_iter_init (sparseset s)
184 : {
185 1747512185 : s->iter = 0;
186 1747512185 : s->iter_inc = 1;
187 1747512185 : s->iterating = true;
188 1747512185 : }
189 :
190 : inline bool
191 5219355779 : sparseset_iter_p (sparseset s)
192 : {
193 5219355779 : if (s->iterating && s->iter < s->members)
194 : return true;
195 : else
196 1544296334 : return s->iterating = false;
197 : }
198 :
199 : inline SPARSESET_ELT_TYPE
200 3675059445 : sparseset_iter_elm (sparseset s)
201 : {
202 3411526929 : return s->dense[s->iter];
203 : }
204 :
205 : inline void
206 3471843594 : sparseset_iter_next (sparseset s)
207 : {
208 3471843594 : s->iter += s->iter_inc;
209 3471843594 : s->iter_inc = 1;
210 3471843594 : }
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 */
|
