contrib/bmake/hash.c

   1 /*      $NetBSD: hash.c,v 1.57 2020/11/14 21:29:44 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.57 2020/11/14 21:29:44 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 HashEntry *
 257 HashTable_Set(HashTable *t, const char *key, void *value)
 258 {
 259         HashEntry *he = HashTable_CreateEntry(t, key, NULL);
 260         HashEntry_Set(he, value);
 261         return he;
 262 }
 263
 264 /* Delete the entry from the table and free the associated memory. */
 265 void
 266 HashTable_DeleteEntry(HashTable *t, HashEntry *he)
 267 {
 268         HashEntry **ref = &t->buckets[he->key_hash & t->bucketsMask];
 269         HashEntry *p;
 270
 271         for (; (p = *ref) != NULL; ref = &p->next) {
 272                 if (p == he) {
 273                         *ref = p->next;
 274                         free(p);
 275                         t->numEntries--;
 276                         return;
 277                 }
 278         }
 279         abort();
 280 }
 281
 282 /* Set things up for iterating over all entries in the hash table. */
 283 void
 284 HashIter_Init(HashIter *hi, HashTable *t)
 285 {
 286         hi->table = t;
 287         hi->nextBucket = 0;
 288         hi->entry = NULL;
 289 }
 290
 291 /* Return the next entry in the hash table, or NULL if the end of the table
 292  * is reached. */
 293 HashEntry *
 294 HashIter_Next(HashIter *hi)
 295 {
 296         HashTable *t = hi->table;
 297         HashEntry *he = hi->entry;
 298         HashEntry **buckets = t->buckets;
 299         unsigned int bucketsSize = t->bucketsSize;
 300
 301         if (he != NULL)
 302                 he = he->next;  /* skip the most recently returned entry */
 303
 304         while (he == NULL) {    /* find the next nonempty chain */
 305                 if (hi->nextBucket >= bucketsSize)
 306                         return NULL;
 307                 he = buckets[hi->nextBucket++];
 308         }
 309         hi->entry = he;
 310         return he;
 311 }
 312
 313 void
 314 HashTable_DebugStats(HashTable *t, const char *name)
 315 {
 316         DEBUG4(HASH, "HashTable %s: size=%u numEntries=%u maxchain=%u\n",
 317                name, t->bucketsSize, t->numEntries, t->maxchain);
 318 }