Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/trunk]: src/usr.bin/make make(1): clean up hash table implementation



details:   https://anonhg.NetBSD.org/src/rev/f9a8a13eebea
branches:  trunk
changeset: 976785:f9a8a13eebea
user:      rillig <rillig%NetBSD.org@localhost>
date:      Sat Oct 03 22:25:04 2020 +0000

description:
make(1): clean up hash table implementation

Having the hash function potentially redefined is a bit too much
flexibility.  If actually needed, this should be done using a patch, not
using the C preprocessor.

Converting the macro to a function made the control flow easier to
understand.  It also revealed that the variable p was unnecessary in
both Hash_FindEntry and Hash_CreateEntry.

diffstat:

 usr.bin/make/hash.c |  54 +++++++++++++++++++++++-----------------------------
 1 files changed, 24 insertions(+), 30 deletions(-)

diffs (125 lines):

diff -r 4988003aead6 -r f9a8a13eebea usr.bin/make/hash.c
--- a/usr.bin/make/hash.c       Sat Oct 03 21:52:50 2020 +0000
+++ b/usr.bin/make/hash.c       Sat Oct 03 22:25:04 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: hash.c,v 1.35 2020/09/28 20:46:11 rillig Exp $ */
+/*     $NetBSD: hash.c,v 1.36 2020/10/03 22:25:04 rillig Exp $ */
 
 /*
  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -79,7 +79,7 @@
 #include "make.h"
 
 /*     "@(#)hash.c     8.1 (Berkeley) 6/6/93"  */
-MAKE_RCSID("$NetBSD: hash.c,v 1.35 2020/09/28 20:46:11 rillig Exp $");
+MAKE_RCSID("$NetBSD: hash.c,v 1.36 2020/10/03 22:25:04 rillig Exp $");
 
 /*
  * Forward references to local procedures that are used before they're
@@ -95,22 +95,20 @@
 
 #define rebuildLimit 3
 
-/* The hash function(s) */
+/* This hash function matches Gosling's emacs. */
+static unsigned int
+hash(const char *key, size_t *out_keylen)
+{
+       unsigned h = 0;
+       const char *p = key;
+       while (*p != '\0')
+               h = (h << 5) - h + (unsigned char)*p++;
+       if (out_keylen != NULL)
+               *out_keylen = (size_t)(p - key);
+       return h;
+}
 
-#ifndef HASH
-/* The default: this one matches Gosling's emacs */
-#define HASH(h, key, p) do { \
-       for (h = 0, p = key; *p;) \
-               h = (h << 5) - h + (unsigned char)*p++; \
-       } while (0)
-
-#endif
-
-/* Sets up the hash table.
- *
- * Input:
- *     t               Structure to to hold the table.
- */
+/* Sets up the hash table. */
 void
 Hash_InitTable(Hash_Table *t)
 {
@@ -164,21 +162,19 @@
 {
        Hash_Entry *e;
        unsigned h;
-       const char *p;
        int chainlen;
 
-       if (t == NULL || t->buckets == NULL) {
+       if (t == NULL || t->buckets == NULL)
            return NULL;
-       }
-       HASH(h, key, p);
-       p = key;
+
+       h = hash(key, NULL);
        chainlen = 0;
 #ifdef DEBUG_HASH_LOOKUP
        DEBUG4(HASH, "%s: %p h=%x key=%s\n", __func__, t, h, key);
 #endif
        for (e = t->buckets[h & t->bucketsMask]; e != NULL; e = e->next) {
                chainlen++;
-               if (e->namehash == h && strcmp(e->name, p) == 0)
+               if (e->namehash == h && strcmp(e->name, key) == 0)
                        break;
        }
        if (chainlen > t->maxchain)
@@ -207,8 +203,7 @@
 {
        Hash_Entry *e;
        unsigned h;
-       const char *p;
-       int keylen;
+       size_t keylen;
        int chainlen;
        struct Hash_Entry **hp;
 
@@ -216,16 +211,14 @@
         * Hash the key.  As a side effect, save the length (strlen) of the
         * key in case we need to create the entry.
         */
-       HASH(h, key, p);
-       keylen = p - key;
-       p = key;
+       h = hash(key, &keylen);
        chainlen = 0;
 #ifdef DEBUG_HASH_LOOKUP
        DEBUG4(HASH, "%s: %p h=%x key=%s\n", __func__, t, h, key);
 #endif
        for (e = t->buckets[h & t->bucketsMask]; e != NULL; e = e->next) {
                chainlen++;
-               if (e->namehash == h && strcmp(e->name, p) == 0) {
+               if (e->namehash == h && strcmp(e->name, key) == 0) {
                        if (newPtr != NULL)
                                *newPtr = FALSE;
                        break;
@@ -243,13 +236,14 @@
         */
        if (t->numEntries >= rebuildLimit * t->bucketsSize)
                RebuildTable(t);
+
        e = bmake_malloc(sizeof(*e) + keylen);
        hp = &t->buckets[h & t->bucketsMask];
        e->next = *hp;
        *hp = e;
        Hash_SetValue(e, NULL);
        e->namehash = h;
-       (void)strcpy(e->name, p);
+       (void)strcpy(e->name, key);
        t->numEntries++;
 
        if (newPtr != NULL)



Home | Main Index | Thread Index | Old Index