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