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