1/* Directory hashing for GNU Make.
2Copyright (C) 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
32002 Free Software Foundation, Inc.
4This file is part of GNU Make.
5
6GNU Make is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 2, or (at your option)
9any later version.
10
11GNU Make is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GNU Make; see the file COPYING.  If not, write to
18the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19Boston, MA 02111-1307, USA.  */
20
21#include "make.h"
22#include "hash.h"
23
24#ifdef	HAVE_DIRENT_H
25# include <dirent.h>
26# define NAMLEN(dirent) strlen((dirent)->d_name)
27# ifdef VMS
28extern char *vmsify PARAMS ((char *name, int type));
29# endif
30#else
31# define dirent direct
32# define NAMLEN(dirent) (dirent)->d_namlen
33# ifdef HAVE_SYS_NDIR_H
34#  include <sys/ndir.h>
35# endif
36# ifdef HAVE_SYS_DIR_H
37#  include <sys/dir.h>
38# endif
39# ifdef HAVE_NDIR_H
40#  include <ndir.h>
41# endif
42# ifdef HAVE_VMSDIR_H
43#  include "vmsdir.h"
44# endif /* HAVE_VMSDIR_H */
45#endif
46
47/* In GNU systems, <dirent.h> defines this macro for us.  */
48#ifdef _D_NAMLEN
49# undef NAMLEN
50# define NAMLEN(d) _D_NAMLEN(d)
51#endif
52
53#if (defined (POSIX) || defined (VMS) || defined (WINDOWS32)) && !defined (__GNU_LIBRARY__)
54/* Posix does not require that the d_ino field be present, and some
55   systems do not provide it. */
56# define REAL_DIR_ENTRY(dp) 1
57# define FAKE_DIR_ENTRY(dp)
58#else
59# define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
60# define FAKE_DIR_ENTRY(dp) (dp->d_ino = 1)
61#endif /* POSIX */
62
63#ifdef __MSDOS__
64#include <ctype.h>
65#include <fcntl.h>
66
67/* If it's MSDOS that doesn't have _USE_LFN, disable LFN support.  */
68#ifndef _USE_LFN
69#define _USE_LFN 0
70#endif
71
72static char *
73dosify (filename)
74     char *filename;
75{
76  static char dos_filename[14];
77  char *df;
78  int i;
79
80  if (filename == 0 || _USE_LFN)
81    return filename;
82
83  /* FIXME: what about filenames which violate
84     8+3 constraints, like "config.h.in", or ".emacs"?  */
85  if (strpbrk (filename, "\"*+,;<=>?[\\]|") != 0)
86    return filename;
87
88  df = dos_filename;
89
90  /* First, transform the name part.  */
91  for (i = 0; *filename != '\0' && i < 8 && *filename != '.'; ++i)
92    *df++ = tolower ((unsigned char)*filename++);
93
94  /* Now skip to the next dot.  */
95  while (*filename != '\0' && *filename != '.')
96    ++filename;
97  if (*filename != '\0')
98    {
99      *df++ = *filename++;
100      for (i = 0; *filename != '\0' && i < 3 && *filename != '.'; ++i)
101	*df++ = tolower ((unsigned char)*filename++);
102    }
103
104  /* Look for more dots.  */
105  while (*filename != '\0' && *filename != '.')
106    ++filename;
107  if (*filename == '.')
108    return filename;
109  *df = 0;
110  return dos_filename;
111}
112#endif /* __MSDOS__ */
113
114#ifdef WINDOWS32
115#include "pathstuff.h"
116#endif
117
118#ifdef _AMIGA
119#include <ctype.h>
120#endif
121
122#ifdef HAVE_CASE_INSENSITIVE_FS
123static char *
124downcase (filename)
125     char *filename;
126{
127#ifdef _AMIGA
128  static char new_filename[136];
129#else
130  static char new_filename[PATH_MAX];
131#endif
132  char *df;
133  int i;
134
135  if (filename == 0)
136    return 0;
137
138  df = new_filename;
139
140  /* First, transform the name part.  */
141  for (i = 0; *filename != '\0'; ++i)
142  {
143    *df++ = tolower ((unsigned char)*filename);
144    ++filename;
145  }
146
147  *df = 0;
148
149  return new_filename;
150}
151#endif /* HAVE_CASE_INSENSITIVE_FS */
152
153#ifdef VMS
154
155static int
156vms_hash (name)
157    char *name;
158{
159  int h = 0;
160  int g;
161
162  while (*name)
163    {
164      unsigned char uc = *name;
165      h = (h << 4) + (isupper (uc) ? tolower (uc) : uc);
166      name++;
167      g = h & 0xf0000000;
168      if (g)
169	{
170	  h = h ^ (g >> 24);
171	  h = h ^ g;
172	}
173    }
174  return h;
175}
176
177/* fake stat entry for a directory */
178static int
179vmsstat_dir (name, st)
180    char *name;
181    struct stat *st;
182{
183  char *s;
184  int h;
185  DIR *dir;
186
187  dir = opendir (name);
188  if (dir == 0)
189    return -1;
190  closedir (dir);
191  s = strchr (name, ':');	/* find device */
192  if (s)
193    {
194      *s++ = 0;
195      st->st_dev = (char *)vms_hash (name);
196      h = vms_hash (s);
197      *(s-1) = ':';
198    }
199  else
200    {
201      st->st_dev = 0;
202      s = name;
203      h = vms_hash (s);
204    }
205
206  st->st_ino[0] = h & 0xff;
207  st->st_ino[1] = h & 0xff00;
208  st->st_ino[2] = h >> 16;
209
210  return 0;
211}
212#endif /* VMS */
213
214/* Hash table of directories.  */
215
216#ifndef	DIRECTORY_BUCKETS
217#define DIRECTORY_BUCKETS 199
218#endif
219
220struct directory_contents
221  {
222    dev_t dev;			/* Device and inode numbers of this dir.  */
223#ifdef WINDOWS32
224    /*
225     * Inode means nothing on WINDOWS32. Even file key information is
226     * unreliable because it is random per file open and undefined
227     * for remote filesystems. The most unique attribute I can
228     * come up with is the fully qualified name of the directory. Beware
229     * though, this is also unreliable. I'm open to suggestion on a better
230     * way to emulate inode.
231     */
232    char *path_key;
233    int   ctime;
234    int   mtime;        /* controls check for stale directory cache */
235    int   fs_flags;     /* FS_FAT, FS_NTFS, ... */
236#define FS_FAT      0x1
237#define FS_NTFS     0x2
238#define FS_UNKNOWN  0x4
239#else
240#ifdef VMS
241    ino_t ino[3];
242#else
243    ino_t ino;
244#endif
245#endif /* WINDOWS32 */
246    struct hash_table dirfiles;	/* Files in this directory.  */
247    DIR *dirstream;		/* Stream reading this directory.  */
248  };
249
250static unsigned long
251directory_contents_hash_1 (key_0)
252    const void *key_0;
253{
254  struct directory_contents const *key = (struct directory_contents const *) key_0;
255  unsigned long hash;
256
257#ifdef WINDOWS32
258  ISTRING_HASH_1 (key->path_key, hash);
259  hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) key->ctime;
260#else
261# ifdef VMS
262  hash = (((unsigned int) key->dev << 4)
263	  ^ ((unsigned int) key->ino[0]
264	     + (unsigned int) key->ino[1]
265	     + (unsigned int) key->ino[2]));
266# else
267  hash = ((unsigned int) key->dev << 4) ^ (unsigned int) key->ino;
268# endif
269#endif /* WINDOWS32 */
270  return hash;
271}
272
273static unsigned long
274directory_contents_hash_2 (key_0)
275    const void *key_0;
276{
277  struct directory_contents const *key = (struct directory_contents const *) key_0;
278  unsigned long hash;
279
280#ifdef WINDOWS32
281  ISTRING_HASH_2 (key->path_key, hash);
282  hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ctime;
283#else
284# ifdef VMS
285  hash = (((unsigned int) key->dev << 4)
286	  ^ ~((unsigned int) key->ino[0]
287	      + (unsigned int) key->ino[1]
288	      + (unsigned int) key->ino[2]));
289# else
290  hash = ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ino;
291# endif
292#endif /* WINDOWS32 */
293
294  return hash;
295}
296
297static int
298directory_contents_hash_cmp (xv, yv)
299    const void *xv;
300    const void *yv;
301{
302  struct directory_contents const *x = (struct directory_contents const *) xv;
303  struct directory_contents const *y = (struct directory_contents const *) yv;
304  int result;
305
306#ifdef WINDOWS32
307  ISTRING_COMPARE (x->path_key, y->path_key, result);
308  if (result)
309    return result;
310  result = x->ctime - y->ctime;
311  if (result)
312    return result;
313#else
314# ifdef VMS
315  result = x->ino[0] - y->ino[0];
316  if (result)
317    return result;
318  result = x->ino[1] - y->ino[1];
319  if (result)
320    return result;
321  result = x->ino[2] - y->ino[2];
322  if (result)
323    return result;
324# else
325  result = x->ino - y->ino;
326  if (result)
327    return result;
328# endif
329#endif /* WINDOWS32 */
330
331  return x->dev - y->dev;
332}
333
334/* Table of directory contents hashed by device and inode number.  */
335static struct hash_table directory_contents;
336
337struct directory
338  {
339    char *name;			/* Name of the directory.  */
340
341    /* The directory's contents.  This data may be shared by several
342       entries in the hash table, which refer to the same directory
343       (identified uniquely by `dev' and `ino') under different names.  */
344    struct directory_contents *contents;
345  };
346
347static unsigned long
348directory_hash_1 (key)
349    const void *key;
350{
351  return_ISTRING_HASH_1 (((struct directory const *) key)->name);
352}
353
354static unsigned long
355directory_hash_2 (key)
356    const void *key;
357{
358  return_ISTRING_HASH_2 (((struct directory const *) key)->name);
359}
360
361static int
362directory_hash_cmp (x, y)
363    const void *x;
364    const void *y;
365{
366  return_ISTRING_COMPARE (((struct directory const *) x)->name,
367			  ((struct directory const *) y)->name);
368}
369
370/* Table of directories hashed by name.  */
371static struct hash_table directories;
372
373/* Never have more than this many directories open at once.  */
374
375#define MAX_OPEN_DIRECTORIES 10
376
377static unsigned int open_directories = 0;
378
379
380/* Hash table of files in each directory.  */
381
382struct dirfile
383  {
384    char *name;			/* Name of the file.  */
385    short length;
386    short impossible;		/* This file is impossible.  */
387  };
388
389static unsigned long
390dirfile_hash_1 (key)
391    const void *key;
392{
393  return_ISTRING_HASH_1 (((struct dirfile const *) key)->name);
394}
395
396static unsigned long
397dirfile_hash_2 (key)
398    const void *key;
399{
400  return_ISTRING_HASH_2 (((struct dirfile const *) key)->name);
401}
402
403static int
404dirfile_hash_cmp (xv, yv)
405    const void *xv;
406    const void *yv;
407{
408  struct dirfile const *x = ((struct dirfile const *) xv);
409  struct dirfile const *y = ((struct dirfile const *) yv);
410  int result = x->length - y->length;
411  if (result)
412    return result;
413  return_ISTRING_COMPARE (x->name, y->name);
414}
415
416#ifndef	DIRFILE_BUCKETS
417#define DIRFILE_BUCKETS 107
418#endif
419
420static int dir_contents_file_exists_p PARAMS ((struct directory_contents *dir, char *filename));
421static struct directory *find_directory PARAMS ((char *name));
422
423/* Find the directory named NAME and return its `struct directory'.  */
424
425static struct directory *
426find_directory (name)
427     register char *name;
428{
429  register char *p;
430  register struct directory *dir;
431  register struct directory **dir_slot;
432  struct directory dir_key;
433  int r;
434#ifdef WINDOWS32
435  char* w32_path;
436  char  fs_label[BUFSIZ];
437  char  fs_type[BUFSIZ];
438  long  fs_serno;
439  long  fs_flags;
440  long  fs_len;
441#endif
442#ifdef VMS
443  if ((*name == '.') && (*(name+1) == 0))
444    name = "[]";
445  else
446    name = vmsify (name,1);
447#endif
448
449  dir_key.name = name;
450  dir_slot = (struct directory **) hash_find_slot (&directories, &dir_key);
451  dir = *dir_slot;
452
453  if (HASH_VACANT (dir))
454    {
455      struct stat st;
456
457      /* The directory was not found.  Create a new entry for it.  */
458
459      p = name + strlen (name);
460      dir = (struct directory *) xmalloc (sizeof (struct directory));
461      dir->name = savestring (name, p - name);
462      hash_insert_at (&directories, dir, dir_slot);
463      /* The directory is not in the name hash table.
464	 Find its device and inode numbers, and look it up by them.  */
465
466#ifdef WINDOWS32
467      /* Remove any trailing '\'.  Windows32 stat fails even on valid
468         directories if they end in '\'. */
469      if (p[-1] == '\\')
470        p[-1] = '\0';
471#endif
472
473#ifdef VMS
474      r = vmsstat_dir (name, &st);
475#else
476      r = stat (name, &st);
477#endif
478
479#ifdef WINDOWS32
480      /* Put back the trailing '\'.  If we don't, we're permanently
481         truncating the value!  */
482      if (p[-1] == '\0')
483        p[-1] = '\\';
484#endif
485
486      if (r < 0)
487        {
488	/* Couldn't stat the directory.  Mark this by
489	   setting the `contents' member to a nil pointer.  */
490	  dir->contents = 0;
491	}
492      else
493	{
494	  /* Search the contents hash table; device and inode are the key.  */
495
496	  struct directory_contents *dc;
497	  struct directory_contents **dc_slot;
498	  struct directory_contents dc_key;
499
500	  dc_key.dev = st.st_dev;
501#ifdef WINDOWS32
502	  dc_key.path_key = w32_path = w32ify (name, 1);
503	  dc_key.ctime = st.st_ctime;
504#else
505# ifdef VMS
506	  dc_key.ino[0] = st.st_ino[0];
507	  dc_key.ino[1] = st.st_ino[1];
508	  dc_key.ino[2] = st.st_ino[2];
509# else
510	  dc_key.ino = st.st_ino;
511# endif
512#endif
513	  dc_slot = (struct directory_contents **) hash_find_slot (&directory_contents, &dc_key);
514	  dc = *dc_slot;
515
516	  if (HASH_VACANT (dc))
517	    {
518	      /* Nope; this really is a directory we haven't seen before.  */
519
520	      dc = (struct directory_contents *)
521		xmalloc (sizeof (struct directory_contents));
522
523	      /* Enter it in the contents hash table.  */
524	      dc->dev = st.st_dev;
525#ifdef WINDOWS32
526              dc->path_key = xstrdup (w32_path);
527	      dc->ctime = st.st_ctime;
528              dc->mtime = st.st_mtime;
529
530              /*
531               * NTFS is the only WINDOWS32 filesystem that bumps mtime
532               * on a directory when files are added/deleted from
533               * a directory.
534               */
535              w32_path[3] = '\0';
536              if (GetVolumeInformation(w32_path,
537                     fs_label, sizeof (fs_label),
538                     &fs_serno, &fs_len,
539                     &fs_flags, fs_type, sizeof (fs_type)) == FALSE)
540                dc->fs_flags = FS_UNKNOWN;
541              else if (!strcmp(fs_type, "FAT"))
542                dc->fs_flags = FS_FAT;
543              else if (!strcmp(fs_type, "NTFS"))
544                dc->fs_flags = FS_NTFS;
545              else
546                dc->fs_flags = FS_UNKNOWN;
547#else
548# ifdef VMS
549	      dc->ino[0] = st.st_ino[0];
550	      dc->ino[1] = st.st_ino[1];
551	      dc->ino[2] = st.st_ino[2];
552# else
553	      dc->ino = st.st_ino;
554# endif
555#endif /* WINDOWS32 */
556	      hash_insert_at (&directory_contents, dc, dc_slot);
557	      dc->dirstream = opendir (name);
558	      if (dc->dirstream == 0)
559                /* Couldn't open the directory.  Mark this by
560                   setting the `files' member to a nil pointer.  */
561                dc->dirfiles.ht_vec = 0;
562	      else
563		{
564		  hash_init (&dc->dirfiles, DIRFILE_BUCKETS,
565			     dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
566		  /* Keep track of how many directories are open.  */
567		  ++open_directories;
568		  if (open_directories == MAX_OPEN_DIRECTORIES)
569		    /* We have too many directories open already.
570		       Read the entire directory and then close it.  */
571		    (void) dir_contents_file_exists_p (dc, (char *) 0);
572		}
573	    }
574
575	  /* Point the name-hashed entry for DIR at its contents data.  */
576	  dir->contents = dc;
577	}
578    }
579
580  return dir;
581}
582
583/* Return 1 if the name FILENAME is entered in DIR's hash table.
584   FILENAME must contain no slashes.  */
585
586static int
587dir_contents_file_exists_p (dir, filename)
588     register struct directory_contents *dir;
589     register char *filename;
590{
591  unsigned int hash;
592  struct dirfile *df;
593  struct dirent *d;
594#ifdef WINDOWS32
595  struct stat st;
596  int rehash = 0;
597#endif
598
599  if (dir == 0 || dir->dirfiles.ht_vec == 0)
600    {
601    /* The directory could not be stat'd or opened.  */
602      return 0;
603    }
604#ifdef __MSDOS__
605  filename = dosify (filename);
606#endif
607
608#ifdef HAVE_CASE_INSENSITIVE_FS
609  filename = downcase (filename);
610#endif
611
612#ifdef VMS
613  filename = vmsify (filename,0);
614#endif
615
616  hash = 0;
617  if (filename != 0)
618    {
619      struct dirfile dirfile_key;
620
621      if (*filename == '\0')
622	{
623	  /* Checking if the directory exists.  */
624	  return 1;
625	}
626      dirfile_key.name = filename;
627      dirfile_key.length = strlen (filename);
628      df = (struct dirfile *) hash_find_item (&dir->dirfiles, &dirfile_key);
629      if (df)
630	{
631	  return !df->impossible;
632	}
633    }
634
635  /* The file was not found in the hashed list.
636     Try to read the directory further.  */
637
638  if (dir->dirstream == 0)
639    {
640#ifdef WINDOWS32
641      /*
642       * Check to see if directory has changed since last read. FAT
643       * filesystems force a rehash always as mtime does not change
644       * on directories (ugh!).
645       */
646      if (dir->path_key
647	  && (dir->fs_flags & FS_FAT
648	      || (stat(dir->path_key, &st) == 0
649		  && st.st_mtime > dir->mtime)))
650	{
651	  /* reset date stamp to show most recent re-process */
652	  dir->mtime = st.st_mtime;
653
654	  /* make sure directory can still be opened */
655	  dir->dirstream = opendir(dir->path_key);
656
657	  if (dir->dirstream)
658	    rehash = 1;
659	  else
660	    return 0; /* couldn't re-read - fail */
661	}
662      else
663#endif
664	/* The directory has been all read in.  */
665	return 0;
666    }
667
668  while ((d = readdir (dir->dirstream)) != 0)
669    {
670      /* Enter the file in the hash table.  */
671      unsigned int len;
672      struct dirfile dirfile_key;
673      struct dirfile **dirfile_slot;
674
675#if defined(VMS) && defined(HAVE_DIRENT_H)
676      /* In VMS we get file versions too, which have to be stripped off */
677      {
678        char *p = strrchr (d->d_name, ';');
679        if (p)
680          *p = '\0';
681      }
682#endif
683      if (!REAL_DIR_ENTRY (d))
684	continue;
685
686      len = NAMLEN (d);
687      dirfile_key.name = d->d_name;
688      dirfile_key.length = len;
689      dirfile_slot = (struct dirfile **) hash_find_slot (&dir->dirfiles, &dirfile_key);
690#ifdef WINDOWS32
691      /*
692       * If re-reading a directory, don't cache files that have
693       * already been discovered.
694       */
695      if (! rehash || HASH_VACANT (*dirfile_slot))
696#endif
697	{
698	  df = (struct dirfile *) xmalloc (sizeof (struct dirfile));
699	  df->name = savestring (d->d_name, len);
700	  df->length = len;
701	  df->impossible = 0;
702	  hash_insert_at (&dir->dirfiles, df, dirfile_slot);
703	}
704      /* Check if the name matches the one we're searching for.  */
705      if (filename != 0 && strieq (d->d_name, filename))
706	{
707	  return 1;
708	}
709    }
710
711  /* If the directory has been completely read in,
712     close the stream and reset the pointer to nil.  */
713  if (d == 0)
714    {
715      --open_directories;
716      closedir (dir->dirstream);
717      dir->dirstream = 0;
718    }
719  return 0;
720}
721
722/* Return 1 if the name FILENAME in directory DIRNAME
723   is entered in the dir hash table.
724   FILENAME must contain no slashes.  */
725
726int
727dir_file_exists_p (dirname, filename)
728     register char *dirname;
729     register char *filename;
730{
731  return dir_contents_file_exists_p (find_directory (dirname)->contents,
732				     filename);
733}
734
735/* Return 1 if the file named NAME exists.  */
736
737int
738file_exists_p (name)
739     register char *name;
740{
741  char *dirend;
742  char *dirname;
743  char *slash;
744
745#ifndef	NO_ARCHIVES
746  if (ar_name (name))
747    return ar_member_date (name) != (time_t) -1;
748#endif
749
750#ifdef VMS
751  dirend = strrchr (name, ']');
752  if (dirend == 0)
753    dirend = strrchr (name, ':');
754  dirend++;
755  if (dirend == (char *)1)
756    return dir_file_exists_p ("[]", name);
757#else /* !VMS */
758  dirend = strrchr (name, '/');
759#ifdef HAVE_DOS_PATHS
760  /* Forward and backslashes might be mixed.  We need the rightmost one.  */
761  {
762    char *bslash = strrchr(name, '\\');
763    if (!dirend || bslash > dirend)
764      dirend = bslash;
765    /* The case of "d:file".  */
766    if (!dirend && name[0] && name[1] == ':')
767      dirend = name + 1;
768  }
769#endif /* HAVE_DOS_PATHS */
770  if (dirend == 0)
771#ifndef _AMIGA
772    return dir_file_exists_p (".", name);
773#else /* !VMS && !AMIGA */
774    return dir_file_exists_p ("", name);
775#endif /* AMIGA */
776#endif /* VMS */
777
778  slash = dirend;
779  if (dirend == name)
780    dirname = "/";
781  else
782    {
783#ifdef HAVE_DOS_PATHS
784  /* d:/ and d: are *very* different...  */
785      if (dirend < name + 3 && name[1] == ':' &&
786	  (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
787	dirend++;
788#endif
789      dirname = (char *) alloca (dirend - name + 1);
790      bcopy (name, dirname, dirend - name);
791      dirname[dirend - name] = '\0';
792    }
793  return dir_file_exists_p (dirname, slash + 1);
794}
795
796/* Mark FILENAME as `impossible' for `file_impossible_p'.
797   This means an attempt has been made to search for FILENAME
798   as an intermediate file, and it has failed.  */
799
800void
801file_impossible (filename)
802     register char *filename;
803{
804  char *dirend;
805  register char *p = filename;
806  register struct directory *dir;
807  register struct dirfile *new;
808
809#ifdef VMS
810  dirend = strrchr (p, ']');
811  if (dirend == 0)
812    dirend = strrchr (p, ':');
813  dirend++;
814  if (dirend == (char *)1)
815    dir = find_directory ("[]");
816#else
817  dirend = strrchr (p, '/');
818# ifdef HAVE_DOS_PATHS
819  /* Forward and backslashes might be mixed.  We need the rightmost one.  */
820  {
821    char *bslash = strrchr(p, '\\');
822    if (!dirend || bslash > dirend)
823      dirend = bslash;
824    /* The case of "d:file".  */
825    if (!dirend && p[0] && p[1] == ':')
826      dirend = p + 1;
827  }
828# endif /* HAVE_DOS_PATHS */
829  if (dirend == 0)
830# ifdef _AMIGA
831    dir = find_directory ("");
832# else /* !VMS && !AMIGA */
833    dir = find_directory (".");
834# endif /* AMIGA */
835#endif /* VMS */
836  else
837    {
838      char *dirname;
839      char *slash = dirend;
840      if (dirend == p)
841	dirname = "/";
842      else
843	{
844#ifdef HAVE_DOS_PATHS
845	  /* d:/ and d: are *very* different...  */
846	  if (dirend < p + 3 && p[1] == ':' &&
847	      (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
848	    dirend++;
849#endif
850	  dirname = (char *) alloca (dirend - p + 1);
851	  bcopy (p, dirname, dirend - p);
852	  dirname[dirend - p] = '\0';
853	}
854      dir = find_directory (dirname);
855      filename = p = slash + 1;
856    }
857
858  if (dir->contents == 0)
859    {
860      /* The directory could not be stat'd.  We allocate a contents
861	 structure for it, but leave it out of the contents hash table.  */
862      dir->contents = (struct directory_contents *)
863	xmalloc (sizeof (struct directory_contents));
864      bzero ((char *) dir->contents, sizeof (struct directory_contents));
865    }
866
867  if (dir->contents->dirfiles.ht_vec == 0)
868    {
869      hash_init (&dir->contents->dirfiles, DIRFILE_BUCKETS,
870		 dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
871    }
872
873  /* Make a new entry and put it in the table.  */
874
875  new = (struct dirfile *) xmalloc (sizeof (struct dirfile));
876  new->name = xstrdup (filename);
877  new->length = strlen (filename);
878  new->impossible = 1;
879  hash_insert (&dir->contents->dirfiles, new);
880}
881
882/* Return nonzero if FILENAME has been marked impossible.  */
883
884int
885file_impossible_p (filename)
886     char *filename;
887{
888  char *dirend;
889  register char *p = filename;
890  register struct directory_contents *dir;
891  register struct dirfile *dirfile;
892  struct dirfile dirfile_key;
893
894#ifdef VMS
895  dirend = strrchr (filename, ']');
896  if (dirend == 0)
897    dir = find_directory ("[]")->contents;
898#else
899  dirend = strrchr (filename, '/');
900#ifdef HAVE_DOS_PATHS
901  /* Forward and backslashes might be mixed.  We need the rightmost one.  */
902  {
903    char *bslash = strrchr(filename, '\\');
904    if (!dirend || bslash > dirend)
905      dirend = bslash;
906    /* The case of "d:file".  */
907    if (!dirend && filename[0] && filename[1] == ':')
908      dirend = filename + 1;
909  }
910#endif /* HAVE_DOS_PATHS */
911  if (dirend == 0)
912#ifdef _AMIGA
913    dir = find_directory ("")->contents;
914#else /* !VMS && !AMIGA */
915    dir = find_directory (".")->contents;
916#endif /* AMIGA */
917#endif /* VMS */
918  else
919    {
920      char *dirname;
921      char *slash = dirend;
922      if (dirend == filename)
923	dirname = "/";
924      else
925	{
926#ifdef HAVE_DOS_PATHS
927	  /* d:/ and d: are *very* different...  */
928	  if (dirend < filename + 3 && filename[1] == ':' &&
929	      (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
930	    dirend++;
931#endif
932	  dirname = (char *) alloca (dirend - filename + 1);
933	  bcopy (p, dirname, dirend - p);
934	  dirname[dirend - p] = '\0';
935	}
936      dir = find_directory (dirname)->contents;
937      p = filename = slash + 1;
938    }
939
940  if (dir == 0 || dir->dirfiles.ht_vec == 0)
941    /* There are no files entered for this directory.  */
942    return 0;
943
944#ifdef __MSDOS__
945  filename = dosify (p);
946#endif
947#ifdef HAVE_CASE_INSENSITIVE_FS
948  filename = downcase (p);
949#endif
950#ifdef VMS
951  filename = vmsify (p, 1);
952#endif
953
954  dirfile_key.name = filename;
955  dirfile_key.length = strlen (filename);
956  dirfile = (struct dirfile *) hash_find_item (&dir->dirfiles, &dirfile_key);
957  if (dirfile)
958    return dirfile->impossible;
959
960  return 0;
961}
962
963/* Return the already allocated name in the
964   directory hash table that matches DIR.  */
965
966char *
967dir_name (dir)
968     char *dir;
969{
970  return find_directory (dir)->name;
971}
972
973/* Print the data base of directories.  */
974
975void
976print_dir_data_base ()
977{
978  register unsigned int files;
979  register unsigned int impossible;
980  register struct directory **dir_slot;
981  register struct directory **dir_end;
982
983  puts (_("\n# Directories\n"));
984
985  files = impossible = 0;
986
987  dir_slot = (struct directory **) directories.ht_vec;
988  dir_end = dir_slot + directories.ht_size;
989  for ( ; dir_slot < dir_end; dir_slot++)
990    {
991      register struct directory *dir = *dir_slot;
992      if (! HASH_VACANT (dir))
993	{
994	  if (dir->contents == 0)
995	    printf (_("# %s: could not be stat'd.\n"), dir->name);
996	  else if (dir->contents->dirfiles.ht_vec == 0)
997	    {
998#ifdef WINDOWS32
999	      printf (_("# %s (key %s, mtime %d): could not be opened.\n"),
1000		      dir->name, dir->contents->path_key,dir->contents->mtime);
1001#else  /* WINDOWS32 */
1002#ifdef VMS
1003	      printf (_("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n"),
1004		      dir->name, dir->contents->dev,
1005		      dir->contents->ino[0], dir->contents->ino[1],
1006		      dir->contents->ino[2]);
1007#else
1008	      printf (_("# %s (device %ld, inode %ld): could not be opened.\n"),
1009		      dir->name, (long int) dir->contents->dev,
1010		      (long int) dir->contents->ino);
1011#endif
1012#endif /* WINDOWS32 */
1013	    }
1014	  else
1015	    {
1016	      register unsigned int f = 0;
1017	      register unsigned int im = 0;
1018	      register struct dirfile **files_slot;
1019	      register struct dirfile **files_end;
1020
1021	      files_slot = (struct dirfile **) dir->contents->dirfiles.ht_vec;
1022	      files_end = files_slot + dir->contents->dirfiles.ht_size;
1023	      for ( ; files_slot < files_end; files_slot++)
1024		{
1025		  register struct dirfile *df = *files_slot;
1026		  if (! HASH_VACANT (df))
1027		    {
1028		      if (df->impossible)
1029			++im;
1030		      else
1031			++f;
1032		    }
1033		}
1034#ifdef WINDOWS32
1035	      printf (_("# %s (key %s, mtime %d): "),
1036		      dir->name, dir->contents->path_key, dir->contents->mtime);
1037#else  /* WINDOWS32 */
1038#ifdef VMS
1039	      printf (_("# %s (device %d, inode [%d,%d,%d]): "),
1040		      dir->name, dir->contents->dev,
1041		      dir->contents->ino[0], dir->contents->ino[1],
1042		      dir->contents->ino[2]);
1043#else
1044	      printf (_("# %s (device %ld, inode %ld): "),
1045		      dir->name,
1046		      (long)dir->contents->dev, (long)dir->contents->ino);
1047#endif
1048#endif /* WINDOWS32 */
1049	      if (f == 0)
1050		fputs (_("No"), stdout);
1051	      else
1052		printf ("%u", f);
1053	      fputs (_(" files, "), stdout);
1054	      if (im == 0)
1055		fputs (_("no"), stdout);
1056	      else
1057		printf ("%u", im);
1058	      fputs (_(" impossibilities"), stdout);
1059	      if (dir->contents->dirstream == 0)
1060		puts (".");
1061	      else
1062		puts (_(" so far."));
1063	      files += f;
1064	      impossible += im;
1065	    }
1066	}
1067    }
1068
1069  fputs ("\n# ", stdout);
1070  if (files == 0)
1071    fputs (_("No"), stdout);
1072  else
1073    printf ("%u", files);
1074  fputs (_(" files, "), stdout);
1075  if (impossible == 0)
1076    fputs (_("no"), stdout);
1077  else
1078    printf ("%u", impossible);
1079  printf (_(" impossibilities in %lu directories.\n"), directories.ht_fill);
1080}
1081
1082/* Hooks for globbing.  */
1083
1084#include <glob.h>
1085
1086/* Structure describing state of iterating through a directory hash table.  */
1087
1088struct dirstream
1089  {
1090    struct directory_contents *contents; /* The directory being read.  */
1091    struct dirfile **dirfile_slot; /* Current slot in table.  */
1092  };
1093
1094/* Forward declarations.  */
1095static __ptr_t open_dirstream PARAMS ((const char *));
1096static struct dirent *read_dirstream PARAMS ((__ptr_t));
1097
1098static __ptr_t
1099open_dirstream (directory)
1100     const char *directory;
1101{
1102  struct dirstream *new;
1103  struct directory *dir = find_directory ((char *)directory);
1104
1105  if (dir->contents == 0 || dir->contents->dirfiles.ht_vec == 0)
1106    /* DIR->contents is nil if the directory could not be stat'd.
1107       DIR->contents->dirfiles is nil if it could not be opened.  */
1108    return 0;
1109
1110  /* Read all the contents of the directory now.  There is no benefit
1111     in being lazy, since glob will want to see every file anyway.  */
1112
1113  (void) dir_contents_file_exists_p (dir->contents, (char *) 0);
1114
1115  new = (struct dirstream *) xmalloc (sizeof (struct dirstream));
1116  new->contents = dir->contents;
1117  new->dirfile_slot = (struct dirfile **) new->contents->dirfiles.ht_vec;
1118
1119  return (__ptr_t) new;
1120}
1121
1122static struct dirent *
1123read_dirstream (stream)
1124     __ptr_t stream;
1125{
1126  struct dirstream *const ds = (struct dirstream *) stream;
1127  struct directory_contents *dc = ds->contents;
1128  struct dirfile **dirfile_end = (struct dirfile **) dc->dirfiles.ht_vec + dc->dirfiles.ht_size;
1129  static char *buf;
1130  static unsigned int bufsz;
1131
1132  while (ds->dirfile_slot < dirfile_end)
1133    {
1134      register struct dirfile *df = *ds->dirfile_slot++;
1135      if (! HASH_VACANT (df) && !df->impossible)
1136	{
1137	  /* The glob interface wants a `struct dirent',
1138	     so mock one up.  */
1139	  struct dirent *d;
1140	  unsigned int len = df->length + 1;
1141	  if (sizeof *d - sizeof d->d_name + len > bufsz)
1142	    {
1143	      if (buf != 0)
1144		free (buf);
1145	      bufsz *= 2;
1146	      if (sizeof *d - sizeof d->d_name + len > bufsz)
1147		bufsz = sizeof *d - sizeof d->d_name + len;
1148	      buf = xmalloc (bufsz);
1149	    }
1150	  d = (struct dirent *) buf;
1151	  FAKE_DIR_ENTRY (d);
1152#ifdef _DIRENT_HAVE_D_NAMLEN
1153	  d->d_namlen = len - 1;
1154#endif
1155#ifdef _DIRENT_HAVE_D_TYPE
1156	  d->d_type = DT_UNKNOWN;
1157#endif
1158	  memcpy (d->d_name, df->name, len);
1159	  return d;
1160	}
1161    }
1162
1163  return 0;
1164}
1165
1166static void
1167ansi_free(p)
1168  void *p;
1169{
1170    if (p)
1171      free(p);
1172}
1173
1174/* On 64 bit ReliantUNIX (5.44 and above) in LFS mode, stat() is actually a
1175 * macro for stat64().  If stat is a macro, make a local wrapper function to
1176 * invoke it.
1177 */
1178#ifndef stat
1179# ifndef VMS
1180extern int stat ();
1181# endif
1182# define local_stat stat
1183#else
1184static int local_stat (path, buf)
1185    char *path;
1186    struct stat *buf;
1187{
1188  return stat (path, buf);
1189}
1190#endif
1191
1192void
1193dir_setup_glob (gl)
1194     glob_t *gl;
1195{
1196  /* Bogus sunos4 compiler complains (!) about & before functions.  */
1197  gl->gl_opendir = open_dirstream;
1198  gl->gl_readdir = read_dirstream;
1199  gl->gl_closedir = ansi_free;
1200  gl->gl_stat = local_stat;
1201  /* We don't bother setting gl_lstat, since glob never calls it.
1202     The slot is only there for compatibility with 4.4 BSD.  */
1203}
1204
1205void
1206hash_init_directories ()
1207{
1208  hash_init (&directories, DIRECTORY_BUCKETS,
1209	     directory_hash_1, directory_hash_2, directory_hash_cmp);
1210  hash_init (&directory_contents, DIRECTORY_BUCKETS,
1211	     directory_contents_hash_1, directory_contents_hash_2, directory_contents_hash_cmp);
1212}
1213