contrib/bmake/hash.c

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