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