dir.c

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