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