1 /* Set operations on pointers
2 Copyright (C) 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
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)
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.
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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "pointer-set.h"
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.
36 size_t n_slots; /* n_slots = 2^log_slots */
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.
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 2^32 / phi, where phi is the
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. */
57 hash1 (const void *p, unsigned long max, unsigned long logmax)
59 const unsigned long A = 0x9e3779b9u;
60 const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - logmax;
62 return ((A * (unsigned long) p) >> shift) & (max - 1);
65 /* Allocate an empty pointer set. */
66 struct pointer_set_t *
67 pointer_set_create (void)
69 struct pointer_set_t *result = XNEW (struct pointer_set_t);
71 result->n_elements = 0;
72 result->log_slots = 8;
73 result->n_slots = (size_t) 1 << result->log_slots;
75 result->slots = XCNEWVEC (void *, result->n_slots);
79 /* Reclaims all memory associated with PSET. */
80 void pointer_set_destroy (struct pointer_set_t *pset)
82 XDELETEVEC (pset->slots);
86 /* Returns nonzero if PSET contains P. P must be nonnull.
88 Collisions are resolved by linear probing. More complicated
89 collision management schemes are only useful when the load factor
90 significantly exceeds 0.5, and we never let that happen. */
92 pointer_set_contains (struct pointer_set_t *pset, void *p)
94 size_t n = hash1 (p, pset->n_slots, pset->log_slots);
98 if (pset->slots[n] == p)
100 else if (pset->slots[n] == 0)
105 if (n == pset->n_slots)
111 /* Subroutine of pointer_set_insert. Inserts P into an empty
112 element of SLOTS, an array of length N_SLOTS. Returns nonzero
113 if P was already present in N_SLOTS. */
115 insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
117 size_t n = hash1 (p, n_slots, log_slots);
122 else if (slots[n] == 0)
136 /* Inserts P into PSET if it wasn't already there. Returns nonzero
137 if it was already there. P must be nonnull. */
139 pointer_set_insert (struct pointer_set_t *pset, void *p)
141 if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
144 /* We've inserted a new element. Expand the table if necessary to keep
145 the load factor small. */
147 if (pset->n_elements > pset->n_slots / 4)
149 size_t new_log_slots = pset->log_slots + 1;
150 size_t new_n_slots = pset->n_slots * 2;
151 void **new_slots = XCNEWVEC (void *, new_n_slots);
154 for (i = 0; i < pset->n_slots; ++i)
157 insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
160 XDELETEVEC (pset->slots);
161 pset->n_slots = new_n_slots;
162 pset->log_slots = new_log_slots;
163 pset->slots = new_slots;