dir.c

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