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