aboutsummaryrefslogtreecommitdiff
path: root/gdb/dictionary.h
diff options
context:
space:
mode:
authorPaul N. Hilfinger <hilfinger@adacore.com>2010-10-07 06:53:44 +0000
committerPaul N. Hilfinger <hilfinger@adacore.com>2010-10-07 06:53:44 +0000
commitc4d840bdd6f9e19843bd35835cc08e992fe5e1db (patch)
tree2325091dc2685b2a8c4732104f6e151cce07c486 /gdb/dictionary.h
parent543ecec77cfc25df40fb60a852f7e08df5317635 (diff)
downloadgdb-c4d840bdd6f9e19843bd35835cc08e992fe5e1db.zip
gdb-c4d840bdd6f9e19843bd35835cc08e992fe5e1db.tar.gz
gdb-c4d840bdd6f9e19843bd35835cc08e992fe5e1db.tar.bz2
Extend hashed symbol dictionaries to work with Ada
This patch allows Ada to speed up symbol lookup by using the facilities in dictionary.[ch] for hashed lookups. First, we generalize dictionary search to allow clients to specify any matching function compatible with the hashing function. Next, we modify the hashing algorithm so that symbols that wild-match a name hash to the same value. Finally, we modify Ada symbol lookup to use these facilities. Because this patch touches on a hashing algorithm used by other languages, I took the precaution of doing a speed test on a list of about 12000 identifiers (repeatedly inserting all of them into a table and then doing a lookup on a million names at random, thus testing the speed of the hashing algorithm and how well it distributed names). There was actually a slight speedup, probably as a result of open- coding some of the tests in msymbol_hash_iw. By design, the revised hashing algorithm produces the same results as the original on most "normal" C identifiers. We considered augmenting the dictionary interface still further by allowing different hashing algorithms for different dictionaries, based on the (supposed) language of the symbols in that dictionary. While this produced better isolation of the changes to Ada programs, the additional flexibility also complicated the dictionary interface. I'd prefer to keep things simple for now. Tested w/o regressions on Linux i686. ChangeLog: gdb/ * ada-lang.c (ada_match_name): Use new API for wild_match. (wild_match): Change API to be consistent with that of strcmp_iw; return 0 for a match, and switch operand order. (full_match): New function. (ada_add_block_symbols): Use dict_iter_match_{first,next} for matching to allow use of hashing. * dictionary.c (struct dict_vector): Generalize iter_name_first, iter_name_next ot iter_match_first, iter_match_next. (iter_name_first_hashed): Replace with iter_match_first_hashed. (iter_name_next_hashed): Replace with iter_match_next_hashed. (iter_name_first_linear): Replace with iter_match_first_linear. (iter_name_next_linear): Replace with iter_match_next_linear. (dict_iter_name_first): Re-implement to use dict_iter_match_first. (dict_iter_name_next): Re-implement to use dict_iter_match_next. (dict_iter_match_first): New function. (dict_iter_match_next): New function. (dict_hash): New function. * dictionary.h (dict_iter_match_first, dict_iter_match_next): Declare. * psymtab.c (ada_lookup_partial_symbol): Use new wild_match API.
Diffstat (limited to 'gdb/dictionary.h')
-rw-r--r--gdb/dictionary.h25
1 files changed, 25 insertions, 0 deletions
diff --git a/gdb/dictionary.h b/gdb/dictionary.h
index 2242a79..f7d3035 100644
--- a/gdb/dictionary.h
+++ b/gdb/dictionary.h
@@ -134,6 +134,31 @@ extern struct symbol *dict_iter_name_first (const struct dictionary *dict,
extern struct symbol *dict_iter_name_next (const char *name,
struct dict_iterator *iterator);
+/* Initialize ITERATOR to point at the first symbol in DICT whose
+ SYMBOL_SEARCH_NAME is NAME, as tested using COMPARE (which must use
+ the same conventions as strcmp_iw and be compatible with any
+ dictionary hashing function), and return that first symbol, or NULL
+ if there are no such symbols. */
+
+extern struct symbol *dict_iter_match_first (const struct dictionary *dict,
+ const char *name,
+ int (*compare) (const char*,
+ const char *),
+ struct dict_iterator *iterator);
+
+/* Advance ITERATOR to point at the next symbol in DICT whose
+ SYMBOL_SEARCH_NAME is NAME, as tested using COMPARE (see
+ dict_iter_match_first), or NULL if there are no more such symbols.
+ Don't call this if you've previously received NULL from
+ dict_iterator_match_first or dict_iterator_match_next on this
+ iteration. And don't call it unless ITERATOR was created by a
+ previous call to dict_iter_match_first with the same NAME and COMPARE. */
+
+extern struct symbol *dict_iter_match_next (const char *name,
+ int (*compare) (const char*,
+ const char *),
+ struct dict_iterator *iterator);
+
/* Return some notion of the size of the dictionary: the number of
symbols if we have that, the number of hash buckets otherwise. */