Install Greg McGary's patches to port the id-utils hashing functions to

GNU make.  Also he provides some other performance fixups after doing
some profiling of make on large makefiles.

Modify the test suite to allow the use of Valgrind to find memory problems.

21 files changed, 1843 insertions, 1028 deletions

diff --git a/ChangeLog b/ChangeLog
index 97d08b5..48adc23 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,122 @@
 2002-07-10  Paul D. Smith  <psmith@gnu.org>
 
+	* variable.c (pop_variable_scope): Remove variable made unused by
+	new hash infrastructure.
+	* read.c (dep_hash_cmp): Rewrite this to handle ignore_mtime
+	comparisons as well as name comparisons.
+	* variable.h: Add a prototype for new hash_init_function_table().
+	* file.c (lookup_file): Remove variables made unused by new hash
+	infrastructure.
+	* dir.c (directory_contents_hash_2): Missing return of hash value.
+	(dir_contents_file_exists_p): Remove variables made unused by new
+	hash infrastructure.
+
+
+	Installed Greg McGary's integration of the hash functions from the
+	GNU id-utils package:
+
+2002-07-10  Greg McGary  <greg@mcgary.org>
+
+	* scripts/functions/filter-out: Add literals to to the
+	pattern space in order to add complexity, and trigger
+	use of an internal hash table.  Fix documentation strings.
+	* scripts/targets/INTERMEDIATE: Reverse order of files
+	passed to expected `rm' command.
+
+2002-07-10  Greg McGary  <greg@mcgary.org>
+
+	* Makefile.am (SRCS): Add hash.c (noinst_HEADERS): Add hash.h
+	* hash.c: New file, taken from id-utils.
+	* hash.h: New file, taken from id-utils.
+
+	* make.h (HASH, HASHI): Remove macros.
+	(find_char_unquote): Change arglist in decl.
+	(hash_init_directories): New function decl.
+	* variable.h (hash.h): New #include.
+	(MAKELEVEL_NAME, MAKELEVEL_LENGTH): New constants.
+	* filedef.h (hash.h): New #include.
+	(struct file) [next]: Remove member.
+	(file_hash_enter): Remove function decl.
+	(init_hash_files): New function decl.
+
+	* ar.c (ar_name): Delay call to strlen until needed.
+	* main.c (initialize_global_hash_tables): New function.
+	(main): Call it.  Use MAKELEVEL_NAME & MAKELEVEL_LENGTH.
+	* misc.c (remove_comments): Pass char constants to find_char_unquote.
+	* remake.c (notice_finished_file): Update last_mtime on `prev' chain.
+
+	* dir.c (hash.h): New #include.
+	(struct directory_contents) [next, files]: Remove members.
+	[ctime]: Add member for VMS.  [dirfiles]: Add hash-table member.
+	(directory_contents_hash_1, directory_contents_hash_2,
+	directory_contents_hash_cmp): New functions.
+	(directories_contents): Change type to `struct hash_table'.
+	(struct directory) [next]: Remove member.
+	(directory_hash_1, directory_hash_2, directory_hash_cmp): New funcs.
+	(directory): Change type to `struct hash_table'.
+	(struct dirfile) [next]: Remove member.
+	[length]: Add member.  [impossible]: widen type to fill alignment gap.
+	(dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp): New functions.
+	(find_directory): Use new hash table package.
+	(dir_contents_file_exists_p): Likewise.
+	(file_impossible): Likewise.
+	(file_impossible_p): Likewise.
+	(print_dir_data_base): Likewise.
+	(open_dirstream): Likewise.
+	(read_dirstream): Likewise.
+	(hash_init_directories): New function.
+
+	* file.c (hash.h): New #include.
+	(file_hash_1, file_hash_2, file_hash_cmp): New functions.
+	(files): Change type to `struct hash_table'.
+	(lookup_file): Use new hash table package.
+	(enter_file): Likewise.
+	(remove_intermediates): Likewise.
+	(snap_deps): Likewise.
+	(print_file_data_base): Likewise.
+
+	* function.c
+	(function_table_entry_hash_1, function_table_entry_hash_2,
+	function_table_entry_hash_cmp): New functions.
+	(lookup_function): Remove `table' argument.
+	Use new hash table package.
+	(struct a_word) [chain, length]: New members.
+	(a_word_hash_1, a_word_hash_2, a_word_hash_cmp): New functions.
+	(struct a_pattern): New struct.
+	(func_filter_filterout): Pass through patterns noting boundaries
+	and '%', if present.  Note a_word length.  Use a hash table if
+	arglists are large enough to justify cost.
+	(function_table_init): Renamed from function_table.
+	(function_table): Declare as `struct hash_table'.
+	(FUNCTION_TABLE_ENTRIES): New constant.
+	(hash_init_function_table): New function.
+
+	* read.c (hash.h): New #include.
+	(read_makefile): Pass char constants to find_char_unquote.
+	(dep_hash_1, dep_hash_2, dep_hash_cmp): New functions.
+	(uniquize_deps): Use hash table to efficiently identify duplicates.
+	(find_char_unquote): Accept two char-constant stop chars, rather
+	than a string constant, avoiding zillions of calls to strchr.
+	Tighten inner search loops to test only for desired delimiters.
+
+	* variable.c (variable_hash_1, variable_hash_2,
+	variable_hash_cmp): New functions.
+	(variable_table): Declare as `struct hash_table'.
+	(global_variable_set): Remove initialization.
+	(init_hash_global_variable_set): New function.
+	(define_variable_in_set): Use new hash table package.
+	(lookup_variable): Likewise.
+	(lookup_variable_in_set): Likewise.
+	(initialize_file_variables): Likewise.
+	(pop_variable_scope): Likewise.
+	(create_new_variable_set): Likewise.
+	(merge_variable_sets): Likewise.
+	(define_automatic_variables): Likewise.
+	(target_environment): Likewise.
+	(print_variable_set): Likewise.
+
+2002-07-10  Paul D. Smith  <psmith@gnu.org>
+
 	Implement the SysV make syntax $$@, $$(@D), and $$(@F) in the
 	prerequisite list.  A real SysV make will expand the entire
 	prerequisites list _twice_: we don't do that as it's a big
diff --git a/Makefile.am b/Makefile.am
index 5d70f42..2afb6b9 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -16,12 +16,12 @@ endif
 make_SOURCES =	ar.c arscan.c commands.c default.c dir.c expand.c file.c \
 		function.c getopt.c getopt1.c implicit.c job.c main.c \
 		misc.c read.c remake.c $(remote) rule.c signame.c \
-		variable.c version.c vpath.c
+		variable.c version.c vpath.c hash.c
 
 EXTRA_make_SOURCES = remote-stub.c remote-cstms.c
 
 noinst_HEADERS = commands.h dep.h filedef.h job.h make.h rule.h variable.h \
-		debug.h getopt.h gettext.h
+		debug.h getopt.h gettext.h hash.h
 
 make_LDADD =	@LIBOBJS@ @ALLOCA@ $(GLOBLIB) @GETLOADAVG_LIBS@ @LIBINTL@
 
diff --git a/ar.c b/ar.c
index 3827f40..286be55 100644
--- a/ar.c
+++ b/ar.c
@@ -1,5 +1,6 @@
 /* Interface to `ar' archives for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,97 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1997,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -41,9 +42,14 @@ int
 ar_name (name)
      char *name;
 {
-  char *p = strchr (name, '('), *end = name + strlen (name) - 1;
+  char *p = strchr (name, '(');
+  char *end;
+
+  if (p == 0 || p == name)
+    return 0;
 
-  if (p == 0 || p == name || *end != ')')
+  end = p + strlen (p) - 1;
+  if (*end != ')')
     return 0;
 
   if (p[1] == '(' && end[-1] == ')')
diff --git a/dir.c b/dir.c
index bc926b9..a84402f 100644
--- a/dir.c
+++ b/dir.c
@@ -1,5 +1,6 @@
 /* Directory hashing for GNU Make.
-Copyright (C) 1988,89,91,92,93,94,95,96,97 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -18,6 +19,7 @@ the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 Boston, MA 02111-1307, USA.  */
 
 #include "make.h"
+#include "hash.h"
 
 #ifdef	HAVE_DIRENT_H
 # include <dirent.h>
@@ -217,8 +219,6 @@ vmsstat_dir (name, st)
 
 struct directory_contents
   {
-    struct directory_contents *next;
-
     dev_t dev;			/* Device and inode numbers of this dir.  */
 #ifdef WINDOWS32
     /*
@@ -230,6 +230,7 @@ struct directory_contents
      * way to emulate inode.
      */
     char *path_key;
+    int   ctime;
     int   mtime;        /* controls check for stale directory cache */
     int   fs_flags;     /* FS_FAT, FS_NTFS, ... */
 #define FS_FAT      0x1
@@ -242,17 +243,95 @@ struct directory_contents
     ino_t ino;
 #endif
 #endif /* WINDOWS32 */
-    struct dirfile **files;	/* Files in this directory.  */
+    struct hash_table dirfiles;	/* Files in this directory.  */
     DIR *dirstream;		/* Stream reading this directory.  */
   };
 
+static unsigned long
+directory_contents_hash_1 (void const *key_0)
+{
+  struct directory_contents const *key = (struct directory_contents const *) key_0;
+  unsigned long hash;
+
+#ifdef WINDOWS32
+  ISTRING_HASH_1 (key->path_key, hash);
+  hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) key->ctime;
+#else
+# ifdef VMS
+  hash = (((unsigned int) key->dev << 4)
+	  ^ ((unsigned int) key->ino[0]
+	     + (unsigned int) key->ino[1]
+	     + (unsigned int) key->ino[2]));
+# else
+  hash = ((unsigned int) key->dev << 4) ^ (unsigned int) key->ino;
+# endif
+#endif /* WINDOWS32 */
+  return hash;
+}
+
+static unsigned long
+directory_contents_hash_2 (void const *key_0)
+{
+  struct directory_contents const *key = (struct directory_contents const *) key_0;
+  unsigned long hash;
+
+#ifdef WINDOWS32
+  ISTRING_HASH_2 (key->path_key, hash);
+  hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ctime;
+#else
+# ifdef VMS
+  hash = (((unsigned int) key->dev << 4)
+	  ^ ~((unsigned int) key->ino[0]
+	      + (unsigned int) key->ino[1]
+	      + (unsigned int) key->ino[2]));
+# else
+  hash = ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ino;
+# endif
+#endif /* WINDOWS32 */
+
+  return hash;
+}
+
+static int
+directory_contents_hash_cmp (void const *xv, void const *yv)
+{
+  struct directory_contents const *x = (struct directory_contents const *) xv;
+  struct directory_contents const *y = (struct directory_contents const *) yv;
+  int result;
+
+#ifdef WINDOWS32
+  ISTRING_COMPARE (x->path_key, y->path_key, result);
+  if (result)
+    return result;
+  result = x->ctime - y->ctime;
+  if (result)
+    return result;
+#else
+# ifdef VMS
+  result = x->ino[0] - y->ino[0];
+  if (result)
+    return result;
+  result = x->ino[1] - y->ino[1];
+  if (result)
+    return result;
+  result = x->ino[2] - y->ino[2];
+  if (result)
+    return result;
+# else
+  result = x->ino - y->ino;
+  if (result)
+    return result;
+# endif
+#endif /* WINDOWS32 */
+
+  return x->dev - y->dev;
+}
+
 /* Table of directory contents hashed by device and inode number.  */
-static struct directory_contents *directories_contents[DIRECTORY_BUCKETS];
+static struct hash_table directory_contents;
 
 struct directory
   {
-    struct directory *next;
-
     char *name;			/* Name of the directory.  */
 
     /* The directory's contents.  This data may be shared by several
@@ -261,9 +340,27 @@ struct directory
     struct directory_contents *contents;
   };
 
-/* Table of directories hashed by name.  */
-static struct directory *directories[DIRECTORY_BUCKETS];
+static unsigned long
+directory_hash_1 (void const *key)
+{
+  return_ISTRING_HASH_1 (((struct directory const *) key)->name);
+}
+
+static unsigned long
+directory_hash_2 (void const *key)
+{
+  return_ISTRING_HASH_2 (((struct directory const *) key)->name);
+}
+
+static int
+directory_hash_cmp (void const *x, void const *y)
+{
+  return_ISTRING_COMPARE (((struct directory const *) x)->name,
+			  ((struct directory const *) y)->name);
+}
 
+/* Table of directories hashed by name.  */
+static struct hash_table directories;
 
 /* Never have more than this many directories open at once.  */
 
@@ -276,11 +373,34 @@ static unsigned int open_directories = 0;
 
 struct dirfile
   {
-    struct dirfile *next;
     char *name;			/* Name of the file.  */
-    char impossible;		/* This file is impossible.  */
+    short length;
+    short impossible;		/* This file is impossible.  */
   };
 
+static unsigned long
+dirfile_hash_1 (void const *key)
+{
+  return_ISTRING_HASH_1 (((struct dirfile const *) key)->name);
+}
+
+static unsigned long
+dirfile_hash_2 (void const *key)
+{
+  return_ISTRING_HASH_2 (((struct dirfile const *) key)->name);
+}
+
+static int
+dirfile_hash_cmp (void const *xv, void const *yv)
+{
+  struct dirfile const *x = ((struct dirfile const *) xv);
+  struct dirfile const *y = ((struct dirfile const *) yv);
+  int result = x->length - y->length;
+  if (result)
+    return result;
+  return_ISTRING_COMPARE (x->name, y->name);
+}
+
 #ifndef	DIRFILE_BUCKETS
 #define DIRFILE_BUCKETS 107
 #endif
@@ -294,9 +414,10 @@ static struct directory *
 find_directory (name)
      register char *name;
 {
-  register unsigned int hash = 0;
   register char *p;
   register struct directory *dir;
+  register struct directory **dir_slot;
+  struct directory dir_key;
   int r;
 #ifdef WINDOWS32
   char* w32_path;
@@ -313,25 +434,20 @@ find_directory (name)
     name = vmsify (name,1);
 #endif
 
-  for (p = name; *p != '\0'; ++p)
-    HASHI (hash, *p);
-  hash %= DIRECTORY_BUCKETS;
-
-  for (dir = directories[hash]; dir != 0; dir = dir->next)
-    if (strieq (dir->name, name))
-      break;
+  dir_key.name = name;
+  dir_slot = (struct directory **) hash_find_slot (&directories, &dir_key);
+  dir = *dir_slot;
 
-  if (dir == 0)
+  if (HASH_VACANT (dir))
     {
       struct stat st;
 
       /* The directory was not found.  Create a new entry for it.  */
 
+      p = name + strlen (name);
       dir = (struct directory *) xmalloc (sizeof (struct directory));
-      dir->next = directories[hash];
-      directories[hash] = dir;
       dir->name = savestring (name, p - name);
-
+      hash_insert_at (&directories, dir, dir_slot);
       /* The directory is not in the name hash table.
 	 Find its device and inode numbers, and look it up by them.  */
 
@@ -366,39 +482,26 @@ find_directory (name)
 	  /* Search the contents hash table; device and inode are the key.  */
 
 	  struct directory_contents *dc;
+	  struct directory_contents **dc_slot;
+	  struct directory_contents dc_key;
 
+	  dc_key.dev = st.st_dev;
 #ifdef WINDOWS32
-          w32_path = w32ify(name, 1);
-          hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ctime;
+	  dc_key.path_key = w32_path = w32ify (name, 1);
+	  dc_key.ctime = st.st_ctime;
 #else
 # ifdef VMS
-          hash = (((unsigned int) st.st_dev << 16)
-                  | ((unsigned int) st.st_ino[0]
-                     + (unsigned int) st.st_ino[1]
-                     + (unsigned int) st.st_ino[2]));
+	  dc_key.ino[0] = st.st_ino[0];
+	  dc_key.ino[1] = st.st_ino[1];
+	  dc_key.ino[2] = st.st_ino[2];
 # else
-	  hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ino;
+	  dc_key.ino = st.st_ino;
 # endif
 #endif
-	  hash %= DIRECTORY_BUCKETS;
-
-	  for (dc = directories_contents[hash]; dc != 0; dc = dc->next)
-#ifdef WINDOWS32
-            if (strieq(dc->path_key, w32_path))
-#else
-	    if (dc->dev == st.st_dev
-# ifdef VMS
-		&& dc->ino[0] == st.st_ino[0]
-		&& dc->ino[1] == st.st_ino[1]
-		&& dc->ino[2] == st.st_ino[2]
-# else
-                && dc->ino == st.st_ino
-# endif
-                )
-#endif /* WINDOWS32 */
-	      break;
+	  dc_slot = (struct directory_contents **) hash_find_slot (&directory_contents, &dc_key);
+	  dc = *dc_slot;
 
-	  if (dc == 0)
+	  if (HASH_VACANT (dc))
 	    {
 	      /* Nope; this really is a directory we haven't seen before.  */
 
@@ -408,7 +511,8 @@ find_directory (name)
 	      /* Enter it in the contents hash table.  */
 	      dc->dev = st.st_dev;
 #ifdef WINDOWS32
-              dc->path_key = xstrdup(w32_path);
+              dc->path_key = xstrdup (w32_path);
+	      dc->ctime = st.st_ctime;
               dc->mtime = st.st_mtime;
 
               /*
@@ -437,22 +541,16 @@ find_directory (name)
 	      dc->ino = st.st_ino;
 # endif
 #endif /* WINDOWS32 */
-	      dc->next = directories_contents[hash];
-	      directories_contents[hash] = dc;
-
+	      hash_insert_at (&directory_contents, dc, dc_slot);
 	      dc->dirstream = opendir (name);
 	      if (dc->dirstream == 0)
                 /* Couldn't open the directory.  Mark this by
                    setting the `files' member to a nil pointer.  */
-                dc->files = 0;
+		hash_free (&dc->dirfiles, 0);
 	      else
 		{
-		  /* Allocate an array of buckets for files and zero it.  */
-		  dc->files = (struct dirfile **)
-		    xmalloc (sizeof (struct dirfile *) * DIRFILE_BUCKETS);
-		  bzero ((char *) dc->files,
-			 sizeof (struct dirfile *) * DIRFILE_BUCKETS);
-
+		  hash_init (&dc->dirfiles, DIRFILE_BUCKETS,
+			     dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
 		  /* Keep track of how many directories are open.  */
 		  ++open_directories;
 		  if (open_directories == MAX_OPEN_DIRECTORIES)
@@ -478,16 +576,15 @@ dir_contents_file_exists_p (dir, filename)
      register struct directory_contents *dir;
      register char *filename;
 {
-  register unsigned int hash;
-  register char *p;
-  register struct dirfile *df;
-  register struct dirent *d;
+  unsigned int hash;
+  struct dirfile *df;
+  struct dirent *d;
 #ifdef WINDOWS32
   struct stat st;
   int rehash = 0;
 #endif
 
-  if (dir == 0 || dir->files == 0)
+  if (dir == 0 || dir->dirfiles.ht_vec == 0)
     {
     /* The directory could not be stat'd or opened.  */
       return 0;
@@ -507,24 +604,19 @@ dir_contents_file_exists_p (dir, filename)
   hash = 0;
   if (filename != 0)
     {
+      struct dirfile dirfile_key;
+
       if (*filename == '\0')
 	{
-	/* Checking if the directory exists.  */
+	  /* Checking if the directory exists.  */
 	  return 1;
 	}
-
-      for (p = filename; *p != '\0'; ++p)
-	HASH (hash, *p);
-      hash %= DIRFILE_BUCKETS;
-
-      /* Search the list of hashed files.  */
-
-      for (df = dir->files[hash]; df != 0; df = df->next)
+      dirfile_key.name = filename;
+      dirfile_key.length = strlen (filename);
+      df = (struct dirfile *) hash_find_item (&dir->dirfiles, &dirfile_key);
+      if (df)
 	{
-	  if (strieq (df->name, filename))
-	    {
-	      return !df->impossible;
-	    }
+	  return !df->impossible;
 	}
     }
 
@@ -539,33 +631,34 @@ dir_contents_file_exists_p (dir, filename)
        * filesystems force a rehash always as mtime does not change
        * on directories (ugh!).
        */
-      if (dir->path_key &&
-          (dir->fs_flags & FS_FAT ||
-           (stat(dir->path_key, &st) == 0 &&
-            st.st_mtime > dir->mtime))) {
-
-        /* reset date stamp to show most recent re-process */
-        dir->mtime = st.st_mtime;
-
-        /* make sure directory can still be opened */
-        dir->dirstream = opendir(dir->path_key);
-
-        if (dir->dirstream)
-          rehash = 1;
-        else
-          return 0; /* couldn't re-read - fail */
-      } else
+      if (dir->path_key
+	  && (dir->fs_flags & FS_FAT
+	      || (stat(dir->path_key, &st) == 0
+		  && st.st_mtime > dir->mtime)))
+	{
+	  /* reset date stamp to show most recent re-process */
+	  dir->mtime = st.st_mtime;
+
+	  /* make sure directory can still be opened */
+	  dir->dirstream = opendir(dir->path_key);
+
+	  if (dir->dirstream)
+	    rehash = 1;
+	  else
+	    return 0; /* couldn't re-read - fail */
+	}
+      else
 #endif
-    /* The directory has been all read in.  */
-      return 0;
+	/* The directory has been all read in.  */
+	return 0;
     }
 
   while ((d = readdir (dir->dirstream)) != 0)
     {
       /* Enter the file in the hash table.  */
-      register unsigned int newhash = 0;
       unsigned int len;
-      register unsigned int i;
+      struct dirfile dirfile_key;
+      struct dirfile **dirfile_slot;
 
 #if defined(VMS) && defined(HAVE_DIRENT_H)
       /* In VMS we get file versions too, which have to be stripped off */
@@ -579,39 +672,25 @@ dir_contents_file_exists_p (dir, filename)
 	continue;
 
       len = NAMLEN (d);
-      for (i = 0; i < len; ++i)
-	HASHI (newhash, d->d_name[i]);
-      newhash %= DIRFILE_BUCKETS;
+      dirfile_key.name = d->d_name;
+      dirfile_key.length = len;
+      dirfile_slot = (struct dirfile **) hash_find_slot (&dir->dirfiles, &dirfile_key);
 #ifdef WINDOWS32
       /*
-       * If re-reading a directory, check that this file isn't already
-       * in the cache.
-       */
-      if (rehash) {
-        for (df = dir->files[newhash]; df != 0; df = df->next)
-          if (streq(df->name, d->d_name))
-            break;
-      } else
-        df = 0;
-
-      /*
        * If re-reading a directory, don't cache files that have
        * already been discovered.
        */
-      if (!df) {
-#endif
-
-      df = (struct dirfile *) xmalloc (sizeof (struct dirfile));
-      df->next = dir->files[newhash];
-      dir->files[newhash] = df;
-      df->name = savestring (d->d_name, len);
-      df->impossible = 0;
-#ifdef WINDOWS32
-      }
+      if (! rehash || HASH_VACANT (*dirfile_slot))
 #endif
+	{
+	  df = (struct dirfile *) xmalloc (sizeof (struct dirfile));
+	  df->name = savestring (d->d_name, len);
+	  df->length = len;
+	  df->impossible = 0;
+	  hash_insert_at (&dir->dirfiles, df, dirfile_slot);
+	}
       /* Check if the name matches the one we're searching for.  */
-      if (filename != 0
-	  && newhash == hash && strieq (d->d_name, filename))
+      if (filename != 0 && strieq (d->d_name, filename))
 	{
 	  return 1;
 	}
@@ -712,7 +791,6 @@ file_impossible (filename)
 {
   char *dirend;
   register char *p = filename;
-  register unsigned int hash;
   register struct directory *dir;
   register struct dirfile *new;
 
@@ -765,48 +843,28 @@ file_impossible (filename)
       filename = p = slash + 1;
     }
 
-  for (hash = 0; *p != '\0'; ++p)
-    HASHI (hash, *p);
-  hash %= DIRFILE_BUCKETS;
-
   if (dir->contents == 0)
     {
       /* The directory could not be stat'd.  We allocate a contents
 	 structure for it, but leave it out of the contents hash table.  */
       dir->contents = (struct directory_contents *)
 	xmalloc (sizeof (struct directory_contents));
-#ifdef WINDOWS32
-      dir->contents->path_key = NULL;
-      dir->contents->mtime = 0;
-#else  /* WINDOWS32 */
-#ifdef VMS
-      dir->contents->dev = 0;
-      dir->contents->ino[0] = dir->contents->ino[1] =
-	dir->contents->ino[2] = 0;
-#else
-      dir->contents->dev = dir->contents->ino = 0;
-#endif
-#endif /* WINDOWS32 */
-      dir->contents->files = 0;
-      dir->contents->dirstream = 0;
+      bzero ((char *) dir->contents, sizeof (struct directory_contents));
     }
 
-  if (dir->contents->files == 0)
+  if (dir->contents->dirfiles.ht_vec == 0)
     {
-      /* The directory was not opened; we must allocate the hash buckets.  */
-      dir->contents->files = (struct dirfile **)
-	xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS);
-      bzero ((char *) dir->contents->files,
-	     sizeof (struct dirfile) * DIRFILE_BUCKETS);
+      hash_init (&dir->contents->dirfiles, DIRFILE_BUCKETS,
+		 dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
     }
 
   /* Make a new entry and put it in the table.  */
 
   new = (struct dirfile *) xmalloc (sizeof (struct dirfile));
-  new->next = dir->contents->files[hash];
-  dir->contents->files[hash] = new;
   new->name = xstrdup (filename);
+  new->length = strlen (filename);
   new->impossible = 1;
+  hash_insert (&dir->contents->dirfiles, new);
 }
 
 /* Return nonzero if FILENAME has been marked impossible.  */
@@ -817,9 +875,9 @@ file_impossible_p (filename)
 {
   char *dirend;
   register char *p = filename;
-  register unsigned int hash;
   register struct directory_contents *dir;
-  register struct dirfile *next;
+  register struct dirfile *dirfile;
+  struct dirfile dirfile_key;
 
 #ifdef VMS
   dirend = strrchr (filename, ']');
@@ -867,27 +925,25 @@ file_impossible_p (filename)
       p = filename = slash + 1;
     }
 
-  if (dir == 0 || dir->files == 0)
+  if (dir == 0 || dir->dirfiles.ht_vec == 0)
     /* There are no files entered for this directory.  */
     return 0;
 
 #ifdef __MSDOS__
-  p = filename = dosify (p);
+  filename = dosify (p);
 #endif
 #ifdef HAVE_CASE_INSENSITIVE_FS
-  p = filename = downcase (p);
+  filename = downcase (p);
 #endif
 #ifdef VMS
-  p = filename = vmsify (p, 1);
+  filename = vmsify (p, 1);
 #endif
 
-  for (hash = 0; *p != '\0'; ++p)
-    HASH (hash, *p);
-  hash %= DIRFILE_BUCKETS;
-
-  for (next = dir->files[hash]; next != 0; next = next->next)
-    if (strieq (filename, next->name))
-      return next->impossible;
+  dirfile_key.name = filename;
+  dirfile_key.length = strlen (filename);
+  dirfile = (struct dirfile *) hash_find_item (&dir->dirfiles, &dirfile_key);
+  if (dirfile)
+    return dirfile->impossible;
 
   return 0;
 }
@@ -907,78 +963,96 @@ dir_name (dir)
 void
 print_dir_data_base ()
 {
-  register unsigned int i, dirs, files, impossible;
-  register struct directory *dir;
+  register unsigned int files;
+  register unsigned int impossible;
+  register struct directory **dir_slot;
+  register struct directory **dir_end;
 
   puts (_("\n# Directories\n"));
 
-  dirs = files = impossible = 0;
-  for (i = 0; i < DIRECTORY_BUCKETS; ++i)
-    for (dir = directories[i]; dir != 0; dir = dir->next)
-      {
-	++dirs;
-	if (dir->contents == 0)
-	  printf (_("# %s: could not be stat'd.\n"), dir->name);
-	else if (dir->contents->files == 0)
+  files = impossible = 0;
+
+  dir_slot = (struct directory **) directories.ht_vec;
+  dir_end = dir_slot + directories.ht_size;
+  for ( ; dir_slot < dir_end; dir_slot++)
+    {
+      register struct directory *dir = *dir_slot;
+      if (! HASH_VACANT (dir))
+	{
+	  if (dir->contents == 0)
+	    printf (_("# %s: could not be stat'd.\n"), dir->name);
+	  else if (dir->contents->dirfiles.ht_vec == 0)
+	    {
 #ifdef WINDOWS32
-          printf (_("# %s (key %s, mtime %d): could not be opened.\n"),
-                  dir->name, dir->contents->path_key,dir->contents->mtime);
+	      printf (_("# %s (key %s, mtime %d): could not be opened.\n"),
+		      dir->name, dir->contents->path_key,dir->contents->mtime);
 #else  /* WINDOWS32 */
 #ifdef VMS
-	  printf (_("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n"),
-		  dir->name, dir->contents->dev,
-		  dir->contents->ino[0], dir->contents->ino[1],
-		  dir->contents->ino[2]);
+	      printf (_("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n"),
+		      dir->name, dir->contents->dev,
+		      dir->contents->ino[0], dir->contents->ino[1],
+		      dir->contents->ino[2]);
 #else
-	  printf (_("# %s (device %ld, inode %ld): could not be opened.\n"),
-		  dir->name, (long int) dir->contents->dev,
-		  (long int) dir->contents->ino);
+	      printf (_("# %s (device %ld, inode %ld): could not be opened.\n"),
+		      dir->name, (long int) dir->contents->dev,
+		      (long int) dir->contents->ino);
 #endif
 #endif /* WINDOWS32 */
-	else
-	  {
-	    register unsigned int f = 0, im = 0;
-	    register unsigned int j;
-	    register struct dirfile *df;
-	    for (j = 0; j < DIRFILE_BUCKETS; ++j)
-	      for (df = dir->contents->files[j]; df != 0; df = df->next)
-		if (df->impossible)
-		  ++im;
-		else
-		  ++f;
+	    }
+	  else
+	    {
+	      register unsigned int f = 0;
+	      register unsigned int im = 0;
+	      register struct dirfile **files_slot;
+	      register struct dirfile **files_end;
+
+	      files_slot = (struct dirfile **) dir->contents->dirfiles.ht_vec;
+	      files_end = files_slot + dir->contents->dirfiles.ht_size;
+	      for ( ; files_slot < files_end; files_slot++)
+		{
+		  register struct dirfile *df = *files_slot;
+		  if (! HASH_VACANT (df))
+		    {
+		      if (df->impossible)
+			++im;
+		      else
+			++f;
+		    }
+		}
 #ifdef WINDOWS32
-            printf (_("# %s (key %s, mtime %d): "),
-                    dir->name, dir->contents->path_key, dir->contents->mtime);
+	      printf (_("# %s (key %s, mtime %d): "),
+		      dir->name, dir->contents->path_key, dir->contents->mtime);
 #else  /* WINDOWS32 */
 #ifdef VMS
-	    printf (_("# %s (device %d, inode [%d,%d,%d]): "),
-		    dir->name, dir->contents->dev,
-			dir->contents->ino[0], dir->contents->ino[1],
-			dir->contents->ino[2]);
+	      printf (_("# %s (device %d, inode [%d,%d,%d]): "),
+		      dir->name, dir->contents->dev,
+		      dir->contents->ino[0], dir->contents->ino[1],
+		      dir->contents->ino[2]);
 #else
-	    printf (_("# %s (device %ld, inode %ld): "),
-		    dir->name,
-                    (long)dir->contents->dev, (long)dir->contents->ino);
+	      printf (_("# %s (device %ld, inode %ld): "),
+		      dir->name,
+		      (long)dir->contents->dev, (long)dir->contents->ino);
 #endif
 #endif /* WINDOWS32 */
-	    if (f == 0)
-	      fputs (_("No"), stdout);
-	    else
-	      printf ("%u", f);
-	    fputs (_(" files, "), stdout);
-	    if (im == 0)
-	      fputs (_("no"), stdout);
-	    else
-	      printf ("%u", im);
-	    fputs (_(" impossibilities"), stdout);
-	    if (dir->contents->dirstream == 0)
-	      puts (".");
-	    else
-	      puts (_(" so far."));
-	    files += f;
-	    impossible += im;
-	  }
-      }
+	      if (f == 0)
+		fputs (_("No"), stdout);
+	      else
+		printf ("%u", f);
+	      fputs (_(" files, "), stdout);
+	      if (im == 0)
+		fputs (_("no"), stdout);
+	      else
+		printf ("%u", im);
+	      fputs (_(" impossibilities"), stdout);
+	      if (dir->contents->dirstream == 0)
+		puts (".");
+	      else
+		puts (_(" so far."));
+	      files += f;
+	      impossible += im;
+	    }
+	}
+    }
 
   fputs ("\n# ", stdout);
   if (files == 0)
@@ -990,7 +1064,7 @@ print_dir_data_base ()
     fputs (_("no"), stdout);
   else
     printf ("%u", impossible);
-  printf (_(" impossibilities in %u directories.\n"), dirs);
+  printf (_(" impossibilities in %lu directories.\n"), directories.ht_fill);
 }
 
 /* Hooks for globbing.  */
@@ -1002,9 +1076,7 @@ print_dir_data_base ()
 struct dirstream
   {
     struct directory_contents *contents; /* The directory being read.  */
-
-    unsigned int bucket;	/* Current hash bucket.  */
-    struct dirfile *elt;	/* Current elt in bucket.  */
+    struct dirfile **dirfile_slot; /* Current slot in table.  */
   };
 
 /* Forward declarations.  */
@@ -1018,9 +1090,9 @@ open_dirstream (directory)
   struct dirstream *new;
   struct directory *dir = find_directory ((char *)directory);
 
-  if (dir->contents == 0 || dir->contents->files == 0)
+  if (dir->contents == 0 || dir->contents->dirfiles.ht_vec == 0)
     /* DIR->contents is nil if the directory could not be stat'd.
-       DIR->contents->files is nil if it could not be opened.  */
+       DIR->contents->dirfiles is nil if it could not be opened.  */
     return 0;
 
   /* Read all the contents of the directory now.  There is no benefit
@@ -1030,8 +1102,7 @@ open_dirstream (directory)
 
   new = (struct dirstream *) xmalloc (sizeof (struct dirstream));
   new->contents = dir->contents;
-  new->bucket = 0;
-  new->elt = new->contents->files[0];
+  new->dirfile_slot = (struct dirfile **) new->contents->dirfiles.ht_vec;
 
   return (__ptr_t) new;
 }
@@ -1041,45 +1112,40 @@ read_dirstream (stream)
      __ptr_t stream;
 {
   struct dirstream *const ds = (struct dirstream *) stream;
-  register struct dirfile *df;
+  struct directory_contents *dc = ds->contents;
+  struct dirfile **dirfile_end = (struct dirfile **) dc->dirfiles.ht_vec + dc->dirfiles.ht_size;
   static char *buf;
   static unsigned int bufsz;
 
-  while (ds->bucket < DIRFILE_BUCKETS)
+  while (ds->dirfile_slot < dirfile_end)
     {
-      while ((df = ds->elt) != 0)
+      register struct dirfile *df = *ds->dirfile_slot++;
+      if (! HASH_VACANT (df) && !df->impossible)
 	{
-	  ds->elt = df->next;
-	  if (!df->impossible)
+	  /* The glob interface wants a `struct dirent',
+	     so mock one up.  */
+	  struct dirent *d;
+	  unsigned int len = df->length + 1;
+	  if (sizeof *d - sizeof d->d_name + len > bufsz)
 	    {
-	      /* The glob interface wants a `struct dirent',
-		 so mock one up.  */
-	      struct dirent *d;
-	      unsigned int len = strlen (df->name) + 1;
+	      if (buf != 0)
+		free (buf);
+	      bufsz *= 2;
 	      if (sizeof *d - sizeof d->d_name + len > bufsz)
-		{
-		  if (buf != 0)
-		    free (buf);
-		  bufsz *= 2;
-		  if (sizeof *d - sizeof d->d_name + len > bufsz)
-		    bufsz = sizeof *d - sizeof d->d_name + len;
-		  buf = xmalloc (bufsz);
-		}
-	      d = (struct dirent *) buf;
-	      FAKE_DIR_ENTRY (d);
+		bufsz = sizeof *d - sizeof d->d_name + len;
+	      buf = xmalloc (bufsz);
+	    }
+	  d = (struct dirent *) buf;
+	  FAKE_DIR_ENTRY (d);
 #ifdef _DIRENT_HAVE_D_NAMLEN
-	      d->d_namlen = len - 1;
+	  d->d_namlen = len - 1;
 #endif
 #ifdef _DIRENT_HAVE_D_TYPE
-	      d->d_type = DT_UNKNOWN;
+	  d->d_type = DT_UNKNOWN;
 #endif
-	      memcpy (d->d_name, df->name, len);
-	      return d;
-	    }
+	  memcpy (d->d_name, df->name, len);
+	  return d;
 	}
-      if (++ds->bucket == DIRFILE_BUCKETS)
-	break;
-      ds->elt = ds->contents->files[ds->bucket];
     }
 
   return 0;
@@ -1123,3 +1189,12 @@ dir_setup_glob (gl)
   /* We don't bother setting gl_lstat, since glob never calls it.
      The slot is only there for compatibility with 4.4 BSD.  */
 }
+
+void
+hash_init_directories ()
+{
+  hash_init (&directories, DIRECTORY_BUCKETS,
+	     directory_hash_1, directory_hash_2, directory_hash_cmp);
+  hash_init (&directory_contents, DIRECTORY_BUCKETS,
+	     directory_contents_hash_1, directory_contents_hash_2, directory_contents_hash_cmp);
+}
diff --git a/expand.c b/expand.c
index e32e289..6722e1b 100644
--- a/expand.c
+++ b/expand.c
@@ -100,7 +100,7 @@ recursively_expand_for_file (v, file)
      struct file *file;
 {
   char *value;
-  struct variable_set_list *save;
+  struct variable_set_list *save = 0;
 
   if (v->expanding)
     {
diff --git a/file.c b/file.c
index 1e87443..cfb11bb 100644
--- a/file.c
+++ b/file.c
@@ -1,5 +1,6 @@
 /* Target file hash table management for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,94,95,96,97 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -27,14 +28,34 @@ Boston, MA 02111-1307, USA.  */
 #include "commands.h"
 #include "variable.h"
 #include "debug.h"
+#include "hash.h"
 
 
 /* Hash table of files the makefile knows how to make.  */
 
+static unsigned long
+file_hash_1 (void const *key)
+{
+  return_ISTRING_HASH_1 (((struct file const *) key)->hname);
+}
+
+static unsigned long
+file_hash_2 (void const *key)
+{
+  return_ISTRING_HASH_2 (((struct file const *) key)->hname);
+}
+
+static int
+file_hash_cmp (void const *x, void const *y)
+{
+  return_ISTRING_COMPARE (((struct file const *) x)->hname,
+			  ((struct file const *) y)->hname);
+}
+
 #ifndef	FILE_BUCKETS
 #define FILE_BUCKETS	1007
 #endif
-static struct file *files[FILE_BUCKETS];
+static struct hash_table files;
 
 /* Whether or not .SECONDARY with no prerequisites was given.  */
 static int all_secondary = 0;
@@ -49,8 +70,7 @@ lookup_file (name)
      char *name;
 {
   register struct file *f;
-  register char *n;
-  register unsigned int hashval;
+  struct file file_key;
 #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS)
   register char *lname, *ln;
 #endif
@@ -62,11 +82,14 @@ lookup_file (name)
      on the command line.  */
 #ifdef VMS
 # ifndef WANT_CASE_SENSITIVE_TARGETS
-  lname = (char *)malloc(strlen(name) + 1);
-  for (n=name, ln=lname; *n != '\0'; ++n, ++ln)
-    *ln = isupper((unsigned char)*n) ? tolower((unsigned char)*n) : *n;
-  *ln = '\0';
-  name = lname;
+  {
+    register char *n;
+    lname = (char *) malloc (strlen (name) + 1);
+    for (n = name, ln = lname; *n != '\0'; ++n, ++ln)
+      *ln = isupper ((unsigned char)*n) ? tolower ((unsigned char)*n) : *n;
+    *ln = '\0';
+    name = lname;
+  }
 # endif
 
   while (name[0] == '[' && name[1] == ']' && name[2] != '\0')
@@ -92,34 +115,22 @@ lookup_file (name)
 #endif /* AMIGA */
 #endif /* VMS */
 
-  hashval = 0;
-  for (n = name; *n != '\0'; ++n)
-    HASHI (hashval, *n);
-  hashval %= FILE_BUCKETS;
-
-  for (f = files[hashval]; f != 0; f = f->next)
-    {
-      if (strieq (f->hname, name))
-	{
-#if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS)
-	  free (lname);
-#endif
-	  return f;
-	}
-    }
+  file_key.hname = name;
+  f = (struct file *) hash_find_item (&files, &file_key);
 #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS)
   free (lname);
 #endif
-  return 0;
+  return f;
 }
 
 struct file *
 enter_file (name)
      char *name;
 {
-  register struct file *f, *new;
-  register char *n;
-  register unsigned int hashval;
+  register struct file *f;
+  register struct file *new;
+  register struct file **file_slot;
+  struct file file_key;
 #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS)
   char *lname, *ln;
 #endif
@@ -127,30 +138,28 @@ enter_file (name)
   assert (*name != '\0');
 
 #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS)
-  lname = (char *)malloc (strlen (name) + 1);
-  for (n = name, ln = lname; *n != '\0'; ++n, ++ln)
-    {
-      if (isupper((unsigned char)*n))
-	*ln = tolower((unsigned char)*n);
-      else
-	*ln = *n;
-    }
-  *ln = 0;
-  /* Creates a possible leak, old value of name is unreachable, but I
-     currently don't know how to fix it. */
-  name = lname;
-#endif
-
-  hashval = 0;
-  for (n = name; *n != '\0'; ++n)
-    HASHI (hashval, *n);
-  hashval %= FILE_BUCKETS;
+  {
+    register char *n;
+    lname = (char *) malloc (strlen (name) + 1);
+    for (n = name, ln = lname; *n != '\0'; ++n, ++ln)
+      {
+        if (isupper ((unsigned char)*n))
+          *ln = tolower ((unsigned char)*n);
+        else
+          *ln = *n;
+      }
 
-  for (f = files[hashval]; f != 0; f = f->next)
-    if (strieq (f->hname, name))
-      break;
+    *ln = 0;
+    /* Creates a possible leak, old value of name is unreachable, but I
+       currently don't know how to fix it. */
+    name = lname;
+  }
+#endif
 
-  if (f != 0 && !f->double_colon)
+  file_key.hname = name;
+  file_slot = (struct file **) hash_find_slot (&files, &file_key);
+  f = *file_slot;
+  if (! HASH_VACANT (f) && !f->double_colon)
     {
 #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS)
       free(lname);
@@ -163,12 +172,8 @@ enter_file (name)
   new->name = new->hname = name;
   new->update_status = -1;
 
-  if (f == 0)
-    {
-      /* This is a completely new file.  */
-      new->next = files[hashval];
-      files[hashval] = new;
-    }
+  if (HASH_VACANT (f))
+    hash_insert_at (&files, new, file_slot);
   else
     {
       /* There is already a double-colon entry for this file.  */
@@ -181,179 +186,129 @@ enter_file (name)
   return new;
 }
 
-/* Rehash FILE to NAME.  This is not as simple as resetting
-   the `hname' member, since it must be put in a new hash bucket,
-   and possibly merged with an existing file called NAME.  */
-
-void
-rehash_file (file, name)
-     register struct file *file;
-     char *name;
-{
-  char *oldname = file->hname;
-  register unsigned int oldhash;
-  register char *n;
-
-  while (file->renamed != 0)
-    file = file->renamed;
-
-  /* Find the hash values of the old and new names.  */
-
-  oldhash = 0;
-  for (n = oldname; *n != '\0'; ++n)
-    HASHI (oldhash, *n);
-
-  file_hash_enter (file, name, oldhash, file->name);
-}
-
 /* Rename FILE to NAME.  This is not as simple as resetting
    the `name' member, since it must be put in a new hash bucket,
    and possibly merged with an existing file called NAME.  */
 
 void
-rename_file (file, name)
-     register struct file *file;
-     char *name;
+rename_file (from_file, to_hname)
+     register struct file *from_file;
+     char *to_hname;
 {
-  rehash_file(file, name);
-  while (file)
+  rehash_file (from_file, to_hname);
+  while (from_file)
     {
-      file->name = file->hname;
-      file = file->prev;
+      from_file->name = from_file->hname;
+      from_file = from_file->prev;
     }
 }
 
+/* Rehash FILE to NAME.  This is not as simple as resetting
+   the `hname' member, since it must be put in a new hash bucket,
+   and possibly merged with an existing file called NAME.  */
+
 void
-file_hash_enter (file, name, oldhash, oldname)
-     register struct file *file;
-     char *name;
-     unsigned int oldhash;
-     char *oldname;
+rehash_file (from_file, to_hname)
+     register struct file *from_file;
+     char *to_hname;
 {
-  unsigned int oldbucket = oldhash % FILE_BUCKETS;
-  register unsigned int newhash, newbucket;
-  struct file *oldfile;
-  register char *n;
-  register struct file *f;
-
-  newhash = 0;
-  for (n = name; *n != '\0'; ++n)
-    HASHI (newhash, *n);
-  newbucket = newhash % FILE_BUCKETS;
-
-  /* Look for an existing file under the new name.  */
-
-  for (oldfile = files[newbucket]; oldfile != 0; oldfile = oldfile->next)
-    if (strieq (oldfile->hname, name))
-      break;
-
-  /* If the old file is the same as the new file, never mind.  */
-  if (oldfile == file)
+  struct file file_key;
+  struct file **file_slot;
+  struct file *to_file;
+  struct file *deleted_file;
+  struct file *f;
+
+  file_key.hname = to_hname;
+  if (0 == file_hash_cmp (from_file, &file_key))
     return;
 
-  if (oldhash != 0 && (newbucket != oldbucket || oldfile != 0))
-    {
-      /* Remove FILE from its hash bucket.  */
-
-      struct file *lastf = 0;
+  file_key.hname = from_file->hname;
+  while (from_file->renamed != 0)
+    from_file = from_file->renamed;
+  if (file_hash_cmp (from_file, &file_key))
+    /* hname changed unexpectedly */
+    abort ();
 
-      for (f = files[oldbucket]; f != file; f = f->next)
-	lastf = f;
-
-      if (lastf == 0)
-	files[oldbucket] = f->next;
-      else
-	lastf->next = f->next;
-    }
+  deleted_file = hash_delete (&files, from_file);
+  if (deleted_file != from_file)
+    /* from_file isn't the one stored in files */
+    abort ();
 
-  /* Give FILE its new name.  */
+  file_key.hname = to_hname;
+  file_slot = (struct file **) hash_find_slot (&files, &file_key);
+  to_file = *file_slot;
 
-  file->hname = name;
-  for (f = file->double_colon; f != 0; f = f->prev)
-    f->hname = name;
+  from_file->hname = to_hname;
+  for (f = from_file->double_colon; f != 0; f = f->prev)
+    f->hname = to_hname;
 
-  if (oldfile == 0)
-    {
-      /* There is no existing file with the new name.  */
-
-      if (newbucket != oldbucket)
-	{
-	  /* Put FILE in its new hash bucket.  */
-	  file->next = files[newbucket];
-	  files[newbucket] = file;
-	}
-    }
+  if (HASH_VACANT (to_file))
+    hash_insert_at (&files, from_file, file_slot);
   else
     {
-      /* There is an existing file with the new name.
-	 We must merge FILE into the existing file.  */
-
-      register struct dep *d;
+      /* TO_FILE already exists under TO_HNAME.
+	 We must retain TO_FILE and merge FROM_FILE into it.  */
 
-      if (file->cmds != 0)
+      if (from_file->cmds != 0)
 	{
-	  if (oldfile->cmds == 0)
-	    oldfile->cmds = file->cmds;
-	  else if (file->cmds != oldfile->cmds)
+	  if (to_file->cmds == 0)
+	    to_file->cmds = from_file->cmds;
+	  else if (from_file->cmds != to_file->cmds)
 	    {
 	      /* We have two sets of commands.  We will go with the
 		 one given in the rule explicitly mentioning this name,
 		 but give a message to let the user know what's going on.  */
-	      if (oldfile->cmds->fileinfo.filenm != 0)
-                error (&file->cmds->fileinfo,
-                                _("Commands were specified for \
-file `%s' at %s:%lu,"),
-                                oldname, oldfile->cmds->fileinfo.filenm,
-                                oldfile->cmds->fileinfo.lineno);
+	      if (to_file->cmds->fileinfo.filenm != 0)
+                error (&from_file->cmds->fileinfo,
+		       _("Commands were specified for file `%s' at %s:%lu,"),
+		       from_file->name, to_file->cmds->fileinfo.filenm,
+		       to_file->cmds->fileinfo.lineno);
 	      else
-		error (&file->cmds->fileinfo,
-				_("Commands for file `%s' were found by \
-implicit rule search,"),
-				oldname);
-	      error (&file->cmds->fileinfo,
-			      _("but `%s' is now considered the same file \
-as `%s'."),
-			      oldname, name);
-	      error (&file->cmds->fileinfo,
-			      _("Commands for `%s' will be ignored \
-in favor of those for `%s'."),
-			      name, oldname);
+		error (&from_file->cmds->fileinfo,
+		       _("Commands for file `%s' were found by implicit rule search,"),
+		       from_file->name);
+	      error (&from_file->cmds->fileinfo,
+		     _("but `%s' is now considered the same file as `%s'."),
+		     from_file->name, to_hname);
+	      error (&from_file->cmds->fileinfo,
+		     _("Commands for `%s' will be ignored in favor of those for `%s'."),
+		     to_hname, from_file->name);
 	    }
 	}
 
       /* Merge the dependencies of the two files.  */
 
-      d = oldfile->deps;
-      if (d == 0)
-	oldfile->deps = file->deps;
+      if (to_file->deps == 0)
+	to_file->deps = from_file->deps;
       else
 	{
-	  while (d->next != 0)
-	    d = d->next;
-	  d->next = file->deps;
+	  register struct dep *deps = to_file->deps;
+	  while (deps->next != 0)
+	    deps = deps->next;
+	  deps->next = from_file->deps;
 	}
 
-      merge_variable_set_lists (&oldfile->variables, file->variables);
+      merge_variable_set_lists (&to_file->variables, from_file->variables);
 
-      if (oldfile->double_colon && file->is_target && !file->double_colon)
+      if (to_file->double_colon && from_file->is_target && !from_file->double_colon)
 	fatal (NILF, _("can't rename single-colon `%s' to double-colon `%s'"),
-	       oldname, name);
-      if (!oldfile->double_colon  && file->double_colon)
+	       from_file->name, to_hname);
+      if (!to_file->double_colon  && from_file->double_colon)
 	{
-	  if (oldfile->is_target)
+	  if (to_file->is_target)
 	    fatal (NILF, _("can't rename double-colon `%s' to single-colon `%s'"),
-		   oldname, name);
+		   from_file->name, to_hname);
 	  else
-	    oldfile->double_colon = file->double_colon;
+	    to_file->double_colon = from_file->double_colon;
 	}
 
-      if (file->last_mtime > oldfile->last_mtime)
+      if (from_file->last_mtime > to_file->last_mtime)
 	/* %%% Kludge so -W wins on a file that gets vpathized.  */
-	oldfile->last_mtime = file->last_mtime;
+	to_file->last_mtime = from_file->last_mtime;
 
-      oldfile->mtime_before_update = file->mtime_before_update;
+      to_file->mtime_before_update = from_file->mtime_before_update;
 
-#define MERGE(field) oldfile->field |= file->field
+#define MERGE(field) to_file->field |= from_file->field
       MERGE (precious);
       MERGE (tried_implicit);
       MERGE (updating);
@@ -364,7 +319,7 @@ in favor of those for `%s'."),
       MERGE (ignore_vpath);
 #undef MERGE
 
-      file->renamed = oldfile;
+      from_file->renamed = to_file;
     }
 }
 
@@ -377,9 +332,9 @@ void
 remove_intermediates (sig)
      int sig;
 {
-  register int i;
-  register struct file *f;
-  char doneany;
+  register struct file **file_slot;
+  register struct file **file_end;
+  int doneany = 0;
 
   /* If there's no way we will ever remove anything anyway, punt early.  */
   if (question_flag || touch_flag || all_secondary)
@@ -388,50 +343,54 @@ remove_intermediates (sig)
   if (sig && just_print_flag)
     return;
 
-  doneany = 0;
-  for (i = 0; i < FILE_BUCKETS; ++i)
-    for (f = files[i]; f != 0; f = f->next)
-      if (f->intermediate && (f->dontcare || !f->precious)
-	  && !f->secondary && !f->cmd_target)
-	{
-	  int status;
-	  if (f->update_status == -1)
-	    /* If nothing would have created this file yet,
-	       don't print an "rm" command for it.  */
-            continue;
- 	  if (just_print_flag)
-  	    status = 0;
-	  else
-	    {
-	      status = unlink (f->name);
-	      if (status < 0 && errno == ENOENT)
-		continue;
-	    }
-	  if (!f->dontcare)
-	    {
-	      if (sig)
-		error (NILF, _("*** Deleting intermediate file `%s'"), f->name);
-	      else
-                {
-                  if (! doneany)
-                    DB (DB_BASIC, (_("Removing intermediate files...\n")));
-                  if (!silent_flag)
-                    {
-                      if (! doneany)
-                        {
-                          fputs ("rm ", stdout);
-                          doneany = 1;
-                        }
-                      else
-                        putchar (' ');
-                      fputs (f->name, stdout);
-                      fflush (stdout);
-                    }
-                }
-	      if (status < 0)
-		perror_with_name ("unlink: ", f->name);
-	    }
-	}
+  file_slot = (struct file **) files.ht_vec;
+  file_end = file_slot + files.ht_size;
+  for ( ; file_slot < file_end; file_slot++)
+    if (! HASH_VACANT (*file_slot))
+      {
+	register struct file *f = *file_slot;
+	if (f->intermediate && (f->dontcare || !f->precious)
+	    && !f->secondary && !f->cmd_target)
+	  {
+	    int status;
+	    if (f->update_status == -1)
+	      /* If nothing would have created this file yet,
+		 don't print an "rm" command for it.  */
+	      continue;
+	    if (just_print_flag)
+	      status = 0;
+	    else
+	      {
+		status = unlink (f->name);
+		if (status < 0 && errno == ENOENT)
+		  continue;
+	      }
+	    if (!f->dontcare)
+	      {
+		if (sig)
+		  error (NILF, _("*** Deleting intermediate file `%s'"), f->name);
+		else
+		  {
+		    if (! doneany)
+		      DB (DB_BASIC, (_("Removing intermediate files...\n")));
+		    if (!silent_flag)
+		      {
+			if (! doneany)
+			  {
+			    fputs ("rm ", stdout);
+			    doneany = 1;
+			  }
+			else
+			  putchar (' ');
+			fputs (f->name, stdout);
+			fflush (stdout);
+		      }
+		  }
+		if (status < 0)
+		  perror_with_name ("unlink: ", f->name);
+	      }
+	  }
+      }
 
   if (doneany && !sig)
     {
@@ -449,24 +408,32 @@ remove_intermediates (sig)
 void
 snap_deps ()
 {
-  register struct file *f, *f2;
+  register struct file *f;
+  register struct file *f2;
   register struct dep *d;
-  register int i;
+  register struct file **file_slot_0;
+  register struct file **file_slot;
+  register struct file **file_end;
 
   /* Enter each dependency name as a file.  */
-  for (i = 0; i < FILE_BUCKETS; ++i)
-    for (f = files[i]; f != 0; f = f->next)
-      for (f2 = f; f2 != 0; f2 = f2->prev)
-	for (d = f2->deps; d != 0; d = d->next)
-	  if (d->name != 0)
-	    {
-	      d->file = lookup_file (d->name);
-	      if (d->file == 0)
-		d->file = enter_file (d->name);
-	      else
-		free (d->name);
-	      d->name = 0;
-	    }
+  /* We must use hash_dump (), because within this loop
+     we might add new files to the table, possibly causing
+     an in-situ table expansion.  */
+  file_slot_0 = (struct file **) hash_dump (&files, 0, 0);
+  file_end = file_slot_0 + files.ht_fill;
+  for (file_slot = file_slot_0; file_slot < file_end; file_slot++)
+    for (f2 = *file_slot; f2 != 0; f2 = f2->prev)
+      for (d = f2->deps; d != 0; d = d->next)
+	if (d->name != 0)
+	  {
+	    d->file = lookup_file (d->name);
+	    if (d->file == 0)
+	      d->file = enter_file (d->name);
+	    else
+	      free (d->name);
+	    d->name = 0;
+	  }
+  free (file_slot_0);
 
   for (f = lookup_file (".PRECIOUS"); f != 0; f = f->prev)
     for (d = f->deps; d != 0; d = d->next)
@@ -790,41 +757,18 @@ print_file (f)
 void
 print_file_data_base ()
 {
-  register unsigned int i, nfiles, per_bucket;
-  register struct file *file;
-
   puts (_("\n# Files"));
 
-  per_bucket = nfiles = 0;
-  for (i = 0; i < FILE_BUCKETS; ++i)
-    {
-      register unsigned int this_bucket = 0;
-
-      for (file = files[i]; file != 0; file = file->next)
-	{
-	  register struct file *f;
-
-	  ++this_bucket;
-
-	  for (f = file; f != 0; f = f->prev)
-	    print_file (f);
-	}
+  hash_map (&files, print_file);
 
-      nfiles += this_bucket;
-      if (this_bucket > per_bucket)
-	per_bucket = this_bucket;
-    }
+  fputs (_("\n# files hash-table stats:\n# "), stdout);
+  hash_print_stats (&files, stdout);
+}
 
-  if (nfiles == 0)
-    puts (_("\n# No files."));
-  else
-    {
-      printf (_("\n# %u files in %u hash buckets.\n"), nfiles, FILE_BUCKETS);
-#ifndef	NO_FLOAT
-      printf (_("# average %.3f files per bucket, max %u files in one bucket.\n"),
-	      ((double) nfiles) / ((double) FILE_BUCKETS), per_bucket);
-#endif
-    }
+void
+init_hash_files ()
+{
+  hash_init (&files, 1000, file_hash_1, file_hash_2, file_hash_cmp);
 }
 
 /* EOF */
diff --git a/filedef.h b/filedef.h
index 4a5b9dd..7ee2902 100644
--- a/filedef.h
+++ b/filedef.h
@@ -1,5 +1,6 @@
 /* Definition of target file data structures for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,94,97 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1997,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -22,13 +23,14 @@ Boston, MA 02111-1307, USA.  */
    that the makefile says how to make.
    All of these are chained together through `next'.  */
 
+#include "hash.h"
+
 struct file
   {
-    struct file *next;
     char *name;
     char *hname;                /* Hashed filename */
     char *vpath;                /* VPATH/vpath pathname */
-    struct dep *deps;
+    struct dep *deps;		/* all dependencies, including duplicates */
     struct commands *cmds;	/* Commands to execute for this target.  */
     int command_flags;		/* Flags OR'd in for cmds; see commands.h.  */
     char *stem;			/* Implicit stem, if an implicit
@@ -106,11 +108,9 @@ extern void remove_intermediates PARAMS ((int sig));
 extern void snap_deps PARAMS ((void));
 extern void rename_file PARAMS ((struct file *file, char *name));
 extern void rehash_file PARAMS ((struct file *file, char *name));
-extern void file_hash_enter PARAMS ((struct file *file, char *name,
-                                     unsigned int oldhash, char *oldname));
 extern void set_command_state PARAMS ((struct file *file, int state));
 extern void notice_finished_file PARAMS ((struct file *file));
-
+extern void init_hash_files PARAMS ((void));
 
 #if FILE_TIMESTAMP_HI_RES
 # define FILE_TIMESTAMP_STAT_MODTIME(fname, st) \
diff --git a/function.c b/function.c
index 889caa8..c67d8a9 100644
--- a/function.c
+++ b/function.c
@@ -1,5 +1,5 @@
 /* Builtin function expansion for GNU Make.
-Copyright (C) 1988,1989,1991-1997,1999 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1991-1997, 1999, 2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -39,6 +39,33 @@ struct function_table_entry
     char expand_args;
     char *(*func_ptr) PARAMS ((char *output, char **argv, const char *fname));
   };
+
+static unsigned long
+function_table_entry_hash_1 (void const *keyv)
+{
+  struct function_table_entry const *key = (struct function_table_entry const *) keyv;
+  return_STRING_N_HASH_1 (key->name, key->len);
+}
+
+static unsigned long
+function_table_entry_hash_2 (void const *keyv)
+{
+  struct function_table_entry const *key = (struct function_table_entry const *) keyv;
+  return_STRING_N_HASH_2 (key->name, key->len);
+}
+
+static int
+function_table_entry_hash_cmp (void const *xv, void const *yv)
+{
+  struct function_table_entry const *x = (struct function_table_entry const *) xv;
+  struct function_table_entry const *y = (struct function_table_entry const *) yv;
+  int result = x->len - y->len;
+  if (result)
+    return result;
+  return_STRING_N_COMPARE (x->name, y->name, x->len);
+}
+
+static struct hash_table function_table;
 
 
 /* Store into VARIABLE_BUFFER at O the result of scanning TEXT and replacing
@@ -221,25 +248,25 @@ patsubst_expand (o, text, pattern, replace, pattern_percent, replace_percent)
 }
 
 
-/* Look up a function by name.
-   The table is currently small enough that it's not really worthwhile to use
-   a fancier lookup algorithm.  If it gets larger, maybe...
-*/
+/* Look up a function by name.  */
 
 static const struct function_table_entry *
-lookup_function (table, s)
-     const struct function_table_entry *table;
+lookup_function (s)
      const char *s;
 {
-  int len = strlen (s);
+  const char *e = s;
 
-  for (; table->name != NULL; ++table)
-    if (table->len <= len
-        && (isblank ((unsigned char)s[table->len]) || s[table->len] == '\0')
-        && strneq (s, table->name, table->len))
-      return table;
+  while (*e && ( (*e >= 'a' && *e <= 'z') || *e == '-'))
+    e++;
+  if (*e == '\0' || isblank ((unsigned char) *e))
+    {
+      struct function_table_entry function_table_entry_key;
+      function_table_entry_key.name = s;
+      function_table_entry_key.len = e - s;
 
-  return NULL;
+      return hash_find_item (&function_table, &function_table_entry_key);
+    }
+  return 0;
 }
 
 
@@ -862,64 +889,150 @@ func_foreach (o, argv, funcname)
 struct a_word
 {
   struct a_word *next;
+  struct a_word *chain;
   char *str;
+  int length;
   int matched;
 };
 
+static unsigned long
+a_word_hash_1 (void const *key)
+{
+  return_STRING_HASH_1 (((struct a_word const *) key)->str);
+}
+
+static unsigned long
+a_word_hash_2 (void const *key)
+{
+  return_STRING_HASH_2 (((struct a_word const *) key)->str);
+}
+
+static int
+a_word_hash_cmp (void const *x, void const *y)
+{
+  int result = ((struct a_word const *) x)->length - ((struct a_word const *) y)->length;
+  if (result)
+    return result;
+  return_STRING_COMPARE (((struct a_word const *) x)->str,
+			 ((struct a_word const *) y)->str);
+}
+
+struct a_pattern
+{
+  struct a_pattern *next;
+  char *str;
+  char *percent;
+  int length;
+  int save_c;
+};
+
 static char *
 func_filter_filterout (o, argv, funcname)
      char *o;
      char **argv;
      const char *funcname;
 {
-  struct a_word *wordhead = 0;
-  struct a_word *wordtail = 0;
-
+  struct a_word *wordhead;
+  struct a_word **wordtail;
+  struct a_word *wp;
+  struct a_pattern *pathead;
+  struct a_pattern **pattail;
+  struct a_pattern *pp;
+  
+  struct hash_table a_word_table;
   int is_filter = streq (funcname, "filter");
-  char *patterns = argv[0];
+  char *pat_iterator = argv[0];
   char *word_iterator = argv[1];
-
+  int literals = 0;
+  int words = 0;
+  int hashing = 0;
   char *p;
   unsigned int len;
 
-  /* Chop ARGV[1] up into words and then run each pattern through.  */
+  /* Chop ARGV[0] up into patterns to match against the words.  */
+
+  pattail = &pathead;
+  while ((p = find_next_token (&pat_iterator, &len)) != 0)
+    {
+      struct a_pattern *pat = (struct a_pattern *) alloca (sizeof (struct a_pattern));
+
+      *pattail = pat;
+      pattail = &pat->next;
+
+      if (*pat_iterator != '\0')
+	++pat_iterator;
+
+      pat->str = p;
+      pat->length = len;
+      pat->save_c = p[len];
+      p[len] = '\0';
+      pat->percent = find_percent (p);
+      if (pat->percent == 0)
+	literals++;
+    }
+  *pattail = 0;
+
+  /* Chop ARGV[1] up into words to match against the patterns.  */
+
+  wordtail = &wordhead;
   while ((p = find_next_token (&word_iterator, &len)) != 0)
     {
-      struct a_word *w = (struct a_word *)alloca (sizeof (struct a_word));
-      if (wordhead == 0)
-	wordhead = w;
-      else
-	wordtail->next = w;
-      wordtail = w;
+      struct a_word *word = (struct a_word *) alloca (sizeof (struct a_word));
+
+      *wordtail = word;
+      wordtail = &word->next;
 
       if (*word_iterator != '\0')
 	++word_iterator;
+
       p[len] = '\0';
-      w->str = p;
-      w->matched = 0;
+      word->str = p;
+      word->length = len;
+      word->matched = 0;
+      word->chain = 0;
+      words++;
     }
+  *wordtail = 0;
 
-  if (wordhead != 0)
+  /* Only use a hash table if arg list lengths justifies the cost.  */
+  hashing = (literals >= 2 && (literals * words) >= 10);
+  if (hashing)
     {
-      char *pat_iterator = patterns;
-      int doneany = 0;
-      struct a_word *wp;
+      hash_init (&a_word_table, words, a_word_hash_1, a_word_hash_2, a_word_hash_cmp);
+      for (wp = wordhead; wp != 0; wp = wp->next)
+	{
+	  struct a_word *owp = hash_insert (&a_word_table, wp);
+	  if (owp)
+	    wp->chain = owp;
+	}
+    }
 
-      wordtail->next = 0;
+  if (words)
+    {
+      int doneany = 0;
 
       /* Run each pattern through the words, killing words.  */
-      while ((p = find_next_token (&pat_iterator, &len)) != 0)
+      for (pp = pathead; pp != 0; pp = pp->next)
 	{
-	  char *percent;
-	  char save = p[len];
-	  p[len] = '\0';
-
-	  percent = find_percent (p);
-	  for (wp = wordhead; wp != 0; wp = wp->next)
-	    wp->matched |= (percent == 0 ? streq (p, wp->str)
-			    : pattern_matches (p, percent, wp->str));
-
-	  p[len] = save;
+	  if (pp->percent)
+	    for (wp = wordhead; wp != 0; wp = wp->next)
+	      wp->matched |= pattern_matches (pp->str, pp->percent, wp->str);
+	  else if (hashing)
+	    {
+	      struct a_word a_word_key;
+	      a_word_key.str = pp->str;
+	      a_word_key.length = pp->length;
+	      wp = (struct a_word *) hash_find_item (&a_word_table, &a_word_key);
+	      while (wp)
+		{
+		  wp->matched |= 1;
+		  wp = wp->chain;
+		}
+	    }
+	  else
+	    for (wp = wordhead; wp != 0; wp = wp->next)
+	      wp->matched |= (wp->length == pp->length
+			      && strneq (pp->str, wp->str, wp->length));
 	}
 
       /* Output the words that matched (or didn't, for filter-out).  */
@@ -936,6 +1049,12 @@ func_filter_filterout (o, argv, funcname)
 	--o;
     }
 
+  for (pp = pathead; pp != 0; pp = pp->next)
+    pp->str[pp->length] = pp->save_c;
+
+  if (hashing)
+    hash_free (&a_word_table, 0);
+
   return o;
 }
 
@@ -1669,7 +1788,7 @@ func_not (char* o, char **argv, char *funcname)
 static char *func_call PARAMS ((char *o, char **argv, const char *funcname));
 
 
-static struct function_table_entry function_table[] =
+static struct function_table_entry function_table_init[] =
 {
  /* Name/size */                    /* MIN MAX EXP? Function */
   { STRING_SIZE_TUPLE("addprefix"),     2,  2,  1,  func_addsuffix_addprefix},
@@ -1704,11 +1823,12 @@ static struct function_table_entry function_table[] =
   { STRING_SIZE_TUPLE("eq"),            2,  2,  1,  func_eq},
   { STRING_SIZE_TUPLE("not"),           0,  1,  1,  func_not},
 #endif
-  { 0 }
 };
+
+#define FUNCTION_TABLE_ENTRIES (sizeof (function_table_init) / sizeof (struct function_table_entry))
 
 
-/* These must come after the definition of function_table[].  */
+/* These must come after the definition of function_table.  */
 
 static char *
 expand_builtin_function (o, argc, argv, entry_p)
@@ -1758,7 +1878,7 @@ handle_function (op, stringp)
 
   beg = *stringp + 1;
 
-  entry_p = lookup_function (function_table, beg);
+  entry_p = lookup_function (beg);
 
   if (!entry_p)
     return 0;
@@ -1881,7 +2001,7 @@ func_call (o, argv, funcname)
 
   /* Are we invoking a builtin function?  */
 
-  entry_p = lookup_function (function_table, fname);
+  entry_p = lookup_function (fname);
 
   if (entry_p)
     {
@@ -1936,3 +2056,13 @@ func_call (o, argv, funcname)
 
   return o + strlen (o);
 }
+
+void
+hash_init_function_table ()
+{
+  hash_init (&function_table, FUNCTION_TABLE_ENTRIES * 2,
+	     function_table_entry_hash_1, function_table_entry_hash_2,
+	     function_table_entry_hash_cmp);
+  hash_load (&function_table, function_table_init,
+	     FUNCTION_TABLE_ENTRIES, sizeof (struct function_table_entry));
+}
diff --git a/hash.c b/hash.c
new file mode 100644
index 0000000..525f62d
--- /dev/null
+++ b/hash.c
@@ -0,0 +1,328 @@
+/* hash.c -- hash table maintenance
+   Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc.
+   Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+*/
+
+#include "make.h"
+#include "hash.h"
+
+#define	CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
+#define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
+#define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
+#define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
+
+static void hash_rehash __P((struct hash_table* ht));
+static unsigned long round_up_2 __P((unsigned long rough));
+
+/* Implement double hashing with open addressing.  The table size is
+   always a power of two.  The secondary (`increment') hash function
+   is forced to return an odd-value, in order to be relatively prime
+   to the table size.  This guarantees that the increment can
+   potentially hit every slot in the table during collision
+   resolution.  */
+
+void *hash_deleted_item = &hash_deleted_item;
+
+/* Force the table size to be a power of two, possibly rounding up the
+   given size.  */
+
+void
+hash_init (struct hash_table* ht, unsigned long size,
+	   hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
+{
+  ht->ht_size = round_up_2 (size);
+  ht->ht_empty_slots = ht->ht_size;
+  ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
+  if (ht->ht_vec == 0)
+    {
+      fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"),
+	       ht->ht_size * sizeof(struct token *));
+      exit (1);
+    }
+
+  ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
+  ht->ht_fill = 0;
+  ht->ht_collisions = 0;
+  ht->ht_lookups = 0;
+  ht->ht_rehashes = 0;
+  ht->ht_hash_1 = hash_1;
+  ht->ht_hash_2 = hash_2;
+  ht->ht_compare = hash_cmp;
+}
+
+/* Load an array of items into `ht'.  */
+
+void
+hash_load (struct hash_table* ht, void *item_table, unsigned long cardinality, unsigned long size)
+{
+  char *items = (char *) item_table;
+  while (cardinality--)
+    {
+      hash_insert (ht, items);
+      items += size;
+    }
+}
+
+/* Returns the address of the table slot matching `key'.  If `key' is
+   not found, return the address of an empty slot suitable for
+   inserting `key'.  The caller is responsible for incrementing
+   ht_fill on insertion.  */
+
+void **
+hash_find_slot (struct hash_table* ht, void const *key)
+{
+  void **slot;
+  void **deleted_slot = 0;
+  unsigned int hash_2 = 0;
+  unsigned int hash_1 = (*ht->ht_hash_1) (key);
+
+  ht->ht_lookups++;
+  for (;;)
+    {
+      hash_1 &= (ht->ht_size - 1);
+      slot = &ht->ht_vec[hash_1];
+
+      if (*slot == 0)
+	return (deleted_slot ? deleted_slot : slot);
+      if (*slot == hash_deleted_item)
+	{
+	  if (deleted_slot == 0)
+	    deleted_slot = slot;
+	}
+      else
+	{
+	  if (key == *slot)
+	    return slot;
+	  if ((*ht->ht_compare) (key, *slot) == 0)
+	    return slot;
+	  ht->ht_collisions++;
+	}
+      if (!hash_2)
+	  hash_2 = (*ht->ht_hash_2) (key) | 1;
+      hash_1 += hash_2;
+    }
+}
+
+void *
+hash_find_item (struct hash_table* ht, void const *key)
+{
+  void **slot = hash_find_slot (ht, key);
+  return ((HASH_VACANT (*slot)) ? 0 : *slot);
+}
+
+void *
+hash_insert (struct hash_table* ht, void *item)
+{
+  void **slot = hash_find_slot (ht, item);
+  void *old_item = slot ? *slot : 0;
+  hash_insert_at (ht, item, slot);
+  return ((HASH_VACANT (old_item)) ? 0 : old_item);
+}
+
+void *
+hash_insert_at (struct hash_table* ht, void *item, void const *slot)
+{
+  void *old_item = *(void **) slot;
+  if (HASH_VACANT (old_item))
+    {
+      ht->ht_fill++;
+      if (old_item == 0)
+	ht->ht_empty_slots--;
+      old_item = item;
+    }
+  *(void const **) slot = item;
+  if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
+    {
+      hash_rehash (ht);
+      return (void *) hash_find_slot (ht, item);
+    }
+  else
+    return (void *) slot;
+}
+
+void *
+hash_delete (struct hash_table* ht, void const *item)
+{
+  void **slot = hash_find_slot (ht, item);
+  return hash_delete_at (ht, slot);
+}
+
+void *
+hash_delete_at (struct hash_table* ht, void const *slot)
+{
+  void *item = *(void **) slot;
+  if (!HASH_VACANT (item))
+    {
+      *(void const **) slot = hash_deleted_item;
+      ht->ht_fill--;
+      return item;
+    }
+  else
+    return 0;
+}
+
+void
+hash_free_items (struct hash_table* ht)
+{
+  void **vec = ht->ht_vec;
+  void **end = &vec[ht->ht_size];
+  for (; vec < end; vec++)
+    {
+      void *item = *vec;
+      if (!HASH_VACANT (item))
+	free (item);
+      *vec = 0;
+    }
+  ht->ht_fill = 0;
+  ht->ht_empty_slots = ht->ht_size;
+}
+
+void
+hash_delete_items (struct hash_table* ht)
+{
+  void **vec = ht->ht_vec;
+  void **end = &vec[ht->ht_size];
+  for (; vec < end; vec++)
+    *vec = 0;
+  ht->ht_fill = 0;
+  ht->ht_collisions = 0;
+  ht->ht_lookups = 0;
+  ht->ht_rehashes = 0;
+  ht->ht_empty_slots = ht->ht_size;
+}
+
+void
+hash_free (struct hash_table* ht, int free_items)
+{
+  if (free_items)
+    hash_free_items (ht);
+  else
+    {
+      ht->ht_fill = 0;
+      ht->ht_empty_slots = ht->ht_size;
+    }
+  free (ht->ht_vec);
+  ht->ht_vec = 0;
+  ht->ht_capacity = 0;
+}
+
+void
+hash_map (struct hash_table *ht, hash_map_func_t map)
+{
+  void **slot;
+  void **end = &ht->ht_vec[ht->ht_size];
+
+  for (slot = ht->ht_vec; slot < end; slot++)
+    {
+      if (!HASH_VACANT (*slot))
+	(*map) (*slot);
+    }
+}
+
+void
+hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
+{
+  void **slot;
+  void **end = &ht->ht_vec[ht->ht_size];
+
+  for (slot = ht->ht_vec; slot < end; slot++)
+    {
+      if (!HASH_VACANT (*slot))
+	(*map) (*slot, arg);
+    }
+}
+
+/* Double the size of the hash table in the event of overflow... */
+
+static void
+hash_rehash (struct hash_table* ht)
+{
+  unsigned long old_ht_size = ht->ht_size;
+  void **old_vec = ht->ht_vec;
+  void **ovp;
+
+  if (ht->ht_fill >= ht->ht_capacity)
+    {
+      ht->ht_size *= 2;
+      ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
+    }
+  ht->ht_rehashes++;
+  ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
+
+  for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
+    {
+      if (! HASH_VACANT (*ovp))
+	{
+	  void **slot = hash_find_slot (ht, *ovp);
+	  *slot = *ovp;
+	}
+    }
+  ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
+  free (old_vec);
+}
+
+void
+hash_print_stats (struct hash_table *ht, FILE *out_FILE)
+{
+  /* GKM FIXME: honor NO_FLOAT */
+  fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
+	   100.0 * (double) ht->ht_fill / (double) ht->ht_size);
+  fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
+  fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
+	   (ht->ht_lookups
+	    ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
+	    : 0));
+}
+
+/* Dump all items into a NULL-terminated vector.  Use the
+   user-supplied vector, or malloc one.  */
+
+void **
+hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
+{
+  void **vector;
+  void **slot;
+  void **end = &ht->ht_vec[ht->ht_size];
+
+  if (vector_0 == 0)
+    vector_0 = MALLOC (void *, ht->ht_fill + 1);
+  vector = vector_0;
+
+  for (slot = ht->ht_vec; slot < end; slot++)
+    if (!HASH_VACANT (*slot))
+      *vector++ = *slot;
+  *vector = 0;
+
+  if (compare)
+    qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
+  return vector_0;
+}
+
+/* Round a given number up to the nearest power of 2. */
+
+static unsigned long
+round_up_2 (unsigned long n)
+{
+  n |= (n >> 1);
+  n |= (n >> 2);
+  n |= (n >> 4);
+  n |= (n >> 8);
+  n |= (n >> 16);
+  n |= (n >> 32);
+
+  return n + 1;
+}
diff --git a/hash.h b/hash.h
new file mode 100644
index 0000000..60193b0
--- /dev/null
+++ b/hash.h
@@ -0,0 +1,233 @@
+/* hash.h -- decls for hash table
+   Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc.
+   Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+
+#ifndef _hash_h_
+#define _hash_h_
+
+#include <stdio.h>
+#include <ctype.h>
+
+#if defined __cplusplus || (defined __STDC__ && __STDC__) || defined WINDOWS32
+# if !defined __GLIBC__ || !defined __P
+#  undef	__P
+#  define __P(protos)	protos
+# endif
+#else /* Not C++ or ANSI C.  */
+# undef	__P
+# define __P(protos)	()
+/* We can get away without defining `const' here only because in this file
+   it is used only inside the prototype for `fnmatch', which is elided in
+   non-ANSI C where `const' is problematical.  */
+#endif /* C++ or ANSI C.  */
+
+typedef unsigned long (*hash_func_t) __P((void const *key));
+typedef int (*hash_cmp_func_t) __P((void const *x, void const *y));
+typedef void (*hash_map_func_t) __P((void const *item));
+typedef void (*hash_map_arg_func_t) __P((void const *item, void *arg));
+
+struct hash_table
+{
+  void **ht_vec;
+  unsigned long ht_size;	/* total number of slots (power of 2) */
+  unsigned long ht_capacity;	/* usable slots, limited by loading-factor */
+  unsigned long ht_fill;	/* items in table */
+  unsigned long ht_empty_slots;	/* empty slots not including deleted slots */
+  unsigned long ht_collisions;	/* # of failed calls to comparison function */
+  unsigned long ht_lookups;	/* # of queries */
+  unsigned int ht_rehashes;	/* # of times we've expanded table */
+  hash_func_t ht_hash_1;	/* primary hash function */
+  hash_func_t ht_hash_2;	/* secondary hash function */
+  hash_cmp_func_t ht_compare;	/* comparison function */
+};
+
+typedef int (*qsort_cmp_t) __P((void const *, void const *));
+
+void hash_init __P((struct hash_table *ht, unsigned long size,
+		    hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp));
+void hash_load __P((struct hash_table *ht, void *item_table,
+		    unsigned long cardinality, unsigned long size));
+void **hash_find_slot __P((struct hash_table *ht, void const *key));
+void *hash_find_item __P((struct hash_table *ht, void const *key));
+void *hash_insert __P((struct hash_table *ht, void *item));
+void *hash_insert_at __P((struct hash_table *ht, void *item, void const *slot));
+void *hash_delete __P((struct hash_table *ht, void const *item));
+void *hash_delete_at __P((struct hash_table *ht, void const *slot));
+void hash_delete_items __P((struct hash_table *ht));
+void hash_free_items __P((struct hash_table *ht));
+void hash_free __P((struct hash_table *ht, int free_items));
+void hash_map __P((struct hash_table *ht, hash_map_func_t map));
+void hash_map_arg __P((struct hash_table *ht, hash_map_arg_func_t map, void *arg));
+void hash_print_stats __P((struct hash_table *ht, FILE *out_FILE));
+void **hash_dump __P((struct hash_table *ht, void **vector_0, qsort_cmp_t compare));
+
+extern void *hash_deleted_item;
+#define HASH_VACANT(item) ((item) == 0 || (void *) (item) == hash_deleted_item)
+
+
+/* hash and comparison macros for case-sensitive string keys. */
+
+#define STRING_HASH_1(KEY, RESULT) do { \
+  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
+  while (*++_key_) \
+    (RESULT) += (*_key_ << (_key_[1] & 0xf)); \
+} while (0)
+#define return_STRING_HASH_1(KEY) do { \
+  unsigned long _result_ = 0; \
+  STRING_HASH_1 ((KEY), _result_); \
+  return _result_; \
+} while (0)
+
+#define STRING_HASH_2(KEY, RESULT) do { \
+  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
+  while (*++_key_) \
+    (RESULT) += (*_key_ << (_key_[1] & 0x7)); \
+} while (0)
+#define return_STRING_HASH_2(KEY) do { \
+  unsigned long _result_ = 0; \
+  STRING_HASH_2 ((KEY), _result_); \
+  return _result_; \
+} while (0)
+
+#define STRING_COMPARE(X, Y, RESULT) do { \
+  _RESULT_ = strcmp ((X), (Y)); \
+} while (0)
+#define return_STRING_COMPARE(X, Y) do { \
+  return strcmp ((X), (Y)); \
+} while (0)
+
+
+#define STRING_N_HASH_1(KEY, N, RESULT) do { \
+  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
+  int _n_ = (N); \
+  if (_n_) \
+    while (--_n_ && *++_key_) \
+      (RESULT) += (*_key_ << (_key_[1] & 0xf)); \
+  (RESULT) += *++_key_; \
+} while (0)
+#define return_STRING_N_HASH_1(KEY, N) do { \
+  unsigned long _result_ = 0; \
+  STRING_N_HASH_1 ((KEY), (N), _result_); \
+  return _result_; \
+} while (0)
+
+#define STRING_N_HASH_2(KEY, N, RESULT) do { \
+  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
+  int _n_ = (N); \
+  if (_n_) \
+    while (--_n_ && *++_key_) \
+      (RESULT) += (*_key_ << (_key_[1] & 0x7)); \
+  (RESULT) += *++_key_; \
+} while (0)
+#define return_STRING_N_HASH_2(KEY, N) do { \
+  unsigned long _result_ = 0; \
+  STRING_N_HASH_2 ((KEY), (N), _result_); \
+  return _result_; \
+} while (0)
+
+#define STRING_N_COMPARE(X, Y, N, RESULT) do { \
+  _RESULT_ = strncmp ((X), (Y), (N)); \
+} while (0)
+#define return_STRING_N_COMPARE(X, Y, N) do { \
+  return strncmp ((X), (Y), (N)); \
+} while (0)
+
+#ifdef HAVE_CASE_INSENSITIVE_FS
+
+/* hash and comparison macros for case-insensitive string _key_s. */
+
+#define ISTRING_HASH_1(KEY, RESULT) do { \
+  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
+  while (*++_key_) \
+    (RESULT) += ((isupper (*_key_) ? tolower (*_key_) : *_key_) << (_key_[1] & 0xf)); \
+} while (0)
+#define return_ISTRING_HASH_1(KEY) do { \
+  unsigned long _result_ = 0; \
+  ISTRING_HASH_1 ((KEY), _result_); \
+  return _result_; \
+} while (0)
+
+#define ISTRING_HASH_2(KEY, RESULT) do { \
+  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
+  while (*++_key_) \
+    (RESULT) += ((isupper (*_key_) ? tolower (*_key_) : *_key_) << (_key_[1] & 0x7)); \
+} while (0)
+#define return_ISTRING_HASH_2(KEY) do { \
+  unsigned long _result_ = 0; \
+  ISTRING_HASH_2 ((KEY), _result_); \
+  return _result_; \
+} while (0)
+
+#define ISTRING_COMPARE(X, Y, RESULT) do { \
+  _RESULT_ = stricmp ((X), (Y));
+} while (0)
+#define return_ISTRING_COMPARE(X, Y) do { \
+  return stricmp ((X), (Y));
+} while (0)
+
+#else
+
+#define ISTRING_HASH_1(KEY, RESULT) STRING_HASH_1 ((KEY), (RESULT))
+#define return_ISTRING_HASH_1(KEY) return_STRING_HASH_1 (KEY)
+
+#define ISTRING_HASH_2(KEY, RESULT) STRING_HASH_2 ((KEY), (RESULT))
+#define return_ISTRING_HASH_2(KEY) return_STRING_HASH_2 (KEY)
+
+#define ISTRING_COMPARE(X, Y, RESULT) STRING_COMPARE ((X), (Y), (RESULT))
+#define return_ISTRING_COMPARE(X, Y) return_STRING_COMPARE ((X), (Y))
+
+#endif
+
+/* hash and comparison macros for integer _key_s. */
+
+#define INTEGER_HASH_1(KEY, RESULT) do { \
+  (RESULT) += ((unsigned long)(KEY)); \
+} while (0)
+#define return_INTEGER_HASH_1(KEY) do { \
+  unsigned long _result_ = 0; \
+  INTEGER_HASH_1 ((KEY), _result_); \
+  return _result_; \
+} while (0)
+
+#define INTEGER_HASH_2(KEY, RESULT) do { \
+  (RESULT) += ~((unsigned long)(KEY)); \
+} while (0)
+#define return_INTEGER_HASH_2(KEY) do { \
+  unsigned long _result_ = 0; \
+  INTEGER_HASH_2 ((KEY), _result_); \
+  return _result_; \
+} while (0)
+
+#define INTEGER_COMPARE(X, Y, RESULT) do { \
+  (RESULT) = X - Y; \
+} while (0)
+#define return_INTEGER_COMPARE(X, Y) do { \
+  int _result_; \
+  INTEGER_COMPARE (X, Y, _result_); \
+  return _result_; \
+} while (0)
+
+/* hash and comparison macros for address keys. */
+
+#define ADDRESS_HASH_1(KEY, RESULT) INTEGER_HASH_1 (((unsigned long)(KEY)) >> 3, (RESULT))
+#define ADDRESS_HASH_2(KEY, RESULT) INTEGER_HASH_2 (((unsigned long)(KEY)) >> 3, (RESULT))
+#define ADDRESS_COMPARE(X, Y, RESULT) INTEGER_COMPARE ((X), (Y), (RESULT))
+#define return_ADDRESS_HASH_1(KEY) return_INTEGER_HASH_1 (((unsigned long)(KEY)) >> 3)
+#define return_ADDRESS_HASH_2(KEY) return_INTEGER_HASH_2 (((unsigned long)(KEY)) >> 3)
+#define return_ADDRESS_COMPARE(X, Y) return_INTEGER_COMPARE ((X), (Y))
+
+#endif /* not _hash_h_ */
diff --git a/main.c b/main.c
index fcf0b91..7079e01 100644
--- a/main.c
+++ b/main.c
@@ -1,5 +1,6 @@
 /* Argument parsing and main program of GNU Make.
-Copyright (C) 1988,89,90,91,94,95,96,97,98,99 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1994, 1995, 1996, 1997, 1998, 1999,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -75,6 +76,8 @@ static void decode_switches PARAMS ((int argc, char **argv, int env));
 static void decode_env_switches PARAMS ((char *envar, unsigned int len));
 static void define_makeflags PARAMS ((int all, int makefile));
 static char *quote_for_env PARAMS ((char *out, char *in));
+static void initialize_global_hash_tables PARAMS ((void));
+
 
 /* The structure that describes an accepted command switch.  */
 
@@ -471,6 +474,15 @@ bsd_signal (sig, func)
 # endif
 #endif
 
+static void
+initialize_global_hash_tables ()
+{
+  init_hash_global_variable_set ();
+  init_hash_files ();
+  hash_init_directories ();
+  hash_init_function_table ();
+}
+
 static struct file *
 enter_command_line_file (name)
      char *name;
@@ -951,6 +963,8 @@ int main (int argc, char ** argv)
   /* Set up to access user data (files).  */
   user_access ();
 
+  initialize_global_hash_tables ();
+
   /* Figure out where we are.  */
 
 #ifdef WINDOWS32
@@ -1217,7 +1231,7 @@ int main (int argc, char ** argv)
 #endif /* WINDOWS32 */
   /* Figure out the level of recursion.  */
   {
-    struct variable *v = lookup_variable ("MAKELEVEL", 9);
+    struct variable *v = lookup_variable (MAKELEVEL_NAME, MAKELEVEL_LENGTH);
     if (v != 0 && v->value[0] != '\0' && v->value[0] != '-')
       makelevel = (unsigned int) atoi (v->value);
     else
@@ -1807,7 +1821,8 @@ int main (int argc, char ** argv)
 
 #ifndef _AMIGA
 	  for (p = environ; *p != 0; ++p)
-	    if (strneq (*p, "MAKELEVEL=", 10))
+	    if ((*p)[MAKELEVEL_LENGTH] == '='
+		&& strneq (*p, MAKELEVEL_NAME, MAKELEVEL_LENGTH))
 	      {
 		/* The SGI compiler apparently can't understand
 		   the concept of storing the result of a function
@@ -1815,7 +1830,7 @@ int main (int argc, char ** argv)
 		char *sgi_loses;
 		sgi_loses = (char *) alloca (40);
 		*p = sgi_loses;
-		sprintf (*p, "MAKELEVEL=%u", makelevel);
+		sprintf (*p, "%s=%u", MAKELEVEL_NAME, makelevel);
 		break;
 	      }
 #else /* AMIGA */
@@ -1823,12 +1838,12 @@ int main (int argc, char ** argv)
 	    char buffer[256];
 	    int len;
 
-	    len = GetVar ("MAKELEVEL", buffer, sizeof (buffer), GVF_GLOBAL_ONLY);
+	    len = GetVar (MAKELEVEL_NAME, buffer, sizeof (buffer), GVF_GLOBAL_ONLY);
 
 	    if (len != -1)
 	    {
 	    sprintf (buffer, "%u", makelevel);
-	      SetVar ("MAKELEVEL", buffer, -1, GVF_GLOBAL_ONLY);
+	      SetVar (MAKELEVEL_NAME, buffer, -1, GVF_GLOBAL_ONLY);
 	    }
 	  }
 #endif
diff --git a/make.h b/make.h
index 5162d8b..c69bd96 100644
--- a/make.h
+++ b/make.h
@@ -1,5 +1,6 @@
 /* Miscellaneous global declarations and portability cruft for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,94,95,96,97,99 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1999,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -325,16 +326,6 @@ extern char *strsignal PARAMS ((int signum));
 extern int strcmpi (const char *,const char *);
 #endif
 
-/* Add to VAR the hashing value of C, one character in a name.  */
-#define HASH(var, c) \
-  ((var += (c)), (var = ((var) << 7) + ((var) >> 20)))
-#ifdef HAVE_CASE_INSENSITIVE_FS /* Fold filenames */
-# define HASHI(var, c) \
-   ((var += tolower((unsigned char)(c))), (var = ((var) << 7) + ((var) >> 20)))
-#else
-# define HASHI(var, c) HASH(var,c)
-#endif
-
 #if defined(__GNUC__) || defined(ENUM_BITFIELDS)
 # define ENUM_BITFIELD(bits)    :bits
 #else
@@ -430,7 +421,7 @@ extern char *sindex PARAMS ((const char *, unsigned int, \
 extern char *lindex PARAMS ((const char *, const char *, int));
 extern int alpha_compare PARAMS ((const void *, const void *));
 extern void print_spaces PARAMS ((unsigned int));
-extern char *find_char_unquote PARAMS ((char *, char *, int));
+extern char *find_char_unquote PARAMS ((char *, int, int, int));
 extern char *find_percent PARAMS ((char *));
 extern FILE *open_tmpfile PARAMS ((char **, const char *));
 
@@ -446,6 +437,7 @@ extern int file_exists_p PARAMS ((char *));
 extern int file_impossible_p PARAMS ((char *));
 extern void file_impossible PARAMS ((char *));
 extern char *dir_name PARAMS ((char *));
+extern void hash_init_directories PARAMS ((void));
 
 extern void define_default_variables PARAMS ((void));
 extern void set_default_suffixes PARAMS ((void));
diff --git a/misc.c b/misc.c
index ee0a597..b4e778a 100644
--- a/misc.c
+++ b/misc.c
@@ -1,5 +1,6 @@
 /* Miscellaneous generic support functions for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,94,95,97 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1997,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -162,7 +163,7 @@ remove_comments (line)
 {
   char *comment;
 
-  comment = find_char_unquote (line, "#", 0);
+  comment = find_char_unquote (line, '#', 0, 0);
 
   if (comment != 0)
     /* Cut off the line at the #.  */
diff --git a/read.c b/read.c
index a6d85b2..ec54650 100644
--- a/read.c
+++ b/read.c
@@ -1,5 +1,6 @@
 /* Reading and parsing of makefiles for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,94,95,96,97 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -30,6 +31,7 @@ Boston, MA 02111-1307, USA.  */
 #include "variable.h"
 #include "rule.h"
 #include "debug.h"
+#include "hash.h"
 
 
 #ifndef WINDOWS32
@@ -378,6 +380,7 @@ eval_makefile (filename, flags)
 
   reading_file = curfile;
 
+  free(ebuf.bufstart);
   return r;
 }
 
@@ -853,7 +856,7 @@ eval (ebuf, set_default)
 
         /* Search the line for an unquoted ; that is not after an
            unquoted #.  */
-        cmdleft = find_char_unquote (line, ";#", 0);
+        cmdleft = find_char_unquote (line, ';', '#', 0);
         if (cmdleft != 0 && *cmdleft == '#')
           {
             /* We found a comment before a semicolon.  */
@@ -899,7 +902,7 @@ eval (ebuf, set_default)
             if (cmdleft == 0)
               {
                 /* Look for a semicolon in the expanded line.  */
-                cmdleft = find_char_unquote (p2, ";", 0);
+                cmdleft = find_char_unquote (p2, ';', 0, 0);
 
                 if (cmdleft != 0)
                   {
@@ -926,7 +929,7 @@ eval (ebuf, set_default)
                   }
               }
 
-            colonp = find_char_unquote(p2, ":", 0);
+            colonp = find_char_unquote(p2, ':', 0, 0);
 #if defined(__MSDOS__) || defined(WINDOWS32)
             /* The drive spec brain-damage strikes again...  */
             /* Note that the only separators of targets in this context
@@ -935,7 +938,7 @@ eval (ebuf, set_default)
             while (colonp && (colonp[1] == '/' || colonp[1] == '\\') &&
                    colonp > p2 && isalpha ((unsigned char)colonp[-1]) &&
                    (colonp == p2 + 1 || strchr (" \t(", colonp[-2]) != 0))
-              colonp = find_char_unquote(colonp + 1, ":", 0);
+              colonp = find_char_unquote(colonp + 1, ':', 0, 0);
 #endif
             if (colonp != 0)
               break;
@@ -1038,7 +1041,7 @@ eval (ebuf, set_default)
 
         /* This is a normal target, _not_ a target-specific variable.
            Unquote any = in the dependency list.  */
-        find_char_unquote (lb_next, "=", 0);
+        find_char_unquote (lb_next, '=', 0, 0);
 
         /* We have some targets, so don't ignore the following commands.  */
         no_targets = 0;
@@ -1053,7 +1056,7 @@ eval (ebuf, set_default)
             /* Look for a semicolon in the expanded line.  */
             if (cmdleft == 0)
               {
-                cmdleft = find_char_unquote (p2, ";", 0);
+                cmdleft = find_char_unquote (p2, ';', 0, 0);
                 if (cmdleft != 0)
                   *(cmdleft++) = '\0';
               }
@@ -1519,47 +1522,68 @@ conditional_line (line, flocp)
 
 /* Remove duplicate dependencies in CHAIN.  */
 
+static unsigned long
+dep_hash_1 (void const *key)
+{
+  return_STRING_HASH_1 (dep_name ((struct dep const *) key));
+}
+
+static unsigned long
+dep_hash_2 (void const *key)
+{
+  return_STRING_HASH_2 (dep_name ((struct dep const *) key));
+}
+
+static int
+dep_hash_cmp (void const *x, void const *y)
+{
+  struct dep *dx = (struct dep *) x;
+  struct dep *dy = (struct dep *) y;
+  int cmp = strcmp (dep_name (dx), dep_name (dy));
+
+  /* If the names are the same but ignore_mtimes are not equal, one of these
+     is an order-only prerequisite and one isn't.  That means that we should
+     remove the one that isn't and keep the one that is.  */
+
+  if (!cmp && dx->ignore_mtime != dy->ignore_mtime)
+    dx->ignore_mtime = dy->ignore_mtime = 0;
+
+  return cmp;
+}
+
+
 void
 uniquize_deps (chain)
      struct dep *chain;
 {
-  register struct dep *d;
+  struct hash_table deps;
+  register struct dep **depp;
+
+  hash_init (&deps, 500, dep_hash_1, dep_hash_2, dep_hash_cmp);
 
   /* Make sure that no dependencies are repeated.  This does not
      really matter for the purpose of updating targets, but it
      might make some names be listed twice for $^ and $?.  */
 
-  for (d = chain; d != 0; d = d->next)
+  depp = &chain;
+  while (*depp)
     {
-      struct dep *last, *next;
-
-      last = d;
-      next = d->next;
-      while (next != 0)
-	if (streq (dep_name (d), dep_name (next)))
-	  {
-	    struct dep *n = next->next;
-            /* If ignore_mtimes are not equal, one of these is an order-only
-               prerequisite and one isn't.  That means that we should remove
-               the one that isn't and keep the one that is.  Ideally we'd
-               like to keep the normal one always but that's hard, and
-               probably not very important, so just remove the second one and
-               force the first one to be normal.  */
-            if (d->ignore_mtime != next->ignore_mtime)
-              d->ignore_mtime = 0;
-	    last->next = n;
-	    if (next->name != 0 && next->name != d->name)
-	      free (next->name);
-	    if (next != d)
-	      free ((char *) next);
-	    next = n;
-	  }
-	else
-	  {
-	    last = next;
-	    next = next->next;
-	  }
+      struct dep *dep = *depp;
+      struct dep **dep_slot = (struct dep **) hash_find_slot (&deps, dep);
+      if (HASH_VACANT (*dep_slot))
+	{
+	  hash_insert_at (&deps, dep, dep_slot);
+	  depp = &dep->next;
+	}
+      else
+	{
+	  /* Don't bother freeing duplicates.
+	     It's dangerous and little benefit accrues.  */
+	  *depp = dep->next;
+	}
     }
+
+  hash_free (&deps, 0);
 }
 
 /* Record target-specific variable values for files FILENAMES.
@@ -2076,9 +2100,10 @@ record_files (filenames, pattern, pattern_percent, deps, cmds_started,
    one, or nil if there are none.  */
 
 char *
-find_char_unquote (string, stopchars, blank)
+find_char_unquote (string, stop1, stop2, blank)
      char *string;
-     char *stopchars;
+     int stop1;
+     int stop2;
      int blank;
 {
   unsigned int string_len = 0;
@@ -2086,9 +2111,21 @@ find_char_unquote (string, stopchars, blank)
 
   while (1)
     {
-      while (*p != '\0' && strchr (stopchars, *p) == 0
-	     && (!blank || !isblank ((unsigned char)*p)))
-	++p;
+      if (stop2 && blank)
+	while (*p != '\0' && *p != stop1 && *p != stop2
+	       && ! isblank ((unsigned char) *p))
+	  ++p;
+      else if (stop2)
+	while (*p != '\0' && *p != stop1 && *p != stop2)
+	  ++p;
+      else if (blank)
+	while (*p != '\0' && *p != stop1
+	       && ! isblank ((unsigned char) *p))
+	  ++p;
+      else
+	while (*p != '\0' && *p != stop1)
+	  ++p;
+
       if (*p == '\0')
 	break;
 
@@ -2128,7 +2165,7 @@ char *
 find_percent (pattern)
      char *pattern;
 {
-  return find_char_unquote (pattern, "%", 0);
+  return find_char_unquote (pattern, '%', 0, 0);
 }
 
 /* Parse a string into a sequence of filenames represented as a
@@ -2156,15 +2193,11 @@ parse_file_seq (stringp, stopchar, size, strip)
   register char *p = *stringp;
   char *q;
   char *name;
-  char stopchars[3];
 
 #ifdef VMS
-  stopchars[0] = ',';
-  stopchars[1] = stopchar;
-  stopchars[2] = '\0';
+# define VMS_COMMA ','
 #else
-  stopchars[0] = stopchar;
-  stopchars[1] = '\0';
+# define VMS_COMMA 0
 #endif
 
   while (1)
@@ -2178,7 +2211,7 @@ parse_file_seq (stringp, stopchar, size, strip)
 
       /* Yes, find end of next name.  */
       q = p;
-      p = find_char_unquote (q, stopchars, 1);
+      p = find_char_unquote (q, stopchar, VMS_COMMA, 1);
 #ifdef VMS
 	/* convert comma separated list to space separated */
       if (p && *p == ',')
@@ -2189,7 +2222,7 @@ parse_file_seq (stringp, stopchar, size, strip)
           && !(isspace ((unsigned char)p[1]) || !p[1]
                || isspace ((unsigned char)p[-1])))
       {
-	p = find_char_unquote (p+1, stopchars, 1);
+	p = find_char_unquote (p+1, stopchar, VMS_COMMA, 1);
       }
 #endif
 #if defined(WINDOWS32) || defined(__MSDOS__)
@@ -2200,7 +2233,7 @@ parse_file_seq (stringp, stopchar, size, strip)
     if (stopchar == ':')
       while (p != 0 && !isspace ((unsigned char)*p) &&
              (p[1] == '\\' || p[1] == '/') && isalpha ((unsigned char)p[-1]))
-        p = find_char_unquote (p + 1, stopchars, 1);
+        p = find_char_unquote (p + 1, stopchar, VMS_COMMA, 1);
 #endif
       if (p == 0)
 	p = q + strlen (q);
@@ -2436,9 +2469,9 @@ static long
 readline (ebuf)
      struct ebuffer *ebuf;
 {
-  char *buffer = ebuf->buffer;
-  char *p = ebuf->buffer;
-  char *end = p + ebuf->size;
+  char *p;
+  char *end;
+  char *start;
   long nlines = 0;
 
   /* The behaviors between string and stream buffers are different enough to
@@ -2447,6 +2480,11 @@ readline (ebuf)
   if (!ebuf->fp)
     return readstring (ebuf);
 
+  /* When reading from a file, we always start over at the beginning of the
+     buffer for each new line.  */
+
+  p = start = ebuf->bufstart;
+  end = p + ebuf->size;
   *p = '\0';
 
   while (fgets (p, end - p, ebuf->fp) != 0)
@@ -2475,16 +2513,7 @@ readline (ebuf)
       /* If the last char isn't a newline, the whole line didn't fit into the
          buffer.  Get some more buffer and try again.  */
       if (p[-1] != '\n')
-	{
-	  unsigned long p_off = p - buffer;
-	  ebuf->size *= 2;
-	  buffer = (char *) xrealloc (buffer, ebuf->size);
-	  p = buffer + p_off;
-	  end = buffer + ebuf->size;
-	  ebuf->buffer = buffer;
-	  *p = '\0';
-	  continue;
-	}
+        goto more_buffer;
 
       /* We got a newline, so add one to the count of lines.  */
       ++nlines;
@@ -2492,7 +2521,7 @@ readline (ebuf)
 #if !defined(WINDOWS32) && !defined(__MSDOS__)
       /* Check to see if the line was really ended with CRLF; if so ignore
          the CR.  */
-      if ((p - buffer) > 1 && p[-2] == '\r')
+      if ((p - start) > 1 && p[-2] == '\r')
         {
           --p;
           p[-1] = '\n';
@@ -2500,7 +2529,7 @@ readline (ebuf)
 #endif
 
       backslash = 0;
-      for (p2 = p - 2; p2 >= buffer; --p2)
+      for (p2 = p - 2; p2 >= start; --p2)
 	{
 	  if (*p2 != '\\')
 	    break;
@@ -2513,16 +2542,23 @@ readline (ebuf)
 	  break;
 	}
 
-      if (end - p <= 1)
-	{
-	  /* Enlarge the buffer.  */
-	  unsigned int p_off = p - buffer;
-	  ebuf->size *= 2;
-	  buffer = (char *) xrealloc (buffer, ebuf->size);
-	  p = buffer + p_off;
-	  end = buffer + ebuf->size;
-	  ebuf->buffer = buffer;
-	}
+      /* It was a backslash/newline combo.  If we have more space, read
+         another line.  */
+      if (end - p >= 80)
+        continue;
+
+      /* We need more space at the end of our buffer, so realloc it.
+         Make sure to preserve the current offset of p.  */
+    more_buffer:
+      {
+        unsigned long off = p - start;
+        ebuf->size *= 2;
+        start = ebuf->buffer = ebuf->bufstart = (char *) xrealloc (start,
+                                                                   ebuf->size);
+        p = start + off;
+        end = start + ebuf->size;
+        *p = '\0';
+      }
     }
 
   if (ferror (ebuf->fp))
diff --git a/remake.c b/remake.c
index fcefdc7..66c6d31 100644
--- a/remake.c
+++ b/remake.c
@@ -1,5 +1,6 @@
 /* Basic dependency engine for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,94,95,96,97,99 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1999,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
diff --git a/tests/ChangeLog b/tests/ChangeLog
index 3a13e9e..2dc997f 100644
--- a/tests/ChangeLog
+++ b/tests/ChangeLog
@@ -1,3 +1,13 @@
+2002-07-11  Paul D. Smith  <psmith@gnu.org>
+
+	* run_make_tests.pl (valid_option): Add support for Valgrind
+	<http://developer.kde.org/~sewardj/>.  Use -valgrind option to the
+	test suite.
+	(set_more_defaults): Set up the file descriptor to capture
+	Valgrind output.  We have to unset its close-on-exec flag; we
+	hardcode the value for F_SETFD (2) rather than load it; hopefully
+	this will help us avoid breaking the Windows/DOS test suite.
+
 2002-07-10  Paul D. Smith  <psmith@gnu.org>
 
 	* scripts/variables/automatic: Add some tests for $$@, $$(@D), and
diff --git a/tests/run_make_tests.pl b/tests/run_make_tests.pl
index baf55f8..0ada574 100755
--- a/tests/run_make_tests.pl
+++ b/tests/run_make_tests.pl
@@ -11,11 +11,16 @@
 #                         [-make <make prog>]
 #                        (and others)
 
+$valgrind = 0;              # invoke make with valgrind
+
 require "test_driver.pl";
 
+#$SIG{INT} = sub { print STDERR "Caught a signal!\n"; die @_; };
+
 sub valid_option
 {
    local($option) = @_;
+
    if ($option =~ /^-make([-_]?path)?$/)
    {
       $make_path = shift @argv;
@@ -27,6 +32,11 @@ sub valid_option
       return 1;
    }
 
+   if ($option =~ /^-valgrind$/i) {
+     $valgrind = 1;
+     return 1;
+   }
+
 # This doesn't work--it _should_!  Someone needs to fix this badly.
 #
 #   elsif ($option =~ /^-work([-_]?dir)?$/)
@@ -56,6 +66,10 @@ sub run_make_with_options
       $command .= " $options";
    }
 
+   if ($valgrind) {
+     print VALGRIND "\n\nExecuting: $command\n";
+   }
+
    $code = &run_command_with_output($logname,$command);
 
    # Check to see if we have Purify errors.  If so, keep the logfile.
@@ -81,6 +95,11 @@ sub run_make_with_options
    {
       print "Error running $make_path ($code): $command\n";
       $test_passed = 0;
+      # If it's a SIGINT, stop here
+      if ($code & 127) {
+        print STDERR "\nCaught signal ".($code & 127)."!\n";
+        exit($code);
+      }
       return 0;
    }
 
@@ -215,6 +234,21 @@ sub set_more_defaults
    else {
      $parallel_jobs = 1;
    }
+
+   # Set up for valgrind, if requested.
+
+   if ($valgrind) {
+#     use POSIX qw(:fcntl_h);
+#     require Fcntl;
+     open(VALGRIND, "> valgrind.out")
+       || die "Cannot open valgrind.out: $!\n";
+     #  -q --leak-check=yes
+     $make_path = "valgrind --num-callers=15 --logfile-fd=".fileno(VALGRIND)." $make_path";
+     # F_SETFD is 2
+     fcntl(VALGRIND, 2, 0) or die "fcntl(setfd) failed: $!\n";
+     system("echo Starting on `date` 1>&".fileno(VALGRIND));
+     print "Enabled valgrind support.\n";
+   }
 }
 
 sub setup_for_test
diff --git a/tests/scripts/functions/filter-out b/tests/scripts/functions/filter-out
index 0559a8d..6c8b27a 100644
--- a/tests/scripts/functions/filter-out
+++ b/tests/scripts/functions/filter-out
@@ -1,35 +1,28 @@
-$description = "The following test creates a makefile to test static \n"
-              ."pattern rules.  Static pattern rules are rules which \n"
-              ."specify multiple targets and construct the dependency \n"
-              ."names for each target based on the target name. ";
+#                                                                    -*-perl-*-
 
-$details = "The makefile created in this test has three targets.  The \n"
-          ."filter command is used to get those target names ending in \n"
-          .".o and statically creates a compile command with the target\n"
-          ."name and the target name with .c.  It also does the same thing\n"
-          ."for another target filtered with .elc and creates a command\n"
-          ."to emacs a .el file";
+$description = "Test the filter-out function.";
 
-open(MAKEFILE,"> $makefile");
-
-# The Contents of the MAKEFILE ...
+$details = "The makefile created in this test has two variables.  The
+filter-out function is first used to discard names ending in
+.o with a single simple pattern.  The second filter-out function
+augments the simple pattern with three literal names, which are
+also added to the text argument.  This tests an internal hash table
+which is only used if there are multiple literals present in both
+the pattern and text arguments.  The result of both filter-out
+functions is the same single .elc name.\n";
 
-print MAKEFILE "files := \$(filter-out %.o, foo.elc bar.o lose.o) \n" 
-              ."all: \n"
-              ."\t\@echo \$(files) \n";
+open(MAKEFILE,"> $makefile");
 
-# END of Contents of MAKEFILE
+print MAKEFILE <<'EOF';
+files1 := $(filter-out %.o, foo.elc bar.o lose.o)
+files2 := $(filter-out foo.i bar.i lose.i %.o, foo.i bar.i lose.i foo.elc bar.o lose.o)
+all: ; @echo $(files1) $(files2)
+EOF
 
 close(MAKEFILE);
 
-&run_make_with_options($makefile,
-                       "",
-                       &get_logfile,
-                       0);
-
-# Create the answer to what should be produced by this Makefile
-$answer = "foo.elc\n";
-
+&run_make_with_options($makefile, "", &get_logfile, 0);
+$answer = "foo.elc foo.elc\n";
 &compare_output($answer,&get_logfile(1));
 
 1;
diff --git a/tests/scripts/targets/INTERMEDIATE b/tests/scripts/targets/INTERMEDIATE
index fe3f4e9..725ab0e 100644
--- a/tests/scripts/targets/INTERMEDIATE
+++ b/tests/scripts/targets/INTERMEDIATE
@@ -59,7 +59,7 @@ $answer = "cp foo.f foo.e\ncp foo.e foo.d\nrm foo.e\n";
 # TEST #3
 
 &run_make_with_options($makefile,'foo.c',&get_logfile);
-$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm foo.e bar.e\n";
+$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm bar.e foo.e\n";
 &compare_output($answer, &get_logfile(1));
 
 # TEST #4
@@ -74,7 +74,7 @@ sleep($wtime);
 &touch('foo.f');
 
 &run_make_with_options($makefile,'foo.c',&get_logfile);
-$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm foo.e bar.e\n";
+$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm bar.e foo.e\n";
 &compare_output($answer, &get_logfile(1));
 
 # TEST #6 -- added for PR/1669: don't remove files mentioned on the cmd line.
diff --git a/variable.c b/variable.c
index ca9265c..5495fbc 100644
--- a/variable.c
+++ b/variable.c
@@ -1,5 +1,6 @@
 /* Internals of variables for GNU Make.
-Copyright (C) 1988,89,90,91,92,93,94,96,97 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1996, 1997,
+2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -27,9 +28,35 @@ Boston, MA 02111-1307, USA.  */
 #ifdef WINDOWS32
 #include "pathstuff.h"
 #endif
+#include "hash.h"
 
 /* Hash table of all global variable definitions.  */
 
+static unsigned long
+variable_hash_1 (void const *keyv)
+{
+  struct variable const *key = (struct variable const *) keyv;
+  return_STRING_N_HASH_1 (key->name, key->length);
+}
+
+static unsigned long
+variable_hash_2 (void const *keyv)
+{
+  struct variable const *key = (struct variable const *) keyv;
+  return_STRING_N_HASH_2 (key->name, key->length);
+}
+
+static int
+variable_hash_cmp (void const *xv, void const *yv)
+{
+  struct variable const *x = (struct variable const *) xv;
+  struct variable const *y = (struct variable const *) yv;
+  int result = x->length - y->length;
+  if (result)
+    return result;
+  return_STRING_N_COMPARE (x->name, y->name, x->length);
+}
+
 #ifndef	VARIABLE_BUCKETS
 #define VARIABLE_BUCKETS		523
 #endif
@@ -39,15 +66,21 @@ Boston, MA 02111-1307, USA.  */
 #ifndef	SMALL_SCOPE_VARIABLE_BUCKETS
 #define	SMALL_SCOPE_VARIABLE_BUCKETS	13
 #endif
-static struct variable *variable_table[VARIABLE_BUCKETS];
-static struct variable_set global_variable_set
-  = { variable_table, VARIABLE_BUCKETS };
+
+static struct variable_set global_variable_set;
 static struct variable_set_list global_setlist
   = { 0, &global_variable_set };
 struct variable_set_list *current_variable_set_list = &global_setlist;
 
 /* Implement variables.  */
 
+void
+init_hash_global_variable_set ()
+{
+  hash_init (&global_variable_set.table, VARIABLE_BUCKETS,
+	     variable_hash_1, variable_hash_2, variable_hash_cmp);
+}
+
 /* Define variable named NAME with value VALUE in SET.  VALUE is copied.
    LENGTH is the length of NAME, which does not need to be null-terminated.
    ORIGIN specifies the origin of the variable (makefile, command line
@@ -65,28 +98,22 @@ define_variable_in_set (name, length, value, origin, recursive, set, flocp)
      struct variable_set *set;
      const struct floc *flocp;
 {
-  register unsigned int i;
-  register unsigned int hashval;
-  register struct variable *v;
+  struct variable *v;
+  struct variable **var_slot;
+  struct variable var_key;
 
   if (set == NULL)
     set = &global_variable_set;
 
-  hashval = 0;
-  for (i = 0; i < length; ++i)
-    HASH (hashval, name[i]);
-  hashval %= set->buckets;
-
-  for (v = set->table[hashval]; v != 0; v = v->next)
-    if (*v->name == *name
-	&& strneq (v->name + 1, name + 1, length - 1)
-	&& v->name[length] == '\0')
-      break;
+  var_key.name = (char *) name;
+  var_key.length = length;
+  var_slot = (struct variable **) hash_find_slot (&set->table, &var_key);
 
   if (env_overrides && origin == o_env)
     origin = o_env_override;
 
-  if (v != 0)
+  v = *var_slot;
+  if (! HASH_VACANT (v))
     {
       if (env_overrides && v->origin == o_env)
 	/* V came from in the environment.  Since it was defined
@@ -115,6 +142,8 @@ define_variable_in_set (name, length, value, origin, recursive, set, flocp)
 
   v = (struct variable *) xmalloc (sizeof (struct variable));
   v->name = savestring (name, length);
+  v->length = length;
+  hash_insert_at (&set->table, v, var_slot);
   v->value = xstrdup (value);
   if (flocp != 0)
     v->fileinfo = *flocp;
@@ -127,8 +156,7 @@ define_variable_in_set (name, length, value, origin, recursive, set, flocp)
   v->per_target = 0;
   v->append = 0;
   v->export = v_default;
-  v->next = set->table[hashval];
-  set->table[hashval] = v;
+
   return v;
 }
 
@@ -143,26 +171,20 @@ lookup_variable (name, length)
      unsigned int length;
 {
   const struct variable_set_list *setlist;
+  struct variable var_key;
 
-  unsigned int i;
-  unsigned int rawhash = 0;
-
-  for (i = 0; i < length; ++i)
-    HASH (rawhash, name[i]);
+  var_key.name = (char *) name;
+  var_key.length = length;
 
   for (setlist = current_variable_set_list;
        setlist != 0; setlist = setlist->next)
     {
       const struct variable_set *set = setlist->set;
-      unsigned int hashval = rawhash % set->buckets;
       struct variable *v;
 
-      /* Look through this set list; return it if found.  */
-      for (v = set->table[hashval]; v != 0; v = v->next)
-	if (*v->name == *name
-	    && strneq (v->name + 1, name + 1, length - 1)
-	    && v->name[length] == '\0')
-          return v;
+      v = (struct variable *) hash_find_item ((struct hash_table *) &set->table, &var_key);
+      if (v)
+	return v;
     }
 
 #ifdef VMS
@@ -235,21 +257,12 @@ lookup_variable_in_set (name, length, set)
      unsigned int length;
      const struct variable_set *set;
 {
-  unsigned int i;
-  unsigned int hash = 0;
-  struct variable *v;
+  struct variable var_key;
 
-  for (i = 0; i < length; ++i)
-    HASH (hash, name[i]);
-  hash %= set->buckets;
-
-  for (v = set->table[hash]; v != 0; v = v->next)
-    if (*v->name == *name
-        && strneq (v->name + 1, name + 1, length - 1)
-        && v->name[length] == 0)
-      return v;
+  var_key.name = (char *) name;
+  var_key.length = length;
 
-  return 0;
+  return (struct variable *) hash_find_item ((struct hash_table *) &set->table, &var_key);
 }
 
 /* Initialize FILE's variable set list.  If FILE already has a variable set
@@ -270,11 +283,8 @@ initialize_file_variables (file, reading)
       l = (struct variable_set_list *)
 	xmalloc (sizeof (struct variable_set_list));
       l->set = (struct variable_set *) xmalloc (sizeof (struct variable_set));
-      l->set->buckets = PERFILE_VARIABLE_BUCKETS;
-      l->set->table = (struct variable **)
-	xmalloc (l->set->buckets * sizeof (struct variable *));
-      bzero ((char *) l->set->table,
-	     l->set->buckets * sizeof (struct variable *));
+      hash_init (&l->set->table, PERFILE_VARIABLE_BUCKETS,
+			     variable_hash_1, variable_hash_2, variable_hash_cmp);
       file->variables = l;
     }
 
@@ -316,31 +326,27 @@ initialize_file_variables (file, reading)
 /* Pop the top set off the current variable set list,
    and free all its storage.  */
 
+static void
+free_variable_name_and_value (item)
+     void *item;
+{
+  struct variable *v = (struct variable *) item;
+  free (v->name);
+  free (v->value);
+}
+
 void
 pop_variable_scope ()
 {
-  register struct variable_set_list *setlist = current_variable_set_list;
-  register struct variable_set *set = setlist->set;
-  register unsigned int i;
+  struct variable_set_list *setlist = current_variable_set_list;
+  struct variable_set *set = setlist->set;
 
   current_variable_set_list = setlist->next;
   free ((char *) setlist);
 
-  for (i = 0; i < set->buckets; ++i)
-    {
-      register struct variable *next = set->table[i];
-      while (next != 0)
-	{
-	  register struct variable *v = next;
-	  next = v->next;
+  hash_map (&set->table, free_variable_name_and_value);
+  hash_free (&set->table, 1);
 
-	  free (v->name);
-	  if (v->value)
-	    free (v->value);
-	  free ((char *) v);
-	}
-    }
-  free ((char *) set->table);
   free ((char *) set);
 }
 
@@ -351,10 +357,8 @@ create_new_variable_set ()
   register struct variable_set *set;
 
   set = (struct variable_set *) xmalloc (sizeof (struct variable_set));
-  set->buckets = SMALL_SCOPE_VARIABLE_BUCKETS;
-  set->table = (struct variable **)
-    xmalloc (set->buckets * sizeof (struct variable *));
-  bzero ((char *) set->table, set->buckets * sizeof (struct variable *));
+  hash_init (&set->table, SMALL_SCOPE_VARIABLE_BUCKETS,
+	     variable_hash_1, variable_hash_2, variable_hash_cmp);
 
   setlist = (struct variable_set_list *)
     xmalloc (sizeof (struct variable_set_list));
@@ -375,52 +379,27 @@ push_new_variable_scope ()
 /* Merge SET1 into SET0, freeing unused storage in SET1.  */
 
 static void
-merge_variable_sets (set0, set1)
-     struct variable_set *set0, *set1;
+merge_variable_sets (to_set, from_set)
+     struct variable_set *to_set, *from_set;
 {
-  register unsigned int bucket1;
-
-  for (bucket1 = 0; bucket1 < set1->buckets; ++bucket1)
-    {
-      register struct variable *v1 = set1->table[bucket1];
-      while (v1 != 0)
-	{
-	  struct variable *next = v1->next;
-	  unsigned int bucket0;
-	  register struct variable *v0;
-
-	  if (set1->buckets >= set0->buckets)
-	    bucket0 = bucket1;
-	  else
-	    {
-	      register char *n;
-	      bucket0 = 0;
-	      for (n = v1->name; *n != '\0'; ++n)
-		HASH (bucket0, *n);
-	    }
-	  bucket0 %= set0->buckets;
+  struct variable **from_var_slot = (struct variable **) from_set->table.ht_vec;
+  struct variable **from_var_end = from_var_slot + from_set->table.ht_size;
 
-	  for (v0 = set0->table[bucket0]; v0 != 0; v0 = v0->next)
-	    if (streq (v0->name, v1->name))
-	      break;
-
-	  if (v0 == 0)
-	    {
-	      /* There is no variable in SET0 with the same name.  */
-	      v1->next = set0->table[bucket0];
-	      set0->table[bucket0] = v1;
-	    }
-	  else
-	    {
-	      /* The same variable exists in both sets.
-		 SET0 takes precedence.  */
-	      free (v1->value);
-	      free ((char *) v1);
-	    }
-
-	  v1 = next;
-	}
-    }
+  for ( ; from_var_slot < from_var_end; from_var_slot++)
+    if (! HASH_VACANT (*from_var_slot))
+      {
+	struct variable *from_var = *from_var_slot;
+	struct variable **to_var_slot
+	  = (struct variable **) hash_find_slot (&to_set->table, *from_var_slot);
+	if (HASH_VACANT (*to_var_slot))
+	  hash_insert_at (&to_set->table, from_var, to_var_slot);
+	else
+	  {
+	    /* GKM FIXME: delete in from_set->table */
+	    free (from_var->value);
+	    free (from_var);
+	  }
+      }
 }
 
 /* Merge SETLIST1 into SETLIST0, freeing unused storage in SETLIST1.  */
@@ -467,7 +446,7 @@ define_automatic_variables ()
   char buf[200];
 
   sprintf (buf, "%u", makelevel);
-  (void) define_variable ("MAKELEVEL", 9, buf, o_env, 0);
+  (void) define_variable (MAKELEVEL_NAME, MAKELEVEL_LENGTH, buf, o_env, 0);
 
   sprintf (buf, "%s%s%s",
 	   version_string,
@@ -564,184 +543,135 @@ target_environment (file)
 {
   struct variable_set_list *set_list;
   register struct variable_set_list *s;
-  struct variable_bucket
-    {
-      struct variable_bucket *next;
-      struct variable *variable;
-    };
-  struct variable_bucket **table;
-  unsigned int buckets;
-  register unsigned int i;
-  register unsigned nvariables;
+  struct hash_table table;
+  struct variable **v_slot;
+  struct variable **v_end;
+  struct variable makelevel_key;
+  char **result_0;
   char **result;
-  unsigned int mklev_hash;
 
   if (file == 0)
     set_list = current_variable_set_list;
   else
     set_list = file->variables;
 
-  /* Find the lowest number of buckets in any set in the list.  */
-  s = set_list;
-  buckets = s->set->buckets;
-  for (s = s->next; s != 0; s = s->next)
-    if (s->set->buckets < buckets)
-      buckets = s->set->buckets;
-
-  /* Find the hash value of the bucket `MAKELEVEL' will fall into.  */
-  {
-    char *p = "MAKELEVEL";
-    mklev_hash = 0;
-    while (*p != '\0')
-      HASH (mklev_hash, *p++);
-  }
-
-  /* Temporarily allocate a table with that many buckets.  */
-  table = (struct variable_bucket **)
-    alloca (buckets * sizeof (struct variable_bucket *));
-  bzero ((char *) table, buckets * sizeof (struct variable_bucket *));
+  hash_init (&table, VARIABLE_BUCKETS,
+	     variable_hash_1, variable_hash_2, variable_hash_cmp);
 
   /* Run through all the variable sets in the list,
      accumulating variables in TABLE.  */
-  nvariables = 0;
   for (s = set_list; s != 0; s = s->next)
     {
-      register struct variable_set *set = s->set;
-      for (i = 0; i < set->buckets; ++i)
-	{
-	  register struct variable *v;
-	  for (v = set->table[i]; v != 0; v = v->next)
-	    {
-	      unsigned int j = i % buckets;
-	      register struct variable_bucket *ov;
-	      register char *p = v->name;
-
-	      if (i == mklev_hash % set->buckets
-		  && streq (v->name, "MAKELEVEL"))
-		/* Don't include MAKELEVEL because it will be
-		   added specially at the end.  */
-		continue;
-
-              /* If this is a per-target variable and it hasn't been touched
-                 already then look up the global version and take its export
-                 value.  */
-              if (v->per_target && v->export == v_default)
-                {
-                  struct variable *gv;
-
-                  gv = lookup_variable_in_set(v->name, strlen(v->name),
-                                              &global_variable_set);
-                  if (gv)
-                    v->export = gv->export;
-                }
-
-	      switch (v->export)
-		{
-		case v_default:
-		  if (v->origin == o_default || v->origin == o_automatic)
-		    /* Only export default variables by explicit request.  */
-		    continue;
-
-		  if (! export_all_variables
-		      && v->origin != o_command
-		      && v->origin != o_env && v->origin != o_env_override)
-		    continue;
-
-		  if (*p != '_' && (*p < 'A' || *p > 'Z')
-		      && (*p < 'a' || *p > 'z'))
-		    continue;
-		  for (++p; *p != '\0'; ++p)
-		    if (*p != '_' && (*p < 'a' || *p > 'z')
-			&& (*p < 'A' || *p > 'Z') && (*p < '0' || *p > '9'))
-		      continue;
-		  if (*p != '\0')
+      struct variable_set *set = s->set;
+      v_slot = (struct variable **) set->table.ht_vec;
+      v_end = v_slot + set->table.ht_size;
+      for ( ; v_slot < v_end; v_slot++)
+	if (! HASH_VACANT (*v_slot))
+	  {
+	    struct variable **new_slot;
+	    struct variable *v = *v_slot;
+	    char *p = v->name;
+
+	    /* If this is a per-target variable and it hasn't been touched
+	       already then look up the global version and take its export
+	       value.  */
+	    if (v->per_target && v->export == v_default)
+	      {
+		struct variable *gv;
+
+		gv = lookup_variable_in_set (v->name, strlen(v->name),
+                                             &global_variable_set);
+		if (gv)
+		  v->export = gv->export;
+	      }
+
+	    switch (v->export)
+	      {
+	      case v_default:
+		if (v->origin == o_default || v->origin == o_automatic)
+		  /* Only export default variables by explicit request.  */
+		  continue;
+
+		if (! export_all_variables
+		    && v->origin != o_command
+		    && v->origin != o_env && v->origin != o_env_override)
+		  continue;
+
+		if (*p != '_' && (*p < 'A' || *p > 'Z')
+                    && (*p < 'a' || *p > 'z'))
+ 		  continue;
+		for (++p; *p != '\0'; ++p)
+		  if (*p != '_' && (*p < 'a' || *p > 'z')
+		      && (*p < 'A' || *p > 'Z') && (*p < '0' || *p > '9'))
 		    continue;
-		  break;
+		if (*p != '\0')
+		  continue;
+		break;
 
-                case v_export:
-                  break;
+	      case v_export:
+		break;
 
-                case v_noexport:
-                  continue;
-
-		case v_ifset:
-		  if (v->origin == o_default)
-		    continue;
-		  break;
-		}
+	      case v_noexport:
+		continue;
 
-              /* If this was from a different-sized hash table, then
-                 recalculate the bucket it goes in.  */
-              if (set->buckets != buckets)
-                {
-                  register char *np;
+	      case v_ifset:
+		if (v->origin == o_default)
+		  continue;
+		break;
+	      }
 
-                  j = 0;
-                  for (np = v->name; *np != '\0'; ++np)
-                    HASH (j, *np);
-                  j %= buckets;
-                }
+	    new_slot = (struct variable **) hash_find_slot (&table, v);
+	    if (HASH_VACANT (*new_slot))
+	      hash_insert_at (&table, v, new_slot);
+	  }
+    }
 
-	      for (ov = table[j]; ov != 0; ov = ov->next)
-		if (streq (v->name, ov->variable->name))
-		  break;
+  makelevel_key.name = MAKELEVEL_NAME;
+  makelevel_key.length = MAKELEVEL_LENGTH;
+  hash_delete (&table, &makelevel_key);
 
-	      if (ov == 0)
-		{
-		  register struct variable_bucket *entry;
-		  entry = (struct variable_bucket *)
-		    alloca (sizeof (struct variable_bucket));
-		  entry->next = table[j];
-		  entry->variable = v;
-		  table[j] = entry;
-		  ++nvariables;
-		}
-	    }
-	}
-    }
+  result = result_0 = (char **) xmalloc ((table.ht_fill + 2) * sizeof (char *));
 
-  result = (char **) xmalloc ((nvariables + 2) * sizeof (char *));
-  nvariables = 0;
-  for (i = 0; i < buckets; ++i)
-    {
-      register struct variable_bucket *b;
-      for (b = table[i]; b != 0; b = b->next)
-	{
-	  register struct variable *v = b->variable;
+  v_slot = (struct variable **) table.ht_vec;
+  v_end = v_slot + table.ht_size;
+  for ( ; v_slot < v_end; v_slot++)
+    if (! HASH_VACANT (*v_slot))
+      {
+	struct variable *v = *v_slot;
 
-	  /* If V is recursively expanded and didn't come from the environment,
-	     expand its value.  If it came from the environment, it should
-	     go back into the environment unchanged.  */
-	  if (v->recursive
-	      && v->origin != o_env && v->origin != o_env_override)
-	    {
-	      char *value = recursively_expand_for_file (v, file);
+	/* If V is recursively expanded and didn't come from the environment,
+	   expand its value.  If it came from the environment, it should
+	   go back into the environment unchanged.  */
+	if (v->recursive
+	    && v->origin != o_env && v->origin != o_env_override)
+	  {
+	    char *value = recursively_expand_for_file (v, file);
 #ifdef WINDOWS32
-              if (strcmp(v->name, "Path") == 0 ||
-                  strcmp(v->name, "PATH") == 0)
-                convert_Path_to_windows32(value, ';');
+	    if (strcmp(v->name, "Path") == 0 ||
+		strcmp(v->name, "PATH") == 0)
+	      convert_Path_to_windows32(value, ';');
 #endif
-	      result[nvariables++] = concat (v->name, "=", value);
-	      free (value);
-	    }
-	  else
+	    *result++ = concat (v->name, "=", value);
+	    free (value);
+	  }
+	else
+	  {
 #ifdef WINDOWS32
-          {
             if (strcmp(v->name, "Path") == 0 ||
                 strcmp(v->name, "PATH") == 0)
               convert_Path_to_windows32(v->value, ';');
-            result[nvariables++] = concat (v->name, "=", v->value);
-          }
-#else
-	    result[nvariables++] = concat (v->name, "=", v->value);
 #endif
-	}
-    }
-  result[nvariables] = (char *) xmalloc (100);
-  (void) sprintf (result[nvariables], "MAKELEVEL=%u", makelevel + 1);
-  result[++nvariables] = 0;
+	    *result++ = concat (v->name, "=", v->value);
+	  }
+      }
+
+  *result = (char *) xmalloc (100);
+  (void) sprintf (*result, "%s=%u", MAKELEVEL_NAME, makelevel + 1);
+  *++result = 0;
 
-  return result;
+  hash_free (&table, 0);
+
+  return result_0;
 }
 
 /* Given a variable, a value, and a flavor, define the variable.
@@ -1159,49 +1089,14 @@ print_variable_set (set, prefix)
      register struct variable_set *set;
      char *prefix;
 {
-  register unsigned int i, nvariables, per_bucket;
-  register struct variable *v;
-
-  per_bucket = nvariables = 0;
-  for (i = 0; i < set->buckets; ++i)
-    {
-      register unsigned int this_bucket = 0;
-
-      for (v = set->table[i]; v != 0; v = v->next)
-	{
-	  ++this_bucket;
-	  print_variable (v, prefix);
-	}
+  hash_map_arg (&set->table, print_variable, prefix);
 
-      nvariables += this_bucket;
-      if (this_bucket > per_bucket)
-	per_bucket = this_bucket;
-    }
-
-  if (nvariables == 0)
-    puts (_("# No variables."));
-  else
-    {
-      printf (_("# %u variables in %u hash buckets.\n"),
-	      nvariables, set->buckets);
-#ifndef	NO_FLOAT
-      printf (_("# average of %.1f variables per bucket, \
-max %u in one bucket.\n"),
-	      (double) nvariables / (double) set->buckets,
-	      per_bucket);
-#else
-      {
-	int f = (nvariables * 1000 + 5) / set->buckets;
-	printf (_("# average of %d.%d variables per bucket, \
-max %u in one bucket.\n"),
-	      f/10, f%10,
-	      per_bucket);
-      }
-#endif
-    }
+  fputs (_("# variable set hash-table stats:\n"), stdout);
+  fputs ("# ", stdout);
+  hash_print_stats (&set->table, stdout);
+  putc ('\n', stdout);
 }
 
-
 /* Print the data base of variables.  */
 
 void
diff --git a/variable.h b/variable.h
index 483427a..806f9e1 100644
--- a/variable.h
+++ b/variable.h
@@ -1,5 +1,5 @@
 /* Definitions for using variables in GNU Make.
-Copyright (C) 1988, 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
+Copyright (C) 1988, 1989, 1990, 1991, 1992, 2002 Free Software Foundation, Inc.
 This file is part of GNU Make.
 
 GNU Make is free software; you can redistribute it and/or modify
@@ -17,6 +17,8 @@ along with GNU Make; see the file COPYING.  If not, write to
 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 Boston, MA 02111-1307, USA.  */
 
+#include "hash.h"
+
 /* Codes in a variable definition saying where the definition came from.
    Increasing numeric values signify less-overridable definitions.  */
 enum variable_origin
@@ -50,8 +52,8 @@ enum variable_flavor
 
 struct variable
   {
-    struct variable *next;	/* Link in the chain.  */
     char *name;			/* Variable name.  */
+    int length;			/* strlen (name) */
     char *value;		/* Variable value.  */
     struct floc fileinfo;       /* Where the variable was defined.  */
     unsigned int recursive:1;	/* Gets recursively re-evaluated.  */
@@ -79,8 +81,7 @@ struct variable
 
 struct variable_set
   {
-    struct variable **table;	/* Hash table of variables.  */
-    unsigned int buckets;	/* Number of hash buckets in `table'.  */
+    struct hash_table table;	/* Hash table of variables.  */
   };
 
 /* Structure that represents a list of variable sets.  */
@@ -128,7 +129,8 @@ extern void print_variable_set PARAMS ((struct variable_set *set, char *prefix))
 extern void merge_variable_set_lists PARAMS ((struct variable_set_list **setlist0, struct variable_set_list *setlist1));
 extern struct variable *do_variable_definition PARAMS ((const struct floc *flocp, const char *name, char *value, enum variable_origin origin, enum variable_flavor flavor, int target_var));
 extern struct variable *try_variable_definition PARAMS ((const struct floc *flocp, char *line, enum variable_origin origin, int target_var));
-
+extern void init_hash_global_variable_set PARAMS ((void));
+extern void hash_init_function_table PARAMS ((void));
 extern struct variable *lookup_variable PARAMS ((const char *name, unsigned int length));
 extern struct variable *lookup_variable_in_set PARAMS ((const char *name,
                                                         unsigned int length,
@@ -173,3 +175,6 @@ extern struct variable *define_variable_in_set
 extern char **target_environment PARAMS ((struct file *file));
 
 extern int export_all_variables;
+
+#define MAKELEVEL_NAME "MAKELEVEL"
+#define MAKELEVEL_LENGTH (sizeof (MAKELEVEL_NAME) - 1)