X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=gdb%2Fdictionary.c;h=a6f80dca50f56f825b377ba87783c60bc13057ab;hb=a12ac51333cf97f4da0597d049cc694b4535e7dd;hp=e916a73b10abfac4cfc67ee5b07ed3452f7ef738;hpb=9b254dd1ce46c19dde1dde5b8d1e22e862dfacce;p=deliverable%2Fbinutils-gdb.git diff --git a/gdb/dictionary.c b/gdb/dictionary.c index e916a73b10..a6f80dca50 100644 --- a/gdb/dictionary.c +++ b/gdb/dictionary.c @@ -1,6 +1,6 @@ /* Routines for name->symbol lookups in GDB. - Copyright (C) 2003, 2007, 2008 Free Software Foundation, Inc. + Copyright (C) 2003-2016 Free Software Foundation, Inc. Contributed by David Carlton and by Kealia, Inc. @@ -21,10 +21,10 @@ along with this program. If not, see . */ #include "defs.h" +#include #include "gdb_obstack.h" #include "symtab.h" #include "buildsym.h" -#include "gdb_assert.h" #include "dictionary.h" /* This file implements dictionaries, which are tables that associate @@ -81,9 +81,7 @@ * Define a function dict_ that looks up in the dict_vector and calls the appropriate function. Add a declaration for - dict_ to dictionary.h. - -*/ + dict_ to dictionary.h. */ /* An enum representing the various implementations of dictionaries. Used only for debugging. */ @@ -116,11 +114,13 @@ struct dict_vector struct dict_iterator *iterator); struct symbol *(*iterator_next) (struct dict_iterator *iterator); /* Functions to iterate over symbols with a given name. */ - struct symbol *(*iter_name_first) (const struct dictionary *dict, - const char *name, + struct symbol *(*iter_match_first) (const struct dictionary *dict, + const char *name, + symbol_compare_ftype *equiv, + struct dict_iterator *iterator); + struct symbol *(*iter_match_next) (const char *name, + symbol_compare_ftype *equiv, struct dict_iterator *iterator); - struct symbol *(*iter_name_next) (const char *name, - struct dict_iterator *iterator); /* A size function, for maint print symtabs. */ int (*size) (const struct dictionary *dict); }; @@ -236,12 +236,16 @@ static struct symbol *iterator_first_hashed (const struct dictionary *dict, static struct symbol *iterator_next_hashed (struct dict_iterator *iterator); -static struct symbol *iter_name_first_hashed (const struct dictionary *dict, - const char *name, +static struct symbol *iter_match_first_hashed (const struct dictionary *dict, + const char *name, + symbol_compare_ftype *compare, struct dict_iterator *iterator); -static struct symbol *iter_name_next_hashed (const char *name, - struct dict_iterator *iterator); +static struct symbol *iter_match_next_hashed (const char *name, + symbol_compare_ftype *compare, + struct dict_iterator *iterator); + +static unsigned int dict_hash (const char *string); /* Functions only for DICT_HASHED. */ @@ -264,12 +268,14 @@ static struct symbol *iterator_first_linear (const struct dictionary *dict, static struct symbol *iterator_next_linear (struct dict_iterator *iterator); -static struct symbol *iter_name_first_linear (const struct dictionary *dict, - const char *name, - struct dict_iterator *iterator); +static struct symbol *iter_match_first_linear (const struct dictionary *dict, + const char *name, + symbol_compare_ftype *compare, + struct dict_iterator *iterator); -static struct symbol *iter_name_next_linear (const char *name, - struct dict_iterator *iterator); +static struct symbol *iter_match_next_linear (const char *name, + symbol_compare_ftype *compare, + struct dict_iterator *iterator); static int size_linear (const struct dictionary *dict); @@ -287,10 +293,10 @@ static const struct dict_vector dict_hashed_vector = DICT_HASHED, /* type */ free_obstack, /* free */ add_symbol_nonexpandable, /* add_symbol */ - iterator_first_hashed, /* iteractor_first */ + iterator_first_hashed, /* iterator_first */ iterator_next_hashed, /* iterator_next */ - iter_name_first_hashed, /* iter_name_first */ - iter_name_next_hashed, /* iter_name_next */ + iter_match_first_hashed, /* iter_name_first */ + iter_match_next_hashed, /* iter_name_next */ size_hashed, /* size */ }; @@ -299,10 +305,10 @@ static const struct dict_vector dict_hashed_expandable_vector = DICT_HASHED_EXPANDABLE, /* type */ free_hashed_expandable, /* free */ add_symbol_hashed_expandable, /* add_symbol */ - iterator_first_hashed, /* iteractor_first */ + iterator_first_hashed, /* iterator_first */ iterator_next_hashed, /* iterator_next */ - iter_name_first_hashed, /* iter_name_first */ - iter_name_next_hashed, /* iter_name_next */ + iter_match_first_hashed, /* iter_name_first */ + iter_match_next_hashed, /* iter_name_next */ size_hashed_expandable, /* size */ }; @@ -311,10 +317,10 @@ static const struct dict_vector dict_linear_vector = DICT_LINEAR, /* type */ free_obstack, /* free */ add_symbol_nonexpandable, /* add_symbol */ - iterator_first_linear, /* iteractor_first */ + iterator_first_linear, /* iterator_first */ iterator_next_linear, /* iterator_next */ - iter_name_first_linear, /* iter_name_first */ - iter_name_next_linear, /* iter_name_next */ + iter_match_first_linear, /* iter_name_first */ + iter_match_next_linear, /* iter_name_next */ size_linear, /* size */ }; @@ -323,10 +329,10 @@ static const struct dict_vector dict_linear_expandable_vector = DICT_LINEAR_EXPANDABLE, /* type */ free_linear_expandable, /* free */ add_symbol_linear_expandable, /* add_symbol */ - iterator_first_linear, /* iteractor_first */ + iterator_first_linear, /* iterator_first */ iterator_next_linear, /* iterator_next */ - iter_name_first_linear, /* iter_name_first */ - iter_name_next_linear, /* iter_name_next */ + iter_match_first_linear, /* iter_name_first */ + iter_match_next_linear, /* iter_name_next */ size_linear, /* size */ }; @@ -355,7 +361,7 @@ dict_create_hashed (struct obstack *obstack, struct symbol **buckets; const struct pending *list_counter; - retval = obstack_alloc (obstack, sizeof (struct dictionary)); + retval = XOBNEW (obstack, struct dictionary); DICT_VECTOR (retval) = &dict_hashed_vector; /* Calculate the number of symbols, and allocate space for them. */ @@ -367,7 +373,7 @@ dict_create_hashed (struct obstack *obstack, } nbuckets = DICT_HASHTABLE_SIZE (nsyms); DICT_HASHED_NBUCKETS (retval) = nbuckets; - buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *)); + buckets = XOBNEWVEC (obstack, struct symbol *, nbuckets); memset (buckets, 0, nbuckets * sizeof (struct symbol *)); DICT_HASHED_BUCKETS (retval) = buckets; @@ -393,13 +399,12 @@ dict_create_hashed (struct obstack *obstack, extern struct dictionary * dict_create_hashed_expandable (void) { - struct dictionary *retval; + struct dictionary *retval = XNEW (struct dictionary); - retval = xmalloc (sizeof (struct dictionary)); DICT_VECTOR (retval) = &dict_hashed_expandable_vector; DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY; - DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY, - sizeof (struct symbol *)); + DICT_HASHED_BUCKETS (retval) = XCNEWVEC (struct symbol *, + DICT_EXPANDABLE_INITIAL_CAPACITY); DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0; return retval; @@ -419,7 +424,7 @@ dict_create_linear (struct obstack *obstack, struct symbol **syms; const struct pending *list_counter; - retval = obstack_alloc (obstack, sizeof (struct dictionary)); + retval = XOBNEW (obstack, struct dictionary); DICT_VECTOR (retval) = &dict_linear_vector; /* Calculate the number of symbols, and allocate space for them. */ @@ -430,7 +435,7 @@ dict_create_linear (struct obstack *obstack, nsyms += list_counter->nsyms; } DICT_LINEAR_NSYMS (retval) = nsyms; - syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *)); + syms = XOBNEWVEC (obstack, struct symbol *, nsyms ); DICT_LINEAR_SYMS (retval) = syms; /* Now fill in the symbols. Start filling in from the back, so as @@ -458,16 +463,13 @@ dict_create_linear (struct obstack *obstack, struct dictionary * dict_create_linear_expandable (void) { - struct dictionary *retval; + struct dictionary *retval = XNEW (struct dictionary); - retval = xmalloc (sizeof (struct dictionary)); DICT_VECTOR (retval) = &dict_linear_expandable_vector; DICT_LINEAR_NSYMS (retval) = 0; - DICT_LINEAR_EXPANDABLE_CAPACITY (retval) - = DICT_EXPANDABLE_INITIAL_CAPACITY; + DICT_LINEAR_EXPANDABLE_CAPACITY (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY; DICT_LINEAR_SYMS (retval) - = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval) - * sizeof (struct symbol *)); + = XNEWVEC (struct symbol *, DICT_LINEAR_EXPANDABLE_CAPACITY (retval)); return retval; } @@ -491,6 +493,22 @@ dict_add_symbol (struct dictionary *dict, struct symbol *sym) (DICT_VECTOR (dict))->add_symbol (dict, sym); } +/* Utility to add a list of symbols to a dictionary. + DICT must be an expandable dictionary. */ + +void +dict_add_pending (struct dictionary *dict, const struct pending *symbol_list) +{ + const struct pending *list; + int i; + + for (list = symbol_list; list != NULL; list = list->next) + { + for (i = 0; i < list->nsyms; ++i) + dict_add_symbol (dict, list->symbol[i]); + } +} + /* Initialize ITERATOR to point at the first symbol in DICT, and return that first symbol, or NULL if DICT is empty. */ @@ -516,14 +534,30 @@ dict_iter_name_first (const struct dictionary *dict, const char *name, struct dict_iterator *iterator) { - return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator); + return dict_iter_match_first (dict, name, strcmp_iw, iterator); } struct symbol * dict_iter_name_next (const char *name, struct dict_iterator *iterator) +{ + return dict_iter_match_next (name, strcmp_iw, iterator); +} + +struct symbol * +dict_iter_match_first (const struct dictionary *dict, + const char *name, symbol_compare_ftype *compare, + struct dict_iterator *iterator) +{ + return (DICT_VECTOR (dict))->iter_match_first (dict, name, + compare, iterator); +} + +struct symbol * +dict_iter_match_next (const char *name, symbol_compare_ftype *compare, + struct dict_iterator *iterator) { return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) - ->iter_name_next (name, iterator); + ->iter_match_next (name, compare, iterator); } int @@ -578,7 +612,6 @@ iterator_first_hashed (const struct dictionary *dict, static struct symbol * iterator_next_hashed (struct dict_iterator *iterator) { - const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); struct symbol *next; next = DICT_ITERATOR_CURRENT (iterator)->hash_next; @@ -615,12 +648,11 @@ iterator_hashed_advance (struct dict_iterator *iterator) } static struct symbol * -iter_name_first_hashed (const struct dictionary *dict, - const char *name, - struct dict_iterator *iterator) +iter_match_first_hashed (const struct dictionary *dict, const char *name, + symbol_compare_ftype *compare, + struct dict_iterator *iterator) { - unsigned int hash_index - = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict); + unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict); struct symbol *sym; DICT_ITERATOR_DICT (iterator) = dict; @@ -633,8 +665,8 @@ iter_name_first_hashed (const struct dictionary *dict, sym != NULL; sym = sym->hash_next) { - /* Warning: the order of arguments to strcmp_iw matters! */ - if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0) + /* Warning: the order of arguments to compare matters! */ + if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0) { break; } @@ -646,7 +678,8 @@ iter_name_first_hashed (const struct dictionary *dict, } static struct symbol * -iter_name_next_hashed (const char *name, struct dict_iterator *iterator) +iter_match_next_hashed (const char *name, symbol_compare_ftype *compare, + struct dict_iterator *iterator) { struct symbol *next; @@ -654,7 +687,7 @@ iter_name_next_hashed (const char *name, struct dict_iterator *iterator) next != NULL; next = next->hash_next) { - if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0) + if (compare (SYMBOL_SEARCH_NAME (next), name) == 0) break; } @@ -672,8 +705,8 @@ insert_symbol_hashed (struct dictionary *dict, unsigned int hash_index; struct symbol **buckets = DICT_HASHED_BUCKETS (dict); - hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym)) - % DICT_HASHED_NBUCKETS (dict)); + hash_index = + dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict); sym->hash_next = buckets[hash_index]; buckets[hash_index] = sym; } @@ -717,33 +750,110 @@ expand_hashtable (struct dictionary *dict) { int old_nbuckets = DICT_HASHED_NBUCKETS (dict); struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict); - int new_nbuckets = 2*old_nbuckets + 1; - struct symbol **new_buckets = xcalloc (new_nbuckets, - sizeof (struct symbol *)); + int new_nbuckets = 2 * old_nbuckets + 1; + struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets); int i; DICT_HASHED_NBUCKETS (dict) = new_nbuckets; DICT_HASHED_BUCKETS (dict) = new_buckets; - for (i = 0; i < old_nbuckets; ++i) { - struct symbol *sym, *next_sym; - - sym = old_buckets[i]; - if (sym != NULL) { - for (next_sym = sym->hash_next; - next_sym != NULL; - next_sym = sym->hash_next) { - insert_symbol_hashed (dict, sym); - sym = next_sym; - } + for (i = 0; i < old_nbuckets; ++i) + { + struct symbol *sym, *next_sym; - insert_symbol_hashed (dict, sym); + sym = old_buckets[i]; + if (sym != NULL) + { + for (next_sym = sym->hash_next; + next_sym != NULL; + next_sym = sym->hash_next) + { + insert_symbol_hashed (dict, sym); + sym = next_sym; + } + + insert_symbol_hashed (dict, sym); + } } - } xfree (old_buckets); } +/* Produce an unsigned hash value from STRING0 that is consistent + with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match. + That is, two identifiers equivalent according to any of those three + comparison operators hash to the same value. */ + +static unsigned int +dict_hash (const char *string0) +{ + /* The Ada-encoded version of a name P1.P2...Pn has either the form + P1__P2__...Pn or _ada_P1__P2__...Pn (where the Pi + are lower-cased identifiers). The (which can be empty) + encodes additional information about the denoted entity. This + routine hashes such names to msymbol_hash_iw(Pn). It actually + does this for a superset of both valid Pi and of , but + in other cases it simply returns msymbol_hash_iw(STRING0). */ + + const char *string; + unsigned int hash; + + string = string0; + if (*string == '_') + { + if (startswith (string, "_ada_")) + string += 5; + else + return msymbol_hash_iw (string0); + } + + hash = 0; + while (*string) + { + /* Ignore "TKB" suffixes. + + These are used by Ada for subprograms implementing a task body. + For instance for a task T inside package Pck, the name of the + subprogram implementing T's body is `pck__tTKB'. We need to + ignore the "TKB" suffix because searches for this task body + subprogram are going to be performed using `pck__t' (the encoded + version of the natural name `pck.t'). */ + if (strcmp (string, "TKB") == 0) + return hash; + + switch (*string) + { + case '$': + case '.': + case 'X': + if (string0 == string) + return msymbol_hash_iw (string0); + else + return hash; + case ' ': + case '(': + return msymbol_hash_iw (string0); + case '_': + if (string[1] == '_' && string != string0) + { + int c = string[2]; + + if ((c < 'a' || c > 'z') && c != 'O') + return hash; + hash = 0; + string += 2; + break; + } + /* FALL THROUGH */ + default: + hash = SYMBOL_HASH_NEXT (hash, *string); + string += 1; + break; + } + } + return hash; +} + /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */ static struct symbol * @@ -767,18 +877,19 @@ iterator_next_linear (struct dict_iterator *iterator) } static struct symbol * -iter_name_first_linear (const struct dictionary *dict, - const char *name, - struct dict_iterator *iterator) +iter_match_first_linear (const struct dictionary *dict, + const char *name, symbol_compare_ftype *compare, + struct dict_iterator *iterator) { DICT_ITERATOR_DICT (iterator) = dict; DICT_ITERATOR_INDEX (iterator) = -1; - return iter_name_next_linear (name, iterator); + return iter_match_next_linear (name, compare, iterator); } static struct symbol * -iter_name_next_linear (const char *name, struct dict_iterator *iterator) +iter_match_next_linear (const char *name, symbol_compare_ftype *compare, + struct dict_iterator *iterator) { const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); int i, nsyms = DICT_LINEAR_NSYMS (dict); @@ -787,7 +898,7 @@ iter_name_next_linear (const char *name, struct dict_iterator *iterator) for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i) { sym = DICT_LINEAR_SYM (dict, i); - if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0) + if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0) { retval = sym; break; @@ -822,13 +933,13 @@ add_symbol_linear_expandable (struct dictionary *dict, int nsyms = ++DICT_LINEAR_NSYMS (dict); /* Do we have enough room? If not, grow it. */ - if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) { - DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2; - DICT_LINEAR_SYMS (dict) - = xrealloc (DICT_LINEAR_SYMS (dict), - DICT_LINEAR_EXPANDABLE_CAPACITY (dict) - * sizeof (struct symbol *)); - } + if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) + { + DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2; + DICT_LINEAR_SYMS (dict) + = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict), + DICT_LINEAR_EXPANDABLE_CAPACITY (dict)); + } DICT_LINEAR_SYM (dict, nsyms - 1) = sym; }