dir.c

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