dir.c

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