Use a minimal perfect hash for the special sources/targets too. Add

the corresponding magic to create the hash function to the Makefile.

4 files changed, 114 insertions, 49 deletions

diff --git a/usr.bin/make/Makefile b/usr.bin/make/Makefile
index 0e15bb9..751bd8b 100644
--- a/usr.bin/make/Makefile
+++ b/usr.bin/make/Makefile
@@ -22,26 +22,29 @@ CFLAGS+=-D__FBSDID=__RCSID
 
 main.o: ${MAKEFILE}
 
-# Directive table. We use a hash table. This hash table has been
+# Directive and keyword tables. We use hash tables. These hash tables have been
 # generated with mph which can be found on the usual GNU mirrors.
-# If you change the directives (adding, deleting, reordering) you
-# need to create a new table and hash function (directive_hash).
+# If you change the directives or keywords (adding, deleting, reordering) you
+# need to create new tables and hash functions (directive_hash, keyword_hash).
 #
 # The following changes have been made to the generated code:
 #
-#	o prefix the names of the g, T0 and T1 arrays with 'directive_'.
+#	o prefix the names of the g, T0 and T1 arrays with 'directive_'
+#	  resp. 'keyword_'.
 #
 #	o make the type of the tables 'const [un]signed char' (if you change
 #	  anything make sure that the numbers fit into a char).
 #
 #	o make the hash function use the length for termination,
-#	  not the trailing '\0', via the -l flag in emitc and some editing.
+#	  not the trailing '\0', via the -l flag in emitc and some editing
+#	  (only for directive_hash).
 
 LOCALBASE ?= /usr/local
 MPH	?= ${LOCALBASE}/bin/mph
 EMITC	?= ${LOCALBASE}/bin/emitc
 
 .PRECIOUS: hash
+
 hash:
 	( echo '/*' ;							\
 	  echo ' * DO NOT EDIT' ;					\
@@ -71,7 +74,23 @@ hash:
 	    -e 's/int len)/size_t len)/'				\
 	    -e 's/= T0\[/= directive_T0\[/'				\
 	    -e 's/= T1\[/= directive_T1\[/'				\
-	    -e 's/g\[f/directive_g[f/g'					\
+	    -e 's/g\[f/directive_g[f/g' ;				\
+	  cat ${.CURDIR}/parse.c | sed					\
+	    -e '1,/KEYWORD-START-TAG/d'					\
+	    -e '/KEYWORD-END-TAG/,$$d'					\
+	    -e 's/^[^"]*"\([^"]*\)".*$$/\1/' |				\
+	    ${MPH} -d2 -m1 | ${EMITC} -l -s |				\
+	    sed								\
+	    -e 's/^static int g\[\]/static const signed char keyword_g[]/' \
+	    -e 's/^static int T0\[\]/static const u_char keyword_T0[]/' \
+	    -e 's/^static int T1\[\]/static const u_char keyword_T1[]/' \
+	    -e '/^#define uchar unsigned char/d'			\
+	    -e 's/uchar/u_char/g'					\
+	    -e 's/^hash(/keyword_hash(/'				\
+	    -e 's/int len)/size_t len)/'				\
+	    -e 's/= T0\[/= keyword_T0\[/'				\
+	    -e 's/= T1\[/= keyword_T1\[/'				\
+	    -e 's/g\[f/keyword_g[f/g'					\
 	) > ${.CURDIR}/directive_hash.c
 
 # Set the shell which make(1) uses.  Bourne is the default, but a decent
diff --git a/usr.bin/make/directive_hash.c b/usr.bin/make/directive_hash.c
index 0c53fac..3478bc5 100644
--- a/usr.bin/make/directive_hash.c
+++ b/usr.bin/make/directive_hash.c
@@ -64,3 +64,66 @@ directive_hash(const u_char *key, size_t len)
 
 	return (directive_g[f0] + directive_g[f1]) % 18;
 }
+/*
+ * d=2
+ * n=67
+ * m=32
+ * c=2.09
+ * maxlen=1
+ * minklen=4
+ * maxklen=12
+ * minchar=46
+ * maxchar=95
+ * loop=0
+ * numiter=2
+ * seed=
+ */
+
+static const signed char keyword_g[] = {
+	17, -1, 18, 13, 26, 0, 0, 29, -1, 0,
+	7, -1, -1, 23, 13, 27, -1, 0, 14, 24,
+	-1, -1, 0, 24, -1, 0, -1, 27, 19, 12,
+	3, -1, -1, 3, 19, 28, 10, 17, -1, 8,
+	-1, -1, -1, 0, 5, 8, -1, 0, -1, -1,
+	0, 27, 4, -1, -1, 25, -1, 30, -1, 8,
+	16, -1, 0, -1, 0, 26, 14, 
+};
+
+static const u_char keyword_T0[] = {
+	17, 32, 43, 6, 64, 15, 20, 26, 30, 64,
+	54, 31, 6, 61, 4, 49, 62, 37, 23, 50,
+	6, 58, 29, 19, 32, 50, 56, 8, 18, 40,
+	51, 36, 6, 27, 42, 3, 59, 12, 46, 23,
+	9, 50, 4, 16, 44, 25, 15, 40, 62, 55,
+};
+
+static const u_char keyword_T1[] = {
+	24, 38, 31, 14, 65, 31, 23, 17, 27, 45,
+	32, 44, 19, 45, 18, 31, 28, 43, 0, 21,
+	29, 27, 42, 55, 21, 31, 14, 13, 66, 17,
+	39, 40, 5, 4, 5, 4, 52, 28, 21, 12,
+	7, 54, 6, 43, 49, 24, 7, 27, 0, 24,
+};
+
+
+int
+keyword_hash(const u_char *key, size_t len)
+{
+	unsigned f0, f1;
+	const u_char *kp = key;
+
+	if (len < 4 || len > 12)
+		return -1;
+
+	for (f0=f1=0; *kp; ++kp) {
+		if (*kp < 46 || *kp > 95)
+			return -1;
+		f0 += keyword_T0[-46 + *kp];
+		f1 += keyword_T1[-46 + *kp];
+	}
+
+	f0 %= 67;
+	f1 %= 67;
+
+	return (keyword_g[f0] + keyword_g[f1]) % 32;
+}
diff --git a/usr.bin/make/directive_hash.h b/usr.bin/make/directive_hash.h
index 12bfcc0..231a84b 100644
--- a/usr.bin/make/directive_hash.h
+++ b/usr.bin/make/directive_hash.h
@@ -32,5 +32,6 @@
 #include <sys/types.h>
 
 int directive_hash(const u_char *, size_t);
+int keyword_hash(const u_char *, size_t);
 
 #endif
diff --git a/usr.bin/make/parse.c b/usr.bin/make/parse.c
index 05701b5..8274aa4 100644
--- a/usr.bin/make/parse.c
+++ b/usr.bin/make/parse.c
@@ -193,11 +193,12 @@ static GNode *predecessor;
  * the 'op' field is the operator to apply to the list of targets if the
  * keyword is used as a source ("0" if the keyword isn't special as a source)
  */
-static struct {
+static const struct keyword {
 	const char	*name;	/* Name of keyword */
 	ParseSpecial	spec;	/* Type when used as a target */
 	int		op;	/* Operator when used as a source */
 } parseKeywords[] = {
+	/* KEYWORD-START-TAG */
 	{ ".BEGIN",		Begin,		0 },
 	{ ".DEFAULT",		Default,	0 },
 	{ ".END",		End,		0 },
@@ -230,7 +231,9 @@ static struct {
 	{ ".SUFFIXES",		Suffixes,	0 },
 	{ ".USE",		Attribute,	OP_USE },
 	{ ".WAIT",		Wait,		0 },
+	/* KEYWORD-END-TAG */
 };
+#define	NKEYWORDS	(sizeof(parseKeywords) / sizeof(parseKeywords[0]))
 
 static void parse_include(char *, int, int);
 static void parse_message(char *, int, int);
@@ -268,41 +271,22 @@ static const struct directive {
 #define	NDIRECTS	(sizeof(directives) / sizeof(directives[0]))
 
 /*-
- *----------------------------------------------------------------------
- * ParseFindKeyword --
+ * ParseFindKeyword
  *	Look in the table of keywords for one matching the given string.
  *
  * Results:
- *	The index of the keyword, or -1 if it isn't there.
- *
- * Side Effects:
- *	None
- *----------------------------------------------------------------------
+ *	The pointer to keyword table entry or NULL.
  */
-static int
-ParseFindKeyword(char *str)
+static const struct keyword *
+ParseFindKeyword(const char *str)
 {
-	int	start;
-	int	end;
-	int	cur;
-	int	diff;
-
-	start = 0;
-	end = (sizeof(parseKeywords) / sizeof(parseKeywords[0])) - 1;
+	int kw;
 
-	do {
-		cur = start + (end - start) / 2;
-		diff = strcmp(str, parseKeywords[cur].name);
-		if (diff == 0) {
-			return (cur);
-		} else if (diff < 0) {
-			end = cur - 1;
-		} else {
-			start = cur + 1;
-		}
-	} while (start <= end);
-
-	return (-1);
+	kw = keyword_hash(str, strlen(str));
+	if (kw < 0 || kw >= (int)NKEYWORDS ||
+	    strcmp(str, parseKeywords[kw].name) != 0)
+		return (NULL);
+	return (&parseKeywords[kw]);
 }
 
 /*-
@@ -541,15 +525,15 @@ static void
 ParseDoSrc(int tOp, char *src, Lst *allsrc)
 {
 	GNode	*gn = NULL;
+	const struct keyword *kw;
 
-	if (*src == '.' && isupper ((unsigned char) src[1])) {
-		int keywd = ParseFindKeyword(src);
-		if (keywd != -1) {
-			if(parseKeywords[keywd].op != 0) {
-				ParseDoOp(parseKeywords[keywd].op);
+	if (src[0] == '.' && isupper ((unsigned char)src[1])) {
+		if ((kw = ParseFindKeyword(src)) != NULL) {
+			if (kw->op != 0) {
+				ParseDoOp(kw->op);
 				return;
 			}
-			if (parseKeywords[keywd].spec == Wait) {
+			if (kw->spec == Wait) {
 				waiting++;
 				return;
 			}
@@ -698,6 +682,7 @@ ParseDoDependency(char *line)
 	Lst	paths;	/* Search paths to alter when parsing .PATH targets */
 	int	tOp;	/* operator from special target */
 	LstNode	*ln;
+	const struct keyword *kw;
 
 	tOp = 0;
 
@@ -814,18 +799,15 @@ ParseDoDependency(char *line)
 			 * See if the target is a special target that must have
 			 * it or its sources handled specially.
 			 */
-			int keywd = ParseFindKeyword(line);
-
-			if (keywd != -1) {
-				if (specType == ExPath &&
-				    parseKeywords[keywd].spec != ExPath) {
+			if ((kw = ParseFindKeyword(line)) != NULL) {
+				if (specType == ExPath && kw->spec != ExPath) {
 					Parse_Error(PARSE_FATAL,
 					    "Mismatched special targets");
 					return;
 				}
 
-				specType = parseKeywords[keywd].spec;
-				tOp = parseKeywords[keywd].op;
+				specType = kw->spec;
+				tOp = kw->op;
 
 				/*
 				 * Certain special targets have special