/* Routines for name->symbol lookups in GDB.
- Copyright (C) 2003, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+ Copyright (C) 2003-2017 Free Software Foundation, Inc.
Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
Inc.
along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include "defs.h"
+#include <ctype.h>
#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
* Define a function dict_<op> that looks up <op> in the dict_vector
and calls the appropriate function. Add a declaration for
- dict_<op> to dictionary.h.
-
-*/
+ dict_<op> to dictionary.h. */
/* An enum representing the various implementations of dictionaries.
Used only for debugging. */
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);
};
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. */
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);
add_symbol_nonexpandable, /* add_symbol */
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 */
};
add_symbol_hashed_expandable, /* add_symbol */
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 */
};
add_symbol_nonexpandable, /* add_symbol */
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 */
};
add_symbol_linear_expandable, /* add_symbol */
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 */
};
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. */
}
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;
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;
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. */
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
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;
}
(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. */
}
struct symbol *
-dict_iter_name_first (const struct dictionary *dict,
- const char *name,
- struct dict_iterator *iterator)
+dict_iter_match_first (const struct dictionary *dict,
+ const char *name, symbol_compare_ftype *compare,
+ struct dict_iterator *iterator)
{
- return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
+ return (DICT_VECTOR (dict))->iter_match_first (dict, name,
+ compare, iterator);
}
struct symbol *
-dict_iter_name_next (const char *name, struct dict_iterator *iterator)
+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
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;
}
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;
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;
}
}
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;
next != NULL;
next = next->hash_next)
{
- if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
+ if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
break;
}
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;
}
{
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<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
+ are lower-cased identifiers). The <suffix> (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 <suffix>, 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 *
}
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);
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;
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;
}