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