Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / sparseset.h
1 /* SparseSet implementation.
2    Copyright (C) 2007-2015 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*HOST_BITS_PER_WIDEST_FAST_INT * 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_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
87 #define SPARSESET_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
88
89 typedef struct sparseset_def
90 {
91   SPARSESET_ELT_TYPE *dense;    /* Dense array.  */
92   SPARSESET_ELT_TYPE *sparse;   /* Sparse array.  */
93   SPARSESET_ELT_TYPE members;   /* Number of elements.  */
94   SPARSESET_ELT_TYPE size;      /* Maximum number of elements.  */
95   SPARSESET_ELT_TYPE iter;      /* Iterator index.  */
96   unsigned char iter_inc;       /* Iteration increment amount.  */
97   bool iterating;
98   SPARSESET_ELT_TYPE elms[2];   /* Combined dense and sparse arrays.  */
99 } *sparseset;
100
101 #define sparseset_free(MAP)  free(MAP)
102 extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
103 extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
104 extern void sparseset_copy (sparseset, sparseset);
105 extern void sparseset_and (sparseset, sparseset, sparseset);
106 extern void sparseset_and_compl (sparseset, sparseset, sparseset);
107 extern void sparseset_ior (sparseset, sparseset, sparseset);
108 extern bool sparseset_equal_p (sparseset, sparseset);
109
110 /* Operation: S = {}
111    Clear the set of all elements.  */
112
113 static inline void
114 sparseset_clear (sparseset s)
115 {
116   s->members = 0;
117   s->iterating = false;
118 }
119
120 /* Return the number of elements currently in the set.  */
121
122 static inline SPARSESET_ELT_TYPE
123 sparseset_cardinality (sparseset s)
124 {
125   return s->members;
126 }
127
128 /* Return the maximum number of elements this set can hold.  */
129
130 static inline SPARSESET_ELT_TYPE
131 sparseset_size (sparseset s)
132 {
133   return s->size;
134 }
135
136 /* Return true if e is a member of the set S, otherwise return false.  */
137
138 static inline bool
139 sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e)
140 {
141   SPARSESET_ELT_TYPE idx;
142
143   gcc_checking_assert (e < s->size);
144
145   idx = s->sparse[e];
146
147   return idx < s->members && s->dense[idx] == e;
148 }
149
150 /* Low level insertion routine not meant for use outside of sparseset.[ch].
151    Assumes E is valid and not already a member of the set S.  */
152
153 static inline void
154 sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx)
155 {
156   s->sparse[e] = idx;
157   s->dense[idx] = e;
158 }
159
160 /* Operation: S = S + {e}
161    Insert E into the set S, if it isn't already a member.  */
162
163 static inline void
164 sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e)
165 {
166   if (!sparseset_bit_p (s, e))
167     sparseset_insert_bit (s, e, s->members++);
168 }
169
170 /* Return and remove the last member added to the set S.  */
171
172 static inline SPARSESET_ELT_TYPE
173 sparseset_pop (sparseset s)
174 {
175   SPARSESET_ELT_TYPE mem = s->members;
176
177   gcc_checking_assert (mem != 0);
178
179   s->members = mem - 1;
180   return s->dense[s->members];
181 }
182
183 static inline void
184 sparseset_iter_init (sparseset s)
185 {
186   s->iter = 0;
187   s->iter_inc = 1;
188   s->iterating = true;
189 }
190
191 static inline bool
192 sparseset_iter_p (sparseset s)
193 {
194   if (s->iterating && s->iter < s->members)
195     return true;
196   else
197     return s->iterating = false;
198 }
199
200 static inline SPARSESET_ELT_TYPE
201 sparseset_iter_elm (sparseset s)
202 {
203   return s->dense[s->iter];
204 }
205
206 static inline void
207 sparseset_iter_next (sparseset s)
208 {
209   s->iter += s->iter_inc;
210   s->iter_inc = 1;
211 }
212
213 #define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER)                    \
214   for (sparseset_iter_init (SPARSESET);                                 \
215        sparseset_iter_p (SPARSESET)                                     \
216        && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1);             \
217        sparseset_iter_next (SPARSESET))
218
219 #endif /* GCC_SPARSESET_H */