dir.c

   1 /* Directory hashing for GNU Make.
   2 Copyright (C) 1988, 89, 91, 92, 93, 94, 95 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 #if     defined (POSIX) || defined (HAVE_DIRENT_H) || defined (__GNU_LIBRARY__)
  22 #include <dirent.h>
  23 #if     defined (__GNU_LIBRARY__) && __GNU_LIBRARY__ > 1
  24 #define HAVE_D_NAMLEN
  25 #endif  /* GNU C library.  */
  26 #else   /* Not POSIX or HAVE_DIRENT_H.  */
  27 #define direct dirent
  28 #define HAVE_D_NAMLEN
  29 #ifdef  HAVE_SYS_NDIR_H
  30 #include <sys/ndir.h>
  31 #endif  /* HAVE_SYS_NDIR_H */
  32 #ifdef  HAVE_SYS_DIR_H
  33 #include <sys/dir.h>
  34 #endif  /* HAVE_SYS_DIR_H */
  35 #ifdef HAVE_NDIR_H
  36 #include <ndir.h>
  37 #endif  /* HAVE_NDIR_H */
  38 #endif  /* POSIX or HAVE_DIRENT_H or __GNU_LIBRARY__.  */
  39
  40 #if defined (POSIX) && !defined (__GNU_LIBRARY__)
  41 /* Posix does not require that the d_ino field be present, and some
  42    systems do not provide it. */
  43 #define REAL_DIR_ENTRY(dp) 1
  44 #define FAKE_DIR_ENTRY(dp)
  45 #else
  46 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  47 #define FAKE_DIR_ENTRY(dp) (dp->d_ino = 1)
  48 #endif /* POSIX */
  49 \f
  50 #ifdef __MSDOS__
  51 #include <ctype.h>
  52
  53 static char *
  54 dosify (filename)
  55      char *filename;
  56 {
  57   static char dos_filename[14];
  58   char *df;
  59   int i;
  60
  61   if (filename == 0)
  62     return 0;
  63
  64   if (strpbrk (filename, "\"*+,;<=>?[\\]|") != 0)
  65     return filename;
  66
  67   df = dos_filename;
  68
  69   /* First, transform the name part.  */
  70   for (i = 0; *filename != '\0' && i < 8 && *filename != '.'; ++i)
  71     *df++ = tolower (*filename++);
  72
  73   /* Now skip to the next dot.  */
  74   while (*filename != '\0' && *filename != '.')
  75     ++filename;
  76   if (*filename != '\0')
  77     {
  78       *df++ = *filename++;
  79       for (i = 0; *filename != '\0' && i < 3 && *filename != '.'; ++i)
  80         *df++ = tolower (*filename++);
  81     }
  82
  83   /* Look for more dots.  */
  84   while (*filename != '\0' && *filename != '.')
  85     ++filename;
  86   if (*filename == '.')
  87     return filename;
  88   *df = 0;
  89   return dos_filename;
  90 }
  91 #endif
  92 \f
  93 /* Hash table of directories.  */
  94
  95 #ifndef DIRECTORY_BUCKETS
  96 #define DIRECTORY_BUCKETS 199
  97 #endif
  98
  99 struct directory_contents
 100   {
 101     struct directory_contents *next;
 102
 103     int dev, ino;               /* Device and inode numbers of this dir.  */
 104
 105     struct dirfile **files;     /* Files in this directory.  */
 106     DIR *dirstream;             /* Stream reading this directory.  */
 107   };
 108
 109 /* Table of directory contents hashed by device and inode number.  */
 110 static struct directory_contents *directories_contents[DIRECTORY_BUCKETS];
 111
 112 struct directory
 113   {
 114     struct directory *next;
 115
 116     char *name;                 /* Name of the directory.  */
 117
 118     /* The directory's contents.  This data may be shared by several
 119        entries in the hash table, which refer to the same directory
 120        (identified uniquely by `dev' and `ino') under different names.  */
 121     struct directory_contents *contents;
 122   };
 123
 124 /* Table of directories hashed by name.  */
 125 static struct directory *directories[DIRECTORY_BUCKETS];
 126
 127
 128 /* Never have more than this many directories open at once.  */
 129
 130 #define MAX_OPEN_DIRECTORIES 10
 131
 132 static unsigned int open_directories = 0;
 133
 134
 135 /* Hash table of files in each directory.  */
 136
 137 struct dirfile
 138   {
 139     struct dirfile *next;
 140     char *name;                 /* Name of the file.  */
 141     char impossible;            /* This file is impossible.  */
 142   };
 143
 144 #ifndef DIRFILE_BUCKETS
 145 #define DIRFILE_BUCKETS 107
 146 #endif
 147 \f
 148 static int dir_contents_file_exists_p ();
 149
 150 /* Find the directory named NAME and return its `struct directory'.  */
 151
 152 static struct directory *
 153 find_directory (name)
 154      register char *name;
 155 {
 156   register unsigned int hash = 0;
 157   register char *p;
 158   register struct directory *dir;
 159
 160   for (p = name; *p != '\0'; ++p)
 161     HASH (hash, *p);
 162   hash %= DIRECTORY_BUCKETS;
 163
 164   for (dir = directories[hash]; dir != 0; dir = dir->next)
 165     if (streq (dir->name, name))
 166       break;
 167
 168   if (dir == 0)
 169     {
 170       struct stat st;
 171
 172       /* The directory was not found.  Create a new entry for it.  */
 173
 174       dir = (struct directory *) xmalloc (sizeof (struct directory));
 175       dir->next = directories[hash];
 176       directories[hash] = dir;
 177       dir->name = savestring (name, p - name);
 178
 179       /* The directory is not in the name hash table.
 180          Find its device and inode numbers, and look it up by them.  */
 181
 182       if (stat (name, &st) < 0)
 183         /* Couldn't stat the directory.  Mark this by
 184            setting the `contents' member to a nil pointer.  */
 185         dir->contents = 0;
 186       else
 187         {
 188           /* Search the contents hash table; device and inode are the key.  */
 189
 190           struct directory_contents *dc;
 191
 192           hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ino;
 193           hash %= DIRECTORY_BUCKETS;
 194
 195           for (dc = directories_contents[hash]; dc != 0; dc = dc->next)
 196             if (dc->dev == st.st_dev && dc->ino == st.st_ino)
 197               break;
 198
 199           if (dc == 0)
 200             {
 201               /* Nope; this really is a directory we haven't seen before.  */
 202
 203               dc = (struct directory_contents *)
 204                 xmalloc (sizeof (struct directory_contents));
 205
 206               /* Enter it in the contents hash table.  */
 207               dc->dev = st.st_dev;
 208               dc->ino = st.st_ino;
 209               dc->next = directories_contents[hash];
 210               directories_contents[hash] = dc;
 211
 212               dc->dirstream = opendir (name);
 213               if (dc->dirstream == 0)
 214                 /* Couldn't open the directory.  Mark this by
 215                    setting the `files' member to a nil pointer.  */
 216                 dc->files = 0;
 217               else
 218                 {
 219                   /* Allocate an array of buckets for files and zero it.  */
 220                   dc->files = (struct dirfile **)
 221                     xmalloc (sizeof (struct dirfile *) * DIRFILE_BUCKETS);
 222                   bzero ((char *) dc->files,
 223                          sizeof (struct dirfile *) * DIRFILE_BUCKETS);
 224
 225                   /* Keep track of how many directories are open.  */
 226                   ++open_directories;
 227                   if (open_directories == MAX_OPEN_DIRECTORIES)
 228                     /* We have too many directories open already.
 229                        Read the entire directory and then close it.  */
 230                     (void) dir_contents_file_exists_p (dc, (char *) 0);
 231                 }
 232             }
 233
 234           /* Point the name-hashed entry for DIR at its contents data.  */
 235           dir->contents = dc;
 236         }
 237     }
 238
 239   return dir;
 240 }
 241 \f
 242 /* Return 1 if the name FILENAME is entered in DIR's hash table.
 243    FILENAME must contain no slashes.  */
 244
 245 static int
 246 dir_contents_file_exists_p (dir, filename)
 247      register struct directory_contents *dir;
 248      register char *filename;
 249 {
 250   register unsigned int hash;
 251   register char *p;
 252   register struct dirfile *df;
 253   register struct dirent *d;
 254
 255   if (dir == 0 || dir->files == 0)
 256     /* The directory could not be stat'd or opened.  */
 257     return 0;
 258
 259 #ifdef __MSDOS__
 260   filename = dosify (filename);
 261 #endif
 262
 263   hash = 0;
 264   if (filename != 0)
 265     {
 266       if (*filename == '\0')
 267         /* Checking if the directory exists.  */
 268         return 1;
 269
 270       for (p = filename; *p != '\0'; ++p)
 271         HASH (hash, *p);
 272       hash %= DIRFILE_BUCKETS;
 273
 274       /* Search the list of hashed files.  */
 275
 276       for (df = dir->files[hash]; df != 0; df = df->next)
 277         if (streq (df->name, filename))
 278           return !df->impossible;
 279     }
 280
 281   /* The file was not found in the hashed list.
 282      Try to read the directory further.  */
 283
 284   if (dir->dirstream == 0)
 285     /* The directory has been all read in.  */
 286     return 0;
 287
 288   while ((d = readdir (dir->dirstream)) != 0)
 289     {
 290       /* Enter the file in the hash table.  */
 291       register unsigned int newhash = 0;
 292       unsigned int len;
 293       register unsigned int i;
 294
 295       if (!REAL_DIR_ENTRY (d))
 296         continue;
 297
 298 #ifdef HAVE_D_NAMLEN
 299       len = d->d_namlen;
 300       while (d->d_name[len - 1] == '\0')
 301         --len;
 302 #else
 303       len = strlen (d->d_name);
 304 #endif
 305
 306       for (i = 0; i < len; ++i)
 307         HASH (newhash, d->d_name[i]);
 308       newhash %= DIRFILE_BUCKETS;
 309
 310       df = (struct dirfile *) xmalloc (sizeof (struct dirfile));
 311       df->next = dir->files[newhash];
 312       dir->files[newhash] = df;
 313       df->name = savestring (d->d_name, len);
 314       df->impossible = 0;
 315
 316       /* Check if the name matches the one we're searching for.  */
 317       if (filename != 0
 318           && newhash == hash && streq (d->d_name, filename))
 319         return 1;
 320     }
 321
 322   /* If the directory has been completely read in,
 323      close the stream and reset the pointer to nil.  */
 324   if (d == 0)
 325     {
 326       --open_directories;
 327       closedir (dir->dirstream);
 328       dir->dirstream = 0;
 329     }
 330
 331   return 0;
 332 }
 333
 334 /* Return 1 if the name FILENAME in directory DIRNAME
 335    is entered in the dir hash table.
 336    FILENAME must contain no slashes.  */
 337
 338 int
 339 dir_file_exists_p (dirname, filename)
 340      register char *dirname;
 341      register char *filename;
 342 {
 343   return dir_contents_file_exists_p (find_directory (dirname)->contents,
 344                                      filename);
 345 }
 346 \f
 347 /* Return 1 if the file named NAME exists.  */
 348
 349 int
 350 file_exists_p (name)
 351      register char *name;
 352 {
 353   char *dirend;
 354   char *dirname;
 355
 356 #ifndef NO_ARCHIVES
 357   if (ar_name (name))
 358     return ar_member_date (name) != (time_t) -1;
 359 #endif
 360
 361   dirend = rindex (name, '/');
 362   if (dirend == 0)
 363     return dir_file_exists_p (".", name);
 364
 365   dirname = (char *) alloca (dirend - name + 1);
 366   bcopy (name, dirname, dirend - name);
 367   dirname[dirend - name] = '\0';
 368   return dir_file_exists_p (dirname, dirend + 1);
 369 }
 370 \f
 371 /* Mark FILENAME as `impossible' for `file_impossible_p'.
 372    This means an attempt has been made to search for FILENAME
 373    as an intermediate file, and it has failed.  */
 374
 375 void
 376 file_impossible (filename)
 377      register char *filename;
 378 {
 379   char *dirend;
 380   register char *p = filename;
 381   register unsigned int hash;
 382   register struct directory *dir;
 383   register struct dirfile *new;
 384
 385   dirend = rindex (p, '/');
 386   if (dirend == 0)
 387     dir = find_directory (".");
 388   else
 389     {
 390       char *dirname = (char *) alloca (dirend - p + 1);
 391       bcopy (p, dirname, dirend - p);
 392       dirname[dirend - p] = '\0';
 393       dir = find_directory (dirname);
 394       filename = p = dirend + 1;
 395     }
 396
 397   for (hash = 0; *p != '\0'; ++p)
 398     HASH (hash, *p);
 399   hash %= DIRFILE_BUCKETS;
 400
 401   if (dir->contents == 0)
 402     {
 403       /* The directory could not be stat'd.  We allocate a contents
 404          structure for it, but leave it out of the contents hash table.  */
 405       dir->contents = (struct directory_contents *)
 406         xmalloc (sizeof (struct directory_contents));
 407       dir->contents->dev = dir->contents->ino = 0;
 408       dir->contents->files = 0;
 409       dir->contents->dirstream = 0;
 410     }
 411
 412   if (dir->contents->files == 0)
 413     {
 414       /* The directory was not opened; we must allocate the hash buckets.  */
 415       dir->contents->files = (struct dirfile **)
 416         xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS);
 417       bzero ((char *) dir->contents->files,
 418              sizeof (struct dirfile) * DIRFILE_BUCKETS);
 419     }
 420
 421   /* Make a new entry and put it in the table.  */
 422
 423   new = (struct dirfile *) xmalloc (sizeof (struct dirfile));
 424   new->next = dir->contents->files[hash];
 425   dir->contents->files[hash] = new;
 426   new->name = savestring (filename, strlen (filename));
 427   new->impossible = 1;
 428 }
 429 \f
 430 /* Return nonzero if FILENAME has been marked impossible.  */
 431
 432 int
 433 file_impossible_p (filename)
 434      char *filename;
 435 {
 436   char *dirend;
 437   register char *p = filename;
 438   register unsigned int hash;
 439   register struct directory_contents *dir;
 440   register struct dirfile *next;
 441
 442   dirend = rindex (filename, '/');
 443   if (dirend == 0)
 444     dir = find_directory (".")->contents;
 445   else
 446     {
 447       char *dirname = (char *) alloca (dirend - filename + 1);
 448       bcopy (p, dirname, dirend - p);
 449       dirname[dirend - p] = '\0';
 450       dir = find_directory (dirname)->contents;
 451       p = filename = dirend + 1;
 452     }
 453
 454   if (dir == 0 || dir->files == 0)
 455     /* There are no files entered for this directory.  */
 456     return 0;
 457
 458 #ifdef __MSDOS__
 459   p = filename = dosify (p);
 460 #endif
 461
 462   for (hash = 0; *p != '\0'; ++p)
 463     HASH (hash, *p);
 464   hash %= DIRFILE_BUCKETS;
 465
 466   for (next = dir->files[hash]; next != 0; next = next->next)
 467     if (streq (filename, next->name))
 468       return next->impossible;
 469
 470   return 0;
 471 }
 472 \f
 473 /* Return the already allocated name in the
 474    directory hash table that matches DIR.  */
 475
 476 char *
 477 dir_name (dir)
 478      char *dir;
 479 {
 480   return find_directory (dir)->name;
 481 }
 482 \f
 483 /* Print the data base of directories.  */
 484
 485 void
 486 print_dir_data_base ()
 487 {
 488   register unsigned int i, dirs, files, impossible;
 489   register struct directory *dir;
 490
 491   puts ("\n# Directories\n");
 492
 493   dirs = files = impossible = 0;
 494   for (i = 0; i < DIRECTORY_BUCKETS; ++i)
 495     for (dir = directories[i]; dir != 0; dir = dir->next)
 496       {
 497         ++dirs;
 498         if (dir->contents == 0)
 499           printf ("# %s: could not be stat'd.\n", dir->name);
 500         else if (dir->contents->files == 0)
 501           printf ("# %s (device %d, inode %d): could not be opened.\n",
 502                   dir->name, dir->contents->dev, dir->contents->ino);
 503         else
 504           {
 505             register unsigned int f = 0, im = 0;
 506             register unsigned int j;
 507             register struct dirfile *df;
 508             for (j = 0; j < DIRFILE_BUCKETS; ++j)
 509               for (df = dir->contents->files[j]; df != 0; df = df->next)
 510                 if (df->impossible)
 511                   ++im;
 512                 else
 513                   ++f;
 514             printf ("# %s (device %d, inode %d): ",
 515                     dir->name, dir->contents->dev, dir->contents->ino);
 516             if (f == 0)
 517               fputs ("No", stdout);
 518             else
 519               printf ("%u", f);
 520             fputs (" files, ", stdout);
 521             if (im == 0)
 522               fputs ("no", stdout);
 523             else
 524               printf ("%u", im);
 525             fputs (" impossibilities", stdout);
 526             if (dir->contents->dirstream == 0)
 527               puts (".");
 528             else
 529               puts (" so far.");
 530             files += f;
 531             impossible += im;
 532           }
 533       }
 534
 535   fputs ("\n# ", stdout);
 536   if (files == 0)
 537     fputs ("No", stdout);
 538   else
 539     printf ("%u", files);
 540   fputs (" files, ", stdout);
 541   if (impossible == 0)
 542     fputs ("no", stdout);
 543   else
 544     printf ("%u", impossible);
 545   printf (" impossibilities in %u directories.\n", dirs);
 546 }
 547 \f
 548 /* Hooks for globbing.  */
 549
 550 #include <glob.h>
 551
 552 /* Structure describing state of iterating through a directory hash table.  */
 553
 554 struct dirstream
 555   {
 556     struct directory_contents *contents; /* The directory being read.  */
 557
 558     unsigned int bucket;        /* Current hash bucket.  */
 559     struct dirfile *elt;        /* Current elt in bucket.  */
 560   };
 561
 562 /* Forward declarations.  */
 563 static __ptr_t open_dirstream __P ((const char *));
 564 static struct dirent *read_dirstream __P ((__ptr_t));
 565
 566 static __ptr_t
 567 open_dirstream (directory)
 568      const char *directory;
 569 {
 570   struct dirstream *new;
 571   struct directory *dir = find_directory (directory);
 572
 573   if (dir->contents == 0 || dir->contents->files == 0)
 574     /* DIR->contents is nil if the directory could not be stat'd.
 575        DIR->contents->files is nil if it could not be opened.  */
 576     return 0;
 577
 578   /* Read all the contents of the directory now.  There is no benefit
 579      in being lazy, since glob will want to see every file anyway.  */
 580
 581   (void) dir_contents_file_exists_p (dir->contents, (char *) 0);
 582
 583   new = (struct dirstream *) xmalloc (sizeof (struct dirstream));
 584   new->contents = dir->contents;
 585   new->bucket = 0;
 586   new->elt = new->contents->files[0];
 587
 588   return (__ptr_t) new;
 589 }
 590
 591 static struct dirent *
 592 read_dirstream (stream)
 593      __ptr_t stream;
 594 {
 595   struct dirstream *const ds = (struct dirstream *) stream;
 596   register struct dirfile *df;
 597   static char *buf;
 598   static unsigned int bufsz;
 599
 600   while (ds->bucket < DIRFILE_BUCKETS)
 601     {
 602       while ((df = ds->elt) != 0)
 603         {
 604           ds->elt = df->next;
 605           if (!df->impossible)
 606             {
 607               /* The glob interface wants a `struct dirent',
 608                  so mock one up.  */
 609               struct dirent *d;
 610               unsigned int len = strlen (df->name) + 1;
 611               if (sizeof *d - sizeof d->d_name + len > bufsz)
 612                 {
 613                   if (buf != 0)
 614                     free (buf);
 615                   bufsz *= 2;
 616                   if (sizeof *d - sizeof d->d_name + len > bufsz)
 617                     bufsz = sizeof *d - sizeof d->d_name + len;
 618                   buf = xmalloc (bufsz);
 619                 }
 620               d = (struct dirent *) buf;
 621               FAKE_DIR_ENTRY (d);
 622 #ifdef HAVE_D_NAMLEN
 623               d->d_namlen = len - 1;
 624 #endif
 625               memcpy (d->d_name, df->name, len);
 626               return d;
 627             }
 628         }
 629       if (++ds->bucket == DIRFILE_BUCKETS)
 630         break;
 631       ds->elt = ds->contents->files[ds->bucket];
 632     }
 633
 634   return 0;
 635 }
 636
 637 void
 638 dir_setup_glob (gl)
 639      glob_t *gl;
 640 {
 641   extern int lstat (), stat ();
 642
 643 #ifdef HAVE_LSTAT
 644 #define lstat stat
 645 #endif
 646   gl->gl_opendir = &open_dirstream;
 647   gl->gl_readdir = &read_dirstream;
 648   gl->gl_closedir = &free;
 649   gl->gl_lstat = &lstat;
 650   gl->gl_stat = &stat;
 651 }