1 /* Routines for name->symbol lookups in GDB.
3 Copyright (C) 2003-2019 Free Software Foundation, Inc.
5 Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
8 This file is part of GDB.
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 3 of the License, or
13 (at your option) any later version.
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program. If not, see <http://www.gnu.org/licenses/>. */
25 /* Standard C includes. */
28 /* Standard C++ includes. */
29 #include <unordered_map>
31 /* Local non-gdb includes. */
33 #include "dictionary.h"
34 #include "gdb_obstack.h"
35 #include "safe-ctype.h"
38 /* This file implements dictionaries, which are tables that associate
39 symbols to names. They are represented by an opaque type 'struct
40 dictionary'. That type has various internal implementations, which
41 you can choose between depending on what properties you need
42 (e.g. fast lookup, order-preserving, expandable).
44 Each dictionary starts with a 'virtual function table' that
45 contains the functions that actually implement the various
46 operations that dictionaries provide. (Note, however, that, for
47 the sake of client code, we also provide some functions that can be
48 implemented generically in terms of the functions in the vtable.)
50 To add a new dictionary implementation <impl>, what you should do
53 * Add a new element DICT_<IMPL> to dict_type.
55 * Create a new structure dictionary_<impl>. If your new
56 implementation is a variant of an existing one, make sure that
57 their structs have the same initial data members. Define accessor
58 macros for your new data members.
60 * Implement all the functions in dict_vector as static functions,
61 whose name is the same as the corresponding member of dict_vector
62 plus _<impl>. You don't have to do this for those members where
63 you can reuse existing generic functions
64 (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
65 your new implementation is a variant of an existing implementation
66 and where the variant doesn't affect the member function in
69 * Define a static const struct dict_vector dict_<impl>_vector.
71 * Define a function dict_create_<impl> to create these
72 gizmos. Add its declaration to dictionary.h.
74 To add a new operation <op> on all existing implementations, what
77 * Add a new member <op> to struct dict_vector.
79 * If there is useful generic behavior <op>, define a static
80 function <op>_something_informative that implements that behavior.
81 (E.g. add_symbol_nonexpandable, free_obstack.)
83 * For every implementation <impl> that should have its own specific
84 behavior for <op>, define a static function <op>_<impl>
87 * Modify all existing dict_vector_<impl>'s to include the appropriate
90 * Define a function dict_<op> that looks up <op> in the dict_vector
91 and calls the appropriate function. Add a declaration for
92 dict_<op> to dictionary.h. */
94 /* An enum representing the various implementations of dictionaries.
95 Used only for debugging. */
99 /* Symbols are stored in a fixed-size hash table. */
101 /* Symbols are stored in an expandable hash table. */
102 DICT_HASHED_EXPANDABLE
,
103 /* Symbols are stored in a fixed-size array. */
105 /* Symbols are stored in an expandable array. */
106 DICT_LINEAR_EXPANDABLE
109 /* The virtual function table. */
113 /* The type of the dictionary. This is only here to make debugging
114 a bit easier; it's not actually used. */
116 /* The function to free a dictionary. */
117 void (*free
) (struct dictionary
*dict
);
118 /* Add a symbol to a dictionary, if possible. */
119 void (*add_symbol
) (struct dictionary
*dict
, struct symbol
*sym
);
120 /* Iterator functions. */
121 struct symbol
*(*iterator_first
) (const struct dictionary
*dict
,
122 struct dict_iterator
*iterator
);
123 struct symbol
*(*iterator_next
) (struct dict_iterator
*iterator
);
124 /* Functions to iterate over symbols with a given name. */
125 struct symbol
*(*iter_match_first
) (const struct dictionary
*dict
,
126 const lookup_name_info
&name
,
127 struct dict_iterator
*iterator
);
128 struct symbol
*(*iter_match_next
) (const lookup_name_info
&name
,
129 struct dict_iterator
*iterator
);
130 /* A size function, for maint print symtabs. */
131 int (*size
) (const struct dictionary
*dict
);
134 /* Now comes the structs used to store the data for different
135 implementations. If two implementations have data in common, put
136 the common data at the top of their structs, ordered in the same
139 struct dictionary_hashed
142 struct symbol
**buckets
;
145 struct dictionary_hashed_expandable
147 /* How many buckets we currently have. */
149 struct symbol
**buckets
;
150 /* How many syms we currently have; we need this so we will know
151 when to add more buckets. */
155 struct dictionary_linear
158 struct symbol
**syms
;
161 struct dictionary_linear_expandable
163 /* How many symbols we currently have. */
165 struct symbol
**syms
;
166 /* How many symbols we can store before needing to reallocate. */
170 /* And now, the star of our show. */
174 const struct language_defn
*language
;
175 const struct dict_vector
*vector
;
178 struct dictionary_hashed hashed
;
179 struct dictionary_hashed_expandable hashed_expandable
;
180 struct dictionary_linear linear
;
181 struct dictionary_linear_expandable linear_expandable
;
186 /* Accessor macros. */
188 #define DICT_VECTOR(d) (d)->vector
189 #define DICT_LANGUAGE(d) (d)->language
191 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
193 #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
194 #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
195 #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
197 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
199 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
201 #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
202 #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
203 #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
205 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
206 (d)->data.linear_expandable.capacity
208 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
210 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
212 /* This calculates the number of buckets we'll use in a hashtable,
213 given the number of symbols that it will contain. */
215 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
217 /* Accessor macros for dict_iterators; they're here rather than
218 dictionary.h because code elsewhere should treat dict_iterators as
221 /* The dictionary that the iterator is associated to. */
222 #define DICT_ITERATOR_DICT(iter) (iter)->dict
223 /* For linear dictionaries, the index of the last symbol returned; for
224 hashed dictionaries, the bucket of the last symbol returned. */
225 #define DICT_ITERATOR_INDEX(iter) (iter)->index
226 /* For hashed dictionaries, this points to the last symbol returned;
227 otherwise, this is unused. */
228 #define DICT_ITERATOR_CURRENT(iter) (iter)->current
230 /* Declarations of functions for vectors. */
232 /* Functions that might work across a range of dictionary types. */
234 static void add_symbol_nonexpandable (struct dictionary
*dict
,
237 static void free_obstack (struct dictionary
*dict
);
239 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
242 static struct symbol
*iterator_first_hashed (const struct dictionary
*dict
,
243 struct dict_iterator
*iterator
);
245 static struct symbol
*iterator_next_hashed (struct dict_iterator
*iterator
);
247 static struct symbol
*iter_match_first_hashed (const struct dictionary
*dict
,
248 const lookup_name_info
&name
,
249 struct dict_iterator
*iterator
);
251 static struct symbol
*iter_match_next_hashed (const lookup_name_info
&name
,
252 struct dict_iterator
*iterator
);
254 /* Functions only for DICT_HASHED. */
256 static int size_hashed (const struct dictionary
*dict
);
258 /* Functions only for DICT_HASHED_EXPANDABLE. */
260 static void free_hashed_expandable (struct dictionary
*dict
);
262 static void add_symbol_hashed_expandable (struct dictionary
*dict
,
265 static int size_hashed_expandable (const struct dictionary
*dict
);
267 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
270 static struct symbol
*iterator_first_linear (const struct dictionary
*dict
,
271 struct dict_iterator
*iterator
);
273 static struct symbol
*iterator_next_linear (struct dict_iterator
*iterator
);
275 static struct symbol
*iter_match_first_linear (const struct dictionary
*dict
,
276 const lookup_name_info
&name
,
277 struct dict_iterator
*iterator
);
279 static struct symbol
*iter_match_next_linear (const lookup_name_info
&name
,
280 struct dict_iterator
*iterator
);
282 static int size_linear (const struct dictionary
*dict
);
284 /* Functions only for DICT_LINEAR_EXPANDABLE. */
286 static void free_linear_expandable (struct dictionary
*dict
);
288 static void add_symbol_linear_expandable (struct dictionary
*dict
,
291 /* Various vectors that we'll actually use. */
293 static const struct dict_vector dict_hashed_vector
=
295 DICT_HASHED
, /* type */
296 free_obstack
, /* free */
297 add_symbol_nonexpandable
, /* add_symbol */
298 iterator_first_hashed
, /* iterator_first */
299 iterator_next_hashed
, /* iterator_next */
300 iter_match_first_hashed
, /* iter_name_first */
301 iter_match_next_hashed
, /* iter_name_next */
302 size_hashed
, /* size */
305 static const struct dict_vector dict_hashed_expandable_vector
=
307 DICT_HASHED_EXPANDABLE
, /* type */
308 free_hashed_expandable
, /* free */
309 add_symbol_hashed_expandable
, /* add_symbol */
310 iterator_first_hashed
, /* iterator_first */
311 iterator_next_hashed
, /* iterator_next */
312 iter_match_first_hashed
, /* iter_name_first */
313 iter_match_next_hashed
, /* iter_name_next */
314 size_hashed_expandable
, /* size */
317 static const struct dict_vector dict_linear_vector
=
319 DICT_LINEAR
, /* type */
320 free_obstack
, /* free */
321 add_symbol_nonexpandable
, /* add_symbol */
322 iterator_first_linear
, /* iterator_first */
323 iterator_next_linear
, /* iterator_next */
324 iter_match_first_linear
, /* iter_name_first */
325 iter_match_next_linear
, /* iter_name_next */
326 size_linear
, /* size */
329 static const struct dict_vector dict_linear_expandable_vector
=
331 DICT_LINEAR_EXPANDABLE
, /* type */
332 free_linear_expandable
, /* free */
333 add_symbol_linear_expandable
, /* add_symbol */
334 iterator_first_linear
, /* iterator_first */
335 iterator_next_linear
, /* iterator_next */
336 iter_match_first_linear
, /* iter_name_first */
337 iter_match_next_linear
, /* iter_name_next */
338 size_linear
, /* size */
341 /* Declarations of helper functions (i.e. ones that don't go into
344 static struct symbol
*iterator_hashed_advance (struct dict_iterator
*iter
);
346 static void insert_symbol_hashed (struct dictionary
*dict
,
349 static void expand_hashtable (struct dictionary
*dict
);
351 /* The creation functions. */
353 /* Create a hashed dictionary of a given language. */
355 static struct dictionary
*
356 dict_create_hashed (struct obstack
*obstack
,
357 enum language language
,
358 const std::vector
<symbol
*> &symbol_list
)
360 /* Allocate the dictionary. */
361 struct dictionary
*retval
= XOBNEW (obstack
, struct dictionary
);
362 DICT_VECTOR (retval
) = &dict_hashed_vector
;
363 DICT_LANGUAGE (retval
) = language_def (language
);
365 /* Allocate space for symbols. */
366 int nsyms
= symbol_list
.size ();
367 int nbuckets
= DICT_HASHTABLE_SIZE (nsyms
);
368 DICT_HASHED_NBUCKETS (retval
) = nbuckets
;
369 struct symbol
**buckets
= XOBNEWVEC (obstack
, struct symbol
*, nbuckets
);
370 memset (buckets
, 0, nbuckets
* sizeof (struct symbol
*));
371 DICT_HASHED_BUCKETS (retval
) = buckets
;
373 /* Now fill the buckets. */
374 for (const auto &sym
: symbol_list
)
375 insert_symbol_hashed (retval
, sym
);
380 /* Create an expandable hashed dictionary of a given language. */
382 static struct dictionary
*
383 dict_create_hashed_expandable (enum language language
)
385 struct dictionary
*retval
= XNEW (struct dictionary
);
387 DICT_VECTOR (retval
) = &dict_hashed_expandable_vector
;
388 DICT_LANGUAGE (retval
) = language_def (language
);
389 DICT_HASHED_NBUCKETS (retval
) = DICT_EXPANDABLE_INITIAL_CAPACITY
;
390 DICT_HASHED_BUCKETS (retval
) = XCNEWVEC (struct symbol
*,
391 DICT_EXPANDABLE_INITIAL_CAPACITY
);
392 DICT_HASHED_EXPANDABLE_NSYMS (retval
) = 0;
397 /* Create a linear dictionary of a given language. */
399 static struct dictionary
*
400 dict_create_linear (struct obstack
*obstack
,
401 enum language language
,
402 const std::vector
<symbol
*> &symbol_list
)
404 struct dictionary
*retval
= XOBNEW (obstack
, struct dictionary
);
405 DICT_VECTOR (retval
) = &dict_linear_vector
;
406 DICT_LANGUAGE (retval
) = language_def (language
);
408 /* Allocate space for symbols. */
409 int nsyms
= symbol_list
.size ();
410 DICT_LINEAR_NSYMS (retval
) = nsyms
;
411 struct symbol
**syms
= XOBNEWVEC (obstack
, struct symbol
*, nsyms
);
412 DICT_LINEAR_SYMS (retval
) = syms
;
414 /* Now fill in the symbols. */
416 for (const auto &sym
: symbol_list
)
422 /* Create an expandable linear dictionary of a given language. */
424 static struct dictionary
*
425 dict_create_linear_expandable (enum language language
)
427 struct dictionary
*retval
= XNEW (struct dictionary
);
429 DICT_VECTOR (retval
) = &dict_linear_expandable_vector
;
430 DICT_LANGUAGE (retval
) = language_def (language
);
431 DICT_LINEAR_NSYMS (retval
) = 0;
432 DICT_LINEAR_EXPANDABLE_CAPACITY (retval
) = DICT_EXPANDABLE_INITIAL_CAPACITY
;
433 DICT_LINEAR_SYMS (retval
)
434 = XNEWVEC (struct symbol
*, DICT_LINEAR_EXPANDABLE_CAPACITY (retval
));
439 /* The functions providing the dictionary interface. */
441 /* Free the memory used by a dictionary that's not on an obstack. (If
445 dict_free (struct dictionary
*dict
)
447 (DICT_VECTOR (dict
))->free (dict
);
450 /* Add SYM to DICT. DICT had better be expandable. */
453 dict_add_symbol (struct dictionary
*dict
, struct symbol
*sym
)
455 (DICT_VECTOR (dict
))->add_symbol (dict
, sym
);
458 /* Utility to add a list of symbols to a dictionary.
459 DICT must be an expandable dictionary. */
462 dict_add_pending (struct dictionary
*dict
,
463 const std::vector
<symbol
*> &symbol_list
)
465 /* Preserve ordering by reversing the list. */
466 for (auto sym
= symbol_list
.rbegin (); sym
!= symbol_list
.rend (); ++sym
)
467 dict_add_symbol (dict
, *sym
);
470 /* Initialize ITERATOR to point at the first symbol in DICT, and
471 return that first symbol, or NULL if DICT is empty. */
474 dict_iterator_first (const struct dictionary
*dict
,
475 struct dict_iterator
*iterator
)
477 return (DICT_VECTOR (dict
))->iterator_first (dict
, iterator
);
480 /* Advance ITERATOR, and return the next symbol, or NULL if there are
484 dict_iterator_next (struct dict_iterator
*iterator
)
486 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
487 ->iterator_next (iterator
);
491 dict_iter_match_first (const struct dictionary
*dict
,
492 const lookup_name_info
&name
,
493 struct dict_iterator
*iterator
)
495 return (DICT_VECTOR (dict
))->iter_match_first (dict
, name
, iterator
);
499 dict_iter_match_next (const lookup_name_info
&name
,
500 struct dict_iterator
*iterator
)
502 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
503 ->iter_match_next (name
, iterator
);
507 dict_size (const struct dictionary
*dict
)
509 return (DICT_VECTOR (dict
))->size (dict
);
512 /* Now come functions (well, one function, currently) that are
513 implemented generically by means of the vtable. Typically, they're
516 /* Test to see if DICT is empty. */
519 dict_empty (struct dictionary
*dict
)
521 struct dict_iterator iter
;
523 return (dict_iterator_first (dict
, &iter
) == NULL
);
527 /* The functions implementing the dictionary interface. */
529 /* Generic functions, where appropriate. */
532 free_obstack (struct dictionary
*dict
)
538 add_symbol_nonexpandable (struct dictionary
*dict
, struct symbol
*sym
)
540 internal_error (__FILE__
, __LINE__
,
541 _("dict_add_symbol: non-expandable dictionary"));
544 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
546 static struct symbol
*
547 iterator_first_hashed (const struct dictionary
*dict
,
548 struct dict_iterator
*iterator
)
550 DICT_ITERATOR_DICT (iterator
) = dict
;
551 DICT_ITERATOR_INDEX (iterator
) = -1;
552 return iterator_hashed_advance (iterator
);
555 static struct symbol
*
556 iterator_next_hashed (struct dict_iterator
*iterator
)
560 next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
563 return iterator_hashed_advance (iterator
);
566 DICT_ITERATOR_CURRENT (iterator
) = next
;
571 static struct symbol
*
572 iterator_hashed_advance (struct dict_iterator
*iterator
)
574 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
575 int nbuckets
= DICT_HASHED_NBUCKETS (dict
);
578 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nbuckets
; ++i
)
580 struct symbol
*sym
= DICT_HASHED_BUCKET (dict
, i
);
584 DICT_ITERATOR_INDEX (iterator
) = i
;
585 DICT_ITERATOR_CURRENT (iterator
) = sym
;
593 static struct symbol
*
594 iter_match_first_hashed (const struct dictionary
*dict
,
595 const lookup_name_info
&name
,
596 struct dict_iterator
*iterator
)
598 const language_defn
*lang
= DICT_LANGUAGE (dict
);
599 unsigned int hash_index
= (name
.search_name_hash (lang
->la_language
)
600 % DICT_HASHED_NBUCKETS (dict
));
601 symbol_name_matcher_ftype
*matches_name
602 = get_symbol_name_matcher (lang
, name
);
605 DICT_ITERATOR_DICT (iterator
) = dict
;
607 /* Loop through the symbols in the given bucket, breaking when SYM
608 first matches. If SYM never matches, it will be set to NULL;
609 either way, we have the right return value. */
611 for (sym
= DICT_HASHED_BUCKET (dict
, hash_index
);
613 sym
= sym
->hash_next
)
615 /* Warning: the order of arguments to compare matters! */
616 if (matches_name (SYMBOL_SEARCH_NAME (sym
), name
, NULL
))
620 DICT_ITERATOR_CURRENT (iterator
) = sym
;
624 static struct symbol
*
625 iter_match_next_hashed (const lookup_name_info
&name
,
626 struct dict_iterator
*iterator
)
628 const language_defn
*lang
= DICT_LANGUAGE (DICT_ITERATOR_DICT (iterator
));
629 symbol_name_matcher_ftype
*matches_name
630 = get_symbol_name_matcher (lang
, name
);
633 for (next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
635 next
= next
->hash_next
)
637 if (matches_name (SYMBOL_SEARCH_NAME (next
), name
, NULL
))
641 DICT_ITERATOR_CURRENT (iterator
) = next
;
646 /* Insert SYM into DICT. */
649 insert_symbol_hashed (struct dictionary
*dict
,
652 unsigned int hash_index
;
654 struct symbol
**buckets
= DICT_HASHED_BUCKETS (dict
);
656 /* We don't want to insert a symbol into a dictionary of a different
657 language. The two may not use the same hashing algorithm. */
658 gdb_assert (SYMBOL_LANGUAGE (sym
) == DICT_LANGUAGE (dict
)->la_language
);
660 hash
= search_name_hash (SYMBOL_LANGUAGE (sym
), SYMBOL_SEARCH_NAME (sym
));
661 hash_index
= hash
% DICT_HASHED_NBUCKETS (dict
);
662 sym
->hash_next
= buckets
[hash_index
];
663 buckets
[hash_index
] = sym
;
667 size_hashed (const struct dictionary
*dict
)
669 return DICT_HASHED_NBUCKETS (dict
);
672 /* Functions only for DICT_HASHED_EXPANDABLE. */
675 free_hashed_expandable (struct dictionary
*dict
)
677 xfree (DICT_HASHED_BUCKETS (dict
));
682 add_symbol_hashed_expandable (struct dictionary
*dict
,
685 int nsyms
= ++DICT_HASHED_EXPANDABLE_NSYMS (dict
);
687 if (DICT_HASHTABLE_SIZE (nsyms
) > DICT_HASHED_NBUCKETS (dict
))
688 expand_hashtable (dict
);
690 insert_symbol_hashed (dict
, sym
);
691 DICT_HASHED_EXPANDABLE_NSYMS (dict
) = nsyms
;
695 size_hashed_expandable (const struct dictionary
*dict
)
697 return DICT_HASHED_EXPANDABLE_NSYMS (dict
);
701 expand_hashtable (struct dictionary
*dict
)
703 int old_nbuckets
= DICT_HASHED_NBUCKETS (dict
);
704 struct symbol
**old_buckets
= DICT_HASHED_BUCKETS (dict
);
705 int new_nbuckets
= 2 * old_nbuckets
+ 1;
706 struct symbol
**new_buckets
= XCNEWVEC (struct symbol
*, new_nbuckets
);
709 DICT_HASHED_NBUCKETS (dict
) = new_nbuckets
;
710 DICT_HASHED_BUCKETS (dict
) = new_buckets
;
712 for (i
= 0; i
< old_nbuckets
; ++i
)
714 struct symbol
*sym
, *next_sym
;
716 sym
= old_buckets
[i
];
719 for (next_sym
= sym
->hash_next
;
721 next_sym
= sym
->hash_next
)
723 insert_symbol_hashed (dict
, sym
);
727 insert_symbol_hashed (dict
, sym
);
734 /* See dictionary.h. */
737 default_search_name_hash (const char *string0
)
739 /* The Ada-encoded version of a name P1.P2...Pn has either the form
740 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
741 are lower-cased identifiers). The <suffix> (which can be empty)
742 encodes additional information about the denoted entity. This
743 routine hashes such names to msymbol_hash_iw(Pn). It actually
744 does this for a superset of both valid Pi and of <suffix>, but
745 in other cases it simply returns msymbol_hash_iw(STRING0). */
753 if (startswith (string
, "_ada_"))
756 return msymbol_hash_iw (string0
);
767 if (string0
== string
)
768 return msymbol_hash_iw (string0
);
773 return msymbol_hash_iw (string0
);
775 if (string
[1] == '_' && string
!= string0
)
779 if ((c
< 'a' || c
> 'z') && c
!= 'O')
787 /* Ignore "TKB" suffixes.
789 These are used by Ada for subprograms implementing a task body.
790 For instance for a task T inside package Pck, the name of the
791 subprogram implementing T's body is `pck__tTKB'. We need to
792 ignore the "TKB" suffix because searches for this task body
793 subprogram are going to be performed using `pck__t' (the encoded
794 version of the natural name `pck.t'). */
795 if (strcmp (string
, "TKB") == 0)
800 hash
= SYMBOL_HASH_NEXT (hash
, *string
);
806 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
808 static struct symbol
*
809 iterator_first_linear (const struct dictionary
*dict
,
810 struct dict_iterator
*iterator
)
812 DICT_ITERATOR_DICT (iterator
) = dict
;
813 DICT_ITERATOR_INDEX (iterator
) = 0;
814 return DICT_LINEAR_NSYMS (dict
) ? DICT_LINEAR_SYM (dict
, 0) : NULL
;
817 static struct symbol
*
818 iterator_next_linear (struct dict_iterator
*iterator
)
820 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
822 if (++DICT_ITERATOR_INDEX (iterator
) >= DICT_LINEAR_NSYMS (dict
))
825 return DICT_LINEAR_SYM (dict
, DICT_ITERATOR_INDEX (iterator
));
828 static struct symbol
*
829 iter_match_first_linear (const struct dictionary
*dict
,
830 const lookup_name_info
&name
,
831 struct dict_iterator
*iterator
)
833 DICT_ITERATOR_DICT (iterator
) = dict
;
834 DICT_ITERATOR_INDEX (iterator
) = -1;
836 return iter_match_next_linear (name
, iterator
);
839 static struct symbol
*
840 iter_match_next_linear (const lookup_name_info
&name
,
841 struct dict_iterator
*iterator
)
843 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
844 const language_defn
*lang
= DICT_LANGUAGE (dict
);
845 symbol_name_matcher_ftype
*matches_name
846 = get_symbol_name_matcher (lang
, name
);
848 int i
, nsyms
= DICT_LINEAR_NSYMS (dict
);
849 struct symbol
*sym
, *retval
= NULL
;
851 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nsyms
; ++i
)
853 sym
= DICT_LINEAR_SYM (dict
, i
);
855 if (matches_name (SYMBOL_SEARCH_NAME (sym
), name
, NULL
))
862 DICT_ITERATOR_INDEX (iterator
) = i
;
868 size_linear (const struct dictionary
*dict
)
870 return DICT_LINEAR_NSYMS (dict
);
873 /* Functions only for DICT_LINEAR_EXPANDABLE. */
876 free_linear_expandable (struct dictionary
*dict
)
878 xfree (DICT_LINEAR_SYMS (dict
));
884 add_symbol_linear_expandable (struct dictionary
*dict
,
887 int nsyms
= ++DICT_LINEAR_NSYMS (dict
);
889 /* Do we have enough room? If not, grow it. */
890 if (nsyms
> DICT_LINEAR_EXPANDABLE_CAPACITY (dict
))
892 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
) *= 2;
893 DICT_LINEAR_SYMS (dict
)
894 = XRESIZEVEC (struct symbol
*, DICT_LINEAR_SYMS (dict
),
895 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
));
898 DICT_LINEAR_SYM (dict
, nsyms
- 1) = sym
;
901 /* Multi-language dictionary support. */
903 /* The structure describing a multi-language dictionary. */
905 struct multidictionary
907 /* An array of dictionaries, one per language. All dictionaries
908 must be of the same type. This should be free'd for expandable
910 struct dictionary
**dictionaries
;
912 /* The number of language dictionaries currently allocated.
913 Only used for expandable dictionaries. */
914 unsigned short n_allocated_dictionaries
;
917 /* A hasher for enum language. Injecting this into std is a convenience
918 when using unordered_map with C++11. */
922 template<> struct hash
<enum language
>
924 typedef enum language argument_type
;
925 typedef std::size_t result_type
;
927 result_type
operator() (const argument_type
&l
) const noexcept
929 return static_cast<result_type
> (l
);
932 } /* namespace std */
934 /* A helper function to collate symbols on the pending list by language. */
936 static std::unordered_map
<enum language
, std::vector
<symbol
*>>
937 collate_pending_symbols_by_language (const struct pending
*symbol_list
)
939 std::unordered_map
<enum language
, std::vector
<symbol
*>> nsyms
;
941 for (const struct pending
*list_counter
= symbol_list
;
942 list_counter
!= nullptr; list_counter
= list_counter
->next
)
944 for (int i
= list_counter
->nsyms
- 1; i
>= 0; --i
)
946 enum language language
= SYMBOL_LANGUAGE (list_counter
->symbol
[i
]);
947 nsyms
[language
].push_back (list_counter
->symbol
[i
]);
954 /* See dictionary.h. */
956 struct multidictionary
*
957 mdict_create_hashed (struct obstack
*obstack
,
958 const struct pending
*symbol_list
)
960 struct multidictionary
*retval
961 = XOBNEW (obstack
, struct multidictionary
);
962 std::unordered_map
<enum language
, std::vector
<symbol
*>> nsyms
963 = collate_pending_symbols_by_language (symbol_list
);
965 /* Loop over all languages and create/populate dictionaries. */
967 = XOBNEWVEC (obstack
, struct dictionary
*, nsyms
.size ());
968 retval
->n_allocated_dictionaries
= nsyms
.size ();
971 for (const auto &pair
: nsyms
)
973 enum language language
= pair
.first
;
974 std::vector
<symbol
*> symlist
= pair
.second
;
976 retval
->dictionaries
[idx
++]
977 = dict_create_hashed (obstack
, language
, symlist
);
983 /* See dictionary.h. */
985 struct multidictionary
*
986 mdict_create_hashed_expandable (enum language language
)
988 struct multidictionary
*retval
= XNEW (struct multidictionary
);
990 /* We have no symbol list to populate, but we create an empty
991 dictionary of the requested language to populate later. */
992 retval
->n_allocated_dictionaries
= 1;
993 retval
->dictionaries
= XNEW (struct dictionary
*);
994 retval
->dictionaries
[0] = dict_create_hashed_expandable (language
);
999 /* See dictionary.h. */
1001 struct multidictionary
*
1002 mdict_create_linear (struct obstack
*obstack
,
1003 const struct pending
*symbol_list
)
1005 struct multidictionary
*retval
1006 = XOBNEW (obstack
, struct multidictionary
);
1007 std::unordered_map
<enum language
, std::vector
<symbol
*>> nsyms
1008 = collate_pending_symbols_by_language (symbol_list
);
1010 /* Loop over all languages and create/populate dictionaries. */
1011 retval
->dictionaries
1012 = XOBNEWVEC (obstack
, struct dictionary
*, nsyms
.size ());
1013 retval
->n_allocated_dictionaries
= nsyms
.size ();
1016 for (const auto &pair
: nsyms
)
1018 enum language language
= pair
.first
;
1019 std::vector
<symbol
*> symlist
= pair
.second
;
1021 retval
->dictionaries
[idx
++]
1022 = dict_create_linear (obstack
, language
, symlist
);
1028 /* See dictionary.h. */
1030 struct multidictionary
*
1031 mdict_create_linear_expandable (enum language language
)
1033 struct multidictionary
*retval
= XNEW (struct multidictionary
);
1035 /* We have no symbol list to populate, but we create an empty
1036 dictionary to populate later. */
1037 retval
->n_allocated_dictionaries
= 1;
1038 retval
->dictionaries
= XNEW (struct dictionary
*);
1039 retval
->dictionaries
[0] = dict_create_linear_expandable (language
);
1044 /* See dictionary.h. */
1047 mdict_free (struct multidictionary
*mdict
)
1049 /* Grab the type of dictionary being used. */
1050 enum dict_type type
= mdict
->dictionaries
[0]->vector
->type
;
1052 /* Loop over all dictionaries and free them. */
1053 for (unsigned short idx
= 0; idx
< mdict
->n_allocated_dictionaries
; ++idx
)
1054 dict_free (mdict
->dictionaries
[idx
]);
1056 /* Free the dictionary list, if needed. */
1061 /* Memory was allocated on an obstack when created. */
1064 case DICT_HASHED_EXPANDABLE
:
1065 case DICT_LINEAR_EXPANDABLE
:
1066 xfree (mdict
->dictionaries
);
1071 /* Helper function to find the dictionary associated with LANGUAGE
1072 or NULL if there is no dictionary of that language. */
1074 static struct dictionary
*
1075 find_language_dictionary (const struct multidictionary
*mdict
,
1076 enum language language
)
1078 for (unsigned short idx
= 0; idx
< mdict
->n_allocated_dictionaries
; ++idx
)
1080 if (DICT_LANGUAGE (mdict
->dictionaries
[idx
])->la_language
== language
)
1081 return mdict
->dictionaries
[idx
];
1087 /* Create a new language dictionary for LANGUAGE and add it to the
1088 multidictionary MDICT's list of dictionaries. If MDICT is not
1089 based on expandable dictionaries, this function throws an
1092 static struct dictionary
*
1093 create_new_language_dictionary (struct multidictionary
*mdict
,
1094 enum language language
)
1096 struct dictionary
*retval
= nullptr;
1098 /* We use the first dictionary entry to decide what create function
1099 to call. Not optimal but sufficient. */
1100 gdb_assert (mdict
->dictionaries
[0] != nullptr);
1101 switch (mdict
->dictionaries
[0]->vector
->type
)
1105 internal_error (__FILE__
, __LINE__
,
1106 _("create_new_language_dictionary: attempted to expand "
1107 "non-expandable multidictionary"));
1109 case DICT_HASHED_EXPANDABLE
:
1110 retval
= dict_create_hashed_expandable (language
);
1113 case DICT_LINEAR_EXPANDABLE
:
1114 retval
= dict_create_linear_expandable (language
);
1118 /* Grow the dictionary vector and save the new dictionary. */
1120 = (struct dictionary
**) xrealloc (mdict
->dictionaries
,
1121 (++mdict
->n_allocated_dictionaries
1122 * sizeof (struct dictionary
*)));
1123 mdict
->dictionaries
[mdict
->n_allocated_dictionaries
- 1] = retval
;
1128 /* See dictionary.h. */
1131 mdict_add_symbol (struct multidictionary
*mdict
, struct symbol
*sym
)
1133 struct dictionary
*dict
1134 = find_language_dictionary (mdict
, SYMBOL_LANGUAGE (sym
));
1136 if (dict
== nullptr)
1138 /* SYM is of a new language that we haven't previously seen.
1139 Create a new dictionary for it. */
1140 dict
= create_new_language_dictionary (mdict
, SYMBOL_LANGUAGE (sym
));
1143 dict_add_symbol (dict
, sym
);
1146 /* See dictionary.h. */
1149 mdict_add_pending (struct multidictionary
*mdict
,
1150 const struct pending
*symbol_list
)
1152 std::unordered_map
<enum language
, std::vector
<symbol
*>> nsyms
1153 = collate_pending_symbols_by_language (symbol_list
);
1155 for (const auto &pair
: nsyms
)
1157 enum language language
= pair
.first
;
1158 std::vector
<symbol
*> symlist
= pair
.second
;
1159 struct dictionary
*dict
= find_language_dictionary (mdict
, language
);
1161 if (dict
== nullptr)
1163 /* The language was not previously seen. Create a new dictionary
1165 dict
= create_new_language_dictionary (mdict
, language
);
1168 dict_add_pending (dict
, symlist
);
1172 /* See dictionary.h. */
1175 mdict_iterator_first (const multidictionary
*mdict
,
1176 struct mdict_iterator
*miterator
)
1178 miterator
->mdict
= mdict
;
1179 miterator
->current_idx
= 0;
1181 for (unsigned short idx
= miterator
->current_idx
;
1182 idx
< mdict
->n_allocated_dictionaries
; ++idx
)
1184 struct symbol
*result
1185 = dict_iterator_first (mdict
->dictionaries
[idx
], &miterator
->iterator
);
1187 if (result
!= nullptr)
1189 miterator
->current_idx
= idx
;
1197 /* See dictionary.h. */
1200 mdict_iterator_next (struct mdict_iterator
*miterator
)
1202 struct symbol
*result
= dict_iterator_next (&miterator
->iterator
);
1204 if (result
!= nullptr)
1207 /* The current dictionary had no matches -- move to the next
1208 dictionary, if any. */
1209 for (unsigned short idx
= ++miterator
->current_idx
;
1210 idx
< miterator
->mdict
->n_allocated_dictionaries
; ++idx
)
1213 = dict_iterator_first (miterator
->mdict
->dictionaries
[idx
],
1214 &miterator
->iterator
);
1215 if (result
!= nullptr)
1217 miterator
->current_idx
= idx
;
1225 /* See dictionary.h. */
1228 mdict_iter_match_first (const struct multidictionary
*mdict
,
1229 const lookup_name_info
&name
,
1230 struct mdict_iterator
*miterator
)
1232 miterator
->mdict
= mdict
;
1233 miterator
->current_idx
= 0;
1235 for (unsigned short idx
= miterator
->current_idx
;
1236 idx
< mdict
->n_allocated_dictionaries
; ++idx
)
1238 struct symbol
*result
1239 = dict_iter_match_first (mdict
->dictionaries
[idx
], name
,
1240 &miterator
->iterator
);
1242 if (result
!= nullptr)
1249 /* See dictionary.h. */
1252 mdict_iter_match_next (const lookup_name_info
&name
,
1253 struct mdict_iterator
*miterator
)
1255 /* Search the current dictionary. */
1256 struct symbol
*result
= dict_iter_match_next (name
, &miterator
->iterator
);
1258 if (result
!= nullptr)
1261 /* The current dictionary had no matches -- move to the next
1262 dictionary, if any. */
1263 for (unsigned short idx
= ++miterator
->current_idx
;
1264 idx
< miterator
->mdict
->n_allocated_dictionaries
; ++idx
)
1267 = dict_iter_match_first (miterator
->mdict
->dictionaries
[idx
],
1268 name
, &miterator
->iterator
);
1269 if (result
!= nullptr)
1271 miterator
->current_idx
= idx
;
1279 /* See dictionary.h. */
1282 mdict_size (const struct multidictionary
*mdict
)
1286 for (unsigned short idx
= 0; idx
< mdict
->n_allocated_dictionaries
; ++idx
)
1287 size
+= dict_size (mdict
->dictionaries
[idx
]);
1292 /* See dictionary.h. */
1295 mdict_empty (const struct multidictionary
*mdict
)
1297 for (unsigned short idx
= 0; idx
< mdict
->n_allocated_dictionaries
; ++idx
)
1299 if (!dict_empty (mdict
->dictionaries
[idx
]))