1169689Skan/* Set operations on pointers 2169689Skan Copyright (C) 2004, 2006 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify 7169689Skanit under the terms of the GNU General Public License as published by 8169689Skanthe Free Software Foundation; either version 2, or (at your option) 9169689Skanany later version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, 12169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169689SkanGNU General Public License for more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to 18169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "pointer-set.h" 24169689Skan 25171825Skan/* A pointer set is represented as a simple open-addressing hash 26169689Skan table. Simplifications: The hash code is based on the value of the 27169689Skan pointer, not what it points to. The number of buckets is always a 28169689Skan power of 2. Null pointers are a reserved value. Deletion is not 29171825Skan supported (yet). There is no mechanism for user control of hash 30171825Skan function, equality comparison, initial size, or resizing policy. */ 31169689Skan 32169689Skanstruct pointer_set_t 33169689Skan{ 34169689Skan size_t log_slots; 35169689Skan size_t n_slots; /* n_slots = 2^log_slots */ 36169689Skan size_t n_elements; 37169689Skan 38169689Skan void **slots; 39169689Skan}; 40169689Skan 41169689Skan/* Use the multiplicative method, as described in Knuth 6.4, to obtain 42169689Skan a hash code for P in the range [0, MAX). MAX == 2^LOGMAX. 43169689Skan 44169689Skan Summary of this method: Multiply p by some number A that's 45169689Skan relatively prime to 2^sizeof(size_t). The result is two words. 46169689Skan Discard the most significant word, and return the most significant 47169689Skan N bits of the least significant word. As suggested by Knuth, our 48169689Skan choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi 49169689Skan is the golden ratio. 50169689Skan 51169689Skan We don't need to do anything special for full-width multiplication 52169689Skan because we're only interested in the least significant word of the 53169689Skan product, and unsigned arithmetic in C is modulo the word size. */ 54169689Skan 55169689Skanstatic inline size_t 56169689Skanhash1 (const void *p, unsigned long max, unsigned long logmax) 57169689Skan{ 58169689Skan#if HOST_BITS_PER_LONG == 32 59169689Skan const unsigned long A = 0x9e3779b9u; 60169689Skan#elif HOST_BITS_PER_LONG == 64 61169689Skan const unsigned long A = 0x9e3779b97f4a7c16ul; 62169689Skan#else 63169689Skan const unsigned long A 64169689Skan = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L; 65169689Skan#endif 66169689Skan const unsigned long shift = HOST_BITS_PER_LONG - logmax; 67169689Skan 68169689Skan return ((A * (unsigned long) p) >> shift) & (max - 1); 69169689Skan} 70169689Skan 71169689Skan/* Allocate an empty pointer set. */ 72169689Skanstruct pointer_set_t * 73169689Skanpointer_set_create (void) 74169689Skan{ 75169689Skan struct pointer_set_t *result = XNEW (struct pointer_set_t); 76169689Skan 77169689Skan result->n_elements = 0; 78169689Skan result->log_slots = 8; 79169689Skan result->n_slots = (size_t) 1 << result->log_slots; 80169689Skan 81169689Skan result->slots = XCNEWVEC (void *, result->n_slots); 82169689Skan return result; 83169689Skan} 84169689Skan 85169689Skan/* Reclaims all memory associated with PSET. */ 86169689Skanvoid 87169689Skanpointer_set_destroy (struct pointer_set_t *pset) 88169689Skan{ 89169689Skan XDELETEVEC (pset->slots); 90169689Skan XDELETE (pset); 91169689Skan} 92169689Skan 93169689Skan/* Returns nonzero if PSET contains P. P must be nonnull. 94169689Skan 95169689Skan Collisions are resolved by linear probing. */ 96169689Skanint 97169689Skanpointer_set_contains (struct pointer_set_t *pset, void *p) 98169689Skan{ 99169689Skan size_t n = hash1 (p, pset->n_slots, pset->log_slots); 100169689Skan 101169689Skan while (true) 102169689Skan { 103169689Skan if (pset->slots[n] == p) 104169689Skan return 1; 105169689Skan else if (pset->slots[n] == 0) 106169689Skan return 0; 107169689Skan else 108169689Skan { 109169689Skan ++n; 110169689Skan if (n == pset->n_slots) 111169689Skan n = 0; 112169689Skan } 113169689Skan } 114169689Skan} 115169689Skan 116171825Skan/* Subroutine of pointer_set_insert. Return the insertion slot for P into 117171825Skan an empty element of SLOTS, an array of length N_SLOTS. */ 118171825Skanstatic inline size_t 119169689Skaninsert_aux (void *p, void **slots, size_t n_slots, size_t log_slots) 120169689Skan{ 121169689Skan size_t n = hash1 (p, n_slots, log_slots); 122169689Skan while (true) 123169689Skan { 124171825Skan if (slots[n] == p || slots[n] == 0) 125171825Skan return n; 126169689Skan else 127169689Skan { 128169689Skan ++n; 129169689Skan if (n == n_slots) 130169689Skan n = 0; 131169689Skan } 132169689Skan } 133169689Skan} 134169689Skan 135169689Skan/* Inserts P into PSET if it wasn't already there. Returns nonzero 136169689Skan if it was already there. P must be nonnull. */ 137169689Skanint 138169689Skanpointer_set_insert (struct pointer_set_t *pset, void *p) 139169689Skan{ 140171825Skan size_t n; 141171825Skan 142171825Skan /* For simplicity, expand the set even if P is already there. This can be 143171825Skan superfluous but can happen at most once. */ 144169689Skan if (pset->n_elements > pset->n_slots / 4) 145169689Skan { 146169689Skan size_t new_log_slots = pset->log_slots + 1; 147169689Skan size_t new_n_slots = pset->n_slots * 2; 148169689Skan void **new_slots = XCNEWVEC (void *, new_n_slots); 149169689Skan size_t i; 150169689Skan 151169689Skan for (i = 0; i < pset->n_slots; ++i) 152171825Skan { 153171825Skan void *value = pset->slots[i]; 154171825Skan n = insert_aux (value, new_slots, new_n_slots, new_log_slots); 155171825Skan new_slots[n] = value; 156169689Skan } 157169689Skan 158169689Skan XDELETEVEC (pset->slots); 159169689Skan pset->n_slots = new_n_slots; 160169689Skan pset->log_slots = new_log_slots; 161169689Skan pset->slots = new_slots; 162169689Skan } 163169689Skan 164171825Skan n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots); 165171825Skan if (pset->slots[n]) 166171825Skan return 1; 167171825Skan 168171825Skan pset->slots[n] = p; 169171825Skan ++pset->n_elements; 170169689Skan return 0; 171169689Skan} 172171825Skan 173171825Skan/* Pass each pointer in PSET to the function in FN, together with the fixed 174171825Skan parameter DATA. If FN returns false, the iteration stops. */ 175171825Skan 176171825Skanvoid pointer_set_traverse (struct pointer_set_t *pset, 177171825Skan bool (*fn) (void *, void *), void *data) 178171825Skan{ 179171825Skan size_t i; 180171825Skan for (i = 0; i < pset->n_slots; ++i) 181171825Skan if (pset->slots[i] && !fn (pset->slots[i], data)) 182171825Skan break; 183171825Skan} 184171825Skan 185171825Skan 186171825Skan/* A pointer map is represented the same way as a pointer_set, so 187171825Skan the hash code is based on the address of the key, rather than 188171825Skan its contents. Null keys are a reserved value. Deletion is not 189171825Skan supported (yet). There is no mechanism for user control of hash 190171825Skan function, equality comparison, initial size, or resizing policy. */ 191171825Skan 192171825Skanstruct pointer_map_t 193171825Skan{ 194171825Skan size_t log_slots; 195171825Skan size_t n_slots; /* n_slots = 2^log_slots */ 196171825Skan size_t n_elements; 197171825Skan 198171825Skan void **keys; 199171825Skan void **values; 200171825Skan}; 201171825Skan 202171825Skan/* Allocate an empty pointer map. */ 203171825Skanstruct pointer_map_t * 204171825Skanpointer_map_create (void) 205171825Skan{ 206171825Skan struct pointer_map_t *result = XNEW (struct pointer_map_t); 207171825Skan 208171825Skan result->n_elements = 0; 209171825Skan result->log_slots = 8; 210171825Skan result->n_slots = (size_t) 1 << result->log_slots; 211171825Skan 212171825Skan result->keys = XCNEWVEC (void *, result->n_slots); 213171825Skan result->values = XCNEWVEC (void *, result->n_slots); 214171825Skan return result; 215171825Skan} 216171825Skan 217171825Skan/* Reclaims all memory associated with PMAP. */ 218171825Skanvoid pointer_map_destroy (struct pointer_map_t *pmap) 219171825Skan{ 220171825Skan XDELETEVEC (pmap->keys); 221171825Skan XDELETEVEC (pmap->values); 222171825Skan XDELETE (pmap); 223171825Skan} 224171825Skan 225171825Skan/* Returns a pointer to the value to which P maps, if PMAP contains P. P 226171825Skan must be nonnull. Return NULL if PMAP does not contain P. 227171825Skan 228171825Skan Collisions are resolved by linear probing. */ 229171825Skanvoid ** 230171825Skanpointer_map_contains (struct pointer_map_t *pmap, void *p) 231171825Skan{ 232171825Skan size_t n = hash1 (p, pmap->n_slots, pmap->log_slots); 233171825Skan 234171825Skan while (true) 235171825Skan { 236171825Skan if (pmap->keys[n] == p) 237171825Skan return &pmap->values[n]; 238171825Skan else if (pmap->keys[n] == 0) 239171825Skan return NULL; 240171825Skan else 241171825Skan { 242171825Skan ++n; 243171825Skan if (n == pmap->n_slots) 244171825Skan n = 0; 245171825Skan } 246171825Skan } 247171825Skan} 248171825Skan 249171825Skan/* Inserts P into PMAP if it wasn't already there. Returns a pointer 250171825Skan to the value. P must be nonnull. */ 251171825Skanvoid ** 252171825Skanpointer_map_insert (struct pointer_map_t *pmap, void *p) 253171825Skan{ 254171825Skan size_t n; 255171825Skan 256171825Skan /* For simplicity, expand the map even if P is already there. This can be 257171825Skan superfluous but can happen at most once. */ 258171825Skan if (pmap->n_elements > pmap->n_slots / 4) 259171825Skan { 260171825Skan size_t new_log_slots = pmap->log_slots + 1; 261171825Skan size_t new_n_slots = pmap->n_slots * 2; 262171825Skan void **new_keys = XCNEWVEC (void *, new_n_slots); 263171825Skan void **new_values = XCNEWVEC (void *, new_n_slots); 264171825Skan size_t i; 265171825Skan 266171825Skan for (i = 0; i < pmap->n_slots; ++i) 267171825Skan if (pmap->keys[i]) 268171825Skan { 269171825Skan void *key = pmap->keys[i]; 270171825Skan n = insert_aux (key, new_keys, new_n_slots, new_log_slots); 271171825Skan new_keys[n] = key; 272171825Skan new_values[n] = pmap->values[i]; 273171825Skan } 274171825Skan 275171825Skan XDELETEVEC (pmap->keys); 276171825Skan XDELETEVEC (pmap->values); 277171825Skan pmap->n_slots = new_n_slots; 278171825Skan pmap->log_slots = new_log_slots; 279171825Skan pmap->keys = new_keys; 280171825Skan pmap->values = new_values; 281171825Skan } 282171825Skan 283171825Skan n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots); 284171825Skan if (!pmap->keys[n]) 285171825Skan { 286171825Skan ++pmap->n_elements; 287171825Skan pmap->keys[n] = p; 288171825Skan } 289171825Skan 290171825Skan return &pmap->values[n]; 291171825Skan} 292171825Skan 293171825Skan/* Pass each pointer in PMAP to the function in FN, together with the pointer 294171825Skan to the value and the fixed parameter DATA. If FN returns false, the 295171825Skan iteration stops. */ 296171825Skan 297171825Skanvoid pointer_map_traverse (struct pointer_map_t *pmap, 298171825Skan bool (*fn) (void *, void **, void *), void *data) 299171825Skan{ 300171825Skan size_t i; 301171825Skan for (i = 0; i < pmap->n_slots; ++i) 302171825Skan if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data)) 303171825Skan break; 304171825Skan} 305