1 files changed, 330 insertions, 255 deletions

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);
+}