contrib/bmake/hash.c

   1 /*      $NetBSD: hash.c,v 1.61 2021/02/01 17:32:10 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.61 2021/02/01 17:32:10 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;
  90         const char *p;
  91
  92         h = 0;
  93         for (p = key; *p != '\0'; p++)
  94                 h = 31 * h + (unsigned char)*p;
  95
  96         if (out_keylen != NULL)
  97                 *out_keylen = (size_t)(p - key);
  98         return h;
  99 }
 100
 101 unsigned int
 102 Hash_Hash(const char *key)
 103 {
 104         return hash(key, NULL);
 105 }
 106
 107 static HashEntry *
 108 HashTable_Find(HashTable *t, unsigned int h, const char *key)
 109 {
 110         HashEntry *e;
 111         unsigned int chainlen = 0;
 112
 113 #ifdef DEBUG_HASH_LOOKUP
 114         DEBUG4(HASH, "%s: %p h=%08x key=%s\n", __func__, t, h, key);
 115 #endif
 116
 117         for (e = t->buckets[h & t->bucketsMask]; e != NULL; e = e->next) {
 118                 chainlen++;
 119                 if (e->key_hash == h && strcmp(e->key, key) == 0)
 120                         break;
 121         }
 122
 123         if (chainlen > t->maxchain)
 124                 t->maxchain = chainlen;
 125
 126         return e;
 127 }
 128
 129 /* Set up the hash table. */
 130 void
 131 HashTable_Init(HashTable *t)
 132 {
 133         unsigned int n = 16, i;
 134         HashEntry **buckets = bmake_malloc(sizeof *buckets * n);
 135         for (i = 0; i < n; i++)
 136                 buckets[i] = NULL;
 137
 138         t->buckets = buckets;
 139         t->bucketsSize = n;
 140         t->numEntries = 0;
 141         t->bucketsMask = n - 1;
 142         t->maxchain = 0;
 143 }
 144
 145 /*
 146  * Remove everything from the hash table and free up the memory for the keys
 147  * of the hash table, but not for the values associated to these keys.
 148  */
 149 void
 150 HashTable_Done(HashTable *t)
 151 {
 152         HashEntry **buckets = t->buckets;
 153         size_t i, n = t->bucketsSize;
 154
 155         for (i = 0; i < n; i++) {
 156                 HashEntry *he = buckets[i];
 157                 while (he != NULL) {
 158                         HashEntry *next = he->next;
 159                         free(he);
 160                         he = next;
 161                 }
 162         }
 163
 164         free(t->buckets);
 165 #ifdef CLEANUP
 166         t->buckets = NULL;
 167 #endif
 168 }
 169
 170 /* Find the entry corresponding to the key, or return NULL. */
 171 HashEntry *
 172 HashTable_FindEntry(HashTable *t, const char *key)
 173 {
 174         unsigned int h = hash(key, NULL);
 175         return HashTable_Find(t, h, key);
 176 }
 177
 178 /* Find the value corresponding to the key, or return NULL. */
 179 void *
 180 HashTable_FindValue(HashTable *t, const char *key)
 181 {
 182         HashEntry *he = HashTable_FindEntry(t, key);
 183         return he != NULL ? he->value : NULL;
 184 }
 185
 186 /*
 187  * Find the value corresponding to the key and the precomputed hash,
 188  * or return NULL.
 189  */
 190 void *
 191 HashTable_FindValueHash(HashTable *t, const char *key, unsigned int h)
 192 {
 193         HashEntry *he = HashTable_Find(t, h, key);
 194         return he != NULL ? he->value : NULL;
 195 }
 196
 197 /*
 198  * Make the hash table larger. Any bucket numbers from the old table become
 199  * invalid; the hash codes stay valid though.
 200  */
 201 static void
 202 HashTable_Enlarge(HashTable *t)
 203 {
 204         unsigned int oldSize = t->bucketsSize;
 205         HashEntry **oldBuckets = t->buckets;
 206         unsigned int newSize = 2 * oldSize;
 207         unsigned int newMask = newSize - 1;
 208         HashEntry **newBuckets = bmake_malloc(sizeof *newBuckets * newSize);
 209         size_t i;
 210
 211         for (i = 0; i < newSize; i++)
 212                 newBuckets[i] = NULL;
 213
 214         for (i = 0; i < oldSize; i++) {
 215                 HashEntry *he = oldBuckets[i];
 216                 while (he != NULL) {
 217                         HashEntry *next = he->next;
 218                         he->next = newBuckets[he->key_hash & newMask];
 219                         newBuckets[he->key_hash & newMask] = he;
 220                         he = next;
 221                 }
 222         }
 223
 224         free(oldBuckets);
 225
 226         t->bucketsSize = newSize;
 227         t->bucketsMask = newMask;
 228         t->buckets = newBuckets;
 229         DEBUG5(HASH, "%s: %p size=%d entries=%d maxchain=%d\n",
 230                __func__, t, t->bucketsSize, t->numEntries, t->maxchain);
 231         t->maxchain = 0;
 232 }
 233
 234 /*
 235  * Find or create an entry corresponding to the key.
 236  * Return in out_isNew whether a new entry has been created.
 237  */
 238 HashEntry *
 239 HashTable_CreateEntry(HashTable *t, const char *key, Boolean *out_isNew)
 240 {
 241         size_t keylen;
 242         unsigned int h = hash(key, &keylen);
 243         HashEntry *he = HashTable_Find(t, h, key);
 244
 245         if (he != NULL) {
 246                 if (out_isNew != NULL)
 247                         *out_isNew = FALSE;
 248                 return he;
 249         }
 250
 251         if (t->numEntries >= rebuildLimit * t->bucketsSize)
 252                 HashTable_Enlarge(t);
 253
 254         he = bmake_malloc(sizeof *he + keylen);
 255         he->value = NULL;
 256         he->key_hash = h;
 257         memcpy(he->key, key, keylen + 1);
 258
 259         he->next = t->buckets[h & t->bucketsMask];
 260         t->buckets[h & t->bucketsMask] = he;
 261         t->numEntries++;
 262
 263         if (out_isNew != NULL)
 264                 *out_isNew = TRUE;
 265         return he;
 266 }
 267
 268 HashEntry *
 269 HashTable_Set(HashTable *t, const char *key, void *value)
 270 {
 271         HashEntry *he = HashTable_CreateEntry(t, key, NULL);
 272         HashEntry_Set(he, value);
 273         return he;
 274 }
 275
 276 /* Delete the entry from the table and free the associated memory. */
 277 void
 278 HashTable_DeleteEntry(HashTable *t, HashEntry *he)
 279 {
 280         HashEntry **ref = &t->buckets[he->key_hash & t->bucketsMask];
 281         HashEntry *p;
 282
 283         for (; (p = *ref) != NULL; ref = &p->next) {
 284                 if (p == he) {
 285                         *ref = p->next;
 286                         free(p);
 287                         t->numEntries--;
 288                         return;
 289                 }
 290         }
 291         abort();
 292 }
 293
 294 /* Set things up for iterating over all entries in the hash table. */
 295 void
 296 HashIter_Init(HashIter *hi, HashTable *t)
 297 {
 298         hi->table = t;
 299         hi->nextBucket = 0;
 300         hi->entry = NULL;
 301 }
 302
 303 /*
 304  * Return the next entry in the hash table, or NULL if the end of the table
 305  * is reached.
 306  */
 307 HashEntry *
 308 HashIter_Next(HashIter *hi)
 309 {
 310         HashTable *t = hi->table;
 311         HashEntry *he = hi->entry;
 312         HashEntry **buckets = t->buckets;
 313         unsigned int bucketsSize = t->bucketsSize;
 314
 315         if (he != NULL)
 316                 he = he->next;  /* skip the most recently returned entry */
 317
 318         while (he == NULL) {    /* find the next nonempty chain */
 319                 if (hi->nextBucket >= bucketsSize)
 320                         return NULL;
 321                 he = buckets[hi->nextBucket++];
 322         }
 323         hi->entry = he;
 324         return he;
 325 }
 326
 327 void
 328 HashTable_DebugStats(HashTable *t, const char *name)
 329 {
 330         DEBUG4(HASH, "HashTable %s: size=%u numEntries=%u maxchain=%u\n",
 331                name, t->bucketsSize, t->numEntries, t->maxchain);
 332 }