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