--- tar-1.13.17.orig/src/incremen.c	Fri Jan  7 17:34:35 2000
+++ tar-1.13.17.hash/src/incremen.c	Sun Oct  8 11:55:34 2000
@@ -15,8 +15,15 @@
    with this program; if not, write to the Free Software Foundation, Inc.,
    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
+#if HAVE_STDBOOL_H
+# include <stdbool.h>
+#else
+typedef enum {false = 0, true = 1} bool;
+#endif
+
 #include "system.h"
 #include "common.h"
+#include "hash.h"
 #include <getline.h>
 #include <quotearg.h>
 
@@ -105,6 +112,8 @@
   };
 static struct directory *directory_list;
 
+static struct hash_table *directory_hash = NULL;
+
 #if HAVE_ST_FSTYPE_STRING
   static const char nfs[] = "nfs";
 # define NFS_FILE_STAT(st) (strcmp ((st).st_fstype, nfs) == 0)
@@ -113,16 +122,50 @@
 # define NFS_FILE_STAT(st) (((st).st_dev & ST_DEV_MSB (st)) != 0)
 #endif
 
+/* A hash function for null-terminated char* strings using
+   the method described in Aho, Sethi, & Ullman, p 436. */
+/* This function was inspired by hash_pjw from fileutils-4.0 */
+
+static unsigned int
+hash_directory (const void *x, unsigned int tablesize)
+{
+  const struct directory *d = x;
+  const char *s = d->name;
+  unsigned int h = 0;
+  unsigned int g;
+  while (*s != 0)
+    {
+      h = (h << 4) + *s++;
+      if ((g = h & (unsigned int) 0xf0000000) != 0)
+        h = (h ^ (g >> 24)) ^ g;
+    }
+
+  return (h % tablesize);
+}
+
+static bool
+hash_compare_directory ( void const *x, void const *y)
+{
+  return strcmp(((struct directory *)x)->name, ((struct directory *)y)->name) ? false : true;
+}
+
 /*-------------------------------------------------------------------.
 | Create and link a new directory entry for directory NAME, having a |
 | DEVICE_NUMBER and a INODE_NUMBER, with some TEXT.		     |
 `-------------------------------------------------------------------*/
 
-static void
+static struct directory *
 note_directory (char *name, struct stat *st, const char *text)
 {
   struct directory *directory
     = xmalloc (sizeof (struct directory));
+  struct directory *idirectory;
+
+  if(directory_hash == NULL) {
+    directory_hash = hash_initialize(53, NULL, hash_directory,hash_compare_directory, NULL);
+    if(directory_hash == NULL)
+      xalloc_die();
+  }
 
   directory->next = directory_list;
   directory_list = directory;
@@ -133,6 +176,10 @@
   directory->dir_text = text;
   directory->children = CHANGED_CHILDREN;
   directory->nfs = NFS_FILE_STAT (*st);
+  idirectory = hash_insert( directory_hash, directory);
+  if(idirectory == NULL)
+    xalloc_die();
+  return directory;
 }
 
 /*------------------------------------------------------------------------.
@@ -143,15 +190,17 @@
 find_directory (char *name)
 {
   struct directory *directory;
+  struct directory lookup_directory;
+
+  if(directory_hash == NULL) {
+    directory_hash = hash_initialize(53, NULL, hash_directory,hash_compare_directory, NULL);
+    if(directory_hash == NULL)
+      xalloc_die();
+  }
+
+  lookup_directory.name = name;
+  return hash_lookup( directory_hash, &lookup_directory );
 
-  for (directory = directory_list;
-       directory;
-       directory = directory->next)
-    {
-      if (!strcmp (directory->name, name))
-	return directory;
-    }
-  return 0;
 }
 
 /*---.
@@ -262,8 +311,7 @@
 		      if (verbose_option)
 			WARN ((0, 0, _("%s: Directory is new"),
 			       quotearg_colon (name_buffer)));
-		      note_directory (name_buffer, &stat_data, "");
-		      directory = find_directory (name_buffer);
+		      directory = note_directory (name_buffer, &stat_data, "");
 		      directory->children = 
 			((listed_incremental_option
 			  || newer_mtime_option <= stat_data.st_mtime