/* 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 (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); }