| /* Directory hashing for GNU Make. |
| Copyright (C) 1988, 1989, 1991 Free Software Foundation, Inc. |
| This file is part of GNU Make. |
| |
| GNU Make is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| GNU Make is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GNU Make; see the file COPYING. If not, write to |
| the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ |
| |
| #include "make.h" |
| |
| #if defined (USGr3) && !defined (DIRENT) |
| #define DIRENT |
| #endif /* USGr3 */ |
| #if defined (Xenix) && !defined (SYSNDIR) |
| #define SYSNDIR |
| #endif /* Xenix */ |
| |
| #if !defined(POSIX) && defined(__CYGWIN__) |
| #define POSIX |
| #endif |
| |
| #if defined (POSIX) || defined (DIRENT) || defined (__GNU_LIBRARY__) |
| #include <dirent.h> |
| #define direct dirent |
| #define D_NAMLEN(d) strlen((d)->d_name) |
| #else /* not POSIX or DIRENT */ |
| #define D_NAMLEN(d) ((d)->d_namlen) |
| #if defined (USG) && !defined (sgi) |
| #if defined (SYSNDIR) |
| #include <sys/ndir.h> |
| #else /* SYSNDIR */ |
| #include "ndir.h" |
| #endif /* not SYSNDIR */ |
| #else /* not USG */ |
| #include <sys/dir.h> |
| #endif /* USG */ |
| #endif /* POSIX or DIRENT or __GNU_LIBRARY__ */ |
| |
| #if defined (POSIX) && !defined (__GNU_LIBRARY__) |
| /* Posix does not require that the d_ino field be present, and some |
| systems do not provide it. */ |
| #define REAL_DIR_ENTRY(dp) 1 |
| #else |
| #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0) |
| #endif /* POSIX */ |
| |
| /* Hash table of directories. */ |
| |
| struct directory |
| { |
| struct directory *next; |
| char *name; /* Name of the directory. */ |
| struct dirfile **files; /* Files in this directory. */ |
| DIR *dirstream; /* Stream reading this directory. */ |
| }; |
| |
| #ifndef DIRECTORY_BUCKETS |
| #define DIRECTORY_BUCKETS 23 |
| #endif |
| |
| static struct directory *directories[DIRECTORY_BUCKETS]; |
| |
| |
| /* Never have more than this many directories open at once. */ |
| |
| #define MAX_OPEN_DIRECTORIES 10 |
| |
| static unsigned int open_directories = 0; |
| |
| |
| /* Hash table of files in each directory. */ |
| |
| struct dirfile |
| { |
| struct dirfile *next; |
| char *name; /* Name of the file. */ |
| char impossible; /* This file is impossible. */ |
| }; |
| |
| #ifndef DIRFILE_BUCKETS |
| #define DIRFILE_BUCKETS 1007 |
| #endif |
| |
| /* Find the directory named NAME and return its `struct directory'. */ |
| |
| static struct directory * |
| find_directory (name) |
| register char *name; |
| { |
| register unsigned int hash = 0; |
| register char *p; |
| register struct directory *dir; |
| |
| for (p = name; *p != '\0'; ++p) |
| HASH (hash, *p); |
| hash %= DIRECTORY_BUCKETS; |
| |
| for (dir = directories[hash]; dir != 0; dir = dir->next) |
| if (streq (dir->name, name)) |
| break; |
| |
| if (dir == 0) |
| { |
| /* The directory was not found. Create a new entry |
| for it and start its directory stream reading. */ |
| dir = (struct directory *) xmalloc (sizeof (struct directory)); |
| dir->next = directories[hash]; |
| directories[hash] = dir; |
| dir->name = savestring (name, p - name); |
| dir->dirstream = opendir (name); |
| if (dir->dirstream == 0) |
| /* Couldn't open the directory. Mark this by |
| setting the `files' member to a nil pointer. */ |
| dir->files = 0; |
| else |
| { |
| /* Allocate an array of hash buckets for files and zero it. */ |
| dir->files = (struct dirfile **) |
| xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS); |
| bzero ((char *) dir->files, |
| sizeof (struct dirfile) * DIRFILE_BUCKETS); |
| |
| /* Keep track of how many directories are open. */ |
| ++open_directories; |
| if (open_directories == MAX_OPEN_DIRECTORIES) |
| /* Read the entire directory and then close it. */ |
| (void) dir_file_exists_p (dir->name, (char *) 0); |
| } |
| } |
| |
| return dir; |
| } |
| |
| /* Return 1 if the name FILENAME in directory DIRNAME |
| is entered in the dir hash table. |
| FILENAME must contain no slashes. */ |
| |
| int |
| dir_file_exists_p (dirname, filename) |
| register char *dirname; |
| register char *filename; |
| { |
| register unsigned int hash; |
| register char *p; |
| register struct directory *dir; |
| register struct dirfile *df; |
| register struct direct *d; |
| dir = find_directory (dirname); |
| |
| if (dir->files == 0) |
| /* The directory could not be opened. */ |
| return 0; |
| |
| hash = 0; |
| if (filename != 0) |
| { |
| if (*filename == '\0') |
| /* Checking if the directory exists. */ |
| return 1; |
| |
| for (p = filename; *p != '\0'; ++p) |
| HASH (hash, *p); |
| hash %= DIRFILE_BUCKETS; |
| |
| /* Search the list of hashed files. */ |
| |
| for (df = dir->files[hash]; df != 0; df = df->next) |
| if (streq (df->name, filename)) |
| return !df->impossible; |
| } |
| |
| /* The file was not found in the hashed list. |
| Try to read the directory further. */ |
| |
| if (dir->dirstream == 0) |
| /* The directory has been all read in. */ |
| return 0; |
| |
| while ((d = readdir (dir->dirstream)) != 0) |
| { |
| /* Enter the file in the hash table. */ |
| register unsigned int newhash = 0; |
| register unsigned int i; |
| |
| if (!REAL_DIR_ENTRY (d)) |
| continue; |
| |
| for (i = 0; i < D_NAMLEN(d); ++i) |
| HASH (newhash, d->d_name[i]); |
| newhash %= DIRFILE_BUCKETS; |
| |
| df = (struct dirfile *) xmalloc (sizeof (struct dirfile)); |
| df->next = dir->files[newhash]; |
| dir->files[newhash] = df; |
| df->name = savestring (d->d_name, D_NAMLEN(d)); |
| df->impossible = 0; |
| |
| /* Check if the name matches the one we're searching for. */ |
| if (filename != 0 |
| && newhash == hash && streq (d->d_name, filename)) |
| return 1; |
| } |
| |
| /* If the directory has been completely read in, |
| close the stream and reset the pointer to nil. */ |
| if (d == 0) |
| { |
| --open_directories; |
| closedir (dir->dirstream); |
| dir->dirstream = 0; |
| } |
| |
| return 0; |
| } |
| |
| /* Return 1 if the file named NAME exists. */ |
| |
| int |
| file_exists_p (name) |
| register char *name; |
| { |
| char *dirend; |
| char *dirname; |
| |
| #ifndef NO_ARCHIVES |
| if (ar_name (name)) |
| return ar_member_date (name) != (time_t) -1; |
| #endif |
| |
| dirend = rindex (name, '/'); |
| if (dirend == 0) |
| return dir_file_exists_p (".", name); |
| |
| dirname = (char *) alloca (dirend - name + 1); |
| bcopy (name, dirname, dirend - name); |
| dirname[dirend - name] = '\0'; |
| return dir_file_exists_p (dirname, dirend + 1); |
| } |
| |
| /* Mark FILENAME as `impossible' for `file_impossible_p'. |
| This means an attempt has been made to search for FILENAME |
| as an intermediate file, and it has failed. */ |
| |
| void |
| file_impossible (filename) |
| register char *filename; |
| { |
| char *dirend; |
| register char *p = filename; |
| register unsigned int hash; |
| register struct directory *dir; |
| register struct dirfile *new; |
| |
| dirend = rindex (p, '/'); |
| if (dirend == 0) |
| dir = find_directory ("."); |
| else |
| { |
| char *dirname = (char *) alloca (dirend - p + 1); |
| bcopy (p, dirname, dirend - p); |
| dirname[dirend - p] = '\0'; |
| dir = find_directory (dirname); |
| filename = p = dirend + 1; |
| } |
| |
| for (hash = 0; *p != '\0'; ++p) |
| HASH (hash, *p); |
| hash %= DIRFILE_BUCKETS; |
| |
| if (dir->files == 0) |
| { |
| /* The directory was not opened; we must allocate the hash buckets. */ |
| dir->files = (struct dirfile **) |
| xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS); |
| bzero ((char *) dir->files, sizeof (struct dirfile) * DIRFILE_BUCKETS); |
| } |
| |
| /* Make a new entry and put it in the table. */ |
| |
| new = (struct dirfile *) xmalloc (sizeof (struct dirfile)); |
| new->next = dir->files[hash]; |
| dir->files[hash] = new; |
| new->name = savestring (filename, strlen (filename)); |
| new->impossible = 1; |
| } |
| |
| /* Return nonzero if FILENAME has been marked impossible. */ |
| |
| int |
| file_impossible_p (filename) |
| char *filename; |
| { |
| char *dirend; |
| register char *p = filename; |
| register unsigned int hash; |
| register struct directory *dir; |
| register struct dirfile *next; |
| |
| dirend = rindex (filename, '/'); |
| if (dirend == 0) |
| dir = find_directory ("."); |
| else |
| { |
| char *dirname = (char *) alloca (dirend - filename + 1); |
| bcopy (p, dirname, dirend - p); |
| dirname[dirend - p] = '\0'; |
| dir = find_directory (dirname); |
| p = dirend + 1; |
| } |
| |
| if (dir->files == 0) |
| /* There are no files entered for this directory. */ |
| return 0; |
| |
| for (hash = 0; *p != '\0'; ++p) |
| HASH (hash, *p); |
| hash %= DIRFILE_BUCKETS; |
| |
| for (next = dir->files[hash]; next != 0; next = next->next) |
| if (streq (filename, next->name)) |
| return next->impossible; |
| |
| return 0; |
| } |
| |
| /* Return the already allocated name in the |
| directory hash table that matches DIR. */ |
| |
| char * |
| dir_name (dir) |
| char *dir; |
| { |
| return find_directory (dir)->name; |
| } |
| |
| /* Print the data base of directories. */ |
| |
| void |
| print_dir_data_base () |
| { |
| register unsigned int i, dirs, files, impossible; |
| register struct directory *dir; |
| |
| puts ("\n# Directories\n"); |
| |
| dirs = files = impossible = 0; |
| for (i = 0; i < DIRECTORY_BUCKETS; ++i) |
| for (dir = directories[i]; dir != 0; dir = dir->next) |
| { |
| ++dirs; |
| if (dir->files == 0) |
| printf ("# %s: could not be opened.\n", dir->name); |
| else |
| { |
| register unsigned int f = 0, im = 0; |
| register unsigned int j; |
| register struct dirfile *df; |
| for (j = 0; j < DIRFILE_BUCKETS; ++j) |
| for (df = dir->files[j]; df != 0; df = df->next) |
| if (df->impossible) |
| ++im; |
| else |
| ++f; |
| printf ("# %s: ", dir->name); |
| if (f == 0) |
| fputs ("No", stdout); |
| else |
| printf ("%u", f); |
| fputs (" files, ", stdout); |
| if (im == 0) |
| fputs ("no", stdout); |
| else |
| printf ("%u", im); |
| fputs (" impossibilities", stdout); |
| if (dir->dirstream == 0) |
| puts ("."); |
| else |
| puts (" so far."); |
| files += f; |
| impossible += im; |
| } |
| } |
| |
| fputs ("\n# ", stdout); |
| if (files == 0) |
| fputs ("No", stdout); |
| else |
| printf ("%u", files); |
| fputs (" files, ", stdout); |
| if (impossible == 0) |
| fputs ("no", stdout); |
| else |
| printf ("%u", impossible); |
| printf (" impossibilities in %u directories.\n", dirs); |
| } |