]>
Commit | Line | Data |
---|---|---|
b4da855a | 1 | /* SparseSet implementation. |
7adcbafe | 2 | Copyright (C) 2007-2022 Free Software Foundation, Inc. |
b4da855a PB |
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 | ||
0263463d SB |
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 | |
22a6d99d | 79 | set for the same universe are 2 * sizeof (SPARSESET_ELT_TYPE) * 8 * S). |
0263463d SB |
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. */ | |
b4da855a PB |
83 | |
84 | /* Data Structure used for the SparseSet representation. */ | |
85 | ||
22a6d99d | 86 | #define SPARSESET_ELT_TYPE unsigned int |
0263463d | 87 | |
b4da855a PB |
88 | typedef struct sparseset_def |
89 | { | |
90 | SPARSESET_ELT_TYPE *dense; /* Dense array. */ | |
59b130b3 | 91 | SPARSESET_ELT_TYPE *sparse; /* Sparse array. */ |
b4da855a PB |
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 | static inline void | |
113 | sparseset_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 | ||
121 | static inline SPARSESET_ELT_TYPE | |
122 | sparseset_cardinality (sparseset s) | |
123 | { | |
124 | return s->members; | |
125 | } | |
126 | ||
127 | /* Return the maximum number of elements this set can hold. */ | |
128 | ||
129 | static 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 | static inline bool | |
138 | sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e) | |
139 | { | |
140 | SPARSESET_ELT_TYPE idx; | |
141 | ||
11452e7b | 142 | gcc_checking_assert (e < s->size); |
b4da855a PB |
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 | ||
152 | static inline void | |
153 | sparseset_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 | ||
162 | static inline void | |
163 | sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e) | |
164 | { | |
165 | if (!sparseset_bit_p (s, e)) | |
166 | sparseset_insert_bit (s, e, s->members++); | |
167 | } | |
168 | ||
0263463d | 169 | /* Return and remove the last member added to the set S. */ |
b4da855a PB |
170 | |
171 | static inline SPARSESET_ELT_TYPE | |
172 | sparseset_pop (sparseset s) | |
173 | { | |
174 | SPARSESET_ELT_TYPE mem = s->members; | |
175 | ||
11452e7b | 176 | gcc_checking_assert (mem != 0); |
b4da855a PB |
177 | |
178 | s->members = mem - 1; | |
ad43b47a | 179 | return s->dense[s->members]; |
b4da855a PB |
180 | } |
181 | ||
182 | static inline void | |
183 | sparseset_iter_init (sparseset s) | |
184 | { | |
185 | s->iter = 0; | |
186 | s->iter_inc = 1; | |
187 | s->iterating = true; | |
188 | } | |
189 | ||
190 | static inline bool | |
191 | sparseset_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 | ||
199 | static inline SPARSESET_ELT_TYPE | |
200 | sparseset_iter_elm (sparseset s) | |
201 | { | |
202 | return s->dense[s->iter]; | |
203 | } | |
204 | ||
205 | static inline void | |
206 | sparseset_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 */ |