pointer-set.c revision 169689 
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 sets 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.  There is no mechanism for user control of hash
30   function, equality comparison, initial size, or resizing policy.
31*/
32
33struct pointer_set_t
34{
35  size_t log_slots;
36  size_t n_slots;		/* n_slots = 2^log_slots */
37  size_t n_elements;
38
39  void **slots;
40};
41
42/* Use the multiplicative method, as described in Knuth 6.4, to obtain
43   a hash code for P in the range [0, MAX).  MAX == 2^LOGMAX.
44
45   Summary of this method: Multiply p by some number A that's
46   relatively prime to 2^sizeof(size_t).  The result is two words.
47   Discard the most significant word, and return the most significant
48   N bits of the least significant word.  As suggested by Knuth, our
49   choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
50   is the golden ratio.
51
52   We don't need to do anything special for full-width multiplication
53   because we're only interested in the least significant word of the
54   product, and unsigned arithmetic in C is modulo the word size.  */
55
56static inline size_t
57hash1 (const void *p, unsigned long max, unsigned long logmax)
58{
59#if HOST_BITS_PER_LONG == 32
60  const unsigned long A = 0x9e3779b9u;
61#elif HOST_BITS_PER_LONG == 64
62  const unsigned long A = 0x9e3779b97f4a7c16ul;
63#else
64  const unsigned long A
65    = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L;
66#endif
67  const unsigned long shift = HOST_BITS_PER_LONG - logmax;
68
69  return ((A * (unsigned long) p) >> shift) & (max - 1);
70}
71
72/* Allocate an empty pointer set.  */
73struct pointer_set_t *
74pointer_set_create (void)
75{
76  struct pointer_set_t *result = XNEW (struct pointer_set_t);
77
78  result->n_elements = 0;
79  result->log_slots = 8;
80  result->n_slots = (size_t) 1 << result->log_slots;
81
82  result->slots = XCNEWVEC (void *, result->n_slots);
83  return result;
84}
85
86/* Reclaims all memory associated with PSET.  */
87void
88pointer_set_destroy (struct pointer_set_t *pset)
89{
90  XDELETEVEC (pset->slots);
91  XDELETE (pset);
92}
93
94/* Returns nonzero if PSET contains P.  P must be nonnull.
95
96   Collisions are resolved by linear probing.  */
97int
98pointer_set_contains (struct pointer_set_t *pset, void *p)
99{
100  size_t n = hash1 (p, pset->n_slots, pset->log_slots);
101
102  while (true)
103    {
104      if (pset->slots[n] == p)
105       return 1;
106      else if (pset->slots[n] == 0)
107       return 0;
108      else
109       {
110         ++n;
111         if (n == pset->n_slots)
112           n = 0;
113       }
114    }
115}
116
117/* Subroutine of pointer_set_insert.  Inserts P into an empty
118   element of SLOTS, an array of length N_SLOTS.  Returns nonzero
119   if P was already present in N_SLOTS.  */
120static int
121insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
122{
123  size_t n = hash1 (p, n_slots, log_slots);
124  while (true)
125    {
126      if (slots[n] == p)
127	return 1;
128      else if (slots[n] == 0)
129	{
130	  slots[n] = p;
131	  return 0;
132	}
133      else
134	{
135	  ++n;
136	  if (n == n_slots)
137	    n = 0;
138	}
139    }
140}
141
142/* Inserts P into PSET if it wasn't already there.  Returns nonzero
143   if it was already there. P must be nonnull.  */
144int
145pointer_set_insert (struct pointer_set_t *pset, void *p)
146{
147  if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
148    return 1;
149
150  /* We've inserted a new element.  Expand the table if necessary to keep
151     the load factor small.  */
152  ++pset->n_elements;
153  if (pset->n_elements > pset->n_slots / 4)
154    {
155      size_t new_log_slots = pset->log_slots + 1;
156      size_t new_n_slots = pset->n_slots * 2;
157      void **new_slots = XCNEWVEC (void *, new_n_slots);
158      size_t i;
159
160      for (i = 0; i < pset->n_slots; ++i)
161	{
162	  if (pset->slots[i])
163	    insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
164	}
165
166      XDELETEVEC (pset->slots);
167      pset->n_slots = new_n_slots;
168      pset->log_slots = new_log_slots;
169      pset->slots = new_slots;
170    }
171
172  return 0;
173}
174