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