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