Mercurial > hg > CbC > CbC_gcc

comparison gcc/sparseset.h @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children f6334be47118
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* SparseSet implementation.
2 Copyright (C) 2007 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 #include <assert.h>
25
26 #define SPARSESET_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
27 #define SPARSESET_ELT_TYPE unsigned int
28
29 /* Data Structure used for the SparseSet representation. */
30
31 typedef struct sparseset_def
32 {
33 SPARSESET_ELT_TYPE *dense; /* Dense array. */
34 SPARSESET_ELT_TYPE *sparse; /* Sparse array. */
35 SPARSESET_ELT_TYPE members; /* Number of elements. */
36 SPARSESET_ELT_TYPE size; /* Maximum number of elements. */
37 SPARSESET_ELT_TYPE iter; /* Iterator index. */
38 unsigned char iter_inc; /* Iteration increment amount. */
39 bool iterating;
40 SPARSESET_ELT_TYPE elms[2]; /* Combined dense and sparse arrays. */
41 } *sparseset;
42
43 #define sparseset_free(MAP) free(MAP)
44 extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
45 extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
46 extern void sparseset_copy (sparseset, sparseset);
47 extern void sparseset_and (sparseset, sparseset, sparseset);
48 extern void sparseset_and_compl (sparseset, sparseset, sparseset);
49 extern void sparseset_ior (sparseset, sparseset, sparseset);
50 extern bool sparseset_equal_p (sparseset, sparseset);
51
52 /* Operation: S = {}
53 Clear the set of all elements. */
54
55 static inline void
56 sparseset_clear (sparseset s)
57 {
58 s->members = 0;
59 s->iterating = false;
60 }
61
62 /* Return the number of elements currently in the set. */
63
64 static inline SPARSESET_ELT_TYPE
65 sparseset_cardinality (sparseset s)
66 {
67 return s->members;
68 }
69
70 /* Return the maximum number of elements this set can hold. */
71
72 static inline SPARSESET_ELT_TYPE
73 sparseset_size (sparseset s)
74 {
75 return s->size;
76 }
77
78 /* Return true if e is a member of the set S, otherwise return false. */
79
80 static inline bool
81 sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e)
82 {
83 SPARSESET_ELT_TYPE idx;
84
85 gcc_assert (e < s->size);
86
87 idx = s->sparse[e];
88
89 return idx < s->members && s->dense[idx] == e;
90 }
91
92 /* Low level insertion routine not meant for use outside of sparseset.[ch].
93 Assumes E is valid and not already a member of the set S. */
94
95 static inline void
96 sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx)
97 {
98 s->sparse[e] = idx;
99 s->dense[idx] = e;
100 }
101
102 /* Operation: S = S + {e}
103 Insert E into the set S, if it isn't already a member. */
104
105 static inline void
106 sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e)
107 {
108 if (!sparseset_bit_p (s, e))
109 sparseset_insert_bit (s, e, s->members++);
110 }
111
112 /* Return and remove an arbitrary element from the set S. */
113
114 static inline SPARSESET_ELT_TYPE
115 sparseset_pop (sparseset s)
116 {
117 SPARSESET_ELT_TYPE mem = s->members;
118
119 gcc_assert (mem != 0);
120
121 s->members = mem - 1;
122 return s->dense[mem];
123 }
124
125 static inline void
126 sparseset_iter_init (sparseset s)
127 {
128 s->iter = 0;
129 s->iter_inc = 1;
130 s->iterating = true;
131 }
132
133 static inline bool
134 sparseset_iter_p (sparseset s)
135 {
136 if (s->iterating && s->iter < s->members)
137 return true;
138 else
139 return s->iterating = false;
140 }
141
142 static inline SPARSESET_ELT_TYPE
143 sparseset_iter_elm (sparseset s)
144 {
145 return s->dense[s->iter];
146 }
147
148 static inline void
149 sparseset_iter_next (sparseset s)
150 {
151 s->iter += s->iter_inc;
152 s->iter_inc = 1;
153 }
154
155 #define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER) \
156 for (sparseset_iter_init (SPARSESET); \
157 sparseset_iter_p (SPARSESET) \
158 && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1); \
159 sparseset_iter_next (SPARSESET))
160
161 #endif /* GCC_SPARSESET_H */