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