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