hash.c revision 1.56
1 /* $NetBSD: hash.c,v 1.56 2020/11/05 17:27:16 rillig Exp $ */ 2 3 /* 4 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Adam de Boor. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 /* 36 * Copyright (c) 1988, 1989 by Adam de Boor 37 * Copyright (c) 1989 by Berkeley Softworks 38 * All rights reserved. 39 * 40 * This code is derived from software contributed to Berkeley by 41 * Adam de Boor. 42 * 43 * Redistribution and use in source and binary forms, with or without 44 * modification, are permitted provided that the following conditions 45 * are met: 46 * 1. Redistributions of source code must retain the above copyright 47 * notice, this list of conditions and the following disclaimer. 48 * 2. Redistributions in binary form must reproduce the above copyright 49 * notice, this list of conditions and the following disclaimer in the 50 * documentation and/or other materials provided with the distribution. 51 * 3. All advertising materials mentioning features or use of this software 52 * must display the following acknowledgement: 53 * This product includes software developed by the University of 54 * California, Berkeley and its contributors. 55 * 4. Neither the name of the University nor the names of its contributors 56 * may be used to endorse or promote products derived from this software 57 * without specific prior written permission. 58 * 59 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 60 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 61 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 62 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 63 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 64 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 65 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 66 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 67 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 68 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 69 * SUCH DAMAGE. 70 */ 71 72 /* Hash tables with string keys. */ 73 74 #include "make.h" 75 76 /* "@(#)hash.c 8.1 (Berkeley) 6/6/93" */ 77 MAKE_RCSID("$NetBSD: hash.c,v 1.56 2020/11/05 17:27:16 rillig Exp $"); 78 79 /* 80 * The ratio of # entries to # buckets at which we rebuild the table to 81 * make it larger. 82 */ 83 #define rebuildLimit 3 84 85 /* This hash function matches Gosling's emacs and java.lang.String. */ 86 static unsigned int 87 hash(const char *key, size_t *out_keylen) 88 { 89 unsigned int h = 0; 90 const char *p = key; 91 while (*p != '\0') 92 h = (h << 5) - h + (unsigned char)*p++; 93 if (out_keylen != NULL) 94 *out_keylen = (size_t)(p - key); 95 return h; 96 } 97 98 unsigned int 99 Hash_Hash(const char *key) 100 { 101 return hash(key, NULL); 102 } 103 104 static HashEntry * 105 HashTable_Find(HashTable *t, unsigned int h, const char *key) 106 { 107 HashEntry *e; 108 unsigned int chainlen = 0; 109 110 #ifdef DEBUG_HASH_LOOKUP 111 DEBUG4(HASH, "%s: %p h=%08x key=%s\n", __func__, t, h, key); 112 #endif 113 114 for (e = t->buckets[h & t->bucketsMask]; e != NULL; e = e->next) { 115 chainlen++; 116 if (e->key_hash == h && strcmp(e->key, key) == 0) 117 break; 118 } 119 120 if (chainlen > t->maxchain) 121 t->maxchain = chainlen; 122 123 return e; 124 } 125 126 /* Set up the hash table. */ 127 void 128 HashTable_Init(HashTable *t) 129 { 130 unsigned int n = 16, i; 131 HashEntry **buckets = bmake_malloc(sizeof *buckets * n); 132 for (i = 0; i < n; i++) 133 buckets[i] = NULL; 134 135 t->buckets = buckets; 136 t->bucketsSize = n; 137 t->numEntries = 0; 138 t->bucketsMask = n - 1; 139 t->maxchain = 0; 140 } 141 142 /* Remove everything from the hash table and frees up the memory. */ 143 void 144 HashTable_Done(HashTable *t) 145 { 146 HashEntry **buckets = t->buckets; 147 size_t i, n = t->bucketsSize; 148 149 for (i = 0; i < n; i++) { 150 HashEntry *he = buckets[i]; 151 while (he != NULL) { 152 HashEntry *next = he->next; 153 free(he); 154 he = next; 155 } 156 } 157 free(t->buckets); 158 159 #ifdef CLEANUP 160 t->buckets = NULL; 161 #endif 162 } 163 164 /* Find the entry corresponding to the key, or return NULL. */ 165 HashEntry * 166 HashTable_FindEntry(HashTable *t, const char *key) 167 { 168 unsigned int h = hash(key, NULL); 169 return HashTable_Find(t, h, key); 170 } 171 172 /* Find the value corresponding to the key, or return NULL. */ 173 void * 174 HashTable_FindValue(HashTable *t, const char *key) 175 { 176 HashEntry *he = HashTable_FindEntry(t, key); 177 return he != NULL ? he->value : NULL; 178 } 179 180 /* Find the value corresponding to the key and the precomputed hash, 181 * or return NULL. */ 182 void * 183 HashTable_FindValueHash(HashTable *t, const char *key, unsigned int h) 184 { 185 HashEntry *he = HashTable_Find(t, h, key); 186 return he != NULL ? he->value : NULL; 187 } 188 189 /* Make the hash table larger. Any bucket numbers from the old table become 190 * invalid; the hash codes stay valid though. */ 191 static void 192 HashTable_Enlarge(HashTable *t) 193 { 194 unsigned int oldSize = t->bucketsSize; 195 HashEntry **oldBuckets = t->buckets; 196 unsigned int newSize = 2 * oldSize; 197 unsigned int newMask = newSize - 1; 198 HashEntry **newBuckets = bmake_malloc(sizeof *newBuckets * newSize); 199 size_t i; 200 201 for (i = 0; i < newSize; i++) 202 newBuckets[i] = NULL; 203 204 for (i = 0; i < oldSize; i++) { 205 HashEntry *he = oldBuckets[i]; 206 while (he != NULL) { 207 HashEntry *next = he->next; 208 he->next = newBuckets[he->key_hash & newMask]; 209 newBuckets[he->key_hash & newMask] = he; 210 he = next; 211 } 212 } 213 214 free(oldBuckets); 215 216 t->bucketsSize = newSize; 217 t->bucketsMask = newMask; 218 t->buckets = newBuckets; 219 DEBUG5(HASH, "%s: %p size=%d entries=%d maxchain=%d\n", 220 __func__, t, t->bucketsSize, t->numEntries, t->maxchain); 221 t->maxchain = 0; 222 } 223 224 /* Find or create an entry corresponding to the key. 225 * Return in out_isNew whether a new entry has been created. */ 226 HashEntry * 227 HashTable_CreateEntry(HashTable *t, const char *key, Boolean *out_isNew) 228 { 229 size_t keylen; 230 unsigned int h = hash(key, &keylen); 231 HashEntry *he = HashTable_Find(t, h, key); 232 233 if (he != NULL) { 234 if (out_isNew != NULL) 235 *out_isNew = FALSE; 236 return he; 237 } 238 239 if (t->numEntries >= rebuildLimit * t->bucketsSize) 240 HashTable_Enlarge(t); 241 242 he = bmake_malloc(sizeof *he + keylen); 243 he->value = NULL; 244 he->key_hash = h; 245 memcpy(he->key, key, keylen + 1); 246 247 he->next = t->buckets[h & t->bucketsMask]; 248 t->buckets[h & t->bucketsMask] = he; 249 t->numEntries++; 250 251 if (out_isNew != NULL) 252 *out_isNew = TRUE; 253 return he; 254 } 255 256 /* Delete the entry from the table and free the associated memory. */ 257 void 258 HashTable_DeleteEntry(HashTable *t, HashEntry *he) 259 { 260 HashEntry **ref = &t->buckets[he->key_hash & t->bucketsMask]; 261 HashEntry *p; 262 263 for (; (p = *ref) != NULL; ref = &p->next) { 264 if (p == he) { 265 *ref = p->next; 266 free(p); 267 t->numEntries--; 268 return; 269 } 270 } 271 abort(); 272 } 273 274 /* Set things up for iterating over all entries in the hash table. */ 275 void 276 HashIter_Init(HashIter *hi, HashTable *t) 277 { 278 hi->table = t; 279 hi->nextBucket = 0; 280 hi->entry = NULL; 281 } 282 283 /* Return the next entry in the hash table, or NULL if the end of the table 284 * is reached. */ 285 HashEntry * 286 HashIter_Next(HashIter *hi) 287 { 288 HashTable *t = hi->table; 289 HashEntry *he = hi->entry; 290 HashEntry **buckets = t->buckets; 291 unsigned int bucketsSize = t->bucketsSize; 292 293 if (he != NULL) 294 he = he->next; /* skip the most recently returned entry */ 295 296 while (he == NULL) { /* find the next nonempty chain */ 297 if (hi->nextBucket >= bucketsSize) 298 return NULL; 299 he = buckets[hi->nextBucket++]; 300 } 301 hi->entry = he; 302 return he; 303 } 304 305 void 306 HashTable_DebugStats(HashTable *t, const char *name) 307 { 308 DEBUG4(HASH, "HashTable %s: size=%u numEntries=%u maxchain=%u\n", 309 name, t->bucketsSize, t->numEntries, t->maxchain); 310 } 311
Indexes created Thu Sep 25 16:09:42 GMT 2025