dir.c

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