dir.c

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