/* Directory hashing for GNU Make. Copyright (C) 1988, 1989, 1991, 1992, 1993, 1994 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 (POSIX) || defined (HAVE_DIRENT_H) || defined (__GNU_LIBRARY__) #include <dirent.h> #ifndef __GNU_LIBRARY__ #define D_NAMLEN(d) strlen((d)->d_name) #else /* GNU C library. */ #define D_NAMLEN(d) ((d)->d_namlen) #endif /* Not GNU C library. */ #else /* Not POSIX or HAVE_DIRENT_H. */ #define direct dirent #define D_NAMLEN(d) ((d)->d_namlen) #ifdef HAVE_SYS_NDIR_H #include <sys/ndir.h> #endif /* HAVE_SYS_NDIR_H */ #ifdef HAVE_SYS_DIR_H #include <sys/dir.h> #endif /* HAVE_SYS_DIR_H */ #ifdef HAVE_NDIR_H #include <ndir.h> #endif /* HAVE_NDIR_H */ #endif /* POSIX or HAVE_DIRENT_H 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 */ #ifdef __MSDOS__ #include <ctype.h> static char * dosify (filename) char *filename; { static char dos_filename[14]; char *df; int i; if (filename == 0) return 0; if (strpbrk (filename, "\"*+,;<=>?[\\]|") != 0) return filename; df = dos_filename; /* First, transform the name part. */ for (i = 0; *filename != '\0' && i < 8 && *filename != '.'; ++i) *df++ = tolower (*filename++); /* Now skip to the next dot. */ while (*filename != '\0' && *filename != '.') ++filename; if (*filename != '\0') { *df++ = *filename++; for (i = 0; *filename != '\0' && i < 3 && *filename != '.'; ++i) *df++ = tolower (*filename++); } /* Look for more dots. */ while (*filename != '\0' && *filename != '.') ++filename; if (*filename == '.') return filename; *df = 0; return dos_filename; } #endif /* Hash table of directories. */ #ifndef DIRECTORY_BUCKETS #define DIRECTORY_BUCKETS 199 #endif struct directory_contents { struct directory_contents *next; int dev, ino; /* Device and inode numbers of this dir. */ struct dirfile **files; /* Files in this directory. */ DIR *dirstream; /* Stream reading this directory. */ }; /* Table of directory contents hashed by device and inode number. */ static struct directory_contents *directories_contents[DIRECTORY_BUCKETS]; struct directory { struct directory *next; char *name; /* Name of the directory. */ /* The directory's contents. This data may be shared by several entries in the hash table, which refer to the same directory (identified uniquely by `dev' and `ino') under different names. */ struct directory_contents *contents; }; /* Table of directories hashed by name. */ 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 107 #endif static int dir_contents_file_exists_p (); /* 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) { struct stat st; /* The directory was not found. Create a new entry for it. */ dir = (struct directory *) xmalloc (sizeof (struct directory)); dir->next = directories[hash]; directories[hash] = dir; dir->name = savestring (name, p - name); /* The directory is not in the name hash table. Find its device and inode numbers, and look it up by them. */ if (safe_stat (name, &st) < 0) /* Couldn't stat the directory. Mark this by setting the `contents' member to a nil pointer. */ dir->contents = 0; else { /* Search the contents hash table; device and inode are the key. */ struct directory_contents *dc; hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ino; hash %= DIRECTORY_BUCKETS; for (dc = directories_contents[hash]; dc != 0; dc = dc->next) if (dc->dev == st.st_dev && dc->ino == st.st_ino) break; if (dc == 0) { /* Nope; this really is a directory we haven't seen before. */ dc = (struct directory_contents *) xmalloc (sizeof (struct directory_contents)); /* Enter it in the contents hash table. */ dc->dev = st.st_dev; dc->ino = st.st_ino; dc->next = directories_contents[hash]; directories_contents[hash] = dc; dc->dirstream = opendir (name); if (dc->dirstream == 0) /* Couldn't open the directory. Mark this by setting the `files' member to a nil pointer. */ dc->files = 0; else { /* Allocate an array of buckets for files and zero it. */ dc->files = (struct dirfile **) xmalloc (sizeof (struct dirfile *) * DIRFILE_BUCKETS); bzero ((char *) dc->files, sizeof (struct dirfile *) * DIRFILE_BUCKETS); /* Keep track of how many directories are open. */ ++open_directories; if (open_directories == MAX_OPEN_DIRECTORIES) /* We have too many directories open already. Read the entire directory and then close it. */ (void) dir_contents_file_exists_p (dc, (char *) 0); } } /* Point the name-hashed entry for DIR at its contents data. */ dir->contents = dc; } } return dir; } /* Return 1 if the name FILENAME is entered in DIR's hash table. FILENAME must contain no slashes. */ static int dir_contents_file_exists_p (dir, filename) register struct directory_contents *dir; register char *filename; { register unsigned int hash; register char *p; register struct dirfile *df; register struct dirent *d; if (dir == 0 || dir->files == 0) /* The directory could not be stat'd or opened. */ return 0; #ifdef __MSDOS__ filename = dosify (filename); #endif 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; unsigned int len; register unsigned int i; if (!REAL_DIR_ENTRY (d)) continue; len = D_NAMLEN (d); while (d->d_name[len - 1] == '\0') --len; for (i = 0; i < len; ++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, len); 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 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; { return dir_contents_file_exists_p (find_directory (dirname)->contents, filename); } /* 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->contents == 0) { /* The directory could not be stat'd. We allocate a contents structure for it, but leave it out of the contents hash table. */ dir->contents = (struct directory_contents *) xmalloc (sizeof (struct directory_contents)); dir->contents->dev = dir->contents->ino = 0; dir->contents->files = 0; dir->contents->dirstream = 0; } if (dir->contents->files == 0) { /* The directory was not opened; we must allocate the hash buckets. */ dir->contents->files = (struct dirfile **) xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS); bzero ((char *) dir->contents->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->contents->files[hash]; dir->contents->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_contents *dir; register struct dirfile *next; dirend = rindex (filename, '/'); if (dirend == 0) dir = find_directory (".")->contents; else { char *dirname = (char *) alloca (dirend - filename + 1); bcopy (p, dirname, dirend - p); dirname[dirend - p] = '\0'; dir = find_directory (dirname)->contents; p = dirend + 1; } if (dir == 0 || dir->files == 0) /* There are no files entered for this directory. */ return 0; #ifdef __MSDOS__ p = filename = dosify (p); #endif 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->contents == 0) printf ("# %s: could not be stat'd.\n", dir->name); else if (dir->contents->files == 0) printf ("# %s (device %d, inode %d): could not be opened.\n", dir->name, dir->contents->dev, dir->contents->ino); 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->contents->files[j]; df != 0; df = df->next) if (df->impossible) ++im; else ++f; printf ("# %s (device %d, inode %d): ", dir->name, dir->contents->dev, dir->contents->ino); 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->contents->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); } /* Hooks for globbing. */ #include <glob.h> /* Structure describing state of iterating through a directory hash table. */ struct dirstream { struct directory_contents *contents; /* The directory being read. */ unsigned int bucket; /* Current hash bucket. */ struct dirfile *elt; /* Current elt in bucket. */ }; /* Forward declarations. */ static __ptr_t open_dirstream __P ((const char *)); static const char *read_dirstream __P ((__ptr_t)); static __ptr_t open_dirstream (directory) const char *directory; { struct dirstream *new; struct directory *dir = find_directory (directory); if (dir->contents == 0 || dir->contents->files == 0) /* DIR->contents is nil if the directory could not be stat'd. DIR->contents->files is nil if it could not be opened. */ return 0; /* Read all the contents of the directory now. There is no benefit in being lazy, since glob will want to see every file anyway. */ (void) dir_contents_file_exists_p (dir->contents, (char *) 0); new = (struct dirstream *) xmalloc (sizeof (struct dirstream)); new->contents = dir->contents; new->bucket = 0; new->elt = new->contents->files[0]; return (__ptr_t) new; } static const char * read_dirstream (stream) __ptr_t stream; { struct dirstream *const ds = (struct dirstream *) stream; register struct dirfile *df; while (ds->bucket < DIRFILE_BUCKETS) { while ((df = ds->elt) != 0) { ds->elt = df->next; if (!df->impossible) return df->name; } if (++ds->bucket == DIRFILE_BUCKETS) break; ds->elt = ds->contents->files[ds->bucket]; } return 0; } void init_dir () { __glob_opendir_hook = open_dirstream; __glob_readdir_hook = read_dirstream; __glob_closedir_hook = (void (*) __P ((__ptr_t stream))) free; }