Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/make Add -dh for DEBUG_HASH
details: https://anonhg.NetBSD.org/src/rev/e85f94dd29f7
branches: trunk
changeset: 936092:e85f94dd29f7
user: sjg <sjg%NetBSD.org@localhost>
date: Sat Jul 18 21:37:38 2020 +0000
description:
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
diffstat:
usr.bin/make/hash.c | 54 +++++++++++++++++++++++++++++++++++++++++-----------
usr.bin/make/hash.h | 3 +-
usr.bin/make/main.c | 9 +++++--
usr.bin/make/make.1 | 6 +++-
usr.bin/make/make.h | 3 +-
5 files changed, 56 insertions(+), 19 deletions(-)
diffs (226 lines):
diff -r 6bac3a76f066 -r e85f94dd29f7 usr.bin/make/hash.c
--- a/usr.bin/make/hash.c Sat Jul 18 20:56:53 2020 +0000
+++ b/usr.bin/make/hash.c Sat Jul 18 21:37:38 2020 +0000
@@ -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 @@
#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 @@
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_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 @@
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 @@
}
}
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)
diff -r 6bac3a76f066 -r e85f94dd29f7 usr.bin/make/hash.h
--- a/usr.bin/make/hash.h Sat Jul 18 20:56:53 2020 +0000
+++ b/usr.bin/make/hash.h Sat Jul 18 21:37:38 2020 +0000
@@ -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 @@
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;
/*
diff -r 6bac3a76f066 -r e85f94dd29f7 usr.bin/make/main.c
--- a/usr.bin/make/main.c Sat Jul 18 20:56:53 2020 +0000
+++ b/usr.bin/make/main.c Sat Jul 18 21:37:38 2020 +0000
@@ -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 @@
#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 @@
++modules;
}
break;
+ case 'h':
+ debug |= DEBUG_HASH;
+ break;
case 'j':
debug |= DEBUG_JOB;
break;
diff -r 6bac3a76f066 -r e85f94dd29f7 usr.bin/make/make.1
--- a/usr.bin/make/make.1 Sat Jul 18 20:56:53 2020 +0000
+++ b/usr.bin/make/make.1 Sat Jul 18 21:37:38 2020 +0000
@@ -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 @@
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
diff -r 6bac3a76f066 -r e85f94dd29f7 usr.bin/make/make.h
--- a/usr.bin/make/make.h Sat Jul 18 20:56:53 2020 +0000
+++ b/usr.bin/make/make.h Sat Jul 18 21:37:38 2020 +0000
@@ -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 @@
#define DEBUG_ERROR 0x01000
#define DEBUG_LOUD 0x02000
#define DEBUG_META 0x04000
+#define DEBUG_HASH 0x08000
#define DEBUG_GRAPH3 0x10000
#define DEBUG_SCRIPT 0x20000
Home |
Main Index |
Thread Index |
Old Index