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