1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282 |
- /* Routines for name->symbol lookups in GDB.
-
- Copyright (C) 2003-2022 Free Software Foundation, Inc.
- Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
- Inc.
- This file is part of GDB.
- 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 3 of the License, 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, see <http://www.gnu.org/licenses/>. */
- #include "defs.h"
- #include <ctype.h>
- #include "gdbsupport/gdb_obstack.h"
- #include "symtab.h"
- #include "buildsym.h"
- #include "dictionary.h"
- #include "safe-ctype.h"
- #include <unordered_map>
- #include "language.h"
- /* This file implements dictionaries, which are tables that associate
- symbols to names. They are represented by an opaque type 'struct
- dictionary'. That type has various internal implementations, which
- you can choose between depending on what properties you need
- (e.g. fast lookup, order-preserving, expandable).
- Each dictionary starts with a 'virtual function table' that
- contains the functions that actually implement the various
- operations that dictionaries provide. (Note, however, that, for
- the sake of client code, we also provide some functions that can be
- implemented generically in terms of the functions in the vtable.)
- To add a new dictionary implementation <impl>, what you should do
- is:
- * Add a new element DICT_<IMPL> to dict_type.
-
- * Create a new structure dictionary_<impl>. If your new
- implementation is a variant of an existing one, make sure that
- their structs have the same initial data members. Define accessor
- macros for your new data members.
- * Implement all the functions in dict_vector as static functions,
- whose name is the same as the corresponding member of dict_vector
- plus _<impl>. You don't have to do this for those members where
- you can reuse existing generic functions
- (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
- your new implementation is a variant of an existing implementation
- and where the variant doesn't affect the member function in
- question.
- * Define a static const struct dict_vector dict_<impl>_vector.
- * Define a function dict_create_<impl> to create these
- gizmos. Add its declaration to dictionary.h.
- To add a new operation <op> on all existing implementations, what
- you should do is:
- * Add a new member <op> to struct dict_vector.
- * If there is useful generic behavior <op>, define a static
- function <op>_something_informative that implements that behavior.
- (E.g. add_symbol_nonexpandable, free_obstack.)
- * For every implementation <impl> that should have its own specific
- behavior for <op>, define a static function <op>_<impl>
- implementing it.
- * Modify all existing dict_vector_<impl>'s to include the appropriate
- member.
- * 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. */
- /* An enum representing the various implementations of dictionaries.
- Used only for debugging. */
- enum dict_type
- {
- /* Symbols are stored in a fixed-size hash table. */
- DICT_HASHED,
- /* Symbols are stored in an expandable hash table. */
- DICT_HASHED_EXPANDABLE,
- /* Symbols are stored in a fixed-size array. */
- DICT_LINEAR,
- /* Symbols are stored in an expandable array. */
- DICT_LINEAR_EXPANDABLE
- };
- /* The virtual function table. */
- struct dict_vector
- {
- /* The type of the dictionary. This is only here to make debugging
- a bit easier; it's not actually used. */
- enum dict_type type;
- /* The function to free a dictionary. */
- void (*free) (struct dictionary *dict);
- /* Add a symbol to a dictionary, if possible. */
- void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
- /* Iterator functions. */
- struct symbol *(*iterator_first) (const struct dictionary *dict,
- struct dict_iterator *iterator);
- struct symbol *(*iterator_next) (struct dict_iterator *iterator);
- /* Functions to iterate over symbols with a given name. */
- struct symbol *(*iter_match_first) (const struct dictionary *dict,
- const lookup_name_info &name,
- struct dict_iterator *iterator);
- struct symbol *(*iter_match_next) (const lookup_name_info &name,
- struct dict_iterator *iterator);
- /* A size function, for maint print symtabs. */
- int (*size) (const struct dictionary *dict);
- };
- /* Now comes the structs used to store the data for different
- implementations. If two implementations have data in common, put
- the common data at the top of their structs, ordered in the same
- way. */
- struct dictionary_hashed
- {
- int nbuckets;
- struct symbol **buckets;
- };
- struct dictionary_hashed_expandable
- {
- /* How many buckets we currently have. */
- int nbuckets;
- struct symbol **buckets;
- /* How many syms we currently have; we need this so we will know
- when to add more buckets. */
- int nsyms;
- };
- struct dictionary_linear
- {
- int nsyms;
- struct symbol **syms;
- };
- struct dictionary_linear_expandable
- {
- /* How many symbols we currently have. */
- int nsyms;
- struct symbol **syms;
- /* How many symbols we can store before needing to reallocate. */
- int capacity;
- };
- /* And now, the star of our show. */
- struct dictionary
- {
- const struct language_defn *language;
- const struct dict_vector *vector;
- union
- {
- struct dictionary_hashed hashed;
- struct dictionary_hashed_expandable hashed_expandable;
- struct dictionary_linear linear;
- struct dictionary_linear_expandable linear_expandable;
- }
- data;
- };
- /* Accessor macros. */
- #define DICT_VECTOR(d) (d)->vector
- #define DICT_LANGUAGE(d) (d)->language
- /* These can be used for DICT_HASHED_EXPANDABLE, too. */
- #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
- #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
- #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
- #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
- /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
- #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
- #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
- #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
- #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
- (d)->data.linear_expandable.capacity
- /* The initial size of a DICT_*_EXPANDABLE dictionary. */
- #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
- /* This calculates the number of buckets we'll use in a hashtable,
- given the number of symbols that it will contain. */
- #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
- /* Accessor macros for dict_iterators; they're here rather than
- dictionary.h because code elsewhere should treat dict_iterators as
- opaque. */
- /* The dictionary that the iterator is associated to. */
- #define DICT_ITERATOR_DICT(iter) (iter)->dict
- /* For linear dictionaries, the index of the last symbol returned; for
- hashed dictionaries, the bucket of the last symbol returned. */
- #define DICT_ITERATOR_INDEX(iter) (iter)->index
- /* For hashed dictionaries, this points to the last symbol returned;
- otherwise, this is unused. */
- #define DICT_ITERATOR_CURRENT(iter) (iter)->current
- /* Declarations of functions for vectors. */
- /* Functions that might work across a range of dictionary types. */
- static void add_symbol_nonexpandable (struct dictionary *dict,
- struct symbol *sym);
- static void free_obstack (struct dictionary *dict);
- /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
- dictionaries. */
- static struct symbol *iterator_first_hashed (const struct dictionary *dict,
- struct dict_iterator *iterator);
- static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
- static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
- const lookup_name_info &name,
- struct dict_iterator *iterator);
- static struct symbol *iter_match_next_hashed (const lookup_name_info &name,
- struct dict_iterator *iterator);
- /* Functions only for DICT_HASHED. */
- static int size_hashed (const struct dictionary *dict);
- /* Functions only for DICT_HASHED_EXPANDABLE. */
- static void free_hashed_expandable (struct dictionary *dict);
- static void add_symbol_hashed_expandable (struct dictionary *dict,
- struct symbol *sym);
- static int size_hashed_expandable (const struct dictionary *dict);
- /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
- dictionaries. */
- static struct symbol *iterator_first_linear (const struct dictionary *dict,
- struct dict_iterator *iterator);
- static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
- static struct symbol *iter_match_first_linear (const struct dictionary *dict,
- const lookup_name_info &name,
- struct dict_iterator *iterator);
- static struct symbol *iter_match_next_linear (const lookup_name_info &name,
- struct dict_iterator *iterator);
- static int size_linear (const struct dictionary *dict);
- /* Functions only for DICT_LINEAR_EXPANDABLE. */
- static void free_linear_expandable (struct dictionary *dict);
- static void add_symbol_linear_expandable (struct dictionary *dict,
- struct symbol *sym);
- /* Various vectors that we'll actually use. */
- static const struct dict_vector dict_hashed_vector =
- {
- DICT_HASHED, /* type */
- free_obstack, /* free */
- add_symbol_nonexpandable, /* add_symbol */
- iterator_first_hashed, /* iterator_first */
- iterator_next_hashed, /* iterator_next */
- iter_match_first_hashed, /* iter_name_first */
- iter_match_next_hashed, /* iter_name_next */
- size_hashed, /* size */
- };
- 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, /* iterator_first */
- iterator_next_hashed, /* iterator_next */
- iter_match_first_hashed, /* iter_name_first */
- iter_match_next_hashed, /* iter_name_next */
- size_hashed_expandable, /* size */
- };
- static const struct dict_vector dict_linear_vector =
- {
- DICT_LINEAR, /* type */
- free_obstack, /* free */
- add_symbol_nonexpandable, /* add_symbol */
- iterator_first_linear, /* iterator_first */
- iterator_next_linear, /* iterator_next */
- iter_match_first_linear, /* iter_name_first */
- iter_match_next_linear, /* iter_name_next */
- size_linear, /* size */
- };
- 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, /* iterator_first */
- iterator_next_linear, /* iterator_next */
- iter_match_first_linear, /* iter_name_first */
- iter_match_next_linear, /* iter_name_next */
- size_linear, /* size */
- };
- /* Declarations of helper functions (i.e. ones that don't go into
- vectors). */
- static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
- static void insert_symbol_hashed (struct dictionary *dict,
- struct symbol *sym);
- static void expand_hashtable (struct dictionary *dict);
- /* The creation functions. */
- /* Create a hashed dictionary of a given language. */
- static struct dictionary *
- dict_create_hashed (struct obstack *obstack,
- enum language language,
- const std::vector<symbol *> &symbol_list)
- {
- /* Allocate the dictionary. */
- struct dictionary *retval = XOBNEW (obstack, struct dictionary);
- DICT_VECTOR (retval) = &dict_hashed_vector;
- DICT_LANGUAGE (retval) = language_def (language);
- /* Allocate space for symbols. */
- int nsyms = symbol_list.size ();
- int nbuckets = DICT_HASHTABLE_SIZE (nsyms);
- DICT_HASHED_NBUCKETS (retval) = nbuckets;
- struct symbol **buckets = XOBNEWVEC (obstack, struct symbol *, nbuckets);
- memset (buckets, 0, nbuckets * sizeof (struct symbol *));
- DICT_HASHED_BUCKETS (retval) = buckets;
- /* Now fill the buckets. */
- for (const auto &sym : symbol_list)
- insert_symbol_hashed (retval, sym);
- return retval;
- }
- /* Create an expandable hashed dictionary of a given language. */
- static struct dictionary *
- dict_create_hashed_expandable (enum language language)
- {
- struct dictionary *retval = XNEW (struct dictionary);
- DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
- DICT_LANGUAGE (retval) = language_def (language);
- DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
- DICT_HASHED_BUCKETS (retval) = XCNEWVEC (struct symbol *,
- DICT_EXPANDABLE_INITIAL_CAPACITY);
- DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
- return retval;
- }
- /* Create a linear dictionary of a given language. */
- static struct dictionary *
- dict_create_linear (struct obstack *obstack,
- enum language language,
- const std::vector<symbol *> &symbol_list)
- {
- struct dictionary *retval = XOBNEW (obstack, struct dictionary);
- DICT_VECTOR (retval) = &dict_linear_vector;
- DICT_LANGUAGE (retval) = language_def (language);
- /* Allocate space for symbols. */
- int nsyms = symbol_list.size ();
- DICT_LINEAR_NSYMS (retval) = nsyms;
- struct symbol **syms = XOBNEWVEC (obstack, struct symbol *, nsyms);
- DICT_LINEAR_SYMS (retval) = syms;
- /* Now fill in the symbols. */
- int idx = nsyms - 1;
- for (const auto &sym : symbol_list)
- syms[idx--] = sym;
- return retval;
- }
- /* Create an expandable linear dictionary of a given language. */
- static struct dictionary *
- dict_create_linear_expandable (enum language language)
- {
- struct dictionary *retval = XNEW (struct dictionary);
- DICT_VECTOR (retval) = &dict_linear_expandable_vector;
- DICT_LANGUAGE (retval) = language_def (language);
- DICT_LINEAR_NSYMS (retval) = 0;
- DICT_LINEAR_EXPANDABLE_CAPACITY (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
- DICT_LINEAR_SYMS (retval)
- = XNEWVEC (struct symbol *, DICT_LINEAR_EXPANDABLE_CAPACITY (retval));
- return retval;
- }
- /* The functions providing the dictionary interface. */
- /* Free the memory used by a dictionary that's not on an obstack. (If
- any.) */
- static void
- dict_free (struct dictionary *dict)
- {
- (DICT_VECTOR (dict))->free (dict);
- }
- /* Add SYM to DICT. DICT had better be expandable. */
- static void
- 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. */
- static void
- dict_add_pending (struct dictionary *dict,
- const std::vector<symbol *> &symbol_list)
- {
- /* Preserve ordering by reversing the list. */
- for (auto sym = symbol_list.rbegin (); sym != symbol_list.rend (); ++sym)
- dict_add_symbol (dict, *sym);
- }
- /* Initialize ITERATOR to point at the first symbol in DICT, and
- return that first symbol, or NULL if DICT is empty. */
- static struct symbol *
- dict_iterator_first (const struct dictionary *dict,
- struct dict_iterator *iterator)
- {
- return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
- }
- /* Advance ITERATOR, and return the next symbol, or NULL if there are
- no more symbols. */
- static struct symbol *
- dict_iterator_next (struct dict_iterator *iterator)
- {
- return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
- ->iterator_next (iterator);
- }
- static struct symbol *
- dict_iter_match_first (const struct dictionary *dict,
- const lookup_name_info &name,
- struct dict_iterator *iterator)
- {
- return (DICT_VECTOR (dict))->iter_match_first (dict, name, iterator);
- }
- static struct symbol *
- dict_iter_match_next (const lookup_name_info &name,
- struct dict_iterator *iterator)
- {
- return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
- ->iter_match_next (name, iterator);
- }
- static int
- dict_size (const struct dictionary *dict)
- {
- return (DICT_VECTOR (dict))->size (dict);
- }
-
- /* Now come functions (well, one function, currently) that are
- implemented generically by means of the vtable. Typically, they're
- rarely used. */
- /* The functions implementing the dictionary interface. */
- /* Generic functions, where appropriate. */
- static void
- free_obstack (struct dictionary *dict)
- {
- /* Do nothing! */
- }
- static void
- add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
- {
- internal_error (__FILE__, __LINE__,
- _("dict_add_symbol: non-expandable dictionary"));
- }
- /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
- static struct symbol *
- iterator_first_hashed (const struct dictionary *dict,
- struct dict_iterator *iterator)
- {
- DICT_ITERATOR_DICT (iterator) = dict;
- DICT_ITERATOR_INDEX (iterator) = -1;
- return iterator_hashed_advance (iterator);
- }
- static struct symbol *
- iterator_next_hashed (struct dict_iterator *iterator)
- {
- struct symbol *next;
- next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
-
- if (next == NULL)
- return iterator_hashed_advance (iterator);
- else
- {
- DICT_ITERATOR_CURRENT (iterator) = next;
- return next;
- }
- }
- static struct symbol *
- iterator_hashed_advance (struct dict_iterator *iterator)
- {
- const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
- int nbuckets = DICT_HASHED_NBUCKETS (dict);
- int i;
- for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
- {
- struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
-
- if (sym != NULL)
- {
- DICT_ITERATOR_INDEX (iterator) = i;
- DICT_ITERATOR_CURRENT (iterator) = sym;
- return sym;
- }
- }
- return NULL;
- }
- static struct symbol *
- iter_match_first_hashed (const struct dictionary *dict,
- const lookup_name_info &name,
- struct dict_iterator *iterator)
- {
- const language_defn *lang = DICT_LANGUAGE (dict);
- unsigned int hash_index = (name.search_name_hash (lang->la_language)
- % DICT_HASHED_NBUCKETS (dict));
- symbol_name_matcher_ftype *matches_name
- = lang->get_symbol_name_matcher (name);
- struct symbol *sym;
- DICT_ITERATOR_DICT (iterator) = dict;
- /* Loop through the symbols in the given bucket, breaking when SYM
- first matches. If SYM never matches, it will be set to NULL;
- either way, we have the right return value. */
-
- for (sym = DICT_HASHED_BUCKET (dict, hash_index);
- sym != NULL;
- sym = sym->hash_next)
- {
- /* Warning: the order of arguments to compare matters! */
- if (matches_name (sym->search_name (), name, NULL))
- break;
- }
- DICT_ITERATOR_CURRENT (iterator) = sym;
- return sym;
- }
- static struct symbol *
- iter_match_next_hashed (const lookup_name_info &name,
- struct dict_iterator *iterator)
- {
- const language_defn *lang = DICT_LANGUAGE (DICT_ITERATOR_DICT (iterator));
- symbol_name_matcher_ftype *matches_name
- = lang->get_symbol_name_matcher (name);
- struct symbol *next;
- for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
- next != NULL;
- next = next->hash_next)
- {
- if (matches_name (next->search_name (), name, NULL))
- break;
- }
- DICT_ITERATOR_CURRENT (iterator) = next;
- return next;
- }
- /* Insert SYM into DICT. */
- static void
- insert_symbol_hashed (struct dictionary *dict,
- struct symbol *sym)
- {
- unsigned int hash_index;
- unsigned int hash;
- struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
- /* We don't want to insert a symbol into a dictionary of a different
- language. The two may not use the same hashing algorithm. */
- gdb_assert (sym->language () == DICT_LANGUAGE (dict)->la_language);
- hash = search_name_hash (sym->language (), sym->search_name ());
- hash_index = hash % DICT_HASHED_NBUCKETS (dict);
- sym->hash_next = buckets[hash_index];
- buckets[hash_index] = sym;
- }
- static int
- size_hashed (const struct dictionary *dict)
- {
- return DICT_HASHED_NBUCKETS (dict);
- }
- /* Functions only for DICT_HASHED_EXPANDABLE. */
- static void
- free_hashed_expandable (struct dictionary *dict)
- {
- xfree (DICT_HASHED_BUCKETS (dict));
- xfree (dict);
- }
- static void
- add_symbol_hashed_expandable (struct dictionary *dict,
- struct symbol *sym)
- {
- int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
- if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
- expand_hashtable (dict);
- insert_symbol_hashed (dict, sym);
- DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
- }
- static int
- size_hashed_expandable (const struct dictionary *dict)
- {
- return DICT_HASHED_EXPANDABLE_NSYMS (dict);
- }
- static void
- 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 = 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;
- }
- insert_symbol_hashed (dict, sym);
- }
- }
- xfree (old_buckets);
- }
- /* See dictionary.h. */
- unsigned int
- language_defn::search_name_hash (const char *string0) const
- {
- /* 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)
- {
- 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 == 'B' && string[3] == '_')
- {
- for (string += 4; ISDIGIT (*string); ++string)
- ;
- continue;
- }
- if ((c < 'a' || c > 'z') && c != 'O')
- return hash;
- hash = 0;
- string += 2;
- continue;
- }
- break;
- case 'T':
- /* 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;
- break;
- }
- hash = SYMBOL_HASH_NEXT (hash, *string);
- string += 1;
- }
- return hash;
- }
- /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
- static struct symbol *
- iterator_first_linear (const struct dictionary *dict,
- struct dict_iterator *iterator)
- {
- DICT_ITERATOR_DICT (iterator) = dict;
- DICT_ITERATOR_INDEX (iterator) = 0;
- return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
- }
- static struct symbol *
- iterator_next_linear (struct dict_iterator *iterator)
- {
- const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
- if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
- return NULL;
- else
- return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
- }
- static struct symbol *
- iter_match_first_linear (const struct dictionary *dict,
- const lookup_name_info &name,
- struct dict_iterator *iterator)
- {
- DICT_ITERATOR_DICT (iterator) = dict;
- DICT_ITERATOR_INDEX (iterator) = -1;
- return iter_match_next_linear (name, iterator);
- }
- static struct symbol *
- iter_match_next_linear (const lookup_name_info &name,
- struct dict_iterator *iterator)
- {
- const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
- const language_defn *lang = DICT_LANGUAGE (dict);
- symbol_name_matcher_ftype *matches_name
- = lang->get_symbol_name_matcher (name);
- int i, nsyms = DICT_LINEAR_NSYMS (dict);
- struct symbol *sym, *retval = NULL;
- for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
- {
- sym = DICT_LINEAR_SYM (dict, i);
- if (matches_name (sym->search_name (), name, NULL))
- {
- retval = sym;
- break;
- }
- }
- DICT_ITERATOR_INDEX (iterator) = i;
-
- return retval;
- }
- static int
- size_linear (const struct dictionary *dict)
- {
- return DICT_LINEAR_NSYMS (dict);
- }
- /* Functions only for DICT_LINEAR_EXPANDABLE. */
- static void
- free_linear_expandable (struct dictionary *dict)
- {
- xfree (DICT_LINEAR_SYMS (dict));
- xfree (dict);
- }
- static void
- add_symbol_linear_expandable (struct dictionary *dict,
- struct symbol *sym)
- {
- 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)
- = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict),
- DICT_LINEAR_EXPANDABLE_CAPACITY (dict));
- }
- DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
- }
- /* Multi-language dictionary support. */
- /* The structure describing a multi-language dictionary. */
- struct multidictionary
- {
- /* An array of dictionaries, one per language. All dictionaries
- must be of the same type. This should be free'd for expandable
- dictionary types. */
- struct dictionary **dictionaries;
- /* The number of language dictionaries currently allocated.
- Only used for expandable dictionaries. */
- unsigned short n_allocated_dictionaries;
- };
- /* A hasher for enum language. Injecting this into std is a convenience
- when using unordered_map with C++11. */
- namespace std
- {
- template<> struct hash<enum language>
- {
- typedef enum language argument_type;
- typedef std::size_t result_type;
- result_type operator() (const argument_type &l) const noexcept
- {
- return static_cast<result_type> (l);
- }
- };
- } /* namespace std */
- /* A helper function to collate symbols on the pending list by language. */
- static std::unordered_map<enum language, std::vector<symbol *>>
- collate_pending_symbols_by_language (const struct pending *symbol_list)
- {
- std::unordered_map<enum language, std::vector<symbol *>> nsyms;
- for (const pending *list_counter = symbol_list;
- list_counter != nullptr; list_counter = list_counter->next)
- {
- for (int i = list_counter->nsyms - 1; i >= 0; --i)
- {
- enum language language = list_counter->symbol[i]->language ();
- nsyms[language].push_back (list_counter->symbol[i]);
- }
- }
- return nsyms;
- }
- /* See dictionary.h. */
- struct multidictionary *
- mdict_create_hashed (struct obstack *obstack,
- const struct pending *symbol_list)
- {
- struct multidictionary *retval
- = XOBNEW (obstack, struct multidictionary);
- std::unordered_map<enum language, std::vector<symbol *>> nsyms
- = collate_pending_symbols_by_language (symbol_list);
- /* Loop over all languages and create/populate dictionaries. */
- retval->dictionaries
- = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
- retval->n_allocated_dictionaries = nsyms.size ();
- int idx = 0;
- for (const auto &pair : nsyms)
- {
- enum language language = pair.first;
- std::vector<symbol *> symlist = pair.second;
- retval->dictionaries[idx++]
- = dict_create_hashed (obstack, language, symlist);
- }
- return retval;
- }
- /* See dictionary.h. */
- struct multidictionary *
- mdict_create_hashed_expandable (enum language language)
- {
- struct multidictionary *retval = XNEW (struct multidictionary);
- /* We have no symbol list to populate, but we create an empty
- dictionary of the requested language to populate later. */
- retval->n_allocated_dictionaries = 1;
- retval->dictionaries = XNEW (struct dictionary *);
- retval->dictionaries[0] = dict_create_hashed_expandable (language);
- return retval;
- }
- /* See dictionary.h. */
- struct multidictionary *
- mdict_create_linear (struct obstack *obstack,
- const struct pending *symbol_list)
- {
- struct multidictionary *retval
- = XOBNEW (obstack, struct multidictionary);
- std::unordered_map<enum language, std::vector<symbol *>> nsyms
- = collate_pending_symbols_by_language (symbol_list);
- /* Loop over all languages and create/populate dictionaries. */
- retval->dictionaries
- = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
- retval->n_allocated_dictionaries = nsyms.size ();
- int idx = 0;
- for (const auto &pair : nsyms)
- {
- enum language language = pair.first;
- std::vector<symbol *> symlist = pair.second;
- retval->dictionaries[idx++]
- = dict_create_linear (obstack, language, symlist);
- }
- return retval;
- }
- /* See dictionary.h. */
- struct multidictionary *
- mdict_create_linear_expandable (enum language language)
- {
- struct multidictionary *retval = XNEW (struct multidictionary);
- /* We have no symbol list to populate, but we create an empty
- dictionary to populate later. */
- retval->n_allocated_dictionaries = 1;
- retval->dictionaries = XNEW (struct dictionary *);
- retval->dictionaries[0] = dict_create_linear_expandable (language);
- return retval;
- }
- /* See dictionary.h. */
- void
- mdict_free (struct multidictionary *mdict)
- {
- /* Grab the type of dictionary being used. */
- enum dict_type type = mdict->dictionaries[0]->vector->type;
- /* Loop over all dictionaries and free them. */
- for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
- dict_free (mdict->dictionaries[idx]);
- /* Free the dictionary list, if needed. */
- switch (type)
- {
- case DICT_HASHED:
- case DICT_LINEAR:
- /* Memory was allocated on an obstack when created. */
- break;
- case DICT_HASHED_EXPANDABLE:
- case DICT_LINEAR_EXPANDABLE:
- xfree (mdict->dictionaries);
- break;
- }
- }
- /* Helper function to find the dictionary associated with LANGUAGE
- or NULL if there is no dictionary of that language. */
- static struct dictionary *
- find_language_dictionary (const struct multidictionary *mdict,
- enum language language)
- {
- for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
- {
- if (DICT_LANGUAGE (mdict->dictionaries[idx])->la_language == language)
- return mdict->dictionaries[idx];
- }
- return nullptr;
- }
- /* Create a new language dictionary for LANGUAGE and add it to the
- multidictionary MDICT's list of dictionaries. If MDICT is not
- based on expandable dictionaries, this function throws an
- internal error. */
- static struct dictionary *
- create_new_language_dictionary (struct multidictionary *mdict,
- enum language language)
- {
- struct dictionary *retval = nullptr;
- /* We use the first dictionary entry to decide what create function
- to call. Not optimal but sufficient. */
- gdb_assert (mdict->dictionaries[0] != nullptr);
- switch (mdict->dictionaries[0]->vector->type)
- {
- case DICT_HASHED:
- case DICT_LINEAR:
- internal_error (__FILE__, __LINE__,
- _("create_new_language_dictionary: attempted to expand "
- "non-expandable multidictionary"));
- case DICT_HASHED_EXPANDABLE:
- retval = dict_create_hashed_expandable (language);
- break;
- case DICT_LINEAR_EXPANDABLE:
- retval = dict_create_linear_expandable (language);
- break;
- }
- /* Grow the dictionary vector and save the new dictionary. */
- mdict->dictionaries
- = (struct dictionary **) xrealloc (mdict->dictionaries,
- (++mdict->n_allocated_dictionaries
- * sizeof (struct dictionary *)));
- mdict->dictionaries[mdict->n_allocated_dictionaries - 1] = retval;
- return retval;
- }
- /* See dictionary.h. */
- void
- mdict_add_symbol (struct multidictionary *mdict, struct symbol *sym)
- {
- struct dictionary *dict
- = find_language_dictionary (mdict, sym->language ());
- if (dict == nullptr)
- {
- /* SYM is of a new language that we haven't previously seen.
- Create a new dictionary for it. */
- dict = create_new_language_dictionary (mdict, sym->language ());
- }
- dict_add_symbol (dict, sym);
- }
- /* See dictionary.h. */
- void
- mdict_add_pending (struct multidictionary *mdict,
- const struct pending *symbol_list)
- {
- std::unordered_map<enum language, std::vector<symbol *>> nsyms
- = collate_pending_symbols_by_language (symbol_list);
- for (const auto &pair : nsyms)
- {
- enum language language = pair.first;
- std::vector<symbol *> symlist = pair.second;
- struct dictionary *dict = find_language_dictionary (mdict, language);
- if (dict == nullptr)
- {
- /* The language was not previously seen. Create a new dictionary
- for it. */
- dict = create_new_language_dictionary (mdict, language);
- }
- dict_add_pending (dict, symlist);
- }
- }
- /* See dictionary.h. */
- struct symbol *
- mdict_iterator_first (const multidictionary *mdict,
- struct mdict_iterator *miterator)
- {
- miterator->mdict = mdict;
- miterator->current_idx = 0;
- for (unsigned short idx = miterator->current_idx;
- idx < mdict->n_allocated_dictionaries; ++idx)
- {
- struct symbol *result
- = dict_iterator_first (mdict->dictionaries[idx], &miterator->iterator);
- if (result != nullptr)
- {
- miterator->current_idx = idx;
- return result;
- }
- }
- return nullptr;
- }
- /* See dictionary.h. */
- struct symbol *
- mdict_iterator_next (struct mdict_iterator *miterator)
- {
- struct symbol *result = dict_iterator_next (&miterator->iterator);
- if (result != nullptr)
- return result;
- /* The current dictionary had no matches -- move to the next
- dictionary, if any. */
- for (unsigned short idx = ++miterator->current_idx;
- idx < miterator->mdict->n_allocated_dictionaries; ++idx)
- {
- result
- = dict_iterator_first (miterator->mdict->dictionaries[idx],
- &miterator->iterator);
- if (result != nullptr)
- {
- miterator->current_idx = idx;
- return result;
- }
- }
- return nullptr;
- }
- /* See dictionary.h. */
- struct symbol *
- mdict_iter_match_first (const struct multidictionary *mdict,
- const lookup_name_info &name,
- struct mdict_iterator *miterator)
- {
- miterator->mdict = mdict;
- miterator->current_idx = 0;
- for (unsigned short idx = miterator->current_idx;
- idx < mdict->n_allocated_dictionaries; ++idx)
- {
- struct symbol *result
- = dict_iter_match_first (mdict->dictionaries[idx], name,
- &miterator->iterator);
- if (result != nullptr)
- return result;
- }
- return nullptr;
- }
- /* See dictionary.h. */
- struct symbol *
- mdict_iter_match_next (const lookup_name_info &name,
- struct mdict_iterator *miterator)
- {
- /* Search the current dictionary. */
- struct symbol *result = dict_iter_match_next (name, &miterator->iterator);
- if (result != nullptr)
- return result;
- /* The current dictionary had no matches -- move to the next
- dictionary, if any. */
- for (unsigned short idx = ++miterator->current_idx;
- idx < miterator->mdict->n_allocated_dictionaries; ++idx)
- {
- result
- = dict_iter_match_first (miterator->mdict->dictionaries[idx],
- name, &miterator->iterator);
- if (result != nullptr)
- {
- miterator->current_idx = idx;
- return result;
- }
- }
- return nullptr;
- }
- /* See dictionary.h. */
- int
- mdict_size (const struct multidictionary *mdict)
- {
- int size = 0;
- for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
- size += dict_size (mdict->dictionaries[idx]);
- return size;
- }
|