dir.c

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