]>
Commit | Line | Data |
---|---|---|
0c58f841 | 1 | /* Set operations on pointers |
9dcd6f09 | 2 | Copyright (C) 2004, 2006, 2007 Free Software Foundation, Inc. |
0c58f841 MA |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
9dcd6f09 | 8 | the Free Software Foundation; either version 3, or (at your option) |
0c58f841 MA |
9 | any later version. |
10 | ||
11 | GCC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
0c58f841 MA |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "pointer-set.h" | |
23 | ||
ad12460b | 24 | /* A pointer set is represented as a simple open-addressing hash |
0c58f841 MA |
25 | table. Simplifications: The hash code is based on the value of the |
26 | pointer, not what it points to. The number of buckets is always a | |
27 | power of 2. Null pointers are a reserved value. Deletion is not | |
ad12460b PB |
28 | supported (yet). There is no mechanism for user control of hash |
29 | function, equality comparison, initial size, or resizing policy. */ | |
0c58f841 MA |
30 | |
31 | struct pointer_set_t | |
32 | { | |
33 | size_t log_slots; | |
34 | size_t n_slots; /* n_slots = 2^log_slots */ | |
35 | size_t n_elements; | |
36 | ||
ac7d7749 | 37 | const void **slots; |
0c58f841 MA |
38 | }; |
39 | ||
40 | /* Use the multiplicative method, as described in Knuth 6.4, to obtain | |
41 | a hash code for P in the range [0, MAX). MAX == 2^LOGMAX. | |
42 | ||
43 | Summary of this method: Multiply p by some number A that's | |
44 | relatively prime to 2^sizeof(size_t). The result is two words. | |
45 | Discard the most significant word, and return the most significant | |
46 | N bits of the least significant word. As suggested by Knuth, our | |
bc54ef99 JJ |
47 | choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi |
48 | is the golden ratio. | |
0c58f841 MA |
49 | |
50 | We don't need to do anything special for full-width multiplication | |
51 | because we're only interested in the least significant word of the | |
471854f8 | 52 | product, and unsigned arithmetic in C is modulo the word size. */ |
0c58f841 MA |
53 | |
54 | static inline size_t | |
55 | hash1 (const void *p, unsigned long max, unsigned long logmax) | |
56 | { | |
bc54ef99 | 57 | #if HOST_BITS_PER_LONG == 32 |
0c58f841 | 58 | const unsigned long A = 0x9e3779b9u; |
bc54ef99 JJ |
59 | #elif HOST_BITS_PER_LONG == 64 |
60 | const unsigned long A = 0x9e3779b97f4a7c16ul; | |
61 | #else | |
b4992641 RH |
62 | const unsigned long A |
63 | = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L; | |
bc54ef99 | 64 | #endif |
b4992641 | 65 | const unsigned long shift = HOST_BITS_PER_LONG - logmax; |
0c58f841 MA |
66 | |
67 | return ((A * (unsigned long) p) >> shift) & (max - 1); | |
68 | } | |
69 | ||
471854f8 | 70 | /* Allocate an empty pointer set. */ |
0c58f841 MA |
71 | struct pointer_set_t * |
72 | pointer_set_create (void) | |
73 | { | |
74 | struct pointer_set_t *result = XNEW (struct pointer_set_t); | |
75 | ||
76 | result->n_elements = 0; | |
77 | result->log_slots = 8; | |
78 | result->n_slots = (size_t) 1 << result->log_slots; | |
79 | ||
ac7d7749 | 80 | result->slots = XCNEWVEC (const void *, result->n_slots); |
0c58f841 MA |
81 | return result; |
82 | } | |
83 | ||
471854f8 | 84 | /* Reclaims all memory associated with PSET. */ |
83f676b3 RS |
85 | void |
86 | pointer_set_destroy (struct pointer_set_t *pset) | |
0c58f841 MA |
87 | { |
88 | XDELETEVEC (pset->slots); | |
89 | XDELETE (pset); | |
90 | } | |
91 | ||
af76441f AP |
92 | /* Returns nonzero if PSET contains P. P must be nonnull. |
93 | ||
94 | Collisions are resolved by linear probing. */ | |
95 | int | |
ac7d7749 | 96 | pointer_set_contains (const struct pointer_set_t *pset, const void *p) |
af76441f AP |
97 | { |
98 | size_t n = hash1 (p, pset->n_slots, pset->log_slots); | |
99 | ||
100 | while (true) | |
101 | { | |
102 | if (pset->slots[n] == p) | |
103 | return 1; | |
104 | else if (pset->slots[n] == 0) | |
105 | return 0; | |
106 | else | |
107 | { | |
108 | ++n; | |
109 | if (n == pset->n_slots) | |
110 | n = 0; | |
111 | } | |
112 | } | |
113 | } | |
114 | ||
ad12460b PB |
115 | /* Subroutine of pointer_set_insert. Return the insertion slot for P into |
116 | an empty element of SLOTS, an array of length N_SLOTS. */ | |
117 | static inline size_t | |
ac7d7749 | 118 | insert_aux (const void *p, const void **slots, size_t n_slots, size_t log_slots) |
0c58f841 MA |
119 | { |
120 | size_t n = hash1 (p, n_slots, log_slots); | |
121 | while (true) | |
122 | { | |
ad12460b PB |
123 | if (slots[n] == p || slots[n] == 0) |
124 | return n; | |
0c58f841 MA |
125 | else |
126 | { | |
127 | ++n; | |
128 | if (n == n_slots) | |
129 | n = 0; | |
130 | } | |
131 | } | |
132 | } | |
133 | ||
134 | /* Inserts P into PSET if it wasn't already there. Returns nonzero | |
471854f8 | 135 | if it was already there. P must be nonnull. */ |
0c58f841 | 136 | int |
ac7d7749 | 137 | pointer_set_insert (struct pointer_set_t *pset, const void *p) |
0c58f841 | 138 | { |
ad12460b PB |
139 | size_t n; |
140 | ||
141 | /* For simplicity, expand the set even if P is already there. This can be | |
142 | superfluous but can happen at most once. */ | |
0c58f841 MA |
143 | if (pset->n_elements > pset->n_slots / 4) |
144 | { | |
145 | size_t new_log_slots = pset->log_slots + 1; | |
146 | size_t new_n_slots = pset->n_slots * 2; | |
ac7d7749 | 147 | const void **new_slots = XCNEWVEC (const void *, new_n_slots); |
0c58f841 MA |
148 | size_t i; |
149 | ||
150 | for (i = 0; i < pset->n_slots; ++i) | |
ad12460b | 151 | { |
ac7d7749 | 152 | const void *value = pset->slots[i]; |
ad12460b PB |
153 | n = insert_aux (value, new_slots, new_n_slots, new_log_slots); |
154 | new_slots[n] = value; | |
0c58f841 MA |
155 | } |
156 | ||
157 | XDELETEVEC (pset->slots); | |
158 | pset->n_slots = new_n_slots; | |
159 | pset->log_slots = new_log_slots; | |
160 | pset->slots = new_slots; | |
161 | } | |
162 | ||
ad12460b PB |
163 | n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots); |
164 | if (pset->slots[n]) | |
165 | return 1; | |
166 | ||
167 | pset->slots[n] = p; | |
168 | ++pset->n_elements; | |
0c58f841 MA |
169 | return 0; |
170 | } | |
ad12460b PB |
171 | |
172 | /* Pass each pointer in PSET to the function in FN, together with the fixed | |
173 | parameter DATA. If FN returns false, the iteration stops. */ | |
174 | ||
ac7d7749 KG |
175 | void pointer_set_traverse (const struct pointer_set_t *pset, |
176 | bool (*fn) (const void *, void *), void *data) | |
ad12460b PB |
177 | { |
178 | size_t i; | |
179 | for (i = 0; i < pset->n_slots; ++i) | |
180 | if (pset->slots[i] && !fn (pset->slots[i], data)) | |
181 | break; | |
182 | } | |
183 | ||
184 | \f | |
185 | /* A pointer map is represented the same way as a pointer_set, so | |
186 | the hash code is based on the address of the key, rather than | |
187 | its contents. Null keys are a reserved value. Deletion is not | |
188 | supported (yet). There is no mechanism for user control of hash | |
189 | function, equality comparison, initial size, or resizing policy. */ | |
190 | ||
191 | struct pointer_map_t | |
192 | { | |
193 | size_t log_slots; | |
194 | size_t n_slots; /* n_slots = 2^log_slots */ | |
195 | size_t n_elements; | |
196 | ||
ac7d7749 | 197 | const void **keys; |
ad12460b PB |
198 | void **values; |
199 | }; | |
200 | ||
201 | /* Allocate an empty pointer map. */ | |
202 | struct pointer_map_t * | |
203 | pointer_map_create (void) | |
204 | { | |
205 | struct pointer_map_t *result = XNEW (struct pointer_map_t); | |
206 | ||
207 | result->n_elements = 0; | |
208 | result->log_slots = 8; | |
209 | result->n_slots = (size_t) 1 << result->log_slots; | |
210 | ||
ac7d7749 | 211 | result->keys = XCNEWVEC (const void *, result->n_slots); |
ad12460b PB |
212 | result->values = XCNEWVEC (void *, result->n_slots); |
213 | return result; | |
214 | } | |
215 | ||
216 | /* Reclaims all memory associated with PMAP. */ | |
217 | void pointer_map_destroy (struct pointer_map_t *pmap) | |
218 | { | |
219 | XDELETEVEC (pmap->keys); | |
220 | XDELETEVEC (pmap->values); | |
221 | XDELETE (pmap); | |
222 | } | |
223 | ||
224 | /* Returns a pointer to the value to which P maps, if PMAP contains P. P | |
225 | must be nonnull. Return NULL if PMAP does not contain P. | |
226 | ||
227 | Collisions are resolved by linear probing. */ | |
228 | void ** | |
ac7d7749 | 229 | pointer_map_contains (const struct pointer_map_t *pmap, const void *p) |
ad12460b PB |
230 | { |
231 | size_t n = hash1 (p, pmap->n_slots, pmap->log_slots); | |
232 | ||
233 | while (true) | |
234 | { | |
235 | if (pmap->keys[n] == p) | |
236 | return &pmap->values[n]; | |
237 | else if (pmap->keys[n] == 0) | |
238 | return NULL; | |
239 | else | |
240 | { | |
241 | ++n; | |
242 | if (n == pmap->n_slots) | |
243 | n = 0; | |
244 | } | |
245 | } | |
246 | } | |
247 | ||
248 | /* Inserts P into PMAP if it wasn't already there. Returns a pointer | |
249 | to the value. P must be nonnull. */ | |
250 | void ** | |
ac7d7749 | 251 | pointer_map_insert (struct pointer_map_t *pmap, const void *p) |
ad12460b PB |
252 | { |
253 | size_t n; | |
254 | ||
255 | /* For simplicity, expand the map even if P is already there. This can be | |
256 | superfluous but can happen at most once. */ | |
257 | if (pmap->n_elements > pmap->n_slots / 4) | |
258 | { | |
259 | size_t new_log_slots = pmap->log_slots + 1; | |
260 | size_t new_n_slots = pmap->n_slots * 2; | |
ac7d7749 | 261 | const void **new_keys = XCNEWVEC (const void *, new_n_slots); |
ad12460b PB |
262 | void **new_values = XCNEWVEC (void *, new_n_slots); |
263 | size_t i; | |
264 | ||
265 | for (i = 0; i < pmap->n_slots; ++i) | |
266 | if (pmap->keys[i]) | |
267 | { | |
ac7d7749 | 268 | const void *key = pmap->keys[i]; |
ad12460b PB |
269 | n = insert_aux (key, new_keys, new_n_slots, new_log_slots); |
270 | new_keys[n] = key; | |
271 | new_values[n] = pmap->values[i]; | |
272 | } | |
273 | ||
274 | XDELETEVEC (pmap->keys); | |
275 | XDELETEVEC (pmap->values); | |
276 | pmap->n_slots = new_n_slots; | |
277 | pmap->log_slots = new_log_slots; | |
278 | pmap->keys = new_keys; | |
279 | pmap->values = new_values; | |
280 | } | |
281 | ||
282 | n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots); | |
283 | if (!pmap->keys[n]) | |
284 | { | |
285 | ++pmap->n_elements; | |
286 | pmap->keys[n] = p; | |
287 | } | |
288 | ||
289 | return &pmap->values[n]; | |
290 | } | |
291 | ||
292 | /* Pass each pointer in PMAP to the function in FN, together with the pointer | |
293 | to the value and the fixed parameter DATA. If FN returns false, the | |
294 | iteration stops. */ | |
295 | ||
ac7d7749 KG |
296 | void pointer_map_traverse (const struct pointer_map_t *pmap, |
297 | bool (*fn) (const void *, void **, void *), void *data) | |
ad12460b PB |
298 | { |
299 | size_t i; | |
300 | for (i = 0; i < pmap->n_slots; ++i) | |
301 | if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data)) | |
302 | break; | |
303 | } |