contrib/bmake/hash.c

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