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 Free Software
   4 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 2, or (at your option) any later version.
  10
  11 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  13 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along with
  16 GNU Make; see the file COPYING.  If not, write to the Free Software
  17 Foundation, 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
  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 WINDOWS32
 458       /* Remove any trailing '\'.  Windows32 stat fails even on valid
 459          directories if they end in '\'. */
 460       if (p[-1] == '\\')
 461         p[-1] = '\0';
 462 #endif
 463
 464 #ifdef VMS
 465       r = vmsstat_dir (name, &st);
 466 #else
 467       EINTRLOOP (r, stat (name, &st));
 468 #endif
 469
 470 #ifdef WINDOWS32
 471       /* Put back the trailing '\'.  If we don't, we're permanently
 472          truncating the value!  */
 473       if (p[-1] == '\0')
 474         p[-1] = '\\';
 475 #endif
 476
 477       if (r < 0)
 478         {
 479         /* Couldn't stat the directory.  Mark this by
 480            setting the `contents' member to a nil pointer.  */
 481           dir->contents = 0;
 482         }
 483       else
 484         {
 485           /* Search the contents hash table; device and inode are the key.  */
 486
 487           struct directory_contents *dc;
 488           struct directory_contents **dc_slot;
 489           struct directory_contents dc_key;
 490
 491           dc_key.dev = st.st_dev;
 492 #ifdef WINDOWS32
 493           dc_key.path_key = w32_path = w32ify (name, 1);
 494           dc_key.ctime = st.st_ctime;
 495 #else
 496 # ifdef VMS
 497           dc_key.ino[0] = st.st_ino[0];
 498           dc_key.ino[1] = st.st_ino[1];
 499           dc_key.ino[2] = st.st_ino[2];
 500 # else
 501           dc_key.ino = st.st_ino;
 502 # endif
 503 #endif
 504           dc_slot = (struct directory_contents **) hash_find_slot (&directory_contents, &dc_key);
 505           dc = *dc_slot;
 506
 507           if (HASH_VACANT (dc))
 508             {
 509               /* Nope; this really is a directory we haven't seen before.  */
 510
 511               dc = (struct directory_contents *)
 512                 xmalloc (sizeof (struct directory_contents));
 513
 514               /* Enter it in the contents hash table.  */
 515               dc->dev = st.st_dev;
 516 #ifdef WINDOWS32
 517               dc->path_key = xstrdup (w32_path);
 518               dc->ctime = st.st_ctime;
 519               dc->mtime = st.st_mtime;
 520
 521               /*
 522                * NTFS is the only WINDOWS32 filesystem that bumps mtime
 523                * on a directory when files are added/deleted from
 524                * a directory.
 525                */
 526               w32_path[3] = '\0';
 527               if (GetVolumeInformation(w32_path,
 528                      fs_label, sizeof (fs_label),
 529                      &fs_serno, &fs_len,
 530                      &fs_flags, fs_type, sizeof (fs_type)) == FALSE)
 531                 dc->fs_flags = FS_UNKNOWN;
 532               else if (!strcmp(fs_type, "FAT"))
 533                 dc->fs_flags = FS_FAT;
 534               else if (!strcmp(fs_type, "NTFS"))
 535                 dc->fs_flags = FS_NTFS;
 536               else
 537                 dc->fs_flags = FS_UNKNOWN;
 538 #else
 539 # ifdef VMS
 540               dc->ino[0] = st.st_ino[0];
 541               dc->ino[1] = st.st_ino[1];
 542               dc->ino[2] = st.st_ino[2];
 543 # else
 544               dc->ino = st.st_ino;
 545 # endif
 546 #endif /* WINDOWS32 */
 547               hash_insert_at (&directory_contents, dc, dc_slot);
 548               ENULLLOOP (dc->dirstream, opendir (name));
 549               if (dc->dirstream == 0)
 550                 /* Couldn't open the directory.  Mark this by setting the
 551                    `files' member to a nil pointer.  */
 552                 dc->dirfiles.ht_vec = 0;
 553               else
 554                 {
 555                   hash_init (&dc->dirfiles, DIRFILE_BUCKETS,
 556                              dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
 557                   /* Keep track of how many directories are open.  */
 558                   ++open_directories;
 559                   if (open_directories == MAX_OPEN_DIRECTORIES)
 560                     /* We have too many directories open already.
 561                        Read the entire directory and then close it.  */
 562                     dir_contents_file_exists_p (dc, 0);
 563                 }
 564             }
 565
 566           /* Point the name-hashed entry for DIR at its contents data.  */
 567           dir->contents = dc;
 568         }
 569     }
 570
 571   return dir;
 572 }
 573 \f
 574 /* Return 1 if the name FILENAME is entered in DIR's hash table.
 575    FILENAME must contain no slashes.  */
 576
 577 static int
 578 dir_contents_file_exists_p (struct directory_contents *dir,
 579                             const char *filename)
 580 {
 581   unsigned int hash;
 582   struct dirfile *df;
 583   struct dirent *d;
 584 #ifdef WINDOWS32
 585   struct stat st;
 586   int rehash = 0;
 587 #endif
 588
 589   if (dir == 0 || dir->dirfiles.ht_vec == 0)
 590     /* The directory could not be stat'd or opened.  */
 591     return 0;
 592
 593 #ifdef __MSDOS__
 594   filename = dosify (filename);
 595 #endif
 596
 597 #ifdef HAVE_CASE_INSENSITIVE_FS
 598   filename = downcase (filename);
 599 #endif
 600
 601 #ifdef __EMX__
 602   if (filename != 0)
 603     _fnlwr (filename); /* lower case for FAT drives */
 604 #endif
 605
 606 #ifdef VMS
 607   filename = vmsify (filename,0);
 608 #endif
 609
 610   hash = 0;
 611   if (filename != 0)
 612     {
 613       struct dirfile dirfile_key;
 614
 615       if (*filename == '\0')
 616         {
 617           /* Checking if the directory exists.  */
 618           return 1;
 619         }
 620       dirfile_key.name = filename;
 621       dirfile_key.length = strlen (filename);
 622       df = hash_find_item (&dir->dirfiles, &dirfile_key);
 623       if (df)
 624         return !df->impossible;
 625     }
 626
 627   /* The file was not found in the hashed list.
 628      Try to read the directory further.  */
 629
 630   if (dir->dirstream == 0)
 631     {
 632 #ifdef WINDOWS32
 633       /*
 634        * Check to see if directory has changed since last read. FAT
 635        * filesystems force a rehash always as mtime does not change
 636        * on directories (ugh!).
 637        */
 638       if (dir->path_key)
 639         {
 640           if ((dir->fs_flags & FS_FAT) != 0)
 641             {
 642               dir->mtime = time ((time_t *) 0);
 643               rehash = 1;
 644             }
 645           else if (stat (dir->path_key, &st) == 0 && st.st_mtime > dir->mtime)
 646             {
 647               /* reset date stamp to show most recent re-process.  */
 648               dir->mtime = st.st_mtime;
 649               rehash = 1;
 650             }
 651
 652           /* If it has been already read in, all done.  */
 653           if (!rehash)
 654             return 0;
 655
 656           /* make sure directory can still be opened; if not return.  */
 657           dir->dirstream = opendir (dir->path_key);
 658           if (!dir->dirstream)
 659             return 0;
 660         }
 661       else
 662 #endif
 663         /* The directory has been all read in.  */
 664         return 0;
 665     }
 666
 667   while (1)
 668     {
 669       /* Enter the file in the hash table.  */
 670       unsigned int len;
 671       struct dirfile dirfile_key;
 672       struct dirfile **dirfile_slot;
 673
 674       ENULLLOOP (d, readdir (dir->dirstream));
 675       if (d == 0)
 676         {
 677           if (errno)
 678             fatal (NILF, "INTERNAL: readdir: %s\n", strerror (errno));
 679           break;
 680         }
 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 = xmalloc (sizeof (struct dirfile));
 706           df->name = strcache_add_len (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         return 1;
 714     }
 715
 716   /* If the directory has been completely read in,
 717      close the stream and reset the pointer to nil.  */
 718   if (d == 0)
 719     {
 720       --open_directories;
 721       closedir (dir->dirstream);
 722       dir->dirstream = 0;
 723     }
 724   return 0;
 725 }
 726
 727 /* Return 1 if the name FILENAME in directory DIRNAME
 728    is entered in the dir hash table.
 729    FILENAME must contain no slashes.  */
 730
 731 int
 732 dir_file_exists_p (const char *dirname, const char *filename)
 733 {
 734   return dir_contents_file_exists_p (find_directory (dirname)->contents,
 735                                      filename);
 736 }
 737 \f
 738 /* Return 1 if the file named NAME exists.  */
 739
 740 int
 741 file_exists_p (const char *name)
 742 {
 743   const char *dirend;
 744   const char *dirname;
 745   const char *slash;
 746
 747 #ifndef NO_ARCHIVES
 748   if (ar_name (name))
 749     return ar_member_date (name) != (time_t) -1;
 750 #endif
 751
 752 #ifdef VMS
 753   dirend = strrchr (name, ']');
 754   if (dirend == 0)
 755     dirend = strrchr (name, ':');
 756   if (dirend == 0)
 757     return dir_file_exists_p ("[]", name);
 758 #else /* !VMS */
 759   dirend = strrchr (name, '/');
 760 #ifdef HAVE_DOS_PATHS
 761   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
 762   {
 763     const char *bslash = strrchr(name, '\\');
 764     if (!dirend || bslash > dirend)
 765       dirend = bslash;
 766     /* The case of "d:file".  */
 767     if (!dirend && name[0] && name[1] == ':')
 768       dirend = name + 1;
 769   }
 770 #endif /* HAVE_DOS_PATHS */
 771   if (dirend == 0)
 772 #ifndef _AMIGA
 773     return dir_file_exists_p (".", name);
 774 #else /* !VMS && !AMIGA */
 775     return dir_file_exists_p ("", name);
 776 #endif /* AMIGA */
 777 #endif /* VMS */
 778
 779   slash = dirend;
 780   if (dirend == name)
 781     dirname = "/";
 782   else
 783     {
 784       char *p;
 785 #ifdef HAVE_DOS_PATHS
 786   /* d:/ and d: are *very* different...  */
 787       if (dirend < name + 3 && name[1] == ':' &&
 788           (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
 789         dirend++;
 790 #endif
 791       p = alloca (dirend - name + 1);
 792       memcpy (p, name, dirend - name);
 793       p[dirend - name] = '\0';
 794       dirname = p;
 795     }
 796   return dir_file_exists_p (dirname, slash + 1);
 797 }
 798 \f
 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
 803 void
 804 file_impossible (const char *filename)
 805 {
 806   const char *dirend;
 807   const char *p = filename;
 808   struct directory *dir;
 809   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     const 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       const char *dirname;
 841       const char *slash = dirend;
 842       if (dirend == p)
 843         dirname = "/";
 844       else
 845         {
 846           char *cp;
 847 #ifdef HAVE_DOS_PATHS
 848           /* d:/ and d: are *very* different...  */
 849           if (dirend < p + 3 && p[1] == ':' &&
 850               (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
 851             dirend++;
 852 #endif
 853           cp = alloca (dirend - p + 1);
 854           memcpy (cp, p, dirend - p);
 855           cp[dirend - p] = '\0';
 856           dirname = cp;
 857         }
 858       dir = find_directory (dirname);
 859       filename = p = slash + 1;
 860     }
 861
 862   if (dir->contents == 0)
 863     {
 864       /* The directory could not be stat'd.  We allocate a contents
 865          structure for it, but leave it out of the contents hash table.  */
 866       dir->contents = xmalloc (sizeof (struct directory_contents));
 867       memset (dir->contents, '\0', sizeof (struct directory_contents));
 868     }
 869
 870   if (dir->contents->dirfiles.ht_vec == 0)
 871     {
 872       hash_init (&dir->contents->dirfiles, DIRFILE_BUCKETS,
 873                  dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp);
 874     }
 875
 876   /* Make a new entry and put it in the table.  */
 877
 878   new = xmalloc (sizeof (struct dirfile));
 879   new->length = strlen (filename);
 880   new->name = strcache_add_len (filename, new->length);
 881   new->impossible = 1;
 882   hash_insert (&dir->contents->dirfiles, new);
 883 }
 884 \f
 885 /* Return nonzero if FILENAME has been marked impossible.  */
 886
 887 int
 888 file_impossible_p (const char *filename)
 889 {
 890   const char *dirend;
 891   const char *p = filename;
 892   struct directory_contents *dir;
 893   struct dirfile *dirfile;
 894   struct dirfile dirfile_key;
 895
 896 #ifdef VMS
 897   dirend = strrchr (filename, ']');
 898   if (dirend == 0)
 899     dir = find_directory ("[]")->contents;
 900 #else
 901   dirend = strrchr (filename, '/');
 902 #ifdef HAVE_DOS_PATHS
 903   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
 904   {
 905     const char *bslash = strrchr(filename, '\\');
 906     if (!dirend || bslash > dirend)
 907       dirend = bslash;
 908     /* The case of "d:file".  */
 909     if (!dirend && filename[0] && filename[1] == ':')
 910       dirend = filename + 1;
 911   }
 912 #endif /* HAVE_DOS_PATHS */
 913   if (dirend == 0)
 914 #ifdef _AMIGA
 915     dir = find_directory ("")->contents;
 916 #else /* !VMS && !AMIGA */
 917     dir = find_directory (".")->contents;
 918 #endif /* AMIGA */
 919 #endif /* VMS */
 920   else
 921     {
 922       const char *dirname;
 923       const char *slash = dirend;
 924       if (dirend == filename)
 925         dirname = "/";
 926       else
 927         {
 928           char *cp;
 929 #ifdef HAVE_DOS_PATHS
 930           /* d:/ and d: are *very* different...  */
 931           if (dirend < filename + 3 && filename[1] == ':' &&
 932               (*dirend == '/' || *dirend == '\\' || *dirend == ':'))
 933             dirend++;
 934 #endif
 935           cp = alloca (dirend - filename + 1);
 936           memcpy (cp, p, dirend - p);
 937           cp[dirend - p] = '\0';
 938           dirname = cp;
 939         }
 940       dir = find_directory (dirname)->contents;
 941       p = filename = slash + 1;
 942     }
 943
 944   if (dir == 0 || dir->dirfiles.ht_vec == 0)
 945     /* There are no files entered for this directory.  */
 946     return 0;
 947
 948 #ifdef __MSDOS__
 949   filename = dosify (p);
 950 #endif
 951 #ifdef HAVE_CASE_INSENSITIVE_FS
 952   filename = downcase (p);
 953 #endif
 954 #ifdef VMS
 955   filename = vmsify (p, 1);
 956 #endif
 957
 958   dirfile_key.name = filename;
 959   dirfile_key.length = strlen (filename);
 960   dirfile = hash_find_item (&dir->dirfiles, &dirfile_key);
 961   if (dirfile)
 962     return dirfile->impossible;
 963
 964   return 0;
 965 }
 966 \f
 967 /* Return the already allocated name in the
 968    directory hash table that matches DIR.  */
 969
 970 const char *
 971 dir_name (const char *dir)
 972 {
 973   return find_directory (dir)->name;
 974 }
 975 \f
 976 /* Print the data base of directories.  */
 977
 978 void
 979 print_dir_data_base (void)
 980 {
 981   unsigned int files;
 982   unsigned int impossible;
 983   struct directory **dir_slot;
 984   struct directory **dir_end;
 985
 986   puts (_("\n# Directories\n"));
 987
 988   files = impossible = 0;
 989
 990   dir_slot = (struct directory **) directories.ht_vec;
 991   dir_end = dir_slot + directories.ht_size;
 992   for ( ; dir_slot < dir_end; dir_slot++)
 993     {
 994       struct directory *dir = *dir_slot;
 995       if (! HASH_VACANT (dir))
 996         {
 997           if (dir->contents == 0)
 998             printf (_("# %s: could not be stat'd.\n"), dir->name);
 999           else if (dir->contents->dirfiles.ht_vec == 0)
1000             {
1001 #ifdef WINDOWS32
1002               printf (_("# %s (key %s, mtime %d): could not be opened.\n"),
1003                       dir->name, dir->contents->path_key,dir->contents->mtime);
1004 #else  /* WINDOWS32 */
1005 #ifdef VMS
1006               printf (_("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n"),
1007                       dir->name, dir->contents->dev,
1008                       dir->contents->ino[0], dir->contents->ino[1],
1009                       dir->contents->ino[2]);
1010 #else
1011               printf (_("# %s (device %ld, inode %ld): could not be opened.\n"),
1012                       dir->name, (long int) dir->contents->dev,
1013                       (long int) dir->contents->ino);
1014 #endif
1015 #endif /* WINDOWS32 */
1016             }
1017           else
1018             {
1019               unsigned int f = 0;
1020               unsigned int im = 0;
1021               struct dirfile **files_slot;
1022               struct dirfile **files_end;
1023
1024               files_slot = (struct dirfile **) dir->contents->dirfiles.ht_vec;
1025               files_end = files_slot + dir->contents->dirfiles.ht_size;
1026               for ( ; files_slot < files_end; files_slot++)
1027                 {
1028                   struct dirfile *df = *files_slot;
1029                   if (! HASH_VACANT (df))
1030                     {
1031                       if (df->impossible)
1032                         ++im;
1033                       else
1034                         ++f;
1035                     }
1036                 }
1037 #ifdef WINDOWS32
1038               printf (_("# %s (key %s, mtime %d): "),
1039                       dir->name, dir->contents->path_key, dir->contents->mtime);
1040 #else  /* WINDOWS32 */
1041 #ifdef VMS
1042               printf (_("# %s (device %d, inode [%d,%d,%d]): "),
1043                       dir->name, dir->contents->dev,
1044                       dir->contents->ino[0], dir->contents->ino[1],
1045                       dir->contents->ino[2]);
1046 #else
1047               printf (_("# %s (device %ld, inode %ld): "),
1048                       dir->name,
1049                       (long)dir->contents->dev, (long)dir->contents->ino);
1050 #endif
1051 #endif /* WINDOWS32 */
1052               if (f == 0)
1053                 fputs (_("No"), stdout);
1054               else
1055                 printf ("%u", f);
1056               fputs (_(" files, "), stdout);
1057               if (im == 0)
1058                 fputs (_("no"), stdout);
1059               else
1060                 printf ("%u", im);
1061               fputs (_(" impossibilities"), stdout);
1062               if (dir->contents->dirstream == 0)
1063                 puts (".");
1064               else
1065                 puts (_(" so far."));
1066               files += f;
1067               impossible += im;
1068             }
1069         }
1070     }
1071
1072   fputs ("\n# ", stdout);
1073   if (files == 0)
1074     fputs (_("No"), stdout);
1075   else
1076     printf ("%u", files);
1077   fputs (_(" files, "), stdout);
1078   if (impossible == 0)
1079     fputs (_("no"), stdout);
1080   else
1081     printf ("%u", impossible);
1082   printf (_(" impossibilities in %lu directories.\n"), directories.ht_fill);
1083 }
1084 \f
1085 /* Hooks for globbing.  */
1086
1087 #include <glob.h>
1088
1089 /* Structure describing state of iterating through a directory hash table.  */
1090
1091 struct dirstream
1092   {
1093     struct directory_contents *contents; /* The directory being read.  */
1094     struct dirfile **dirfile_slot; /* Current slot in table.  */
1095   };
1096
1097 /* Forward declarations.  */
1098 static __ptr_t open_dirstream (const char *);
1099 static struct dirent *read_dirstream (__ptr_t);
1100
1101 static __ptr_t
1102 open_dirstream (const char *directory)
1103 {
1104   struct dirstream *new;
1105   struct directory *dir = find_directory (directory);
1106
1107   if (dir->contents == 0 || dir->contents->dirfiles.ht_vec == 0)
1108     /* DIR->contents is nil if the directory could not be stat'd.
1109        DIR->contents->dirfiles is nil if it could not be opened.  */
1110     return 0;
1111
1112   /* Read all the contents of the directory now.  There is no benefit
1113      in being lazy, since glob will want to see every file anyway.  */
1114
1115   dir_contents_file_exists_p (dir->contents, 0);
1116
1117   new = xmalloc (sizeof (struct dirstream));
1118   new->contents = dir->contents;
1119   new->dirfile_slot = (struct dirfile **) new->contents->dirfiles.ht_vec;
1120
1121   return (__ptr_t) new;
1122 }
1123
1124 static struct dirent *
1125 read_dirstream (__ptr_t stream)
1126 {
1127   static char *buf;
1128   static unsigned int bufsz;
1129
1130   struct dirstream *const ds = (struct dirstream *) stream;
1131   struct directory_contents *dc = ds->contents;
1132   struct dirfile **dirfile_end = (struct dirfile **) dc->dirfiles.ht_vec + dc->dirfiles.ht_size;
1133
1134   while (ds->dirfile_slot < dirfile_end)
1135     {
1136       struct dirfile *df = *ds->dirfile_slot++;
1137       if (! HASH_VACANT (df) && !df->impossible)
1138         {
1139           /* The glob interface wants a `struct dirent', so mock one up.  */
1140           struct dirent *d;
1141           unsigned int len = df->length + 1;
1142           unsigned int sz = sizeof (*d) - sizeof (d->d_name) + len;
1143           if (sz > bufsz)
1144             {
1145               bufsz *= 2;
1146               if (sz > bufsz)
1147                 bufsz = sz;
1148               buf = xrealloc (buf, bufsz);
1149             }
1150           d = (struct dirent *) buf;
1151 #ifdef __MINGW32__
1152 # if __MINGW32_MAJOR_VERSION < 3 || (__MINGW32_MAJOR_VERSION == 3 && \
1153                                      __MINGW32_MINOR_VERSION == 0)
1154           d->d_name = xmalloc(len);
1155 # endif
1156 #endif
1157           FAKE_DIR_ENTRY (d);
1158 #ifdef _DIRENT_HAVE_D_NAMLEN
1159           d->d_namlen = len - 1;
1160 #endif
1161 #ifdef _DIRENT_HAVE_D_TYPE
1162           d->d_type = DT_UNKNOWN;
1163 #endif
1164           memcpy (d->d_name, df->name, len);
1165           return d;
1166         }
1167     }
1168
1169   return 0;
1170 }
1171
1172 static void
1173 ansi_free (void *p)
1174 {
1175   if (p)
1176     free(p);
1177 }
1178
1179 /* On 64 bit ReliantUNIX (5.44 and above) in LFS mode, stat() is actually a
1180  * macro for stat64().  If stat is a macro, make a local wrapper function to
1181  * invoke it.
1182  */
1183 #ifndef stat
1184 # ifndef VMS
1185 int stat (const char *path, struct stat *sbuf);
1186 # endif
1187 # define local_stat stat
1188 #else
1189 static int
1190 local_stat (const char *path, struct stat *buf)
1191 {
1192   int e;
1193
1194   EINTRLOOP (e, stat (path, buf));
1195   return e;
1196 }
1197 #endif
1198
1199 void
1200 dir_setup_glob (glob_t *gl)
1201 {
1202   gl->gl_opendir = open_dirstream;
1203   gl->gl_readdir = read_dirstream;
1204   gl->gl_closedir = ansi_free;
1205   gl->gl_stat = local_stat;
1206   /* We don't bother setting gl_lstat, since glob never calls it.
1207      The slot is only there for compatibility with 4.4 BSD.  */
1208 }
1209
1210 void
1211 hash_init_directories (void)
1212 {
1213   hash_init (&directories, DIRECTORY_BUCKETS,
1214              directory_hash_1, directory_hash_2, directory_hash_cmp);
1215   hash_init (&directory_contents, DIRECTORY_BUCKETS,
1216              directory_contents_hash_1, directory_contents_hash_2,
1217              directory_contents_hash_cmp);
1218 }