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