dir.c

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