xref: /dflybsd-src/contrib/gcc-4.7/gcc/pointer-set.c (revision 81fc95a5293ee307c688a350a3feb4734aaddbb4)
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