Annotation of src/usr.bin/make/hash.c, Revision 1.49
1.49 ! rillig 1: /* $NetBSD: hash.c,v 1.48 2020/10/25 17:01:05 rillig Exp $ */
1.5 christos 2:
1.1 cgd 3: /*
4: * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
1.12 agc 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: /*
1.1 cgd 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:
1.34 rillig 72: /*
73: * This module contains routines to manipulate a hash table.
74: * See hash.h for a definition of the structure of the hash
75: * table. Hash tables grow automatically as the amount of
76: * information increases.
1.1 cgd 77: */
1.34 rillig 78:
1.4 cgd 79: #include "make.h"
1.1 cgd 80:
1.32 rillig 81: /* "@(#)hash.c 8.1 (Berkeley) 6/6/93" */
1.49 ! rillig 82: MAKE_RCSID("$NetBSD: hash.c,v 1.48 2020/10/25 17:01:05 rillig Exp $");
1.32 rillig 83:
1.1 cgd 84: /*
1.43 rillig 85: * The ratio of # entries to # buckets at which we rebuild the table to
86: * make it larger.
1.1 cgd 87: */
1.43 rillig 88: #define rebuildLimit 3
1.1 cgd 89:
1.43 rillig 90: /* This hash function matches Gosling's emacs. */
91: static unsigned int
92: hash(const char *key, size_t *out_keylen)
93: {
94: unsigned h = 0;
95: const char *p = key;
96: while (*p != '\0')
97: h = (h << 5) - h + (unsigned char)*p++;
98: if (out_keylen != NULL)
99: *out_keylen = (size_t)(p - key);
100: return h;
101: }
1.23 sjg 102:
1.48 rillig 103: unsigned int
104: Hash_Hash(const char *key)
105: {
106: return hash(key, NULL);
107: }
108:
1.46 rillig 109: static HashEntry *
110: HashTable_Find(HashTable *t, unsigned int h, const char *key)
1.43 rillig 111: {
1.46 rillig 112: HashEntry *e;
1.44 rillig 113: unsigned int chainlen = 0;
1.41 rillig 114:
1.43 rillig 115: #ifdef DEBUG_HASH_LOOKUP
116: DEBUG4(HASH, "%s: %p h=%x key=%s\n", __func__, t, h, key);
117: #endif
1.41 rillig 118:
1.43 rillig 119: for (e = t->buckets[h & t->bucketsMask]; e != NULL; e = e->next) {
120: chainlen++;
1.47 rillig 121: if (e->key_hash == h && strcmp(e->key, key) == 0)
1.43 rillig 122: break;
123: }
1.41 rillig 124:
1.43 rillig 125: if (chainlen > t->maxchain)
126: t->maxchain = chainlen;
1.41 rillig 127:
1.43 rillig 128: return e;
129: }
1.41 rillig 130:
1.43 rillig 131: /* Sets up the hash table. */
1.1 cgd 132: void
1.46 rillig 133: Hash_InitTable(HashTable *t)
1.1 cgd 134: {
1.44 rillig 135: unsigned int n = 16, i;
1.46 rillig 136: HashEntry **hp;
1.1 cgd 137:
138: t->numEntries = 0;
1.25 sjg 139: t->maxchain = 0;
1.31 rillig 140: t->bucketsSize = n;
141: t->bucketsMask = n - 1;
142: t->buckets = hp = bmake_malloc(sizeof(*hp) * n);
143: for (i = 0; i < n; i++)
144: hp[i] = NULL;
1.1 cgd 145: }
146:
1.28 rillig 147: /* Removes everything from the hash table and frees up the memory space it
1.46 rillig 148: * occupied (except for the space in the HashTable structure). */
1.1 cgd 149: void
1.46 rillig 150: Hash_DeleteTable(HashTable *t)
1.1 cgd 151: {
1.46 rillig 152: HashEntry **hp, *h, *nexth = NULL;
1.10 wiz 153: int i;
1.1 cgd 154:
1.44 rillig 155: for (hp = t->buckets, i = (int)t->bucketsSize; --i >= 0;) {
1.1 cgd 156: for (h = *hp++; h != NULL; h = nexth) {
157: nexth = h->next;
1.16 christos 158: free(h);
1.1 cgd 159: }
160: }
1.29 rillig 161: free(t->buckets);
1.1 cgd 162:
163: /*
164: * Set up the hash table to cause memory faults on any future access
1.6 christos 165: * attempts until re-initialization.
1.1 cgd 166: */
1.29 rillig 167: t->buckets = NULL;
1.1 cgd 168: }
169:
1.28 rillig 170: /* Searches the hash table for an entry corresponding to the key.
1.1 cgd 171: *
1.10 wiz 172: * Input:
173: * t Hash table to search.
174: * key A hash key.
175: *
1.1 cgd 176: * Results:
1.28 rillig 177: * Returns a pointer to the entry for key, or NULL if the table contains
178: * no entry for the key.
1.1 cgd 179: */
1.46 rillig 180: HashEntry *
181: Hash_FindEntry(HashTable *t, const char *key)
1.1 cgd 182: {
1.43 rillig 183: unsigned int h = hash(key, NULL);
184: return HashTable_Find(t, h, key);
1.1 cgd 185: }
186:
1.33 rillig 187: void *
1.46 rillig 188: Hash_FindValue(HashTable *t, const char *key)
1.33 rillig 189: {
1.46 rillig 190: HashEntry *he = Hash_FindEntry(t, key);
1.43 rillig 191: return he != NULL ? he->value : NULL;
192: }
193:
1.48 rillig 194: void *
195: Hash_FindValueHash(HashTable *t, const char *key, unsigned int h)
196: {
197: HashEntry *he = HashTable_Find(t, h, key);
198: return he != NULL ? he->value : NULL;
199: }
200:
1.43 rillig 201: /* Makes a new hash table that is larger than the old one. The entire hash
202: * table is moved, so any bucket numbers from the old table become invalid. */
203: static void
1.46 rillig 204: RebuildTable(HashTable *t)
1.43 rillig 205: {
1.49 ! rillig 206: unsigned int oldSize = t->bucketsSize;
! 207: HashEntry **oldBuckets = t->buckets;
! 208: unsigned int newSize = 2 * oldSize;
! 209: unsigned int newMask = newSize - 1;
! 210: HashEntry **newBuckets = bmake_malloc(sizeof(*newBuckets) * newSize);
! 211: size_t i;
! 212:
! 213: for (i = 0; i < newSize; i++)
! 214: newBuckets[i] = NULL;
! 215:
! 216: for (i = 0; i < oldSize; i++) {
! 217: HashEntry *he = oldBuckets[i];
! 218: while (he != NULL) {
! 219: HashEntry *next = he->next;
! 220: he->next = newBuckets[he->key_hash & newMask];
! 221: newBuckets[he->key_hash & newMask] = he;
! 222: he = next;
1.43 rillig 223: }
224: }
1.49 ! rillig 225:
! 226: free(oldBuckets);
! 227:
! 228: t->bucketsSize = newSize;
! 229: t->bucketsMask = newMask;
! 230: t->buckets = newBuckets;
1.43 rillig 231: DEBUG5(HASH, "%s: %p size=%d entries=%d maxchain=%d\n",
232: __func__, t, t->bucketsSize, t->numEntries, t->maxchain);
233: t->maxchain = 0;
1.33 rillig 234: }
235:
1.28 rillig 236: /* Searches the hash table for an entry corresponding to the key.
237: * If no entry is found, then one is created.
1.1 cgd 238: *
1.10 wiz 239: * Input:
240: * t Hash table to search.
241: * key A hash key.
1.28 rillig 242: * newPtr Filled with TRUE if new entry created,
1.10 wiz 243: * FALSE otherwise.
1.1 cgd 244: */
1.46 rillig 245: HashEntry *
246: Hash_CreateEntry(HashTable *t, const char *key, Boolean *newPtr)
1.1 cgd 247: {
1.46 rillig 248: HashEntry *e;
1.10 wiz 249: unsigned h;
1.43 rillig 250: size_t keylen;
1.46 rillig 251: HashEntry **hp;
1.1 cgd 252:
1.43 rillig 253: h = hash(key, &keylen);
254: e = HashTable_Find(t, h, key);
255: if (e) {
256: if (newPtr != NULL)
257: *newPtr = FALSE;
258: return e;
1.42 rillig 259: }
1.1 cgd 260:
261: /*
262: * The desired entry isn't there. Before allocating a new entry,
263: * expand the table if necessary (and this changes the resulting
1.6 christos 264: * bucket chain).
1.1 cgd 265: */
1.29 rillig 266: if (t->numEntries >= rebuildLimit * t->bucketsSize)
1.1 cgd 267: RebuildTable(t);
1.43 rillig 268:
1.17 joerg 269: e = bmake_malloc(sizeof(*e) + keylen);
1.29 rillig 270: hp = &t->buckets[h & t->bucketsMask];
1.1 cgd 271: e->next = *hp;
272: *hp = e;
1.19 dsl 273: Hash_SetValue(e, NULL);
1.47 rillig 274: e->key_hash = h;
275: memcpy(e->key, key, keylen + 1);
1.1 cgd 276: t->numEntries++;
277:
278: if (newPtr != NULL)
279: *newPtr = TRUE;
1.21 rillig 280: return e;
1.1 cgd 281: }
282:
1.28 rillig 283: /* Delete the given hash table entry and free memory associated with it. */
1.1 cgd 284: void
1.46 rillig 285: Hash_DeleteEntry(HashTable *t, HashEntry *e)
1.1 cgd 286: {
1.46 rillig 287: HashEntry **hp, *p;
1.1 cgd 288:
1.47 rillig 289: for (hp = &t->buckets[e->key_hash & t->bucketsMask];
1.1 cgd 290: (p = *hp) != NULL; hp = &p->next) {
291: if (p == e) {
292: *hp = p->next;
1.16 christos 293: free(p);
1.1 cgd 294: t->numEntries--;
295: return;
296: }
297: }
298: abort();
299: }
300:
1.45 rillig 301: /* Set things up for iterating over all entries in the hash table. */
302: void
1.46 rillig 303: HashIter_Init(HashIter *hi, HashTable *t)
1.1 cgd 304: {
1.45 rillig 305: hi->table = t;
306: hi->nextBucket = 0;
307: hi->entry = NULL;
1.1 cgd 308: }
309:
1.45 rillig 310: /* Return the next entry in the hash table, or NULL if the end of the table
311: * is reached. */
1.46 rillig 312: HashEntry *
1.45 rillig 313: HashIter_Next(HashIter *hi)
1.1 cgd 314: {
1.46 rillig 315: HashEntry *e;
316: HashTable *t = hi->table;
1.1 cgd 317:
318: /*
1.29 rillig 319: * The entry field points to the most recently returned
320: * entry, or is NULL if we are starting up. If not NULL, we have
1.1 cgd 321: * to start at the next one in the chain.
322: */
1.45 rillig 323: e = hi->entry;
1.1 cgd 324: if (e != NULL)
325: e = e->next;
326: /*
327: * If the chain ran out, or if we are starting up, we need to
328: * find the next nonempty chain.
329: */
330: while (e == NULL) {
1.45 rillig 331: if (hi->nextBucket >= t->bucketsSize)
1.18 dsl 332: return NULL;
1.45 rillig 333: e = t->buckets[hi->nextBucket++];
1.1 cgd 334: }
1.45 rillig 335: hi->entry = e;
1.21 rillig 336: return e;
1.1 cgd 337: }
338:
1.28 rillig 339: void
1.46 rillig 340: Hash_DebugStats(HashTable *t, const char *name)
1.25 sjg 341: {
1.46 rillig 342: DEBUG4(HASH, "HashTable %s: size=%u numEntries=%u maxchain=%u\n",
1.43 rillig 343: name, t->bucketsSize, t->numEntries, t->maxchain);
1.25 sjg 344: }
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / usr.bin / make