1/* Set operations on pointers 2 Copyright (C) 2004 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 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 33struct 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 56static inline size_t 57hash1 (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. */ 73struct pointer_set_t * 74pointer_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. */ 87void pointer_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. Inserts P into an empty 117 element of SLOTS, an array of length N_SLOTS. Returns nonzero 118 if P was already present in N_SLOTS. */ 119static int 120insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots) 121{ 122 size_t n = hash1 (p, n_slots, log_slots); 123 while (true) 124 { 125 if (slots[n] == p) 126 return 1; 127 else if (slots[n] == 0) 128 { 129 slots[n] = p; 130 return 0; 131 } 132 else 133 { 134 ++n; 135 if (n == n_slots) 136 n = 0; 137 } 138 } 139} 140 141/* Inserts P into PSET if it wasn't already there. Returns nonzero 142 if it was already there. P must be nonnull. */ 143int 144pointer_set_insert (struct pointer_set_t *pset, void *p) 145{ 146 if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots)) 147 return 1; 148 149 /* We've inserted a new element. Expand the table if necessary to keep 150 the load factor small. */ 151 ++pset->n_elements; 152 if (pset->n_elements > pset->n_slots / 4) 153 { 154 size_t new_log_slots = pset->log_slots + 1; 155 size_t new_n_slots = pset->n_slots * 2; 156 void **new_slots = XCNEWVEC (void *, new_n_slots); 157 size_t i; 158 159 for (i = 0; i < pset->n_slots; ++i) 160 { 161 if (pset->slots[i]) 162 insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots); 163 } 164 165 XDELETEVEC (pset->slots); 166 pset->n_slots = new_n_slots; 167 pset->log_slots = new_log_slots; 168 pset->slots = new_slots; 169 } 170 171 return 0; 172} 173