dir.c

   1 /* Directory hashing for GNU Make.
   2 Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011,
   4 2012 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 }