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