dir.c

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