diff options
Diffstat (limited to 'variable.c')
| -rw-r--r-- | variable.c | 505 |
1 files changed, 200 insertions, 305 deletions
@@ -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 |