diff options
| -rw-r--r-- | ChangeLog | 117 | ||||
| -rw-r--r-- | Makefile.am | 4 | ||||
| -rw-r--r-- | ar.c | 12 | ||||
| -rw-r--r-- | dir.c | 585 | ||||
| -rw-r--r-- | expand.c | 2 | ||||
| -rw-r--r-- | file.c | 498 | ||||
| -rw-r--r-- | filedef.h | 12 | ||||
| -rw-r--r-- | function.c | 228 | ||||
| -rw-r--r-- | hash.c | 328 | ||||
| -rw-r--r-- | hash.h | 233 | ||||
| -rw-r--r-- | main.c | 27 | ||||
| -rw-r--r-- | make.h | 16 | ||||
| -rw-r--r-- | misc.c | 5 | ||||
| -rw-r--r-- | read.c | 190 | ||||
| -rw-r--r-- | remake.c | 3 | ||||
| -rw-r--r-- | tests/ChangeLog | 10 | ||||
| -rwxr-xr-x | tests/run_make_tests.pl | 34 | ||||
| -rw-r--r-- | tests/scripts/functions/filter-out | 43 | ||||
| -rw-r--r-- | tests/scripts/targets/INTERMEDIATE | 4 | ||||
| -rw-r--r-- | variable.c | 505 | ||||
| -rw-r--r-- | variable.h | 15 |
21 files changed, 1843 insertions, 1028 deletions
@@ -1,5 +1,122 @@ 2002-07-10 Paul D. Smith <psmith@gnu.org> + * variable.c (pop_variable_scope): Remove variable made unused by + new hash infrastructure. + * read.c (dep_hash_cmp): Rewrite this to handle ignore_mtime + comparisons as well as name comparisons. + * variable.h: Add a prototype for new hash_init_function_table(). + * file.c (lookup_file): Remove variables made unused by new hash + infrastructure. + * dir.c (directory_contents_hash_2): Missing return of hash value. + (dir_contents_file_exists_p): Remove variables made unused by new + hash infrastructure. + + + Installed Greg McGary's integration of the hash functions from the + GNU id-utils package: + +2002-07-10 Greg McGary <greg@mcgary.org> + + * scripts/functions/filter-out: Add literals to to the + pattern space in order to add complexity, and trigger + use of an internal hash table. Fix documentation strings. + * scripts/targets/INTERMEDIATE: Reverse order of files + passed to expected `rm' command. + +2002-07-10 Greg McGary <greg@mcgary.org> + + * Makefile.am (SRCS): Add hash.c (noinst_HEADERS): Add hash.h + * hash.c: New file, taken from id-utils. + * hash.h: New file, taken from id-utils. + + * make.h (HASH, HASHI): Remove macros. + (find_char_unquote): Change arglist in decl. + (hash_init_directories): New function decl. + * variable.h (hash.h): New #include. + (MAKELEVEL_NAME, MAKELEVEL_LENGTH): New constants. + * filedef.h (hash.h): New #include. + (struct file) [next]: Remove member. + (file_hash_enter): Remove function decl. + (init_hash_files): New function decl. + + * ar.c (ar_name): Delay call to strlen until needed. + * main.c (initialize_global_hash_tables): New function. + (main): Call it. Use MAKELEVEL_NAME & MAKELEVEL_LENGTH. + * misc.c (remove_comments): Pass char constants to find_char_unquote. + * remake.c (notice_finished_file): Update last_mtime on `prev' chain. + + * dir.c (hash.h): New #include. + (struct directory_contents) [next, files]: Remove members. + [ctime]: Add member for VMS. [dirfiles]: Add hash-table member. + (directory_contents_hash_1, directory_contents_hash_2, + directory_contents_hash_cmp): New functions. + (directories_contents): Change type to `struct hash_table'. + (struct directory) [next]: Remove member. + (directory_hash_1, directory_hash_2, directory_hash_cmp): New funcs. + (directory): Change type to `struct hash_table'. + (struct dirfile) [next]: Remove member. + [length]: Add member. [impossible]: widen type to fill alignment gap. + (dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp): New functions. + (find_directory): Use new hash table package. + (dir_contents_file_exists_p): Likewise. + (file_impossible): Likewise. + (file_impossible_p): Likewise. + (print_dir_data_base): Likewise. + (open_dirstream): Likewise. + (read_dirstream): Likewise. + (hash_init_directories): New function. + + * file.c (hash.h): New #include. + (file_hash_1, file_hash_2, file_hash_cmp): New functions. + (files): Change type to `struct hash_table'. + (lookup_file): Use new hash table package. + (enter_file): Likewise. + (remove_intermediates): Likewise. + (snap_deps): Likewise. + (print_file_data_base): Likewise. + + * function.c + (function_table_entry_hash_1, function_table_entry_hash_2, + function_table_entry_hash_cmp): New functions. + (lookup_function): Remove `table' argument. + Use new hash table package. + (struct a_word) [chain, length]: New members. + (a_word_hash_1, a_word_hash_2, a_word_hash_cmp): New functions. + (struct a_pattern): New struct. + (func_filter_filterout): Pass through patterns noting boundaries + and '%', if present. Note a_word length. Use a hash table if + arglists are large enough to justify cost. + (function_table_init): Renamed from function_table. + (function_table): Declare as `struct hash_table'. + (FUNCTION_TABLE_ENTRIES): New constant. + (hash_init_function_table): New function. + + * read.c (hash.h): New #include. + (read_makefile): Pass char constants to find_char_unquote. + (dep_hash_1, dep_hash_2, dep_hash_cmp): New functions. + (uniquize_deps): Use hash table to efficiently identify duplicates. + (find_char_unquote): Accept two char-constant stop chars, rather + than a string constant, avoiding zillions of calls to strchr. + Tighten inner search loops to test only for desired delimiters. + + * variable.c (variable_hash_1, variable_hash_2, + variable_hash_cmp): New functions. + (variable_table): Declare as `struct hash_table'. + (global_variable_set): Remove initialization. + (init_hash_global_variable_set): New function. + (define_variable_in_set): Use new hash table package. + (lookup_variable): Likewise. + (lookup_variable_in_set): Likewise. + (initialize_file_variables): Likewise. + (pop_variable_scope): Likewise. + (create_new_variable_set): Likewise. + (merge_variable_sets): Likewise. + (define_automatic_variables): Likewise. + (target_environment): Likewise. + (print_variable_set): Likewise. + +2002-07-10 Paul D. Smith <psmith@gnu.org> + Implement the SysV make syntax $$@, $$(@D), and $$(@F) in the prerequisite list. A real SysV make will expand the entire prerequisites list _twice_: we don't do that as it's a big diff --git a/Makefile.am b/Makefile.am index 5d70f42..2afb6b9 100644 --- a/Makefile.am +++ b/Makefile.am @@ -16,12 +16,12 @@ endif make_SOURCES = ar.c arscan.c commands.c default.c dir.c expand.c file.c \ function.c getopt.c getopt1.c implicit.c job.c main.c \ misc.c read.c remake.c $(remote) rule.c signame.c \ - variable.c version.c vpath.c + variable.c version.c vpath.c hash.c EXTRA_make_SOURCES = remote-stub.c remote-cstms.c noinst_HEADERS = commands.h dep.h filedef.h job.h make.h rule.h variable.h \ - debug.h getopt.h gettext.h + debug.h getopt.h gettext.h hash.h make_LDADD = @LIBOBJS@ @ALLOCA@ $(GLOBLIB) @GETLOADAVG_LIBS@ @LIBINTL@ @@ -1,5 +1,6 @@ /* Interface to `ar' archives for GNU Make. -Copyright (C) 1988,89,90,91,92,93,97 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1997, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -41,9 +42,14 @@ int ar_name (name) char *name; { - char *p = strchr (name, '('), *end = name + strlen (name) - 1; + char *p = strchr (name, '('); + char *end; + + if (p == 0 || p == name) + return 0; - if (p == 0 || p == name || *end != ')') + end = p + strlen (p) - 1; + if (*end != ')') return 0; if (p[1] == '(' && end[-1] == ')') @@ -1,5 +1,6 @@ /* Directory hashing for GNU Make. -Copyright (C) 1988,89,91,92,93,94,95,96,97 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -18,6 +19,7 @@ the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include "make.h" +#include "hash.h" #ifdef HAVE_DIRENT_H # include <dirent.h> @@ -217,8 +219,6 @@ vmsstat_dir (name, st) struct directory_contents { - struct directory_contents *next; - dev_t dev; /* Device and inode numbers of this dir. */ #ifdef WINDOWS32 /* @@ -230,6 +230,7 @@ struct directory_contents * way to emulate inode. */ char *path_key; + int ctime; int mtime; /* controls check for stale directory cache */ int fs_flags; /* FS_FAT, FS_NTFS, ... */ #define FS_FAT 0x1 @@ -242,17 +243,95 @@ struct directory_contents ino_t ino; #endif #endif /* WINDOWS32 */ - struct dirfile **files; /* Files in this directory. */ + struct hash_table dirfiles; /* Files in this directory. */ DIR *dirstream; /* Stream reading this directory. */ }; +static unsigned long +directory_contents_hash_1 (void const *key_0) +{ + struct directory_contents const *key = (struct directory_contents const *) key_0; + unsigned long hash; + +#ifdef WINDOWS32 + ISTRING_HASH_1 (key->path_key, hash); + hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) key->ctime; +#else +# ifdef VMS + hash = (((unsigned int) key->dev << 4) + ^ ((unsigned int) key->ino[0] + + (unsigned int) key->ino[1] + + (unsigned int) key->ino[2])); +# else + hash = ((unsigned int) key->dev << 4) ^ (unsigned int) key->ino; +# endif +#endif /* WINDOWS32 */ + return hash; +} + +static unsigned long +directory_contents_hash_2 (void const *key_0) +{ + struct directory_contents const *key = (struct directory_contents const *) key_0; + unsigned long hash; + +#ifdef WINDOWS32 + ISTRING_HASH_2 (key->path_key, hash); + hash ^= ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ctime; +#else +# ifdef VMS + hash = (((unsigned int) key->dev << 4) + ^ ~((unsigned int) key->ino[0] + + (unsigned int) key->ino[1] + + (unsigned int) key->ino[2])); +# else + hash = ((unsigned int) key->dev << 4) ^ (unsigned int) ~key->ino; +# endif +#endif /* WINDOWS32 */ + + return hash; +} + +static int +directory_contents_hash_cmp (void const *xv, void const *yv) +{ + struct directory_contents const *x = (struct directory_contents const *) xv; + struct directory_contents const *y = (struct directory_contents const *) yv; + int result; + +#ifdef WINDOWS32 + ISTRING_COMPARE (x->path_key, y->path_key, result); + if (result) + return result; + result = x->ctime - y->ctime; + if (result) + return result; +#else +# ifdef VMS + result = x->ino[0] - y->ino[0]; + if (result) + return result; + result = x->ino[1] - y->ino[1]; + if (result) + return result; + result = x->ino[2] - y->ino[2]; + if (result) + return result; +# else + result = x->ino - y->ino; + if (result) + return result; +# endif +#endif /* WINDOWS32 */ + + return x->dev - y->dev; +} + /* Table of directory contents hashed by device and inode number. */ -static struct directory_contents *directories_contents[DIRECTORY_BUCKETS]; +static struct hash_table directory_contents; struct directory { - struct directory *next; - char *name; /* Name of the directory. */ /* The directory's contents. This data may be shared by several @@ -261,9 +340,27 @@ struct directory struct directory_contents *contents; }; -/* Table of directories hashed by name. */ -static struct directory *directories[DIRECTORY_BUCKETS]; +static unsigned long +directory_hash_1 (void const *key) +{ + return_ISTRING_HASH_1 (((struct directory const *) key)->name); +} + +static unsigned long +directory_hash_2 (void const *key) +{ + return_ISTRING_HASH_2 (((struct directory const *) key)->name); +} + +static int +directory_hash_cmp (void const *x, void const *y) +{ + return_ISTRING_COMPARE (((struct directory const *) x)->name, + ((struct directory const *) y)->name); +} +/* Table of directories hashed by name. */ +static struct hash_table directories; /* Never have more than this many directories open at once. */ @@ -276,11 +373,34 @@ static unsigned int open_directories = 0; struct dirfile { - struct dirfile *next; char *name; /* Name of the file. */ - char impossible; /* This file is impossible. */ + short length; + short impossible; /* This file is impossible. */ }; +static unsigned long +dirfile_hash_1 (void const *key) +{ + return_ISTRING_HASH_1 (((struct dirfile const *) key)->name); +} + +static unsigned long +dirfile_hash_2 (void const *key) +{ + return_ISTRING_HASH_2 (((struct dirfile const *) key)->name); +} + +static int +dirfile_hash_cmp (void const *xv, void const *yv) +{ + struct dirfile const *x = ((struct dirfile const *) xv); + struct dirfile const *y = ((struct dirfile const *) yv); + int result = x->length - y->length; + if (result) + return result; + return_ISTRING_COMPARE (x->name, y->name); +} + #ifndef DIRFILE_BUCKETS #define DIRFILE_BUCKETS 107 #endif @@ -294,9 +414,10 @@ static struct directory * find_directory (name) register char *name; { - register unsigned int hash = 0; register char *p; register struct directory *dir; + register struct directory **dir_slot; + struct directory dir_key; int r; #ifdef WINDOWS32 char* w32_path; @@ -313,25 +434,20 @@ find_directory (name) name = vmsify (name,1); #endif - for (p = name; *p != '\0'; ++p) - HASHI (hash, *p); - hash %= DIRECTORY_BUCKETS; - - for (dir = directories[hash]; dir != 0; dir = dir->next) - if (strieq (dir->name, name)) - break; + dir_key.name = name; + dir_slot = (struct directory **) hash_find_slot (&directories, &dir_key); + dir = *dir_slot; - if (dir == 0) + if (HASH_VACANT (dir)) { struct stat st; /* The directory was not found. Create a new entry for it. */ + p = name + strlen (name); dir = (struct directory *) xmalloc (sizeof (struct directory)); - dir->next = directories[hash]; - directories[hash] = dir; dir->name = savestring (name, p - name); - + hash_insert_at (&directories, dir, dir_slot); /* The directory is not in the name hash table. Find its device and inode numbers, and look it up by them. */ @@ -366,39 +482,26 @@ find_directory (name) /* Search the contents hash table; device and inode are the key. */ struct directory_contents *dc; + struct directory_contents **dc_slot; + struct directory_contents dc_key; + dc_key.dev = st.st_dev; #ifdef WINDOWS32 - w32_path = w32ify(name, 1); - hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ctime; + dc_key.path_key = w32_path = w32ify (name, 1); + dc_key.ctime = st.st_ctime; #else # ifdef VMS - hash = (((unsigned int) st.st_dev << 16) - | ((unsigned int) st.st_ino[0] - + (unsigned int) st.st_ino[1] - + (unsigned int) st.st_ino[2])); + dc_key.ino[0] = st.st_ino[0]; + dc_key.ino[1] = st.st_ino[1]; + dc_key.ino[2] = st.st_ino[2]; # else - hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ino; + dc_key.ino = st.st_ino; # endif #endif - hash %= DIRECTORY_BUCKETS; - - for (dc = directories_contents[hash]; dc != 0; dc = dc->next) -#ifdef WINDOWS32 - if (strieq(dc->path_key, w32_path)) -#else - if (dc->dev == st.st_dev -# ifdef VMS - && dc->ino[0] == st.st_ino[0] - && dc->ino[1] == st.st_ino[1] - && dc->ino[2] == st.st_ino[2] -# else - && dc->ino == st.st_ino -# endif - ) -#endif /* WINDOWS32 */ - break; + dc_slot = (struct directory_contents **) hash_find_slot (&directory_contents, &dc_key); + dc = *dc_slot; - if (dc == 0) + if (HASH_VACANT (dc)) { /* Nope; this really is a directory we haven't seen before. */ @@ -408,7 +511,8 @@ find_directory (name) /* Enter it in the contents hash table. */ dc->dev = st.st_dev; #ifdef WINDOWS32 - dc->path_key = xstrdup(w32_path); + dc->path_key = xstrdup (w32_path); + dc->ctime = st.st_ctime; dc->mtime = st.st_mtime; /* @@ -437,22 +541,16 @@ find_directory (name) dc->ino = st.st_ino; # endif #endif /* WINDOWS32 */ - dc->next = directories_contents[hash]; - directories_contents[hash] = dc; - + hash_insert_at (&directory_contents, dc, dc_slot); 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; + hash_free (&dc->dirfiles, 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); - + hash_init (&dc->dirfiles, DIRFILE_BUCKETS, + dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp); /* Keep track of how many directories are open. */ ++open_directories; if (open_directories == MAX_OPEN_DIRECTORIES) @@ -478,16 +576,15 @@ 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; + unsigned int hash; + struct dirfile *df; + struct dirent *d; #ifdef WINDOWS32 struct stat st; int rehash = 0; #endif - if (dir == 0 || dir->files == 0) + if (dir == 0 || dir->dirfiles.ht_vec == 0) { /* The directory could not be stat'd or opened. */ return 0; @@ -507,24 +604,19 @@ dir_contents_file_exists_p (dir, filename) hash = 0; if (filename != 0) { + struct dirfile dirfile_key; + if (*filename == '\0') { - /* Checking if the directory exists. */ + /* 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) + dirfile_key.name = filename; + dirfile_key.length = strlen (filename); + df = (struct dirfile *) hash_find_item (&dir->dirfiles, &dirfile_key); + if (df) { - if (strieq (df->name, filename)) - { - return !df->impossible; - } + return !df->impossible; } } @@ -539,33 +631,34 @@ dir_contents_file_exists_p (dir, filename) * filesystems force a rehash always as mtime does not change * on directories (ugh!). */ - if (dir->path_key && - (dir->fs_flags & FS_FAT || - (stat(dir->path_key, &st) == 0 && - st.st_mtime > dir->mtime))) { - - /* reset date stamp to show most recent re-process */ - dir->mtime = st.st_mtime; - - /* make sure directory can still be opened */ - dir->dirstream = opendir(dir->path_key); - - if (dir->dirstream) - rehash = 1; - else - return 0; /* couldn't re-read - fail */ - } else + if (dir->path_key + && (dir->fs_flags & FS_FAT + || (stat(dir->path_key, &st) == 0 + && st.st_mtime > dir->mtime))) + { + /* reset date stamp to show most recent re-process */ + dir->mtime = st.st_mtime; + + /* make sure directory can still be opened */ + dir->dirstream = opendir(dir->path_key); + + if (dir->dirstream) + rehash = 1; + else + return 0; /* couldn't re-read - fail */ + } + else #endif - /* The directory has been all read in. */ - return 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; + struct dirfile dirfile_key; + struct dirfile **dirfile_slot; #if defined(VMS) && defined(HAVE_DIRENT_H) /* In VMS we get file versions too, which have to be stripped off */ @@ -579,39 +672,25 @@ dir_contents_file_exists_p (dir, filename) continue; len = NAMLEN (d); - for (i = 0; i < len; ++i) - HASHI (newhash, d->d_name[i]); - newhash %= DIRFILE_BUCKETS; + dirfile_key.name = d->d_name; + dirfile_key.length = len; + dirfile_slot = (struct dirfile **) hash_find_slot (&dir->dirfiles, &dirfile_key); #ifdef WINDOWS32 /* - * If re-reading a directory, check that this file isn't already - * in the cache. - */ - if (rehash) { - for (df = dir->files[newhash]; df != 0; df = df->next) - if (streq(df->name, d->d_name)) - break; - } else - df = 0; - - /* * If re-reading a directory, don't cache files that have * already been discovered. */ - if (!df) { -#endif - - 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; -#ifdef WINDOWS32 - } + if (! rehash || HASH_VACANT (*dirfile_slot)) #endif + { + df = (struct dirfile *) xmalloc (sizeof (struct dirfile)); + df->name = savestring (d->d_name, len); + df->length = len; + df->impossible = 0; + hash_insert_at (&dir->dirfiles, df, dirfile_slot); + } /* Check if the name matches the one we're searching for. */ - if (filename != 0 - && newhash == hash && strieq (d->d_name, filename)) + if (filename != 0 && strieq (d->d_name, filename)) { return 1; } @@ -712,7 +791,6 @@ file_impossible (filename) { char *dirend; register char *p = filename; - register unsigned int hash; register struct directory *dir; register struct dirfile *new; @@ -765,48 +843,28 @@ file_impossible (filename) filename = p = slash + 1; } - for (hash = 0; *p != '\0'; ++p) - HASHI (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)); -#ifdef WINDOWS32 - dir->contents->path_key = NULL; - dir->contents->mtime = 0; -#else /* WINDOWS32 */ -#ifdef VMS - dir->contents->dev = 0; - dir->contents->ino[0] = dir->contents->ino[1] = - dir->contents->ino[2] = 0; -#else - dir->contents->dev = dir->contents->ino = 0; -#endif -#endif /* WINDOWS32 */ - dir->contents->files = 0; - dir->contents->dirstream = 0; + bzero ((char *) dir->contents, sizeof (struct directory_contents)); } - if (dir->contents->files == 0) + if (dir->contents->dirfiles.ht_vec == 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); + hash_init (&dir->contents->dirfiles, DIRFILE_BUCKETS, + dirfile_hash_1, dirfile_hash_2, dirfile_hash_cmp); } /* 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 = xstrdup (filename); + new->length = strlen (filename); new->impossible = 1; + hash_insert (&dir->contents->dirfiles, new); } /* Return nonzero if FILENAME has been marked impossible. */ @@ -817,9 +875,9 @@ file_impossible_p (filename) { char *dirend; register char *p = filename; - register unsigned int hash; register struct directory_contents *dir; - register struct dirfile *next; + register struct dirfile *dirfile; + struct dirfile dirfile_key; #ifdef VMS dirend = strrchr (filename, ']'); @@ -867,27 +925,25 @@ file_impossible_p (filename) p = filename = slash + 1; } - if (dir == 0 || dir->files == 0) + if (dir == 0 || dir->dirfiles.ht_vec == 0) /* There are no files entered for this directory. */ return 0; #ifdef __MSDOS__ - p = filename = dosify (p); + filename = dosify (p); #endif #ifdef HAVE_CASE_INSENSITIVE_FS - p = filename = downcase (p); + filename = downcase (p); #endif #ifdef VMS - p = filename = vmsify (p, 1); + filename = vmsify (p, 1); #endif - for (hash = 0; *p != '\0'; ++p) - HASH (hash, *p); - hash %= DIRFILE_BUCKETS; - - for (next = dir->files[hash]; next != 0; next = next->next) - if (strieq (filename, next->name)) - return next->impossible; + dirfile_key.name = filename; + dirfile_key.length = strlen (filename); + dirfile = (struct dirfile *) hash_find_item (&dir->dirfiles, &dirfile_key); + if (dirfile) + return dirfile->impossible; return 0; } @@ -907,78 +963,96 @@ dir_name (dir) void print_dir_data_base () { - register unsigned int i, dirs, files, impossible; - register struct directory *dir; + register unsigned int files; + register unsigned int impossible; + register struct directory **dir_slot; + register struct directory **dir_end; 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) + files = impossible = 0; + + dir_slot = (struct directory **) directories.ht_vec; + dir_end = dir_slot + directories.ht_size; + for ( ; dir_slot < dir_end; dir_slot++) + { + register struct directory *dir = *dir_slot; + if (! HASH_VACANT (dir)) + { + if (dir->contents == 0) + printf (_("# %s: could not be stat'd.\n"), dir->name); + else if (dir->contents->dirfiles.ht_vec == 0) + { #ifdef WINDOWS32 - printf (_("# %s (key %s, mtime %d): could not be opened.\n"), - dir->name, dir->contents->path_key,dir->contents->mtime); + printf (_("# %s (key %s, mtime %d): could not be opened.\n"), + dir->name, dir->contents->path_key,dir->contents->mtime); #else /* WINDOWS32 */ #ifdef VMS - printf (_("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n"), - dir->name, dir->contents->dev, - dir->contents->ino[0], dir->contents->ino[1], - dir->contents->ino[2]); + printf (_("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n"), + dir->name, dir->contents->dev, + dir->contents->ino[0], dir->contents->ino[1], + dir->contents->ino[2]); #else - printf (_("# %s (device %ld, inode %ld): could not be opened.\n"), - dir->name, (long int) dir->contents->dev, - (long int) dir->contents->ino); + printf (_("# %s (device %ld, inode %ld): could not be opened.\n"), + dir->name, (long int) dir->contents->dev, + (long int) dir->contents->ino); #endif #endif /* WINDOWS32 */ - 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; + } + else + { + register unsigned int f = 0; + register unsigned int im = 0; + register struct dirfile **files_slot; + register struct dirfile **files_end; + + files_slot = (struct dirfile **) dir->contents->dirfiles.ht_vec; + files_end = files_slot + dir->contents->dirfiles.ht_size; + for ( ; files_slot < files_end; files_slot++) + { + register struct dirfile *df = *files_slot; + if (! HASH_VACANT (df)) + { + if (df->impossible) + ++im; + else + ++f; + } + } #ifdef WINDOWS32 - printf (_("# %s (key %s, mtime %d): "), - dir->name, dir->contents->path_key, dir->contents->mtime); + printf (_("# %s (key %s, mtime %d): "), + dir->name, dir->contents->path_key, dir->contents->mtime); #else /* WINDOWS32 */ #ifdef VMS - printf (_("# %s (device %d, inode [%d,%d,%d]): "), - dir->name, dir->contents->dev, - dir->contents->ino[0], dir->contents->ino[1], - dir->contents->ino[2]); + printf (_("# %s (device %d, inode [%d,%d,%d]): "), + dir->name, dir->contents->dev, + dir->contents->ino[0], dir->contents->ino[1], + dir->contents->ino[2]); #else - printf (_("# %s (device %ld, inode %ld): "), - dir->name, - (long)dir->contents->dev, (long)dir->contents->ino); + printf (_("# %s (device %ld, inode %ld): "), + dir->name, + (long)dir->contents->dev, (long)dir->contents->ino); #endif #endif /* WINDOWS32 */ - 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; - } - } + 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) @@ -990,7 +1064,7 @@ print_dir_data_base () fputs (_("no"), stdout); else printf ("%u", impossible); - printf (_(" impossibilities in %u directories.\n"), dirs); + printf (_(" impossibilities in %lu directories.\n"), directories.ht_fill); } /* Hooks for globbing. */ @@ -1002,9 +1076,7 @@ print_dir_data_base () struct dirstream { struct directory_contents *contents; /* The directory being read. */ - - unsigned int bucket; /* Current hash bucket. */ - struct dirfile *elt; /* Current elt in bucket. */ + struct dirfile **dirfile_slot; /* Current slot in table. */ }; /* Forward declarations. */ @@ -1018,9 +1090,9 @@ open_dirstream (directory) struct dirstream *new; struct directory *dir = find_directory ((char *)directory); - if (dir->contents == 0 || dir->contents->files == 0) + if (dir->contents == 0 || dir->contents->dirfiles.ht_vec == 0) /* DIR->contents is nil if the directory could not be stat'd. - DIR->contents->files is nil if it could not be opened. */ + DIR->contents->dirfiles is nil if it could not be opened. */ return 0; /* Read all the contents of the directory now. There is no benefit @@ -1030,8 +1102,7 @@ open_dirstream (directory) new = (struct dirstream *) xmalloc (sizeof (struct dirstream)); new->contents = dir->contents; - new->bucket = 0; - new->elt = new->contents->files[0]; + new->dirfile_slot = (struct dirfile **) new->contents->dirfiles.ht_vec; return (__ptr_t) new; } @@ -1041,45 +1112,40 @@ read_dirstream (stream) __ptr_t stream; { struct dirstream *const ds = (struct dirstream *) stream; - register struct dirfile *df; + struct directory_contents *dc = ds->contents; + struct dirfile **dirfile_end = (struct dirfile **) dc->dirfiles.ht_vec + dc->dirfiles.ht_size; static char *buf; static unsigned int bufsz; - while (ds->bucket < DIRFILE_BUCKETS) + while (ds->dirfile_slot < dirfile_end) { - while ((df = ds->elt) != 0) + register struct dirfile *df = *ds->dirfile_slot++; + if (! HASH_VACANT (df) && !df->impossible) { - ds->elt = df->next; - if (!df->impossible) + /* The glob interface wants a `struct dirent', + so mock one up. */ + struct dirent *d; + unsigned int len = df->length + 1; + if (sizeof *d - sizeof d->d_name + len > bufsz) { - /* The glob interface wants a `struct dirent', - so mock one up. */ - struct dirent *d; - unsigned int len = strlen (df->name) + 1; + if (buf != 0) + free (buf); + bufsz *= 2; if (sizeof *d - sizeof d->d_name + len > bufsz) - { - if (buf != 0) - free (buf); - bufsz *= 2; - if (sizeof *d - sizeof d->d_name + len > bufsz) - bufsz = sizeof *d - sizeof d->d_name + len; - buf = xmalloc (bufsz); - } - d = (struct dirent *) buf; - FAKE_DIR_ENTRY (d); + bufsz = sizeof *d - sizeof d->d_name + len; + buf = xmalloc (bufsz); + } + d = (struct dirent *) buf; + FAKE_DIR_ENTRY (d); #ifdef _DIRENT_HAVE_D_NAMLEN - d->d_namlen = len - 1; + d->d_namlen = len - 1; #endif #ifdef _DIRENT_HAVE_D_TYPE - d->d_type = DT_UNKNOWN; + d->d_type = DT_UNKNOWN; #endif - memcpy (d->d_name, df->name, len); - return d; - } + memcpy (d->d_name, df->name, len); + return d; } - if (++ds->bucket == DIRFILE_BUCKETS) - break; - ds->elt = ds->contents->files[ds->bucket]; } return 0; @@ -1123,3 +1189,12 @@ dir_setup_glob (gl) /* We don't bother setting gl_lstat, since glob never calls it. The slot is only there for compatibility with 4.4 BSD. */ } + +void +hash_init_directories () +{ + hash_init (&directories, DIRECTORY_BUCKETS, + directory_hash_1, directory_hash_2, directory_hash_cmp); + hash_init (&directory_contents, DIRECTORY_BUCKETS, + directory_contents_hash_1, directory_contents_hash_2, directory_contents_hash_cmp); +} @@ -100,7 +100,7 @@ recursively_expand_for_file (v, file) struct file *file; { char *value; - struct variable_set_list *save; + struct variable_set_list *save = 0; if (v->expanding) { @@ -1,5 +1,6 @@ /* Target file hash table management for GNU Make. -Copyright (C) 1988,89,90,91,92,93,94,95,96,97 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -27,14 +28,34 @@ Boston, MA 02111-1307, USA. */ #include "commands.h" #include "variable.h" #include "debug.h" +#include "hash.h" /* Hash table of files the makefile knows how to make. */ +static unsigned long +file_hash_1 (void const *key) +{ + return_ISTRING_HASH_1 (((struct file const *) key)->hname); +} + +static unsigned long +file_hash_2 (void const *key) +{ + return_ISTRING_HASH_2 (((struct file const *) key)->hname); +} + +static int +file_hash_cmp (void const *x, void const *y) +{ + return_ISTRING_COMPARE (((struct file const *) x)->hname, + ((struct file const *) y)->hname); +} + #ifndef FILE_BUCKETS #define FILE_BUCKETS 1007 #endif -static struct file *files[FILE_BUCKETS]; +static struct hash_table files; /* Whether or not .SECONDARY with no prerequisites was given. */ static int all_secondary = 0; @@ -49,8 +70,7 @@ lookup_file (name) char *name; { register struct file *f; - register char *n; - register unsigned int hashval; + struct file file_key; #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS) register char *lname, *ln; #endif @@ -62,11 +82,14 @@ lookup_file (name) on the command line. */ #ifdef VMS # ifndef WANT_CASE_SENSITIVE_TARGETS - lname = (char *)malloc(strlen(name) + 1); - for (n=name, ln=lname; *n != '\0'; ++n, ++ln) - *ln = isupper((unsigned char)*n) ? tolower((unsigned char)*n) : *n; - *ln = '\0'; - name = lname; + { + register char *n; + lname = (char *) malloc (strlen (name) + 1); + for (n = name, ln = lname; *n != '\0'; ++n, ++ln) + *ln = isupper ((unsigned char)*n) ? tolower ((unsigned char)*n) : *n; + *ln = '\0'; + name = lname; + } # endif while (name[0] == '[' && name[1] == ']' && name[2] != '\0') @@ -92,34 +115,22 @@ lookup_file (name) #endif /* AMIGA */ #endif /* VMS */ - hashval = 0; - for (n = name; *n != '\0'; ++n) - HASHI (hashval, *n); - hashval %= FILE_BUCKETS; - - for (f = files[hashval]; f != 0; f = f->next) - { - if (strieq (f->hname, name)) - { -#if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS) - free (lname); -#endif - return f; - } - } + file_key.hname = name; + f = (struct file *) hash_find_item (&files, &file_key); #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS) free (lname); #endif - return 0; + return f; } struct file * enter_file (name) char *name; { - register struct file *f, *new; - register char *n; - register unsigned int hashval; + register struct file *f; + register struct file *new; + register struct file **file_slot; + struct file file_key; #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS) char *lname, *ln; #endif @@ -127,30 +138,28 @@ enter_file (name) assert (*name != '\0'); #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS) - lname = (char *)malloc (strlen (name) + 1); - for (n = name, ln = lname; *n != '\0'; ++n, ++ln) - { - if (isupper((unsigned char)*n)) - *ln = tolower((unsigned char)*n); - else - *ln = *n; - } - *ln = 0; - /* Creates a possible leak, old value of name is unreachable, but I - currently don't know how to fix it. */ - name = lname; -#endif - - hashval = 0; - for (n = name; *n != '\0'; ++n) - HASHI (hashval, *n); - hashval %= FILE_BUCKETS; + { + register char *n; + lname = (char *) malloc (strlen (name) + 1); + for (n = name, ln = lname; *n != '\0'; ++n, ++ln) + { + if (isupper ((unsigned char)*n)) + *ln = tolower ((unsigned char)*n); + else + *ln = *n; + } - for (f = files[hashval]; f != 0; f = f->next) - if (strieq (f->hname, name)) - break; + *ln = 0; + /* Creates a possible leak, old value of name is unreachable, but I + currently don't know how to fix it. */ + name = lname; + } +#endif - if (f != 0 && !f->double_colon) + file_key.hname = name; + file_slot = (struct file **) hash_find_slot (&files, &file_key); + f = *file_slot; + if (! HASH_VACANT (f) && !f->double_colon) { #if defined(VMS) && !defined(WANT_CASE_SENSITIVE_TARGETS) free(lname); @@ -163,12 +172,8 @@ enter_file (name) new->name = new->hname = name; new->update_status = -1; - if (f == 0) - { - /* This is a completely new file. */ - new->next = files[hashval]; - files[hashval] = new; - } + if (HASH_VACANT (f)) + hash_insert_at (&files, new, file_slot); else { /* There is already a double-colon entry for this file. */ @@ -181,179 +186,129 @@ enter_file (name) return new; } -/* Rehash FILE to NAME. This is not as simple as resetting - the `hname' member, since it must be put in a new hash bucket, - and possibly merged with an existing file called NAME. */ - -void -rehash_file (file, name) - register struct file *file; - char *name; -{ - char *oldname = file->hname; - register unsigned int oldhash; - register char *n; - - while (file->renamed != 0) - file = file->renamed; - - /* Find the hash values of the old and new names. */ - - oldhash = 0; - for (n = oldname; *n != '\0'; ++n) - HASHI (oldhash, *n); - - file_hash_enter (file, name, oldhash, file->name); -} - /* Rename FILE to NAME. This is not as simple as resetting the `name' member, since it must be put in a new hash bucket, and possibly merged with an existing file called NAME. */ void -rename_file (file, name) - register struct file *file; - char *name; +rename_file (from_file, to_hname) + register struct file *from_file; + char *to_hname; { - rehash_file(file, name); - while (file) + rehash_file (from_file, to_hname); + while (from_file) { - file->name = file->hname; - file = file->prev; + from_file->name = from_file->hname; + from_file = from_file->prev; } } +/* Rehash FILE to NAME. This is not as simple as resetting + the `hname' member, since it must be put in a new hash bucket, + and possibly merged with an existing file called NAME. */ + void -file_hash_enter (file, name, oldhash, oldname) - register struct file *file; - char *name; - unsigned int oldhash; - char *oldname; +rehash_file (from_file, to_hname) + register struct file *from_file; + char *to_hname; { - unsigned int oldbucket = oldhash % FILE_BUCKETS; - register unsigned int newhash, newbucket; - struct file *oldfile; - register char *n; - register struct file *f; - - newhash = 0; - for (n = name; *n != '\0'; ++n) - HASHI (newhash, *n); - newbucket = newhash % FILE_BUCKETS; - - /* Look for an existing file under the new name. */ - - for (oldfile = files[newbucket]; oldfile != 0; oldfile = oldfile->next) - if (strieq (oldfile->hname, name)) - break; - - /* If the old file is the same as the new file, never mind. */ - if (oldfile == file) + struct file file_key; + struct file **file_slot; + struct file *to_file; + struct file *deleted_file; + struct file *f; + + file_key.hname = to_hname; + if (0 == file_hash_cmp (from_file, &file_key)) return; - if (oldhash != 0 && (newbucket != oldbucket || oldfile != 0)) - { - /* Remove FILE from its hash bucket. */ - - struct file *lastf = 0; + file_key.hname = from_file->hname; + while (from_file->renamed != 0) + from_file = from_file->renamed; + if (file_hash_cmp (from_file, &file_key)) + /* hname changed unexpectedly */ + abort (); - for (f = files[oldbucket]; f != file; f = f->next) - lastf = f; - - if (lastf == 0) - files[oldbucket] = f->next; - else - lastf->next = f->next; - } + deleted_file = hash_delete (&files, from_file); + if (deleted_file != from_file) + /* from_file isn't the one stored in files */ + abort (); - /* Give FILE its new name. */ + file_key.hname = to_hname; + file_slot = (struct file **) hash_find_slot (&files, &file_key); + to_file = *file_slot; - file->hname = name; - for (f = file->double_colon; f != 0; f = f->prev) - f->hname = name; + from_file->hname = to_hname; + for (f = from_file->double_colon; f != 0; f = f->prev) + f->hname = to_hname; - if (oldfile == 0) - { - /* There is no existing file with the new name. */ - - if (newbucket != oldbucket) - { - /* Put FILE in its new hash bucket. */ - file->next = files[newbucket]; - files[newbucket] = file; - } - } + if (HASH_VACANT (to_file)) + hash_insert_at (&files, from_file, file_slot); else { - /* There is an existing file with the new name. - We must merge FILE into the existing file. */ - - register struct dep *d; + /* TO_FILE already exists under TO_HNAME. + We must retain TO_FILE and merge FROM_FILE into it. */ - if (file->cmds != 0) + if (from_file->cmds != 0) { - if (oldfile->cmds == 0) - oldfile->cmds = file->cmds; - else if (file->cmds != oldfile->cmds) + if (to_file->cmds == 0) + to_file->cmds = from_file->cmds; + else if (from_file->cmds != to_file->cmds) { /* We have two sets of commands. We will go with the one given in the rule explicitly mentioning this name, but give a message to let the user know what's going on. */ - if (oldfile->cmds->fileinfo.filenm != 0) - error (&file->cmds->fileinfo, - _("Commands were specified for \ -file `%s' at %s:%lu,"), - oldname, oldfile->cmds->fileinfo.filenm, - oldfile->cmds->fileinfo.lineno); + if (to_file->cmds->fileinfo.filenm != 0) + error (&from_file->cmds->fileinfo, + _("Commands were specified for file `%s' at %s:%lu,"), + from_file->name, to_file->cmds->fileinfo.filenm, + to_file->cmds->fileinfo.lineno); else - error (&file->cmds->fileinfo, - _("Commands for file `%s' were found by \ -implicit rule search,"), - oldname); - error (&file->cmds->fileinfo, - _("but `%s' is now considered the same file \ -as `%s'."), - oldname, name); - error (&file->cmds->fileinfo, - _("Commands for `%s' will be ignored \ -in favor of those for `%s'."), - name, oldname); + error (&from_file->cmds->fileinfo, + _("Commands for file `%s' were found by implicit rule search,"), + from_file->name); + error (&from_file->cmds->fileinfo, + _("but `%s' is now considered the same file as `%s'."), + from_file->name, to_hname); + error (&from_file->cmds->fileinfo, + _("Commands for `%s' will be ignored in favor of those for `%s'."), + to_hname, from_file->name); } } /* Merge the dependencies of the two files. */ - d = oldfile->deps; - if (d == 0) - oldfile->deps = file->deps; + if (to_file->deps == 0) + to_file->deps = from_file->deps; else { - while (d->next != 0) - d = d->next; - d->next = file->deps; + register struct dep *deps = to_file->deps; + while (deps->next != 0) + deps = deps->next; + deps->next = from_file->deps; } - merge_variable_set_lists (&oldfile->variables, file->variables); + merge_variable_set_lists (&to_file->variables, from_file->variables); - if (oldfile->double_colon && file->is_target && !file->double_colon) + if (to_file->double_colon && from_file->is_target && !from_file->double_colon) fatal (NILF, _("can't rename single-colon `%s' to double-colon `%s'"), - oldname, name); - if (!oldfile->double_colon && file->double_colon) + from_file->name, to_hname); + if (!to_file->double_colon && from_file->double_colon) { - if (oldfile->is_target) + if (to_file->is_target) fatal (NILF, _("can't rename double-colon `%s' to single-colon `%s'"), - oldname, name); + from_file->name, to_hname); else - oldfile->double_colon = file->double_colon; + to_file->double_colon = from_file->double_colon; } - if (file->last_mtime > oldfile->last_mtime) + if (from_file->last_mtime > to_file->last_mtime) /* %%% Kludge so -W wins on a file that gets vpathized. */ - oldfile->last_mtime = file->last_mtime; + to_file->last_mtime = from_file->last_mtime; - oldfile->mtime_before_update = file->mtime_before_update; + to_file->mtime_before_update = from_file->mtime_before_update; -#define MERGE(field) oldfile->field |= file->field +#define MERGE(field) to_file->field |= from_file->field MERGE (precious); MERGE (tried_implicit); MERGE (updating); @@ -364,7 +319,7 @@ in favor of those for `%s'."), MERGE (ignore_vpath); #undef MERGE - file->renamed = oldfile; + from_file->renamed = to_file; } } @@ -377,9 +332,9 @@ void remove_intermediates (sig) int sig; { - register int i; - register struct file *f; - char doneany; + register struct file **file_slot; + register struct file **file_end; + int doneany = 0; /* If there's no way we will ever remove anything anyway, punt early. */ if (question_flag || touch_flag || all_secondary) @@ -388,50 +343,54 @@ remove_intermediates (sig) if (sig && just_print_flag) return; - doneany = 0; - for (i = 0; i < FILE_BUCKETS; ++i) - for (f = files[i]; f != 0; f = f->next) - if (f->intermediate && (f->dontcare || !f->precious) - && !f->secondary && !f->cmd_target) - { - int status; - if (f->update_status == -1) - /* If nothing would have created this file yet, - don't print an "rm" command for it. */ - continue; - if (just_print_flag) - status = 0; - else - { - status = unlink (f->name); - if (status < 0 && errno == ENOENT) - continue; - } - if (!f->dontcare) - { - if (sig) - error (NILF, _("*** Deleting intermediate file `%s'"), f->name); - else - { - if (! doneany) - DB (DB_BASIC, (_("Removing intermediate files...\n"))); - if (!silent_flag) - { - if (! doneany) - { - fputs ("rm ", stdout); - doneany = 1; - } - else - putchar (' '); - fputs (f->name, stdout); - fflush (stdout); - } - } - if (status < 0) - perror_with_name ("unlink: ", f->name); - } - } + file_slot = (struct file **) files.ht_vec; + file_end = file_slot + files.ht_size; + for ( ; file_slot < file_end; file_slot++) + if (! HASH_VACANT (*file_slot)) + { + register struct file *f = *file_slot; + if (f->intermediate && (f->dontcare || !f->precious) + && !f->secondary && !f->cmd_target) + { + int status; + if (f->update_status == -1) + /* If nothing would have created this file yet, + don't print an "rm" command for it. */ + continue; + if (just_print_flag) + status = 0; + else + { + status = unlink (f->name); + if (status < 0 && errno == ENOENT) + continue; + } + if (!f->dontcare) + { + if (sig) + error (NILF, _("*** Deleting intermediate file `%s'"), f->name); + else + { + if (! doneany) + DB (DB_BASIC, (_("Removing intermediate files...\n"))); + if (!silent_flag) + { + if (! doneany) + { + fputs ("rm ", stdout); + doneany = 1; + } + else + putchar (' '); + fputs (f->name, stdout); + fflush (stdout); + } + } + if (status < 0) + perror_with_name ("unlink: ", f->name); + } + } + } if (doneany && !sig) { @@ -449,24 +408,32 @@ remove_intermediates (sig) void snap_deps () { - register struct file *f, *f2; + register struct file *f; + register struct file *f2; register struct dep *d; - register int i; + register struct file **file_slot_0; + register struct file **file_slot; + register struct file **file_end; /* Enter each dependency name as a file. */ - for (i = 0; i < FILE_BUCKETS; ++i) - for (f = files[i]; f != 0; f = f->next) - for (f2 = f; f2 != 0; f2 = f2->prev) - for (d = f2->deps; d != 0; d = d->next) - if (d->name != 0) - { - d->file = lookup_file (d->name); - if (d->file == 0) - d->file = enter_file (d->name); - else - free (d->name); - d->name = 0; - } + /* We must use hash_dump (), because within this loop + we might add new files to the table, possibly causing + an in-situ table expansion. */ + file_slot_0 = (struct file **) hash_dump (&files, 0, 0); + file_end = file_slot_0 + files.ht_fill; + for (file_slot = file_slot_0; file_slot < file_end; file_slot++) + for (f2 = *file_slot; f2 != 0; f2 = f2->prev) + for (d = f2->deps; d != 0; d = d->next) + if (d->name != 0) + { + d->file = lookup_file (d->name); + if (d->file == 0) + d->file = enter_file (d->name); + else + free (d->name); + d->name = 0; + } + free (file_slot_0); for (f = lookup_file (".PRECIOUS"); f != 0; f = f->prev) for (d = f->deps; d != 0; d = d->next) @@ -790,41 +757,18 @@ print_file (f) void print_file_data_base () { - register unsigned int i, nfiles, per_bucket; - register struct file *file; - puts (_("\n# Files")); - per_bucket = nfiles = 0; - for (i = 0; i < FILE_BUCKETS; ++i) - { - register unsigned int this_bucket = 0; - - for (file = files[i]; file != 0; file = file->next) - { - register struct file *f; - - ++this_bucket; - - for (f = file; f != 0; f = f->prev) - print_file (f); - } + hash_map (&files, print_file); - nfiles += this_bucket; - if (this_bucket > per_bucket) - per_bucket = this_bucket; - } + fputs (_("\n# files hash-table stats:\n# "), stdout); + hash_print_stats (&files, stdout); +} - if (nfiles == 0) - puts (_("\n# No files.")); - else - { - printf (_("\n# %u files in %u hash buckets.\n"), nfiles, FILE_BUCKETS); -#ifndef NO_FLOAT - printf (_("# average %.3f files per bucket, max %u files in one bucket.\n"), - ((double) nfiles) / ((double) FILE_BUCKETS), per_bucket); -#endif - } +void +init_hash_files () +{ + hash_init (&files, 1000, file_hash_1, file_hash_2, file_hash_cmp); } /* EOF */ @@ -1,5 +1,6 @@ /* Definition of target file data structures for GNU Make. -Copyright (C) 1988,89,90,91,92,93,94,97 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1997, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -22,13 +23,14 @@ Boston, MA 02111-1307, USA. */ that the makefile says how to make. All of these are chained together through `next'. */ +#include "hash.h" + struct file { - struct file *next; char *name; char *hname; /* Hashed filename */ char *vpath; /* VPATH/vpath pathname */ - struct dep *deps; + struct dep *deps; /* all dependencies, including duplicates */ struct commands *cmds; /* Commands to execute for this target. */ int command_flags; /* Flags OR'd in for cmds; see commands.h. */ char *stem; /* Implicit stem, if an implicit @@ -106,11 +108,9 @@ extern void remove_intermediates PARAMS ((int sig)); extern void snap_deps PARAMS ((void)); extern void rename_file PARAMS ((struct file *file, char *name)); extern void rehash_file PARAMS ((struct file *file, char *name)); -extern void file_hash_enter PARAMS ((struct file *file, char *name, - unsigned int oldhash, char *oldname)); extern void set_command_state PARAMS ((struct file *file, int state)); extern void notice_finished_file PARAMS ((struct file *file)); - +extern void init_hash_files PARAMS ((void)); #if FILE_TIMESTAMP_HI_RES # define FILE_TIMESTAMP_STAT_MODTIME(fname, st) \ @@ -1,5 +1,5 @@ /* Builtin function expansion for GNU Make. -Copyright (C) 1988,1989,1991-1997,1999 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1991-1997, 1999, 2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -39,6 +39,33 @@ struct function_table_entry char expand_args; char *(*func_ptr) PARAMS ((char *output, char **argv, const char *fname)); }; + +static unsigned long +function_table_entry_hash_1 (void const *keyv) +{ + struct function_table_entry const *key = (struct function_table_entry const *) keyv; + return_STRING_N_HASH_1 (key->name, key->len); +} + +static unsigned long +function_table_entry_hash_2 (void const *keyv) +{ + struct function_table_entry const *key = (struct function_table_entry const *) keyv; + return_STRING_N_HASH_2 (key->name, key->len); +} + +static int +function_table_entry_hash_cmp (void const *xv, void const *yv) +{ + struct function_table_entry const *x = (struct function_table_entry const *) xv; + struct function_table_entry const *y = (struct function_table_entry const *) yv; + int result = x->len - y->len; + if (result) + return result; + return_STRING_N_COMPARE (x->name, y->name, x->len); +} + +static struct hash_table function_table; /* Store into VARIABLE_BUFFER at O the result of scanning TEXT and replacing @@ -221,25 +248,25 @@ patsubst_expand (o, text, pattern, replace, pattern_percent, replace_percent) } -/* Look up a function by name. - The table is currently small enough that it's not really worthwhile to use - a fancier lookup algorithm. If it gets larger, maybe... -*/ +/* Look up a function by name. */ static const struct function_table_entry * -lookup_function (table, s) - const struct function_table_entry *table; +lookup_function (s) const char *s; { - int len = strlen (s); + const char *e = s; - for (; table->name != NULL; ++table) - if (table->len <= len - && (isblank ((unsigned char)s[table->len]) || s[table->len] == '\0') - && strneq (s, table->name, table->len)) - return table; + while (*e && ( (*e >= 'a' && *e <= 'z') || *e == '-')) + e++; + if (*e == '\0' || isblank ((unsigned char) *e)) + { + struct function_table_entry function_table_entry_key; + function_table_entry_key.name = s; + function_table_entry_key.len = e - s; - return NULL; + return hash_find_item (&function_table, &function_table_entry_key); + } + return 0; } @@ -862,64 +889,150 @@ func_foreach (o, argv, funcname) struct a_word { struct a_word *next; + struct a_word *chain; char *str; + int length; int matched; }; +static unsigned long +a_word_hash_1 (void const *key) +{ + return_STRING_HASH_1 (((struct a_word const *) key)->str); +} + +static unsigned long +a_word_hash_2 (void const *key) +{ + return_STRING_HASH_2 (((struct a_word const *) key)->str); +} + +static int +a_word_hash_cmp (void const *x, void const *y) +{ + int result = ((struct a_word const *) x)->length - ((struct a_word const *) y)->length; + if (result) + return result; + return_STRING_COMPARE (((struct a_word const *) x)->str, + ((struct a_word const *) y)->str); +} + +struct a_pattern +{ + struct a_pattern *next; + char *str; + char *percent; + int length; + int save_c; +}; + static char * func_filter_filterout (o, argv, funcname) char *o; char **argv; const char *funcname; { - struct a_word *wordhead = 0; - struct a_word *wordtail = 0; - + struct a_word *wordhead; + struct a_word **wordtail; + struct a_word *wp; + struct a_pattern *pathead; + struct a_pattern **pattail; + struct a_pattern *pp; + + struct hash_table a_word_table; int is_filter = streq (funcname, "filter"); - char *patterns = argv[0]; + char *pat_iterator = argv[0]; char *word_iterator = argv[1]; - + int literals = 0; + int words = 0; + int hashing = 0; char *p; unsigned int len; - /* Chop ARGV[1] up into words and then run each pattern through. */ + /* Chop ARGV[0] up into patterns to match against the words. */ + + pattail = &pathead; + while ((p = find_next_token (&pat_iterator, &len)) != 0) + { + struct a_pattern *pat = (struct a_pattern *) alloca (sizeof (struct a_pattern)); + + *pattail = pat; + pattail = &pat->next; + + if (*pat_iterator != '\0') + ++pat_iterator; + + pat->str = p; + pat->length = len; + pat->save_c = p[len]; + p[len] = '\0'; + pat->percent = find_percent (p); + if (pat->percent == 0) + literals++; + } + *pattail = 0; + + /* Chop ARGV[1] up into words to match against the patterns. */ + + wordtail = &wordhead; while ((p = find_next_token (&word_iterator, &len)) != 0) { - struct a_word *w = (struct a_word *)alloca (sizeof (struct a_word)); - if (wordhead == 0) - wordhead = w; - else - wordtail->next = w; - wordtail = w; + struct a_word *word = (struct a_word *) alloca (sizeof (struct a_word)); + + *wordtail = word; + wordtail = &word->next; if (*word_iterator != '\0') ++word_iterator; + p[len] = '\0'; - w->str = p; - w->matched = 0; + word->str = p; + word->length = len; + word->matched = 0; + word->chain = 0; + words++; } + *wordtail = 0; - if (wordhead != 0) + /* Only use a hash table if arg list lengths justifies the cost. */ + hashing = (literals >= 2 && (literals * words) >= 10); + if (hashing) { - char *pat_iterator = patterns; - int doneany = 0; - struct a_word *wp; + hash_init (&a_word_table, words, a_word_hash_1, a_word_hash_2, a_word_hash_cmp); + for (wp = wordhead; wp != 0; wp = wp->next) + { + struct a_word *owp = hash_insert (&a_word_table, wp); + if (owp) + wp->chain = owp; + } + } - wordtail->next = 0; + if (words) + { + int doneany = 0; /* Run each pattern through the words, killing words. */ - while ((p = find_next_token (&pat_iterator, &len)) != 0) + for (pp = pathead; pp != 0; pp = pp->next) { - char *percent; - char save = p[len]; - p[len] = '\0'; - - percent = find_percent (p); - for (wp = wordhead; wp != 0; wp = wp->next) - wp->matched |= (percent == 0 ? streq (p, wp->str) - : pattern_matches (p, percent, wp->str)); - - p[len] = save; + if (pp->percent) + for (wp = wordhead; wp != 0; wp = wp->next) + wp->matched |= pattern_matches (pp->str, pp->percent, wp->str); + else if (hashing) + { + struct a_word a_word_key; + a_word_key.str = pp->str; + a_word_key.length = pp->length; + wp = (struct a_word *) hash_find_item (&a_word_table, &a_word_key); + while (wp) + { + wp->matched |= 1; + wp = wp->chain; + } + } + else + for (wp = wordhead; wp != 0; wp = wp->next) + wp->matched |= (wp->length == pp->length + && strneq (pp->str, wp->str, wp->length)); } /* Output the words that matched (or didn't, for filter-out). */ @@ -936,6 +1049,12 @@ func_filter_filterout (o, argv, funcname) --o; } + for (pp = pathead; pp != 0; pp = pp->next) + pp->str[pp->length] = pp->save_c; + + if (hashing) + hash_free (&a_word_table, 0); + return o; } @@ -1669,7 +1788,7 @@ func_not (char* o, char **argv, char *funcname) static char *func_call PARAMS ((char *o, char **argv, const char *funcname)); -static struct function_table_entry function_table[] = +static struct function_table_entry function_table_init[] = { /* Name/size */ /* MIN MAX EXP? Function */ { STRING_SIZE_TUPLE("addprefix"), 2, 2, 1, func_addsuffix_addprefix}, @@ -1704,11 +1823,12 @@ static struct function_table_entry function_table[] = { STRING_SIZE_TUPLE("eq"), 2, 2, 1, func_eq}, { STRING_SIZE_TUPLE("not"), 0, 1, 1, func_not}, #endif - { 0 } }; + +#define FUNCTION_TABLE_ENTRIES (sizeof (function_table_init) / sizeof (struct function_table_entry)) -/* These must come after the definition of function_table[]. */ +/* These must come after the definition of function_table. */ static char * expand_builtin_function (o, argc, argv, entry_p) @@ -1758,7 +1878,7 @@ handle_function (op, stringp) beg = *stringp + 1; - entry_p = lookup_function (function_table, beg); + entry_p = lookup_function (beg); if (!entry_p) return 0; @@ -1881,7 +2001,7 @@ func_call (o, argv, funcname) /* Are we invoking a builtin function? */ - entry_p = lookup_function (function_table, fname); + entry_p = lookup_function (fname); if (entry_p) { @@ -1936,3 +2056,13 @@ func_call (o, argv, funcname) return o + strlen (o); } + +void +hash_init_function_table () +{ + hash_init (&function_table, FUNCTION_TABLE_ENTRIES * 2, + function_table_entry_hash_1, function_table_entry_hash_2, + function_table_entry_hash_cmp); + hash_load (&function_table, function_table_init, + FUNCTION_TABLE_ENTRIES, sizeof (struct function_table_entry)); +} @@ -0,0 +1,328 @@ +/* hash.c -- hash table maintenance + Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc. + Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org> + + This program 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. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +*/ + +#include "make.h" +#include "hash.h" + +#define CALLOC(t, n) ((t *) calloc (sizeof (t), (n))) +#define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n))) +#define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n))) +#define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n))) + +static void hash_rehash __P((struct hash_table* ht)); +static unsigned long round_up_2 __P((unsigned long rough)); + +/* Implement double hashing with open addressing. The table size is + always a power of two. The secondary (`increment') hash function + is forced to return an odd-value, in order to be relatively prime + to the table size. This guarantees that the increment can + potentially hit every slot in the table during collision + resolution. */ + +void *hash_deleted_item = &hash_deleted_item; + +/* Force the table size to be a power of two, possibly rounding up the + given size. */ + +void +hash_init (struct hash_table* ht, unsigned long size, + hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp) +{ + ht->ht_size = round_up_2 (size); + ht->ht_empty_slots = ht->ht_size; + ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size); + if (ht->ht_vec == 0) + { + fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"), + ht->ht_size * sizeof(struct token *)); + exit (1); + } + + ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */ + ht->ht_fill = 0; + ht->ht_collisions = 0; + ht->ht_lookups = 0; + ht->ht_rehashes = 0; + ht->ht_hash_1 = hash_1; + ht->ht_hash_2 = hash_2; + ht->ht_compare = hash_cmp; +} + +/* Load an array of items into `ht'. */ + +void +hash_load (struct hash_table* ht, void *item_table, unsigned long cardinality, unsigned long size) +{ + char *items = (char *) item_table; + while (cardinality--) + { + hash_insert (ht, items); + items += size; + } +} + +/* Returns the address of the table slot matching `key'. If `key' is + not found, return the address of an empty slot suitable for + inserting `key'. The caller is responsible for incrementing + ht_fill on insertion. */ + +void ** +hash_find_slot (struct hash_table* ht, void const *key) +{ + void **slot; + void **deleted_slot = 0; + unsigned int hash_2 = 0; + unsigned int hash_1 = (*ht->ht_hash_1) (key); + + ht->ht_lookups++; + for (;;) + { + hash_1 &= (ht->ht_size - 1); + slot = &ht->ht_vec[hash_1]; + + if (*slot == 0) + return (deleted_slot ? deleted_slot : slot); + if (*slot == hash_deleted_item) + { + if (deleted_slot == 0) + deleted_slot = slot; + } + else + { + if (key == *slot) + return slot; + if ((*ht->ht_compare) (key, *slot) == 0) + return slot; + ht->ht_collisions++; + } + if (!hash_2) + hash_2 = (*ht->ht_hash_2) (key) | 1; + hash_1 += hash_2; + } +} + +void * +hash_find_item (struct hash_table* ht, void const *key) +{ + void **slot = hash_find_slot (ht, key); + return ((HASH_VACANT (*slot)) ? 0 : *slot); +} + +void * +hash_insert (struct hash_table* ht, void *item) +{ + void **slot = hash_find_slot (ht, item); + void *old_item = slot ? *slot : 0; + hash_insert_at (ht, item, slot); + return ((HASH_VACANT (old_item)) ? 0 : old_item); +} + +void * +hash_insert_at (struct hash_table* ht, void *item, void const *slot) +{ + void *old_item = *(void **) slot; + if (HASH_VACANT (old_item)) + { + ht->ht_fill++; + if (old_item == 0) + ht->ht_empty_slots--; + old_item = item; + } + *(void const **) slot = item; + if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity) + { + hash_rehash (ht); + return (void *) hash_find_slot (ht, item); + } + else + return (void *) slot; +} + +void * +hash_delete (struct hash_table* ht, void const *item) +{ + void **slot = hash_find_slot (ht, item); + return hash_delete_at (ht, slot); +} + +void * +hash_delete_at (struct hash_table* ht, void const *slot) +{ + void *item = *(void **) slot; + if (!HASH_VACANT (item)) + { + *(void const **) slot = hash_deleted_item; + ht->ht_fill--; + return item; + } + else + return 0; +} + +void +hash_free_items (struct hash_table* ht) +{ + void **vec = ht->ht_vec; + void **end = &vec[ht->ht_size]; + for (; vec < end; vec++) + { + void *item = *vec; + if (!HASH_VACANT (item)) + free (item); + *vec = 0; + } + ht->ht_fill = 0; + ht->ht_empty_slots = ht->ht_size; +} + +void +hash_delete_items (struct hash_table* ht) +{ + void **vec = ht->ht_vec; + void **end = &vec[ht->ht_size]; + for (; vec < end; vec++) + *vec = 0; + ht->ht_fill = 0; + ht->ht_collisions = 0; + ht->ht_lookups = 0; + ht->ht_rehashes = 0; + ht->ht_empty_slots = ht->ht_size; +} + +void +hash_free (struct hash_table* ht, int free_items) +{ + if (free_items) + hash_free_items (ht); + else + { + ht->ht_fill = 0; + ht->ht_empty_slots = ht->ht_size; + } + free (ht->ht_vec); + ht->ht_vec = 0; + ht->ht_capacity = 0; +} + +void +hash_map (struct hash_table *ht, hash_map_func_t map) +{ + void **slot; + void **end = &ht->ht_vec[ht->ht_size]; + + for (slot = ht->ht_vec; slot < end; slot++) + { + if (!HASH_VACANT (*slot)) + (*map) (*slot); + } +} + +void +hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg) +{ + void **slot; + void **end = &ht->ht_vec[ht->ht_size]; + + for (slot = ht->ht_vec; slot < end; slot++) + { + if (!HASH_VACANT (*slot)) + (*map) (*slot, arg); + } +} + +/* Double the size of the hash table in the event of overflow... */ + +static void +hash_rehash (struct hash_table* ht) +{ + unsigned long old_ht_size = ht->ht_size; + void **old_vec = ht->ht_vec; + void **ovp; + + if (ht->ht_fill >= ht->ht_capacity) + { + ht->ht_size *= 2; + ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4); + } + ht->ht_rehashes++; + ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size); + + for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++) + { + if (! HASH_VACANT (*ovp)) + { + void **slot = hash_find_slot (ht, *ovp); + *slot = *ovp; + } + } + ht->ht_empty_slots = ht->ht_size - ht->ht_fill; + free (old_vec); +} + +void +hash_print_stats (struct hash_table *ht, FILE *out_FILE) +{ + /* GKM FIXME: honor NO_FLOAT */ + fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size, + 100.0 * (double) ht->ht_fill / (double) ht->ht_size); + fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes); + fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups, + (ht->ht_lookups + ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups) + : 0)); +} + +/* Dump all items into a NULL-terminated vector. Use the + user-supplied vector, or malloc one. */ + +void ** +hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare) +{ + void **vector; + void **slot; + void **end = &ht->ht_vec[ht->ht_size]; + + if (vector_0 == 0) + vector_0 = MALLOC (void *, ht->ht_fill + 1); + vector = vector_0; + + for (slot = ht->ht_vec; slot < end; slot++) + if (!HASH_VACANT (*slot)) + *vector++ = *slot; + *vector = 0; + + if (compare) + qsort (vector_0, ht->ht_fill, sizeof (void *), compare); + return vector_0; +} + +/* Round a given number up to the nearest power of 2. */ + +static unsigned long +round_up_2 (unsigned long n) +{ + n |= (n >> 1); + n |= (n >> 2); + n |= (n >> 4); + n |= (n >> 8); + n |= (n >> 16); + n |= (n >> 32); + + return n + 1; +} @@ -0,0 +1,233 @@ +/* hash.h -- decls for hash table + Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc. + Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org> + + This program 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. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#ifndef _hash_h_ +#define _hash_h_ + +#include <stdio.h> +#include <ctype.h> + +#if defined __cplusplus || (defined __STDC__ && __STDC__) || defined WINDOWS32 +# if !defined __GLIBC__ || !defined __P +# undef __P +# define __P(protos) protos +# endif +#else /* Not C++ or ANSI C. */ +# undef __P +# define __P(protos) () +/* We can get away without defining `const' here only because in this file + it is used only inside the prototype for `fnmatch', which is elided in + non-ANSI C where `const' is problematical. */ +#endif /* C++ or ANSI C. */ + +typedef unsigned long (*hash_func_t) __P((void const *key)); +typedef int (*hash_cmp_func_t) __P((void const *x, void const *y)); +typedef void (*hash_map_func_t) __P((void const *item)); +typedef void (*hash_map_arg_func_t) __P((void const *item, void *arg)); + +struct hash_table +{ + void **ht_vec; + unsigned long ht_size; /* total number of slots (power of 2) */ + unsigned long ht_capacity; /* usable slots, limited by loading-factor */ + unsigned long ht_fill; /* items in table */ + unsigned long ht_empty_slots; /* empty slots not including deleted slots */ + unsigned long ht_collisions; /* # of failed calls to comparison function */ + unsigned long ht_lookups; /* # of queries */ + unsigned int ht_rehashes; /* # of times we've expanded table */ + hash_func_t ht_hash_1; /* primary hash function */ + hash_func_t ht_hash_2; /* secondary hash function */ + hash_cmp_func_t ht_compare; /* comparison function */ +}; + +typedef int (*qsort_cmp_t) __P((void const *, void const *)); + +void hash_init __P((struct hash_table *ht, unsigned long size, + hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)); +void hash_load __P((struct hash_table *ht, void *item_table, + unsigned long cardinality, unsigned long size)); +void **hash_find_slot __P((struct hash_table *ht, void const *key)); +void *hash_find_item __P((struct hash_table *ht, void const *key)); +void *hash_insert __P((struct hash_table *ht, void *item)); +void *hash_insert_at __P((struct hash_table *ht, void *item, void const *slot)); +void *hash_delete __P((struct hash_table *ht, void const *item)); +void *hash_delete_at __P((struct hash_table *ht, void const *slot)); +void hash_delete_items __P((struct hash_table *ht)); +void hash_free_items __P((struct hash_table *ht)); +void hash_free __P((struct hash_table *ht, int free_items)); +void hash_map __P((struct hash_table *ht, hash_map_func_t map)); +void hash_map_arg __P((struct hash_table *ht, hash_map_arg_func_t map, void *arg)); +void hash_print_stats __P((struct hash_table *ht, FILE *out_FILE)); +void **hash_dump __P((struct hash_table *ht, void **vector_0, qsort_cmp_t compare)); + +extern void *hash_deleted_item; +#define HASH_VACANT(item) ((item) == 0 || (void *) (item) == hash_deleted_item) + + +/* hash and comparison macros for case-sensitive string keys. */ + +#define STRING_HASH_1(KEY, RESULT) do { \ + unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ + while (*++_key_) \ + (RESULT) += (*_key_ << (_key_[1] & 0xf)); \ +} while (0) +#define return_STRING_HASH_1(KEY) do { \ + unsigned long _result_ = 0; \ + STRING_HASH_1 ((KEY), _result_); \ + return _result_; \ +} while (0) + +#define STRING_HASH_2(KEY, RESULT) do { \ + unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ + while (*++_key_) \ + (RESULT) += (*_key_ << (_key_[1] & 0x7)); \ +} while (0) +#define return_STRING_HASH_2(KEY) do { \ + unsigned long _result_ = 0; \ + STRING_HASH_2 ((KEY), _result_); \ + return _result_; \ +} while (0) + +#define STRING_COMPARE(X, Y, RESULT) do { \ + _RESULT_ = strcmp ((X), (Y)); \ +} while (0) +#define return_STRING_COMPARE(X, Y) do { \ + return strcmp ((X), (Y)); \ +} while (0) + + +#define STRING_N_HASH_1(KEY, N, RESULT) do { \ + unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ + int _n_ = (N); \ + if (_n_) \ + while (--_n_ && *++_key_) \ + (RESULT) += (*_key_ << (_key_[1] & 0xf)); \ + (RESULT) += *++_key_; \ +} while (0) +#define return_STRING_N_HASH_1(KEY, N) do { \ + unsigned long _result_ = 0; \ + STRING_N_HASH_1 ((KEY), (N), _result_); \ + return _result_; \ +} while (0) + +#define STRING_N_HASH_2(KEY, N, RESULT) do { \ + unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ + int _n_ = (N); \ + if (_n_) \ + while (--_n_ && *++_key_) \ + (RESULT) += (*_key_ << (_key_[1] & 0x7)); \ + (RESULT) += *++_key_; \ +} while (0) +#define return_STRING_N_HASH_2(KEY, N) do { \ + unsigned long _result_ = 0; \ + STRING_N_HASH_2 ((KEY), (N), _result_); \ + return _result_; \ +} while (0) + +#define STRING_N_COMPARE(X, Y, N, RESULT) do { \ + _RESULT_ = strncmp ((X), (Y), (N)); \ +} while (0) +#define return_STRING_N_COMPARE(X, Y, N) do { \ + return strncmp ((X), (Y), (N)); \ +} while (0) + +#ifdef HAVE_CASE_INSENSITIVE_FS + +/* hash and comparison macros for case-insensitive string _key_s. */ + +#define ISTRING_HASH_1(KEY, RESULT) do { \ + unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ + while (*++_key_) \ + (RESULT) += ((isupper (*_key_) ? tolower (*_key_) : *_key_) << (_key_[1] & 0xf)); \ +} while (0) +#define return_ISTRING_HASH_1(KEY) do { \ + unsigned long _result_ = 0; \ + ISTRING_HASH_1 ((KEY), _result_); \ + return _result_; \ +} while (0) + +#define ISTRING_HASH_2(KEY, RESULT) do { \ + unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ + while (*++_key_) \ + (RESULT) += ((isupper (*_key_) ? tolower (*_key_) : *_key_) << (_key_[1] & 0x7)); \ +} while (0) +#define return_ISTRING_HASH_2(KEY) do { \ + unsigned long _result_ = 0; \ + ISTRING_HASH_2 ((KEY), _result_); \ + return _result_; \ +} while (0) + +#define ISTRING_COMPARE(X, Y, RESULT) do { \ + _RESULT_ = stricmp ((X), (Y)); +} while (0) +#define return_ISTRING_COMPARE(X, Y) do { \ + return stricmp ((X), (Y)); +} while (0) + +#else + +#define ISTRING_HASH_1(KEY, RESULT) STRING_HASH_1 ((KEY), (RESULT)) +#define return_ISTRING_HASH_1(KEY) return_STRING_HASH_1 (KEY) + +#define ISTRING_HASH_2(KEY, RESULT) STRING_HASH_2 ((KEY), (RESULT)) +#define return_ISTRING_HASH_2(KEY) return_STRING_HASH_2 (KEY) + +#define ISTRING_COMPARE(X, Y, RESULT) STRING_COMPARE ((X), (Y), (RESULT)) +#define return_ISTRING_COMPARE(X, Y) return_STRING_COMPARE ((X), (Y)) + +#endif + +/* hash and comparison macros for integer _key_s. */ + +#define INTEGER_HASH_1(KEY, RESULT) do { \ + (RESULT) += ((unsigned long)(KEY)); \ +} while (0) +#define return_INTEGER_HASH_1(KEY) do { \ + unsigned long _result_ = 0; \ + INTEGER_HASH_1 ((KEY), _result_); \ + return _result_; \ +} while (0) + +#define INTEGER_HASH_2(KEY, RESULT) do { \ + (RESULT) += ~((unsigned long)(KEY)); \ +} while (0) +#define return_INTEGER_HASH_2(KEY) do { \ + unsigned long _result_ = 0; \ + INTEGER_HASH_2 ((KEY), _result_); \ + return _result_; \ +} while (0) + +#define INTEGER_COMPARE(X, Y, RESULT) do { \ + (RESULT) = X - Y; \ +} while (0) +#define return_INTEGER_COMPARE(X, Y) do { \ + int _result_; \ + INTEGER_COMPARE (X, Y, _result_); \ + return _result_; \ +} while (0) + +/* hash and comparison macros for address keys. */ + +#define ADDRESS_HASH_1(KEY, RESULT) INTEGER_HASH_1 (((unsigned long)(KEY)) >> 3, (RESULT)) +#define ADDRESS_HASH_2(KEY, RESULT) INTEGER_HASH_2 (((unsigned long)(KEY)) >> 3, (RESULT)) +#define ADDRESS_COMPARE(X, Y, RESULT) INTEGER_COMPARE ((X), (Y), (RESULT)) +#define return_ADDRESS_HASH_1(KEY) return_INTEGER_HASH_1 (((unsigned long)(KEY)) >> 3) +#define return_ADDRESS_HASH_2(KEY) return_INTEGER_HASH_2 (((unsigned long)(KEY)) >> 3) +#define return_ADDRESS_COMPARE(X, Y) return_INTEGER_COMPARE ((X), (Y)) + +#endif /* not _hash_h_ */ @@ -1,5 +1,6 @@ /* Argument parsing and main program of GNU Make. -Copyright (C) 1988,89,90,91,94,95,96,97,98,99 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1994, 1995, 1996, 1997, 1998, 1999, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -75,6 +76,8 @@ static void decode_switches PARAMS ((int argc, char **argv, int env)); static void decode_env_switches PARAMS ((char *envar, unsigned int len)); static void define_makeflags PARAMS ((int all, int makefile)); static char *quote_for_env PARAMS ((char *out, char *in)); +static void initialize_global_hash_tables PARAMS ((void)); + /* The structure that describes an accepted command switch. */ @@ -471,6 +474,15 @@ bsd_signal (sig, func) # endif #endif +static void +initialize_global_hash_tables () +{ + init_hash_global_variable_set (); + init_hash_files (); + hash_init_directories (); + hash_init_function_table (); +} + static struct file * enter_command_line_file (name) char *name; @@ -951,6 +963,8 @@ int main (int argc, char ** argv) /* Set up to access user data (files). */ user_access (); + initialize_global_hash_tables (); + /* Figure out where we are. */ #ifdef WINDOWS32 @@ -1217,7 +1231,7 @@ int main (int argc, char ** argv) #endif /* WINDOWS32 */ /* Figure out the level of recursion. */ { - struct variable *v = lookup_variable ("MAKELEVEL", 9); + struct variable *v = lookup_variable (MAKELEVEL_NAME, MAKELEVEL_LENGTH); if (v != 0 && v->value[0] != '\0' && v->value[0] != '-') makelevel = (unsigned int) atoi (v->value); else @@ -1807,7 +1821,8 @@ int main (int argc, char ** argv) #ifndef _AMIGA for (p = environ; *p != 0; ++p) - if (strneq (*p, "MAKELEVEL=", 10)) + if ((*p)[MAKELEVEL_LENGTH] == '=' + && strneq (*p, MAKELEVEL_NAME, MAKELEVEL_LENGTH)) { /* The SGI compiler apparently can't understand the concept of storing the result of a function @@ -1815,7 +1830,7 @@ int main (int argc, char ** argv) char *sgi_loses; sgi_loses = (char *) alloca (40); *p = sgi_loses; - sprintf (*p, "MAKELEVEL=%u", makelevel); + sprintf (*p, "%s=%u", MAKELEVEL_NAME, makelevel); break; } #else /* AMIGA */ @@ -1823,12 +1838,12 @@ int main (int argc, char ** argv) char buffer[256]; int len; - len = GetVar ("MAKELEVEL", buffer, sizeof (buffer), GVF_GLOBAL_ONLY); + len = GetVar (MAKELEVEL_NAME, buffer, sizeof (buffer), GVF_GLOBAL_ONLY); if (len != -1) { sprintf (buffer, "%u", makelevel); - SetVar ("MAKELEVEL", buffer, -1, GVF_GLOBAL_ONLY); + SetVar (MAKELEVEL_NAME, buffer, -1, GVF_GLOBAL_ONLY); } } #endif @@ -1,5 +1,6 @@ /* Miscellaneous global declarations and portability cruft for GNU Make. -Copyright (C) 1988,89,90,91,92,93,94,95,96,97,99 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1999, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -325,16 +326,6 @@ extern char *strsignal PARAMS ((int signum)); extern int strcmpi (const char *,const char *); #endif -/* Add to VAR the hashing value of C, one character in a name. */ -#define HASH(var, c) \ - ((var += (c)), (var = ((var) << 7) + ((var) >> 20))) -#ifdef HAVE_CASE_INSENSITIVE_FS /* Fold filenames */ -# define HASHI(var, c) \ - ((var += tolower((unsigned char)(c))), (var = ((var) << 7) + ((var) >> 20))) -#else -# define HASHI(var, c) HASH(var,c) -#endif - #if defined(__GNUC__) || defined(ENUM_BITFIELDS) # define ENUM_BITFIELD(bits) :bits #else @@ -430,7 +421,7 @@ extern char *sindex PARAMS ((const char *, unsigned int, \ extern char *lindex PARAMS ((const char *, const char *, int)); extern int alpha_compare PARAMS ((const void *, const void *)); extern void print_spaces PARAMS ((unsigned int)); -extern char *find_char_unquote PARAMS ((char *, char *, int)); +extern char *find_char_unquote PARAMS ((char *, int, int, int)); extern char *find_percent PARAMS ((char *)); extern FILE *open_tmpfile PARAMS ((char **, const char *)); @@ -446,6 +437,7 @@ extern int file_exists_p PARAMS ((char *)); extern int file_impossible_p PARAMS ((char *)); extern void file_impossible PARAMS ((char *)); extern char *dir_name PARAMS ((char *)); +extern void hash_init_directories PARAMS ((void)); extern void define_default_variables PARAMS ((void)); extern void set_default_suffixes PARAMS ((void)); @@ -1,5 +1,6 @@ /* Miscellaneous generic support functions for GNU Make. -Copyright (C) 1988,89,90,91,92,93,94,95,97 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1997, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -162,7 +163,7 @@ remove_comments (line) { char *comment; - comment = find_char_unquote (line, "#", 0); + comment = find_char_unquote (line, '#', 0, 0); if (comment != 0) /* Cut off the line at the #. */ @@ -1,5 +1,6 @@ /* Reading and parsing of makefiles for GNU Make. -Copyright (C) 1988,89,90,91,92,93,94,95,96,97 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -30,6 +31,7 @@ Boston, MA 02111-1307, USA. */ #include "variable.h" #include "rule.h" #include "debug.h" +#include "hash.h" #ifndef WINDOWS32 @@ -378,6 +380,7 @@ eval_makefile (filename, flags) reading_file = curfile; + free(ebuf.bufstart); return r; } @@ -853,7 +856,7 @@ eval (ebuf, set_default) /* Search the line for an unquoted ; that is not after an unquoted #. */ - cmdleft = find_char_unquote (line, ";#", 0); + cmdleft = find_char_unquote (line, ';', '#', 0); if (cmdleft != 0 && *cmdleft == '#') { /* We found a comment before a semicolon. */ @@ -899,7 +902,7 @@ eval (ebuf, set_default) if (cmdleft == 0) { /* Look for a semicolon in the expanded line. */ - cmdleft = find_char_unquote (p2, ";", 0); + cmdleft = find_char_unquote (p2, ';', 0, 0); if (cmdleft != 0) { @@ -926,7 +929,7 @@ eval (ebuf, set_default) } } - colonp = find_char_unquote(p2, ":", 0); + colonp = find_char_unquote(p2, ':', 0, 0); #if defined(__MSDOS__) || defined(WINDOWS32) /* The drive spec brain-damage strikes again... */ /* Note that the only separators of targets in this context @@ -935,7 +938,7 @@ eval (ebuf, set_default) while (colonp && (colonp[1] == '/' || colonp[1] == '\\') && colonp > p2 && isalpha ((unsigned char)colonp[-1]) && (colonp == p2 + 1 || strchr (" \t(", colonp[-2]) != 0)) - colonp = find_char_unquote(colonp + 1, ":", 0); + colonp = find_char_unquote(colonp + 1, ':', 0, 0); #endif if (colonp != 0) break; @@ -1038,7 +1041,7 @@ eval (ebuf, set_default) /* This is a normal target, _not_ a target-specific variable. Unquote any = in the dependency list. */ - find_char_unquote (lb_next, "=", 0); + find_char_unquote (lb_next, '=', 0, 0); /* We have some targets, so don't ignore the following commands. */ no_targets = 0; @@ -1053,7 +1056,7 @@ eval (ebuf, set_default) /* Look for a semicolon in the expanded line. */ if (cmdleft == 0) { - cmdleft = find_char_unquote (p2, ";", 0); + cmdleft = find_char_unquote (p2, ';', 0, 0); if (cmdleft != 0) *(cmdleft++) = '\0'; } @@ -1519,47 +1522,68 @@ conditional_line (line, flocp) /* Remove duplicate dependencies in CHAIN. */ +static unsigned long +dep_hash_1 (void const *key) +{ + return_STRING_HASH_1 (dep_name ((struct dep const *) key)); +} + +static unsigned long +dep_hash_2 (void const *key) +{ + return_STRING_HASH_2 (dep_name ((struct dep const *) key)); +} + +static int +dep_hash_cmp (void const *x, void const *y) +{ + struct dep *dx = (struct dep *) x; + struct dep *dy = (struct dep *) y; + int cmp = strcmp (dep_name (dx), dep_name (dy)); + + /* If the names are the same but ignore_mtimes are not equal, one of these + is an order-only prerequisite and one isn't. That means that we should + remove the one that isn't and keep the one that is. */ + + if (!cmp && dx->ignore_mtime != dy->ignore_mtime) + dx->ignore_mtime = dy->ignore_mtime = 0; + + return cmp; +} + + void uniquize_deps (chain) struct dep *chain; { - register struct dep *d; + struct hash_table deps; + register struct dep **depp; + + hash_init (&deps, 500, dep_hash_1, dep_hash_2, dep_hash_cmp); /* Make sure that no dependencies are repeated. This does not really matter for the purpose of updating targets, but it might make some names be listed twice for $^ and $?. */ - for (d = chain; d != 0; d = d->next) + depp = &chain; + while (*depp) { - struct dep *last, *next; - - last = d; - next = d->next; - while (next != 0) - if (streq (dep_name (d), dep_name (next))) - { - struct dep *n = next->next; - /* If ignore_mtimes are not equal, one of these is an order-only - prerequisite and one isn't. That means that we should remove - the one that isn't and keep the one that is. Ideally we'd - like to keep the normal one always but that's hard, and - probably not very important, so just remove the second one and - force the first one to be normal. */ - if (d->ignore_mtime != next->ignore_mtime) - d->ignore_mtime = 0; - last->next = n; - if (next->name != 0 && next->name != d->name) - free (next->name); - if (next != d) - free ((char *) next); - next = n; - } - else - { - last = next; - next = next->next; - } + struct dep *dep = *depp; + struct dep **dep_slot = (struct dep **) hash_find_slot (&deps, dep); + if (HASH_VACANT (*dep_slot)) + { + hash_insert_at (&deps, dep, dep_slot); + depp = &dep->next; + } + else + { + /* Don't bother freeing duplicates. + It's dangerous and little benefit accrues. */ + *depp = dep->next; + } } + + hash_free (&deps, 0); } /* Record target-specific variable values for files FILENAMES. @@ -2076,9 +2100,10 @@ record_files (filenames, pattern, pattern_percent, deps, cmds_started, one, or nil if there are none. */ char * -find_char_unquote (string, stopchars, blank) +find_char_unquote (string, stop1, stop2, blank) char *string; - char *stopchars; + int stop1; + int stop2; int blank; { unsigned int string_len = 0; @@ -2086,9 +2111,21 @@ find_char_unquote (string, stopchars, blank) while (1) { - while (*p != '\0' && strchr (stopchars, *p) == 0 - && (!blank || !isblank ((unsigned char)*p))) - ++p; + if (stop2 && blank) + while (*p != '\0' && *p != stop1 && *p != stop2 + && ! isblank ((unsigned char) *p)) + ++p; + else if (stop2) + while (*p != '\0' && *p != stop1 && *p != stop2) + ++p; + else if (blank) + while (*p != '\0' && *p != stop1 + && ! isblank ((unsigned char) *p)) + ++p; + else + while (*p != '\0' && *p != stop1) + ++p; + if (*p == '\0') break; @@ -2128,7 +2165,7 @@ char * find_percent (pattern) char *pattern; { - return find_char_unquote (pattern, "%", 0); + return find_char_unquote (pattern, '%', 0, 0); } /* Parse a string into a sequence of filenames represented as a @@ -2156,15 +2193,11 @@ parse_file_seq (stringp, stopchar, size, strip) register char *p = *stringp; char *q; char *name; - char stopchars[3]; #ifdef VMS - stopchars[0] = ','; - stopchars[1] = stopchar; - stopchars[2] = '\0'; +# define VMS_COMMA ',' #else - stopchars[0] = stopchar; - stopchars[1] = '\0'; +# define VMS_COMMA 0 #endif while (1) @@ -2178,7 +2211,7 @@ parse_file_seq (stringp, stopchar, size, strip) /* Yes, find end of next name. */ q = p; - p = find_char_unquote (q, stopchars, 1); + p = find_char_unquote (q, stopchar, VMS_COMMA, 1); #ifdef VMS /* convert comma separated list to space separated */ if (p && *p == ',') @@ -2189,7 +2222,7 @@ parse_file_seq (stringp, stopchar, size, strip) && !(isspace ((unsigned char)p[1]) || !p[1] || isspace ((unsigned char)p[-1]))) { - p = find_char_unquote (p+1, stopchars, 1); + p = find_char_unquote (p+1, stopchar, VMS_COMMA, 1); } #endif #if defined(WINDOWS32) || defined(__MSDOS__) @@ -2200,7 +2233,7 @@ parse_file_seq (stringp, stopchar, size, strip) if (stopchar == ':') while (p != 0 && !isspace ((unsigned char)*p) && (p[1] == '\\' || p[1] == '/') && isalpha ((unsigned char)p[-1])) - p = find_char_unquote (p + 1, stopchars, 1); + p = find_char_unquote (p + 1, stopchar, VMS_COMMA, 1); #endif if (p == 0) p = q + strlen (q); @@ -2436,9 +2469,9 @@ static long readline (ebuf) struct ebuffer *ebuf; { - char *buffer = ebuf->buffer; - char *p = ebuf->buffer; - char *end = p + ebuf->size; + char *p; + char *end; + char *start; long nlines = 0; /* The behaviors between string and stream buffers are different enough to @@ -2447,6 +2480,11 @@ readline (ebuf) if (!ebuf->fp) return readstring (ebuf); + /* When reading from a file, we always start over at the beginning of the + buffer for each new line. */ + + p = start = ebuf->bufstart; + end = p + ebuf->size; *p = '\0'; while (fgets (p, end - p, ebuf->fp) != 0) @@ -2475,16 +2513,7 @@ readline (ebuf) /* If the last char isn't a newline, the whole line didn't fit into the buffer. Get some more buffer and try again. */ if (p[-1] != '\n') - { - unsigned long p_off = p - buffer; - ebuf->size *= 2; - buffer = (char *) xrealloc (buffer, ebuf->size); - p = buffer + p_off; - end = buffer + ebuf->size; - ebuf->buffer = buffer; - *p = '\0'; - continue; - } + goto more_buffer; /* We got a newline, so add one to the count of lines. */ ++nlines; @@ -2492,7 +2521,7 @@ readline (ebuf) #if !defined(WINDOWS32) && !defined(__MSDOS__) /* Check to see if the line was really ended with CRLF; if so ignore the CR. */ - if ((p - buffer) > 1 && p[-2] == '\r') + if ((p - start) > 1 && p[-2] == '\r') { --p; p[-1] = '\n'; @@ -2500,7 +2529,7 @@ readline (ebuf) #endif backslash = 0; - for (p2 = p - 2; p2 >= buffer; --p2) + for (p2 = p - 2; p2 >= start; --p2) { if (*p2 != '\\') break; @@ -2513,16 +2542,23 @@ readline (ebuf) break; } - if (end - p <= 1) - { - /* Enlarge the buffer. */ - unsigned int p_off = p - buffer; - ebuf->size *= 2; - buffer = (char *) xrealloc (buffer, ebuf->size); - p = buffer + p_off; - end = buffer + ebuf->size; - ebuf->buffer = buffer; - } + /* It was a backslash/newline combo. If we have more space, read + another line. */ + if (end - p >= 80) + continue; + + /* We need more space at the end of our buffer, so realloc it. + Make sure to preserve the current offset of p. */ + more_buffer: + { + unsigned long off = p - start; + ebuf->size *= 2; + start = ebuf->buffer = ebuf->bufstart = (char *) xrealloc (start, + ebuf->size); + p = start + off; + end = start + ebuf->size; + *p = '\0'; + } } if (ferror (ebuf->fp)) @@ -1,5 +1,6 @@ /* Basic dependency engine for GNU Make. -Copyright (C) 1988,89,90,91,92,93,94,95,96,97,99 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1999, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify diff --git a/tests/ChangeLog b/tests/ChangeLog index 3a13e9e..2dc997f 100644 --- a/tests/ChangeLog +++ b/tests/ChangeLog @@ -1,3 +1,13 @@ +2002-07-11 Paul D. Smith <psmith@gnu.org> + + * run_make_tests.pl (valid_option): Add support for Valgrind + <http://developer.kde.org/~sewardj/>. Use -valgrind option to the + test suite. + (set_more_defaults): Set up the file descriptor to capture + Valgrind output. We have to unset its close-on-exec flag; we + hardcode the value for F_SETFD (2) rather than load it; hopefully + this will help us avoid breaking the Windows/DOS test suite. + 2002-07-10 Paul D. Smith <psmith@gnu.org> * scripts/variables/automatic: Add some tests for $$@, $$(@D), and diff --git a/tests/run_make_tests.pl b/tests/run_make_tests.pl index baf55f8..0ada574 100755 --- a/tests/run_make_tests.pl +++ b/tests/run_make_tests.pl @@ -11,11 +11,16 @@ # [-make <make prog>] # (and others) +$valgrind = 0; # invoke make with valgrind + require "test_driver.pl"; +#$SIG{INT} = sub { print STDERR "Caught a signal!\n"; die @_; }; + sub valid_option { local($option) = @_; + if ($option =~ /^-make([-_]?path)?$/) { $make_path = shift @argv; @@ -27,6 +32,11 @@ sub valid_option return 1; } + if ($option =~ /^-valgrind$/i) { + $valgrind = 1; + return 1; + } + # This doesn't work--it _should_! Someone needs to fix this badly. # # elsif ($option =~ /^-work([-_]?dir)?$/) @@ -56,6 +66,10 @@ sub run_make_with_options $command .= " $options"; } + if ($valgrind) { + print VALGRIND "\n\nExecuting: $command\n"; + } + $code = &run_command_with_output($logname,$command); # Check to see if we have Purify errors. If so, keep the logfile. @@ -81,6 +95,11 @@ sub run_make_with_options { print "Error running $make_path ($code): $command\n"; $test_passed = 0; + # If it's a SIGINT, stop here + if ($code & 127) { + print STDERR "\nCaught signal ".($code & 127)."!\n"; + exit($code); + } return 0; } @@ -215,6 +234,21 @@ sub set_more_defaults else { $parallel_jobs = 1; } + + # Set up for valgrind, if requested. + + if ($valgrind) { +# use POSIX qw(:fcntl_h); +# require Fcntl; + open(VALGRIND, "> valgrind.out") + || die "Cannot open valgrind.out: $!\n"; + # -q --leak-check=yes + $make_path = "valgrind --num-callers=15 --logfile-fd=".fileno(VALGRIND)." $make_path"; + # F_SETFD is 2 + fcntl(VALGRIND, 2, 0) or die "fcntl(setfd) failed: $!\n"; + system("echo Starting on `date` 1>&".fileno(VALGRIND)); + print "Enabled valgrind support.\n"; + } } sub setup_for_test diff --git a/tests/scripts/functions/filter-out b/tests/scripts/functions/filter-out index 0559a8d..6c8b27a 100644 --- a/tests/scripts/functions/filter-out +++ b/tests/scripts/functions/filter-out @@ -1,35 +1,28 @@ -$description = "The following test creates a makefile to test static \n" - ."pattern rules. Static pattern rules are rules which \n" - ."specify multiple targets and construct the dependency \n" - ."names for each target based on the target name. "; +# -*-perl-*- -$details = "The makefile created in this test has three targets. The \n" - ."filter command is used to get those target names ending in \n" - .".o and statically creates a compile command with the target\n" - ."name and the target name with .c. It also does the same thing\n" - ."for another target filtered with .elc and creates a command\n" - ."to emacs a .el file"; +$description = "Test the filter-out function."; -open(MAKEFILE,"> $makefile"); - -# The Contents of the MAKEFILE ... +$details = "The makefile created in this test has two variables. The +filter-out function is first used to discard names ending in +.o with a single simple pattern. The second filter-out function +augments the simple pattern with three literal names, which are +also added to the text argument. This tests an internal hash table +which is only used if there are multiple literals present in both +the pattern and text arguments. The result of both filter-out +functions is the same single .elc name.\n"; -print MAKEFILE "files := \$(filter-out %.o, foo.elc bar.o lose.o) \n" - ."all: \n" - ."\t\@echo \$(files) \n"; +open(MAKEFILE,"> $makefile"); -# END of Contents of MAKEFILE +print MAKEFILE <<'EOF'; +files1 := $(filter-out %.o, foo.elc bar.o lose.o) +files2 := $(filter-out foo.i bar.i lose.i %.o, foo.i bar.i lose.i foo.elc bar.o lose.o) +all: ; @echo $(files1) $(files2) +EOF close(MAKEFILE); -&run_make_with_options($makefile, - "", - &get_logfile, - 0); - -# Create the answer to what should be produced by this Makefile -$answer = "foo.elc\n"; - +&run_make_with_options($makefile, "", &get_logfile, 0); +$answer = "foo.elc foo.elc\n"; &compare_output($answer,&get_logfile(1)); 1; diff --git a/tests/scripts/targets/INTERMEDIATE b/tests/scripts/targets/INTERMEDIATE index fe3f4e9..725ab0e 100644 --- a/tests/scripts/targets/INTERMEDIATE +++ b/tests/scripts/targets/INTERMEDIATE @@ -59,7 +59,7 @@ $answer = "cp foo.f foo.e\ncp foo.e foo.d\nrm foo.e\n"; # TEST #3 &run_make_with_options($makefile,'foo.c',&get_logfile); -$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm foo.e bar.e\n"; +$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm bar.e foo.e\n"; &compare_output($answer, &get_logfile(1)); # TEST #4 @@ -74,7 +74,7 @@ sleep($wtime); &touch('foo.f'); &run_make_with_options($makefile,'foo.c',&get_logfile); -$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm foo.e bar.e\n"; +$answer = "cp foo.f foo.e\ncp bar.f bar.e\ncat foo.e bar.e > foo.c\nrm bar.e foo.e\n"; &compare_output($answer, &get_logfile(1)); # TEST #6 -- added for PR/1669: don't remove files mentioned on the cmd line. @@ -1,5 +1,6 @@ /* Internals of variables for GNU Make. -Copyright (C) 1988,89,90,91,92,93,94,96,97 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1996, 1997, +2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -27,9 +28,35 @@ Boston, MA 02111-1307, USA. */ #ifdef WINDOWS32 #include "pathstuff.h" #endif +#include "hash.h" /* Hash table of all global variable definitions. */ +static unsigned long +variable_hash_1 (void const *keyv) +{ + struct variable const *key = (struct variable const *) keyv; + return_STRING_N_HASH_1 (key->name, key->length); +} + +static unsigned long +variable_hash_2 (void const *keyv) +{ + struct variable const *key = (struct variable const *) keyv; + return_STRING_N_HASH_2 (key->name, key->length); +} + +static int +variable_hash_cmp (void const *xv, void const *yv) +{ + struct variable const *x = (struct variable const *) xv; + struct variable const *y = (struct variable const *) yv; + int result = x->length - y->length; + if (result) + return result; + return_STRING_N_COMPARE (x->name, y->name, x->length); +} + #ifndef VARIABLE_BUCKETS #define VARIABLE_BUCKETS 523 #endif @@ -39,15 +66,21 @@ Boston, MA 02111-1307, USA. */ #ifndef SMALL_SCOPE_VARIABLE_BUCKETS #define SMALL_SCOPE_VARIABLE_BUCKETS 13 #endif -static struct variable *variable_table[VARIABLE_BUCKETS]; -static struct variable_set global_variable_set - = { variable_table, VARIABLE_BUCKETS }; + +static struct variable_set global_variable_set; static struct variable_set_list global_setlist = { 0, &global_variable_set }; struct variable_set_list *current_variable_set_list = &global_setlist; /* Implement variables. */ +void +init_hash_global_variable_set () +{ + hash_init (&global_variable_set.table, VARIABLE_BUCKETS, + variable_hash_1, variable_hash_2, variable_hash_cmp); +} + /* Define variable named NAME with value VALUE in SET. VALUE is copied. LENGTH is the length of NAME, which does not need to be null-terminated. ORIGIN specifies the origin of the variable (makefile, command line @@ -65,28 +98,22 @@ define_variable_in_set (name, length, value, origin, recursive, set, flocp) struct variable_set *set; const struct floc *flocp; { - register unsigned int i; - register unsigned int hashval; - register struct variable *v; + struct variable *v; + struct variable **var_slot; + struct variable var_key; if (set == NULL) set = &global_variable_set; - hashval = 0; - for (i = 0; i < length; ++i) - HASH (hashval, name[i]); - hashval %= set->buckets; - - for (v = set->table[hashval]; v != 0; v = v->next) - if (*v->name == *name - && strneq (v->name + 1, name + 1, length - 1) - && v->name[length] == '\0') - break; + var_key.name = (char *) name; + var_key.length = length; + var_slot = (struct variable **) hash_find_slot (&set->table, &var_key); if (env_overrides && origin == o_env) origin = o_env_override; - if (v != 0) + v = *var_slot; + if (! HASH_VACANT (v)) { if (env_overrides && v->origin == o_env) /* V came from in the environment. Since it was defined @@ -115,6 +142,8 @@ define_variable_in_set (name, length, value, origin, recursive, set, flocp) v = (struct variable *) xmalloc (sizeof (struct variable)); v->name = savestring (name, length); + v->length = length; + hash_insert_at (&set->table, v, var_slot); v->value = xstrdup (value); if (flocp != 0) v->fileinfo = *flocp; @@ -127,8 +156,7 @@ define_variable_in_set (name, length, value, origin, recursive, set, flocp) v->per_target = 0; v->append = 0; v->export = v_default; - v->next = set->table[hashval]; - set->table[hashval] = v; + return v; } @@ -143,26 +171,20 @@ lookup_variable (name, length) unsigned int length; { const struct variable_set_list *setlist; + struct variable var_key; - unsigned int i; - unsigned int rawhash = 0; - - for (i = 0; i < length; ++i) - HASH (rawhash, name[i]); + var_key.name = (char *) name; + var_key.length = length; for (setlist = current_variable_set_list; setlist != 0; setlist = setlist->next) { const struct variable_set *set = setlist->set; - unsigned int hashval = rawhash % set->buckets; struct variable *v; - /* Look through this set list; return it if found. */ - for (v = set->table[hashval]; v != 0; v = v->next) - if (*v->name == *name - && strneq (v->name + 1, name + 1, length - 1) - && v->name[length] == '\0') - return v; + v = (struct variable *) hash_find_item ((struct hash_table *) &set->table, &var_key); + if (v) + return v; } #ifdef VMS @@ -235,21 +257,12 @@ lookup_variable_in_set (name, length, set) unsigned int length; const struct variable_set *set; { - unsigned int i; - unsigned int hash = 0; - struct variable *v; + struct variable var_key; - for (i = 0; i < length; ++i) - HASH (hash, name[i]); - hash %= set->buckets; - - for (v = set->table[hash]; v != 0; v = v->next) - if (*v->name == *name - && strneq (v->name + 1, name + 1, length - 1) - && v->name[length] == 0) - return v; + var_key.name = (char *) name; + var_key.length = length; - return 0; + return (struct variable *) hash_find_item ((struct hash_table *) &set->table, &var_key); } /* Initialize FILE's variable set list. If FILE already has a variable set @@ -270,11 +283,8 @@ initialize_file_variables (file, reading) l = (struct variable_set_list *) xmalloc (sizeof (struct variable_set_list)); l->set = (struct variable_set *) xmalloc (sizeof (struct variable_set)); - l->set->buckets = PERFILE_VARIABLE_BUCKETS; - l->set->table = (struct variable **) - xmalloc (l->set->buckets * sizeof (struct variable *)); - bzero ((char *) l->set->table, - l->set->buckets * sizeof (struct variable *)); + hash_init (&l->set->table, PERFILE_VARIABLE_BUCKETS, + variable_hash_1, variable_hash_2, variable_hash_cmp); file->variables = l; } @@ -316,31 +326,27 @@ initialize_file_variables (file, reading) /* Pop the top set off the current variable set list, and free all its storage. */ +static void +free_variable_name_and_value (item) + void *item; +{ + struct variable *v = (struct variable *) item; + free (v->name); + free (v->value); +} + void pop_variable_scope () { - register struct variable_set_list *setlist = current_variable_set_list; - register struct variable_set *set = setlist->set; - register unsigned int i; + struct variable_set_list *setlist = current_variable_set_list; + struct variable_set *set = setlist->set; current_variable_set_list = setlist->next; free ((char *) setlist); - for (i = 0; i < set->buckets; ++i) - { - register struct variable *next = set->table[i]; - while (next != 0) - { - register struct variable *v = next; - next = v->next; + hash_map (&set->table, free_variable_name_and_value); + hash_free (&set->table, 1); - free (v->name); - if (v->value) - free (v->value); - free ((char *) v); - } - } - free ((char *) set->table); free ((char *) set); } @@ -351,10 +357,8 @@ create_new_variable_set () register struct variable_set *set; set = (struct variable_set *) xmalloc (sizeof (struct variable_set)); - set->buckets = SMALL_SCOPE_VARIABLE_BUCKETS; - set->table = (struct variable **) - xmalloc (set->buckets * sizeof (struct variable *)); - bzero ((char *) set->table, set->buckets * sizeof (struct variable *)); + hash_init (&set->table, SMALL_SCOPE_VARIABLE_BUCKETS, + variable_hash_1, variable_hash_2, variable_hash_cmp); setlist = (struct variable_set_list *) xmalloc (sizeof (struct variable_set_list)); @@ -375,52 +379,27 @@ push_new_variable_scope () /* Merge SET1 into SET0, freeing unused storage in SET1. */ static void -merge_variable_sets (set0, set1) - struct variable_set *set0, *set1; +merge_variable_sets (to_set, from_set) + struct variable_set *to_set, *from_set; { - register unsigned int bucket1; - - for (bucket1 = 0; bucket1 < set1->buckets; ++bucket1) - { - register struct variable *v1 = set1->table[bucket1]; - while (v1 != 0) - { - struct variable *next = v1->next; - unsigned int bucket0; - register struct variable *v0; - - if (set1->buckets >= set0->buckets) - bucket0 = bucket1; - else - { - register char *n; - bucket0 = 0; - for (n = v1->name; *n != '\0'; ++n) - HASH (bucket0, *n); - } - bucket0 %= set0->buckets; + struct variable **from_var_slot = (struct variable **) from_set->table.ht_vec; + struct variable **from_var_end = from_var_slot + from_set->table.ht_size; - for (v0 = set0->table[bucket0]; v0 != 0; v0 = v0->next) - if (streq (v0->name, v1->name)) - break; - - if (v0 == 0) - { - /* There is no variable in SET0 with the same name. */ - v1->next = set0->table[bucket0]; - set0->table[bucket0] = v1; - } - else - { - /* The same variable exists in both sets. - SET0 takes precedence. */ - free (v1->value); - free ((char *) v1); - } - - v1 = next; - } - } + for ( ; from_var_slot < from_var_end; from_var_slot++) + if (! HASH_VACANT (*from_var_slot)) + { + struct variable *from_var = *from_var_slot; + struct variable **to_var_slot + = (struct variable **) hash_find_slot (&to_set->table, *from_var_slot); + if (HASH_VACANT (*to_var_slot)) + hash_insert_at (&to_set->table, from_var, to_var_slot); + else + { + /* GKM FIXME: delete in from_set->table */ + free (from_var->value); + free (from_var); + } + } } /* Merge SETLIST1 into SETLIST0, freeing unused storage in SETLIST1. */ @@ -467,7 +446,7 @@ define_automatic_variables () char buf[200]; sprintf (buf, "%u", makelevel); - (void) define_variable ("MAKELEVEL", 9, buf, o_env, 0); + (void) define_variable (MAKELEVEL_NAME, MAKELEVEL_LENGTH, buf, o_env, 0); sprintf (buf, "%s%s%s", version_string, @@ -564,184 +543,135 @@ target_environment (file) { struct variable_set_list *set_list; register struct variable_set_list *s; - struct variable_bucket - { - struct variable_bucket *next; - struct variable *variable; - }; - struct variable_bucket **table; - unsigned int buckets; - register unsigned int i; - register unsigned nvariables; + struct hash_table table; + struct variable **v_slot; + struct variable **v_end; + struct variable makelevel_key; + char **result_0; char **result; - unsigned int mklev_hash; if (file == 0) set_list = current_variable_set_list; else set_list = file->variables; - /* Find the lowest number of buckets in any set in the list. */ - s = set_list; - buckets = s->set->buckets; - for (s = s->next; s != 0; s = s->next) - if (s->set->buckets < buckets) - buckets = s->set->buckets; - - /* Find the hash value of the bucket `MAKELEVEL' will fall into. */ - { - char *p = "MAKELEVEL"; - mklev_hash = 0; - while (*p != '\0') - HASH (mklev_hash, *p++); - } - - /* Temporarily allocate a table with that many buckets. */ - table = (struct variable_bucket **) - alloca (buckets * sizeof (struct variable_bucket *)); - bzero ((char *) table, buckets * sizeof (struct variable_bucket *)); + hash_init (&table, VARIABLE_BUCKETS, + variable_hash_1, variable_hash_2, variable_hash_cmp); /* Run through all the variable sets in the list, accumulating variables in TABLE. */ - nvariables = 0; for (s = set_list; s != 0; s = s->next) { - register struct variable_set *set = s->set; - for (i = 0; i < set->buckets; ++i) - { - register struct variable *v; - for (v = set->table[i]; v != 0; v = v->next) - { - unsigned int j = i % buckets; - register struct variable_bucket *ov; - register char *p = v->name; - - if (i == mklev_hash % set->buckets - && streq (v->name, "MAKELEVEL")) - /* Don't include MAKELEVEL because it will be - added specially at the end. */ - continue; - - /* If this is a per-target variable and it hasn't been touched - already then look up the global version and take its export - value. */ - if (v->per_target && v->export == v_default) - { - struct variable *gv; - - gv = lookup_variable_in_set(v->name, strlen(v->name), - &global_variable_set); - if (gv) - v->export = gv->export; - } - - switch (v->export) - { - case v_default: - if (v->origin == o_default || v->origin == o_automatic) - /* Only export default variables by explicit request. */ - continue; - - if (! export_all_variables - && v->origin != o_command - && v->origin != o_env && v->origin != o_env_override) - continue; - - if (*p != '_' && (*p < 'A' || *p > 'Z') - && (*p < 'a' || *p > 'z')) - continue; - for (++p; *p != '\0'; ++p) - if (*p != '_' && (*p < 'a' || *p > 'z') - && (*p < 'A' || *p > 'Z') && (*p < '0' || *p > '9')) - continue; - if (*p != '\0') + struct variable_set *set = s->set; + v_slot = (struct variable **) set->table.ht_vec; + v_end = v_slot + set->table.ht_size; + for ( ; v_slot < v_end; v_slot++) + if (! HASH_VACANT (*v_slot)) + { + struct variable **new_slot; + struct variable *v = *v_slot; + char *p = v->name; + + /* If this is a per-target variable and it hasn't been touched + already then look up the global version and take its export + value. */ + if (v->per_target && v->export == v_default) + { + struct variable *gv; + + gv = lookup_variable_in_set (v->name, strlen(v->name), + &global_variable_set); + if (gv) + v->export = gv->export; + } + + switch (v->export) + { + case v_default: + if (v->origin == o_default || v->origin == o_automatic) + /* Only export default variables by explicit request. */ + continue; + + if (! export_all_variables + && v->origin != o_command + && v->origin != o_env && v->origin != o_env_override) + continue; + + if (*p != '_' && (*p < 'A' || *p > 'Z') + && (*p < 'a' || *p > 'z')) + continue; + for (++p; *p != '\0'; ++p) + if (*p != '_' && (*p < 'a' || *p > 'z') + && (*p < 'A' || *p > 'Z') && (*p < '0' || *p > '9')) continue; - break; + if (*p != '\0') + continue; + break; - case v_export: - break; + case v_export: + break; - case v_noexport: - continue; - - case v_ifset: - if (v->origin == o_default) - continue; - break; - } + case v_noexport: + continue; - /* If this was from a different-sized hash table, then - recalculate the bucket it goes in. */ - if (set->buckets != buckets) - { - register char *np; + case v_ifset: + if (v->origin == o_default) + continue; + break; + } - j = 0; - for (np = v->name; *np != '\0'; ++np) - HASH (j, *np); - j %= buckets; - } + new_slot = (struct variable **) hash_find_slot (&table, v); + if (HASH_VACANT (*new_slot)) + hash_insert_at (&table, v, new_slot); + } + } - for (ov = table[j]; ov != 0; ov = ov->next) - if (streq (v->name, ov->variable->name)) - break; + makelevel_key.name = MAKELEVEL_NAME; + makelevel_key.length = MAKELEVEL_LENGTH; + hash_delete (&table, &makelevel_key); - if (ov == 0) - { - register struct variable_bucket *entry; - entry = (struct variable_bucket *) - alloca (sizeof (struct variable_bucket)); - entry->next = table[j]; - entry->variable = v; - table[j] = entry; - ++nvariables; - } - } - } - } + result = result_0 = (char **) xmalloc ((table.ht_fill + 2) * sizeof (char *)); - result = (char **) xmalloc ((nvariables + 2) * sizeof (char *)); - nvariables = 0; - for (i = 0; i < buckets; ++i) - { - register struct variable_bucket *b; - for (b = table[i]; b != 0; b = b->next) - { - register struct variable *v = b->variable; + v_slot = (struct variable **) table.ht_vec; + v_end = v_slot + table.ht_size; + for ( ; v_slot < v_end; v_slot++) + if (! HASH_VACANT (*v_slot)) + { + struct variable *v = *v_slot; - /* If V is recursively expanded and didn't come from the environment, - expand its value. If it came from the environment, it should - go back into the environment unchanged. */ - if (v->recursive - && v->origin != o_env && v->origin != o_env_override) - { - char *value = recursively_expand_for_file (v, file); + /* If V is recursively expanded and didn't come from the environment, + expand its value. If it came from the environment, it should + go back into the environment unchanged. */ + if (v->recursive + && v->origin != o_env && v->origin != o_env_override) + { + char *value = recursively_expand_for_file (v, file); #ifdef WINDOWS32 - if (strcmp(v->name, "Path") == 0 || - strcmp(v->name, "PATH") == 0) - convert_Path_to_windows32(value, ';'); + if (strcmp(v->name, "Path") == 0 || + strcmp(v->name, "PATH") == 0) + convert_Path_to_windows32(value, ';'); #endif - result[nvariables++] = concat (v->name, "=", value); - free (value); - } - else + *result++ = concat (v->name, "=", value); + free (value); + } + else + { #ifdef WINDOWS32 - { if (strcmp(v->name, "Path") == 0 || strcmp(v->name, "PATH") == 0) convert_Path_to_windows32(v->value, ';'); - result[nvariables++] = concat (v->name, "=", v->value); - } -#else - result[nvariables++] = concat (v->name, "=", v->value); #endif - } - } - result[nvariables] = (char *) xmalloc (100); - (void) sprintf (result[nvariables], "MAKELEVEL=%u", makelevel + 1); - result[++nvariables] = 0; + *result++ = concat (v->name, "=", v->value); + } + } + + *result = (char *) xmalloc (100); + (void) sprintf (*result, "%s=%u", MAKELEVEL_NAME, makelevel + 1); + *++result = 0; - return result; + hash_free (&table, 0); + + return result_0; } /* Given a variable, a value, and a flavor, define the variable. @@ -1159,49 +1089,14 @@ print_variable_set (set, prefix) register struct variable_set *set; char *prefix; { - register unsigned int i, nvariables, per_bucket; - register struct variable *v; - - per_bucket = nvariables = 0; - for (i = 0; i < set->buckets; ++i) - { - register unsigned int this_bucket = 0; - - for (v = set->table[i]; v != 0; v = v->next) - { - ++this_bucket; - print_variable (v, prefix); - } + hash_map_arg (&set->table, print_variable, prefix); - nvariables += this_bucket; - if (this_bucket > per_bucket) - per_bucket = this_bucket; - } - - if (nvariables == 0) - puts (_("# No variables.")); - else - { - printf (_("# %u variables in %u hash buckets.\n"), - nvariables, set->buckets); -#ifndef NO_FLOAT - printf (_("# average of %.1f variables per bucket, \ -max %u in one bucket.\n"), - (double) nvariables / (double) set->buckets, - per_bucket); -#else - { - int f = (nvariables * 1000 + 5) / set->buckets; - printf (_("# average of %d.%d variables per bucket, \ -max %u in one bucket.\n"), - f/10, f%10, - per_bucket); - } -#endif - } + fputs (_("# variable set hash-table stats:\n"), stdout); + fputs ("# ", stdout); + hash_print_stats (&set->table, stdout); + putc ('\n', stdout); } - /* Print the data base of variables. */ void @@ -1,5 +1,5 @@ /* Definitions for using variables in GNU Make. -Copyright (C) 1988, 1989, 1990, 1991, 1992 Free Software Foundation, Inc. +Copyright (C) 1988, 1989, 1990, 1991, 1992, 2002 Free Software Foundation, Inc. This file is part of GNU Make. GNU Make is free software; you can redistribute it and/or modify @@ -17,6 +17,8 @@ along with GNU Make; see the file COPYING. If not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ +#include "hash.h" + /* Codes in a variable definition saying where the definition came from. Increasing numeric values signify less-overridable definitions. */ enum variable_origin @@ -50,8 +52,8 @@ enum variable_flavor struct variable { - struct variable *next; /* Link in the chain. */ char *name; /* Variable name. */ + int length; /* strlen (name) */ char *value; /* Variable value. */ struct floc fileinfo; /* Where the variable was defined. */ unsigned int recursive:1; /* Gets recursively re-evaluated. */ @@ -79,8 +81,7 @@ struct variable struct variable_set { - struct variable **table; /* Hash table of variables. */ - unsigned int buckets; /* Number of hash buckets in `table'. */ + struct hash_table table; /* Hash table of variables. */ }; /* Structure that represents a list of variable sets. */ @@ -128,7 +129,8 @@ extern void print_variable_set PARAMS ((struct variable_set *set, char *prefix)) extern void merge_variable_set_lists PARAMS ((struct variable_set_list **setlist0, struct variable_set_list *setlist1)); extern struct variable *do_variable_definition PARAMS ((const struct floc *flocp, const char *name, char *value, enum variable_origin origin, enum variable_flavor flavor, int target_var)); extern struct variable *try_variable_definition PARAMS ((const struct floc *flocp, char *line, enum variable_origin origin, int target_var)); - +extern void init_hash_global_variable_set PARAMS ((void)); +extern void hash_init_function_table PARAMS ((void)); extern struct variable *lookup_variable PARAMS ((const char *name, unsigned int length)); extern struct variable *lookup_variable_in_set PARAMS ((const char *name, unsigned int length, @@ -173,3 +175,6 @@ extern struct variable *define_variable_in_set extern char **target_environment PARAMS ((struct file *file)); extern int export_all_variables; + +#define MAKELEVEL_NAME "MAKELEVEL" +#define MAKELEVEL_LENGTH (sizeof (MAKELEVEL_NAME) - 1) |