OSDN Git Service

5daf88bd0bcec082d1524a96e809ab81e9dbd753
[pf3gnuchains/gcc-fork.git] / gcc / pointer-set.c
1 /* Set operations on pointers
2    Copyright (C) 2004, 2006 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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 2, or (at your option)
9 any later version.
10
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.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, 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
33 struct 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
56 static inline size_t
57 hash1 (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.  */
73 struct pointer_set_t *
74 pointer_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.  */
87 void
88 pointer_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.  */
97 int
98 pointer_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.  */
120 static int
121 insert_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.  */
144 int
145 pointer_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 }