Module Name: src
Committed By: sjg
Date: Sat Jul 18 21:37:38 UTC 2020
Modified Files:
src/usr.bin/make: hash.c hash.h main.c make.1 make.h
Log Message:
Add -dh for DEBUG_HASH
Allow tracking of max chain length, to see how well the hash
tables are working.
Pull the actual hash operation into a marco so it can be
easily changed - for experimenting.
The current hash, is pretty good.
Reviewed by: christos
To generate a diff of this commit:
cvs rdiff -u -r1.22 -r1.23 src/usr.bin/make/hash.c
cvs rdiff -u -r1.13 -r1.14 src/usr.bin/make/hash.h
cvs rdiff -u -r1.279 -r1.280 src/usr.bin/make/main.c
cvs rdiff -u -r1.282 -r1.283 src/usr.bin/make/make.1
cvs rdiff -u -r1.109 -r1.110 src/usr.bin/make/make.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/make/hash.c
diff -u src/usr.bin/make/hash.c:1.22 src/usr.bin/make/hash.c:1.23
--- src/usr.bin/make/hash.c:1.22 Fri Jul 3 17:03:09 2020
+++ src/usr.bin/make/hash.c Sat Jul 18 21:37:38 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.c,v 1.22 2020/07/03 17:03:09 rillig Exp $ */
+/* $NetBSD: hash.c,v 1.23 2020/07/18 21:37:38 sjg Exp $ */
/*
* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -70,14 +70,14 @@
*/
#ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: hash.c,v 1.22 2020/07/03 17:03:09 rillig Exp $";
+static char rcsid[] = "$NetBSD: hash.c,v 1.23 2020/07/18 21:37:38 sjg Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93";
#else
-__RCSID("$NetBSD: hash.c,v 1.22 2020/07/03 17:03:09 rillig Exp $");
+__RCSID("$NetBSD: hash.c,v 1.23 2020/07/18 21:37:38 sjg Exp $");
#endif
#endif /* not lint */
#endif
@@ -107,6 +107,14 @@ static void RebuildTable(Hash_Table *);
#define rebuildLimit 3
+/* The hash function(s) */
+/* This one matches Gosling's emacs */
+#define HASH(h, key, p) do { \
+ for (h = 0, p = key; *p;) \
+ h = (h << 5) - h + *p++; \
+ } while (0)
+
+
/*
*---------------------------------------------------------
*
@@ -146,6 +154,7 @@ Hash_InitTable(Hash_Table *t, int numBuc
continue;
}
t->numEntries = 0;
+ t->maxlen = 0;
t->size = i;
t->mask = i - 1;
t->bucketPtr = hp = bmake_malloc(sizeof(*hp) * i);
@@ -220,17 +229,25 @@ Hash_FindEntry(Hash_Table *t, const char
Hash_Entry *e;
unsigned h;
const char *p;
+ int chainlen;
if (t == NULL || t->bucketPtr == NULL) {
return NULL;
}
- for (h = 0, p = key; *p;)
- h = (h << 5) - h + *p++;
+ HASH(h, key, p);
p = key;
- for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
- if (e->namehash == h && strcmp(e->name, p) == 0)
- return e;
- return NULL;
+ if (DEBUG(HASH))
+ fprintf(debug_file, "%s: %p h=%x key=%s\n", __func__,
+ t, h, key);
+ chainlen = 0;
+ for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
+ chainlen++;
+ if (e->namehash == h && strcmp(e->name, p) == 0)
+ break;
+ }
+ if (chainlen > t->maxlen)
+ t->maxlen = chainlen;
+ return e;
}
/*
@@ -265,23 +282,32 @@ Hash_CreateEntry(Hash_Table *t, const ch
unsigned h;
const char *p;
int keylen;
+ int chainlen;
struct Hash_Entry **hp;
/*
* Hash the key. As a side effect, save the length (strlen) of the
* key in case we need to create the entry.
*/
- for (h = 0, p = key; *p;)
- h = (h << 5) - h + *p++;
+ HASH(h, key, p);
keylen = p - key;
p = key;
+ if (DEBUG(HASH))
+ fprintf(debug_file, "%s: %p h=%x key=%s\n", __func__,
+ t, h, key);
+ chainlen = 0;
for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
+ chainlen++;
if (e->namehash == h && strcmp(e->name, p) == 0) {
if (newPtr != NULL)
*newPtr = FALSE;
- return e;
+ break;
}
}
+ if (chainlen > t->maxlen)
+ t->maxlen = chainlen;
+ if (e)
+ return e;
/*
* The desired entry isn't there. Before allocating a new entry,
@@ -463,6 +489,10 @@ RebuildTable(Hash_Table *t)
}
}
free(oldhp);
+ if (DEBUG(HASH))
+ fprintf(debug_file, "%s: %p size=%d entries=%d maxlen=%d\n",
+ __func__, t, t->size, t->numEntries, t->maxlen);
+ t->maxlen = 0;
}
void Hash_ForEach(Hash_Table *t, void (*action)(void *, void *), void *data)
Index: src/usr.bin/make/hash.h
diff -u src/usr.bin/make/hash.h:1.13 src/usr.bin/make/hash.h:1.14
--- src/usr.bin/make/hash.h:1.13 Fri Jul 3 17:03:09 2020
+++ src/usr.bin/make/hash.h Sat Jul 18 21:37:38 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.h,v 1.13 2020/07/03 17:03:09 rillig Exp $ */
+/* $NetBSD: hash.h,v 1.14 2020/07/18 21:37:38 sjg Exp $ */
/*
* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -100,6 +100,7 @@ typedef struct Hash_Table {
int size; /* Actual size of array. */
int numEntries; /* Number of entries in the table. */
int mask; /* Used to select bits for hashing. */
+ int maxlen; /* max length of chain detected */
} Hash_Table;
/*
Index: src/usr.bin/make/main.c
diff -u src/usr.bin/make/main.c:1.279 src/usr.bin/make/main.c:1.280
--- src/usr.bin/make/main.c:1.279 Fri Jul 3 08:13:23 2020
+++ src/usr.bin/make/main.c Sat Jul 18 21:37:38 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: main.c,v 1.279 2020/07/03 08:13:23 rillig Exp $ */
+/* $NetBSD: main.c,v 1.280 2020/07/18 21:37:38 sjg Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -69,7 +69,7 @@
*/
#ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: main.c,v 1.279 2020/07/03 08:13:23 rillig Exp $";
+static char rcsid[] = "$NetBSD: main.c,v 1.280 2020/07/18 21:37:38 sjg Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
@@ -81,7 +81,7 @@ __COPYRIGHT("@(#) Copyright (c) 1988, 19
#if 0
static char sccsid[] = "@(#)main.c 8.3 (Berkeley) 3/19/94";
#else
-__RCSID("$NetBSD: main.c,v 1.279 2020/07/03 08:13:23 rillig Exp $");
+__RCSID("$NetBSD: main.c,v 1.280 2020/07/18 21:37:38 sjg Exp $");
#endif
#endif /* not lint */
#endif
@@ -278,6 +278,9 @@ parse_debug_options(const char *argvalue
++modules;
}
break;
+ case 'h':
+ debug |= DEBUG_HASH;
+ break;
case 'j':
debug |= DEBUG_JOB;
break;
Index: src/usr.bin/make/make.1
diff -u src/usr.bin/make/make.1:1.282 src/usr.bin/make/make.1:1.283
--- src/usr.bin/make/make.1:1.282 Sat Jun 6 20:28:42 2020
+++ src/usr.bin/make/make.1 Sat Jul 18 21:37:38 2020
@@ -1,4 +1,4 @@
-.\" $NetBSD: make.1,v 1.282 2020/06/06 20:28:42 wiz Exp $
+.\" $NetBSD: make.1,v 1.283 2020/07/18 21:37:38 sjg Exp $
.\"
.\" Copyright (c) 1990, 1993
.\" The Regents of the University of California. All rights reserved.
@@ -29,7 +29,7 @@
.\"
.\" from: @(#)make.1 8.4 (Berkeley) 3/19/94
.\"
-.Dd June 5, 2020
+.Dd July 18, 2020
.Dt MAKE 1
.Os
.Sh NAME
@@ -166,6 +166,8 @@ Print the input graph after making every
on error.
.It Ar "g3"
Print the input graph before exiting on error.
+.It Ar h
+Print debugging information about hash table operations.
.It Ar j
Print debugging information about running multiple shells.
.It Ar l
Index: src/usr.bin/make/make.h
diff -u src/usr.bin/make/make.h:1.109 src/usr.bin/make/make.h:1.110
--- src/usr.bin/make/make.h:1.109 Thu Jul 2 15:14:38 2020
+++ src/usr.bin/make/make.h Sat Jul 18 21:37:38 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: make.h,v 1.109 2020/07/02 15:14:38 rillig Exp $ */
+/* $NetBSD: make.h,v 1.110 2020/07/18 21:37:38 sjg Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -465,6 +465,7 @@ extern int debug;
#define DEBUG_ERROR 0x01000
#define DEBUG_LOUD 0x02000
#define DEBUG_META 0x04000
+#define DEBUG_HASH 0x08000
#define DEBUG_GRAPH3 0x10000
#define DEBUG_SCRIPT 0x20000
