Daily bump.
[official-gcc.git] / gcc / pointer-set.c
blobb57c404f6a1a5ead17e45ba7c2ae1f0d5f054234
1 /* Set operations on pointers
2 Copyright (C) 2004, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
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
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "pointer-set.h"
24 /* A pointer set is represented as a simple open-addressing hash
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
28 supported (yet). There is no mechanism for user control of hash
29 function, equality comparison, initial size, or resizing policy. */
31 struct pointer_set_t
33 size_t log_slots;
34 size_t n_slots; /* n_slots = 2^log_slots */
35 size_t n_elements;
37 const void **slots;
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.
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
47 choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
48 is the golden ratio.
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
52 product, and unsigned arithmetic in C is modulo the word size. */
54 static inline size_t
55 hash1 (const void *p, unsigned long max, unsigned long logmax)
57 #if HOST_BITS_PER_LONG == 32
58 const unsigned long A = 0x9e3779b9u;
59 #elif HOST_BITS_PER_LONG == 64
60 const unsigned long A = 0x9e3779b97f4a7c16ul;
61 #else
62 const unsigned long A
63 = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L;
64 #endif
65 const unsigned long shift = HOST_BITS_PER_LONG - logmax;
67 return ((A * (unsigned long) p) >> shift) & (max - 1);
70 /* Allocate an empty pointer set. */
71 struct pointer_set_t *
72 pointer_set_create (void)
74 struct pointer_set_t *result = XNEW (struct pointer_set_t);
76 result->n_elements = 0;
77 result->log_slots = 8;
78 result->n_slots = (size_t) 1 << result->log_slots;
80 result->slots = XCNEWVEC (const void *, result->n_slots);
81 return result;
84 /* Reclaims all memory associated with PSET. */
85 void
86 pointer_set_destroy (struct pointer_set_t *pset)
88 XDELETEVEC (pset->slots);
89 XDELETE (pset);
92 /* Returns nonzero if PSET contains P. P must be nonnull.
94 Collisions are resolved by linear probing. */
95 int
96 pointer_set_contains (const struct pointer_set_t *pset, const void *p)
98 size_t n = hash1 (p, pset->n_slots, pset->log_slots);
100 while (true)
102 if (pset->slots[n] == p)
103 return 1;
104 else if (pset->slots[n] == 0)
105 return 0;
106 else
108 ++n;
109 if (n == pset->n_slots)
110 n = 0;
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
118 insert_aux (const void *p, const void **slots, size_t n_slots, size_t log_slots)
120 size_t n = hash1 (p, n_slots, log_slots);
121 while (true)
123 if (slots[n] == p || slots[n] == 0)
124 return n;
125 else
127 ++n;
128 if (n == n_slots)
129 n = 0;
134 /* Inserts P into PSET if it wasn't already there. Returns nonzero
135 if it was already there. P must be nonnull. */
137 pointer_set_insert (struct pointer_set_t *pset, const void *p)
139 size_t n;
141 /* For simplicity, expand the set even if P is already there. This can be
142 superfluous but can happen at most once. */
143 if (pset->n_elements > pset->n_slots / 4)
145 size_t new_log_slots = pset->log_slots + 1;
146 size_t new_n_slots = pset->n_slots * 2;
147 const void **new_slots = XCNEWVEC (const void *, new_n_slots);
148 size_t i;
150 for (i = 0; i < pset->n_slots; ++i)
152 const void *value = pset->slots[i];
153 n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
154 new_slots[n] = value;
157 XDELETEVEC (pset->slots);
158 pset->n_slots = new_n_slots;
159 pset->log_slots = new_log_slots;
160 pset->slots = new_slots;
163 n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots);
164 if (pset->slots[n])
165 return 1;
167 pset->slots[n] = p;
168 ++pset->n_elements;
169 return 0;
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. */
175 void pointer_set_traverse (const struct pointer_set_t *pset,
176 bool (*fn) (const void *, void *), void *data)
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;
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. */
191 struct pointer_map_t
193 size_t log_slots;
194 size_t n_slots; /* n_slots = 2^log_slots */
195 size_t n_elements;
197 const void **keys;
198 void **values;
201 /* Allocate an empty pointer map. */
202 struct pointer_map_t *
203 pointer_map_create (void)
205 struct pointer_map_t *result = XNEW (struct pointer_map_t);
207 result->n_elements = 0;
208 result->log_slots = 8;
209 result->n_slots = (size_t) 1 << result->log_slots;
211 result->keys = XCNEWVEC (const void *, result->n_slots);
212 result->values = XCNEWVEC (void *, result->n_slots);
213 return result;
216 /* Reclaims all memory associated with PMAP. */
217 void pointer_map_destroy (struct pointer_map_t *pmap)
219 XDELETEVEC (pmap->keys);
220 XDELETEVEC (pmap->values);
221 XDELETE (pmap);
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.
227 Collisions are resolved by linear probing. */
228 void **
229 pointer_map_contains (const struct pointer_map_t *pmap, const void *p)
231 size_t n = hash1 (p, pmap->n_slots, pmap->log_slots);
233 while (true)
235 if (pmap->keys[n] == p)
236 return &pmap->values[n];
237 else if (pmap->keys[n] == 0)
238 return NULL;
239 else
241 ++n;
242 if (n == pmap->n_slots)
243 n = 0;
248 /* Inserts P into PMAP if it wasn't already there. Returns a pointer
249 to the value. P must be nonnull. */
250 void **
251 pointer_map_insert (struct pointer_map_t *pmap, const void *p)
253 size_t n;
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)
259 size_t new_log_slots = pmap->log_slots + 1;
260 size_t new_n_slots = pmap->n_slots * 2;
261 const void **new_keys = XCNEWVEC (const void *, new_n_slots);
262 void **new_values = XCNEWVEC (void *, new_n_slots);
263 size_t i;
265 for (i = 0; i < pmap->n_slots; ++i)
266 if (pmap->keys[i])
268 const void *key = pmap->keys[i];
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];
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;
282 n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots);
283 if (!pmap->keys[n])
285 ++pmap->n_elements;
286 pmap->keys[n] = p;
289 return &pmap->values[n];
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. */
296 void pointer_map_traverse (const struct pointer_map_t *pmap,
297 bool (*fn) (const void *, void **, void *), void *data)
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;