GDB (xrefs)
Loading...
Searching...
No Matches
dictionary.c
Go to the documentation of this file.
1/* Routines for name->symbol lookups in GDB.
2
3 Copyright (C) 2003-2023 Free Software Foundation, Inc.
4
5 Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
6 Inc.
7
8 This file is part of GDB.
9
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.
14
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.
19
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/>. */
22
23#include "defs.h"
24#include <ctype.h>
25#include "gdbsupport/gdb_obstack.h"
26#include "symtab.h"
27#include "buildsym.h"
28#include "dictionary.h"
29#include "gdbsupport/gdb-safe-ctype.h"
30#include <unordered_map>
31#include "language.h"
32
33/* This file implements dictionaries, which are tables that associate
34 symbols to names. They are represented by an opaque type 'struct
35 dictionary'. That type has various internal implementations, which
36 you can choose between depending on what properties you need
37 (e.g. fast lookup, order-preserving, expandable).
38
39 Each dictionary starts with a 'virtual function table' that
40 contains the functions that actually implement the various
41 operations that dictionaries provide. (Note, however, that, for
42 the sake of client code, we also provide some functions that can be
43 implemented generically in terms of the functions in the vtable.)
44
45 To add a new dictionary implementation <impl>, what you should do
46 is:
47
48 * Add a new element DICT_<IMPL> to dict_type.
49
50 * Create a new structure dictionary_<impl>. If your new
51 implementation is a variant of an existing one, make sure that
52 their structs have the same initial data members. Define accessor
53 macros for your new data members.
54
55 * Implement all the functions in dict_vector as static functions,
56 whose name is the same as the corresponding member of dict_vector
57 plus _<impl>. You don't have to do this for those members where
58 you can reuse existing generic functions
59 (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
60 your new implementation is a variant of an existing implementation
61 and where the variant doesn't affect the member function in
62 question.
63
64 * Define a static const struct dict_vector dict_<impl>_vector.
65
66 * Define a function dict_create_<impl> to create these
67 gizmos. Add its declaration to dictionary.h.
68
69 To add a new operation <op> on all existing implementations, what
70 you should do is:
71
72 * Add a new member <op> to struct dict_vector.
73
74 * If there is useful generic behavior <op>, define a static
75 function <op>_something_informative that implements that behavior.
76 (E.g. add_symbol_nonexpandable, free_obstack.)
77
78 * For every implementation <impl> that should have its own specific
79 behavior for <op>, define a static function <op>_<impl>
80 implementing it.
81
82 * Modify all existing dict_vector_<impl>'s to include the appropriate
83 member.
84
85 * Define a function dict_<op> that looks up <op> in the dict_vector
86 and calls the appropriate function. Add a declaration for
87 dict_<op> to dictionary.h. */
88
89/* An enum representing the various implementations of dictionaries.
90 Used only for debugging. */
91
93 {
94 /* Symbols are stored in a fixed-size hash table. */
96 /* Symbols are stored in an expandable hash table. */
98 /* Symbols are stored in a fixed-size array. */
100 /* Symbols are stored in an expandable array. */
102 };
103
104/* The virtual function table. */
105
107{
108 /* The type of the dictionary. This is only here to make debugging
109 a bit easier; it's not actually used. */
111 /* The function to free a dictionary. */
112 void (*free) (struct dictionary *dict);
113 /* Add a symbol to a dictionary, if possible. */
114 void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
115 /* Iterator functions. */
116 struct symbol *(*iterator_first) (const struct dictionary *dict,
117 struct dict_iterator *iterator);
118 struct symbol *(*iterator_next) (struct dict_iterator *iterator);
119 /* Functions to iterate over symbols with a given name. */
120 struct symbol *(*iter_match_first) (const struct dictionary *dict,
121 const lookup_name_info &name,
122 struct dict_iterator *iterator);
123 struct symbol *(*iter_match_next) (const lookup_name_info &name,
124 struct dict_iterator *iterator);
125 /* A size function, for maint print symtabs. */
126 int (*size) (const struct dictionary *dict);
127};
128
129/* Now comes the structs used to store the data for different
130 implementations. If two implementations have data in common, put
131 the common data at the top of their structs, ordered in the same
132 way. */
133
135{
137 struct symbol **buckets;
138};
139
141{
142 /* How many buckets we currently have. */
144 struct symbol **buckets;
145 /* How many syms we currently have; we need this so we will know
146 when to add more buckets. */
147 int nsyms;
148};
149
151{
152 int nsyms;
153 struct symbol **syms;
154};
155
157{
158 /* How many symbols we currently have. */
159 int nsyms;
160 struct symbol **syms;
161 /* How many symbols we can store before needing to reallocate. */
163};
164
165/* And now, the star of our show. */
166
180
181/* Accessor macros. */
182
183#define DICT_VECTOR(d) (d)->vector
184#define DICT_LANGUAGE(d) (d)->language
185
186/* These can be used for DICT_HASHED_EXPANDABLE, too. */
187
188#define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
189#define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
190#define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
191
192#define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
193
194/* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
195
196#define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
197#define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
198#define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
199
200#define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
201 (d)->data.linear_expandable.capacity
202
203/* The initial size of a DICT_*_EXPANDABLE dictionary. */
204
205#define DICT_EXPANDABLE_INITIAL_CAPACITY 10
206
207/* This calculates the number of buckets we'll use in a hashtable,
208 given the number of symbols that it will contain. */
209
210#define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
211
212/* Accessor macros for dict_iterators; they're here rather than
213 dictionary.h because code elsewhere should treat dict_iterators as
214 opaque. */
215
216/* The dictionary that the iterator is associated to. */
217#define DICT_ITERATOR_DICT(iter) (iter)->dict
218/* For linear dictionaries, the index of the last symbol returned; for
219 hashed dictionaries, the bucket of the last symbol returned. */
220#define DICT_ITERATOR_INDEX(iter) (iter)->index
221/* For hashed dictionaries, this points to the last symbol returned;
222 otherwise, this is unused. */
223#define DICT_ITERATOR_CURRENT(iter) (iter)->current
224
225/* Declarations of functions for vectors. */
226
227/* Functions that might work across a range of dictionary types. */
228
229static void add_symbol_nonexpandable (struct dictionary *dict,
230 struct symbol *sym);
231
232static void free_obstack (struct dictionary *dict);
233
234/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
235 dictionaries. */
236
237static struct symbol *iterator_first_hashed (const struct dictionary *dict,
238 struct dict_iterator *iterator);
239
240static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
241
242static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
243 const lookup_name_info &name,
244 struct dict_iterator *iterator);
245
247 struct dict_iterator *iterator);
248
249/* Functions only for DICT_HASHED. */
250
251static int size_hashed (const struct dictionary *dict);
252
253/* Functions only for DICT_HASHED_EXPANDABLE. */
254
255static void free_hashed_expandable (struct dictionary *dict);
256
257static void add_symbol_hashed_expandable (struct dictionary *dict,
258 struct symbol *sym);
259
260static int size_hashed_expandable (const struct dictionary *dict);
261
262/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
263 dictionaries. */
264
265static struct symbol *iterator_first_linear (const struct dictionary *dict,
266 struct dict_iterator *iterator);
267
268static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
269
270static struct symbol *iter_match_first_linear (const struct dictionary *dict,
271 const lookup_name_info &name,
272 struct dict_iterator *iterator);
273
275 struct dict_iterator *iterator);
276
277static int size_linear (const struct dictionary *dict);
278
279/* Functions only for DICT_LINEAR_EXPANDABLE. */
280
281static void free_linear_expandable (struct dictionary *dict);
282
283static void add_symbol_linear_expandable (struct dictionary *dict,
284 struct symbol *sym);
285
286/* Various vectors that we'll actually use. */
287
288static const struct dict_vector dict_hashed_vector =
289 {
290 DICT_HASHED, /* type */
291 free_obstack, /* free */
292 add_symbol_nonexpandable, /* add_symbol */
293 iterator_first_hashed, /* iterator_first */
294 iterator_next_hashed, /* iterator_next */
295 iter_match_first_hashed, /* iter_name_first */
296 iter_match_next_hashed, /* iter_name_next */
297 size_hashed, /* size */
298 };
299
301 {
302 DICT_HASHED_EXPANDABLE, /* type */
303 free_hashed_expandable, /* free */
304 add_symbol_hashed_expandable, /* add_symbol */
305 iterator_first_hashed, /* iterator_first */
306 iterator_next_hashed, /* iterator_next */
307 iter_match_first_hashed, /* iter_name_first */
308 iter_match_next_hashed, /* iter_name_next */
309 size_hashed_expandable, /* size */
310 };
311
312static const struct dict_vector dict_linear_vector =
313 {
314 DICT_LINEAR, /* type */
315 free_obstack, /* free */
316 add_symbol_nonexpandable, /* add_symbol */
317 iterator_first_linear, /* iterator_first */
318 iterator_next_linear, /* iterator_next */
319 iter_match_first_linear, /* iter_name_first */
320 iter_match_next_linear, /* iter_name_next */
321 size_linear, /* size */
322 };
323
325 {
326 DICT_LINEAR_EXPANDABLE, /* type */
327 free_linear_expandable, /* free */
328 add_symbol_linear_expandable, /* add_symbol */
329 iterator_first_linear, /* iterator_first */
330 iterator_next_linear, /* iterator_next */
331 iter_match_first_linear, /* iter_name_first */
332 iter_match_next_linear, /* iter_name_next */
333 size_linear, /* size */
334 };
335
336/* Declarations of helper functions (i.e. ones that don't go into
337 vectors). */
338
339static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
340
341static void insert_symbol_hashed (struct dictionary *dict,
342 struct symbol *sym);
343
344static void expand_hashtable (struct dictionary *dict);
345
346/* The creation functions. */
347
348/* Create a hashed dictionary of a given language. */
349
350static struct dictionary *
351dict_create_hashed (struct obstack *obstack,
352 enum language language,
353 const std::vector<symbol *> &symbol_list)
354{
355 /* Allocate the dictionary. */
356 struct dictionary *retval = XOBNEW (obstack, struct dictionary);
359
360 /* Allocate space for symbols. */
361 int nsyms = symbol_list.size ();
362 int nbuckets = DICT_HASHTABLE_SIZE (nsyms);
363 DICT_HASHED_NBUCKETS (retval) = nbuckets;
364 struct symbol **buckets = XOBNEWVEC (obstack, struct symbol *, nbuckets);
365 memset (buckets, 0, nbuckets * sizeof (struct symbol *));
366 DICT_HASHED_BUCKETS (retval) = buckets;
367
368 /* Now fill the buckets. */
369 for (const auto &sym : symbol_list)
370 insert_symbol_hashed (retval, sym);
371
372 return retval;
373}
374
375/* Create an expandable hashed dictionary of a given language. */
376
377static struct dictionary *
379{
380 struct dictionary *retval = XNEW (struct dictionary);
381
385 DICT_HASHED_BUCKETS (retval) = XCNEWVEC (struct symbol *,
387 DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
388
389 return retval;
390}
391
392/* Create a linear dictionary of a given language. */
393
394static struct dictionary *
395dict_create_linear (struct obstack *obstack,
396 enum language language,
397 const std::vector<symbol *> &symbol_list)
398{
399 struct dictionary *retval = XOBNEW (obstack, struct dictionary);
402
403 /* Allocate space for symbols. */
404 int nsyms = symbol_list.size ();
405 DICT_LINEAR_NSYMS (retval) = nsyms;
406 struct symbol **syms = XOBNEWVEC (obstack, struct symbol *, nsyms);
407 DICT_LINEAR_SYMS (retval) = syms;
408
409 /* Now fill in the symbols. */
410 int idx = nsyms - 1;
411 for (const auto &sym : symbol_list)
412 syms[idx--] = sym;
413
414 return retval;
415}
416
417/* Create an expandable linear dictionary of a given language. */
418
419static struct dictionary *
421{
422 struct dictionary *retval = XNEW (struct dictionary);
423
426 DICT_LINEAR_NSYMS (retval) = 0;
428 DICT_LINEAR_SYMS (retval)
429 = XNEWVEC (struct symbol *, DICT_LINEAR_EXPANDABLE_CAPACITY (retval));
430
431 return retval;
432}
433
434/* The functions providing the dictionary interface. */
435
436/* Free the memory used by a dictionary that's not on an obstack. (If
437 any.) */
438
439static void
440dict_free (struct dictionary *dict)
441{
442 (DICT_VECTOR (dict))->free (dict);
443}
444
445/* Add SYM to DICT. DICT had better be expandable. */
446
447static void
448dict_add_symbol (struct dictionary *dict, struct symbol *sym)
449{
450 (DICT_VECTOR (dict))->add_symbol (dict, sym);
451}
452
453/* Utility to add a list of symbols to a dictionary.
454 DICT must be an expandable dictionary. */
455
456static void
458 const std::vector<symbol *> &symbol_list)
459{
460 /* Preserve ordering by reversing the list. */
461 for (auto sym = symbol_list.rbegin (); sym != symbol_list.rend (); ++sym)
462 dict_add_symbol (dict, *sym);
463}
464
465/* Initialize ITERATOR to point at the first symbol in DICT, and
466 return that first symbol, or NULL if DICT is empty. */
467
468static struct symbol *
469dict_iterator_first (const struct dictionary *dict,
470 struct dict_iterator *iterator)
471{
472 return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
473}
474
475/* Advance ITERATOR, and return the next symbol, or NULL if there are
476 no more symbols. */
477
478static struct symbol *
480{
481 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
482 ->iterator_next (iterator);
483}
484
485static struct symbol *
487 const lookup_name_info &name,
488 struct dict_iterator *iterator)
489{
490 return (DICT_VECTOR (dict))->iter_match_first (dict, name, iterator);
491}
492
493static struct symbol *
495 struct dict_iterator *iterator)
496{
497 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
498 ->iter_match_next (name, iterator);
499}
500
501static int
502dict_size (const struct dictionary *dict)
503{
504 return (DICT_VECTOR (dict))->size (dict);
505}
506
507/* Now come functions (well, one function, currently) that are
508 implemented generically by means of the vtable. Typically, they're
509 rarely used. */
510
511
512/* The functions implementing the dictionary interface. */
513
514/* Generic functions, where appropriate. */
515
516static void
518{
519 /* Do nothing! */
520}
521
522static void
523add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
524{
525 internal_error (_("dict_add_symbol: non-expandable dictionary"));
526}
527
528/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
529
530static struct symbol *
532 struct dict_iterator *iterator)
533{
534 DICT_ITERATOR_DICT (iterator) = dict;
535 DICT_ITERATOR_INDEX (iterator) = -1;
536 return iterator_hashed_advance (iterator);
537}
538
539static struct symbol *
541{
542 struct symbol *next;
543
544 next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
545
546 if (next == NULL)
547 return iterator_hashed_advance (iterator);
548 else
549 {
550 DICT_ITERATOR_CURRENT (iterator) = next;
551 return next;
552 }
553}
554
555static struct symbol *
557{
558 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
559 int nbuckets = DICT_HASHED_NBUCKETS (dict);
560 int i;
561
562 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
563 {
564 struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
565
566 if (sym != NULL)
567 {
568 DICT_ITERATOR_INDEX (iterator) = i;
569 DICT_ITERATOR_CURRENT (iterator) = sym;
570 return sym;
571 }
572 }
573
574 return NULL;
575}
576
577static struct symbol *
579 const lookup_name_info &name,
580 struct dict_iterator *iterator)
581{
582 const language_defn *lang = DICT_LANGUAGE (dict);
583 unsigned int hash_index = (name.search_name_hash (lang->la_language)
584 % DICT_HASHED_NBUCKETS (dict));
585 symbol_name_matcher_ftype *matches_name
587 struct symbol *sym;
588
589 DICT_ITERATOR_DICT (iterator) = dict;
590
591 /* Loop through the symbols in the given bucket, breaking when SYM
592 first matches. If SYM never matches, it will be set to NULL;
593 either way, we have the right return value. */
594
595 for (sym = DICT_HASHED_BUCKET (dict, hash_index);
596 sym != NULL;
597 sym = sym->hash_next)
598 {
599 /* Warning: the order of arguments to compare matters! */
600 if (matches_name (sym->search_name (), name, NULL))
601 break;
602 }
603
604 DICT_ITERATOR_CURRENT (iterator) = sym;
605 return sym;
606}
607
608static struct symbol *
610 struct dict_iterator *iterator)
611{
612 const language_defn *lang = DICT_LANGUAGE (DICT_ITERATOR_DICT (iterator));
613 symbol_name_matcher_ftype *matches_name
615 struct symbol *next;
616
617 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
618 next != NULL;
619 next = next->hash_next)
620 {
621 if (matches_name (next->search_name (), name, NULL))
622 break;
623 }
624
625 DICT_ITERATOR_CURRENT (iterator) = next;
626
627 return next;
628}
629
630/* Insert SYM into DICT. */
631
632static void
634 struct symbol *sym)
635{
636 unsigned int hash_index;
637 unsigned int hash;
638 struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
639
640 /* We don't want to insert a symbol into a dictionary of a different
641 language. The two may not use the same hashing algorithm. */
642 gdb_assert (sym->language () == DICT_LANGUAGE (dict)->la_language);
643
644 hash = search_name_hash (sym->language (), sym->search_name ());
645 hash_index = hash % DICT_HASHED_NBUCKETS (dict);
646 sym->hash_next = buckets[hash_index];
647 buckets[hash_index] = sym;
648}
649
650static int
651size_hashed (const struct dictionary *dict)
652{
653 int nbuckets = DICT_HASHED_NBUCKETS (dict);
654 int total = 0;
655
656 for (int i = 0; i < nbuckets; ++i)
657 {
658 for (struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
659 sym != nullptr;
660 sym = sym->hash_next)
661 total++;
662 }
663
664 return total;
665}
666
667/* Functions only for DICT_HASHED_EXPANDABLE. */
668
669static void
671{
672 xfree (DICT_HASHED_BUCKETS (dict));
673 xfree (dict);
674}
675
676static void
678 struct symbol *sym)
679{
680 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
681
682 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
683 expand_hashtable (dict);
684
685 insert_symbol_hashed (dict, sym);
686 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
687}
688
689static int
691{
692 return DICT_HASHED_EXPANDABLE_NSYMS (dict);
693}
694
695static void
697{
698 int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
699 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
700 int new_nbuckets = 2 * old_nbuckets + 1;
701 struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets);
702 int i;
703
704 DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
705 DICT_HASHED_BUCKETS (dict) = new_buckets;
706
707 for (i = 0; i < old_nbuckets; ++i)
708 {
709 struct symbol *sym, *next_sym;
710
711 sym = old_buckets[i];
712 if (sym != NULL)
713 {
714 for (next_sym = sym->hash_next;
715 next_sym != NULL;
716 next_sym = sym->hash_next)
717 {
718 insert_symbol_hashed (dict, sym);
719 sym = next_sym;
720 }
721
722 insert_symbol_hashed (dict, sym);
723 }
724 }
725
726 xfree (old_buckets);
727}
728
729/* See dictionary.h. */
730
731unsigned int
732language_defn::search_name_hash (const char *string0) const
733{
734 /* The Ada-encoded version of a name P1.P2...Pn has either the form
735 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
736 are lower-cased identifiers). The <suffix> (which can be empty)
737 encodes additional information about the denoted entity. This
738 routine hashes such names to msymbol_hash_iw(Pn). It actually
739 does this for a superset of both valid Pi and of <suffix>, but
740 in other cases it simply returns msymbol_hash_iw(STRING0). */
741
742 const char *string;
743 unsigned int hash;
744
745 string = string0;
746 if (*string == '_')
747 {
748 if (startswith (string, "_ada_"))
749 string += 5;
750 else
751 return msymbol_hash_iw (string0);
752 }
753
754 hash = 0;
755 while (*string)
756 {
757 switch (*string)
758 {
759 case '$':
760 case '.':
761 case 'X':
762 if (string0 == string)
763 return msymbol_hash_iw (string0);
764 else
765 return hash;
766 case ' ':
767 case '(':
768 return msymbol_hash_iw (string0);
769 case '_':
770 if (string[1] == '_' && string != string0)
771 {
772 int c = string[2];
773
774 if (c == 'B' && string[3] == '_')
775 {
776 for (string += 4; ISDIGIT (*string); ++string)
777 ;
778 continue;
779 }
780
781 if ((c < 'a' || c > 'z') && c != 'O')
782 return hash;
783 hash = 0;
784 string += 2;
785 continue;
786 }
787 break;
788 case 'T':
789 /* Ignore "TKB" suffixes.
790
791 These are used by Ada for subprograms implementing a task body.
792 For instance for a task T inside package Pck, the name of the
793 subprogram implementing T's body is `pck__tTKB'. We need to
794 ignore the "TKB" suffix because searches for this task body
795 subprogram are going to be performed using `pck__t' (the encoded
796 version of the natural name `pck.t'). */
797 if (strcmp (string, "TKB") == 0)
798 return hash;
799 break;
800 }
801
802 hash = SYMBOL_HASH_NEXT (hash, *string);
803 string += 1;
804 }
805 return hash;
806}
807
808/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
809
810static struct symbol *
812 struct dict_iterator *iterator)
813{
814 DICT_ITERATOR_DICT (iterator) = dict;
815 DICT_ITERATOR_INDEX (iterator) = 0;
816 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
817}
818
819static struct symbol *
821{
822 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
823
824 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
825 return NULL;
826 else
827 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
828}
829
830static struct symbol *
832 const lookup_name_info &name,
833 struct dict_iterator *iterator)
834{
835 DICT_ITERATOR_DICT (iterator) = dict;
836 DICT_ITERATOR_INDEX (iterator) = -1;
837
838 return iter_match_next_linear (name, iterator);
839}
840
841static struct symbol *
843 struct dict_iterator *iterator)
844{
845 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
846 const language_defn *lang = DICT_LANGUAGE (dict);
847 symbol_name_matcher_ftype *matches_name
849
850 int i, nsyms = DICT_LINEAR_NSYMS (dict);
851 struct symbol *sym, *retval = NULL;
852
853 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
854 {
855 sym = DICT_LINEAR_SYM (dict, i);
856
857 if (matches_name (sym->search_name (), name, NULL))
858 {
859 retval = sym;
860 break;
861 }
862 }
863
864 DICT_ITERATOR_INDEX (iterator) = i;
865
866 return retval;
867}
868
869static int
870size_linear (const struct dictionary *dict)
871{
872 return DICT_LINEAR_NSYMS (dict);
873}
874
875/* Functions only for DICT_LINEAR_EXPANDABLE. */
876
877static void
879{
880 xfree (DICT_LINEAR_SYMS (dict));
881 xfree (dict);
882}
883
884
885static void
887 struct symbol *sym)
888{
889 int nsyms = ++DICT_LINEAR_NSYMS (dict);
890
891 /* Do we have enough room? If not, grow it. */
892 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
893 {
895 DICT_LINEAR_SYMS (dict)
896 = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict),
898 }
899
900 DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
901}
902
903/* Multi-language dictionary support. */
904
905/* The structure describing a multi-language dictionary. */
906
908{
909 /* An array of dictionaries, one per language. All dictionaries
910 must be of the same type. This should be free'd for expandable
911 dictionary types. */
913
914 /* The number of language dictionaries currently allocated.
915 Only used for expandable dictionaries. */
917};
918
919/* A hasher for enum language. Injecting this into std is a convenience
920 when using unordered_map with C++11. */
921
922namespace std
923{
924 template<> struct hash<enum language>
925 {
927 typedef std::size_t result_type;
928
929 result_type operator() (const argument_type &l) const noexcept
930 {
931 return static_cast<result_type> (l);
932 }
933 };
934} /* namespace std */
935
936/* A helper function to collate symbols on the pending list by language. */
937
938static std::unordered_map<enum language, std::vector<symbol *>>
940{
941 std::unordered_map<enum language, std::vector<symbol *>> nsyms;
942
943 for (const pending *list_counter = symbol_list;
944 list_counter != nullptr; list_counter = list_counter->next)
945 {
946 for (int i = list_counter->nsyms - 1; i >= 0; --i)
947 {
948 enum language language = list_counter->symbol[i]->language ();
949 nsyms[language].push_back (list_counter->symbol[i]);
950 }
951 }
952
953 return nsyms;
954}
955
956/* See dictionary.h. */
957
958struct multidictionary *
959mdict_create_hashed (struct obstack *obstack,
960 const struct pending *symbol_list)
961{
962 struct multidictionary *retval
963 = XOBNEW (obstack, struct multidictionary);
964 std::unordered_map<enum language, std::vector<symbol *>> nsyms
966
967 /* Loop over all languages and create/populate dictionaries. */
968 retval->dictionaries
969 = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
970 retval->n_allocated_dictionaries = nsyms.size ();
971
972 int idx = 0;
973 for (const auto &pair : nsyms)
974 {
975 enum language language = pair.first;
976 std::vector<symbol *> symlist = pair.second;
977
978 retval->dictionaries[idx++]
979 = dict_create_hashed (obstack, language, symlist);
980 }
981
982 return retval;
983}
984
985/* See dictionary.h. */
986
987struct multidictionary *
989{
990 struct multidictionary *retval = XNEW (struct multidictionary);
991
992 /* We have no symbol list to populate, but we create an empty
993 dictionary of the requested language to populate later. */
994 retval->n_allocated_dictionaries = 1;
995 retval->dictionaries = XNEW (struct dictionary *);
997
998 return retval;
999}
1000
1001/* See dictionary.h. */
1002
1003struct multidictionary *
1004mdict_create_linear (struct obstack *obstack,
1005 const struct pending *symbol_list)
1006{
1007 struct multidictionary *retval
1008 = XOBNEW (obstack, struct multidictionary);
1009 std::unordered_map<enum language, std::vector<symbol *>> nsyms
1011
1012 /* Loop over all languages and create/populate dictionaries. */
1013 retval->dictionaries
1014 = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
1015 retval->n_allocated_dictionaries = nsyms.size ();
1016
1017 int idx = 0;
1018 for (const auto &pair : nsyms)
1019 {
1020 enum language language = pair.first;
1021 std::vector<symbol *> symlist = pair.second;
1022
1023 retval->dictionaries[idx++]
1024 = dict_create_linear (obstack, language, symlist);
1025 }
1026
1027 return retval;
1028}
1029
1030/* See dictionary.h. */
1031
1032struct multidictionary *
1034{
1035 struct multidictionary *retval = XNEW (struct multidictionary);
1036
1037 /* We have no symbol list to populate, but we create an empty
1038 dictionary to populate later. */
1039 retval->n_allocated_dictionaries = 1;
1040 retval->dictionaries = XNEW (struct dictionary *);
1042
1043 return retval;
1044}
1045
1046/* See dictionary.h. */
1047
1048void
1050{
1051 /* Grab the type of dictionary being used. */
1052 enum dict_type type = mdict->dictionaries[0]->vector->type;
1053
1054 /* Loop over all dictionaries and free them. */
1055 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1056 dict_free (mdict->dictionaries[idx]);
1057
1058 /* Free the dictionary list, if needed. */
1059 switch (type)
1060 {
1061 case DICT_HASHED:
1062 case DICT_LINEAR:
1063 /* Memory was allocated on an obstack when created. */
1064 break;
1065
1068 xfree (mdict->dictionaries);
1069 break;
1070 }
1071}
1072
1073/* Helper function to find the dictionary associated with LANGUAGE
1074 or NULL if there is no dictionary of that language. */
1075
1076static struct dictionary *
1078 enum language language)
1079{
1080 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1081 {
1082 if (DICT_LANGUAGE (mdict->dictionaries[idx])->la_language == language)
1083 return mdict->dictionaries[idx];
1084 }
1085
1086 return nullptr;
1087}
1088
1089/* Create a new language dictionary for LANGUAGE and add it to the
1090 multidictionary MDICT's list of dictionaries. If MDICT is not
1091 based on expandable dictionaries, this function throws an
1092 internal error. */
1093
1094static struct dictionary *
1096 enum language language)
1097{
1098 struct dictionary *retval = nullptr;
1099
1100 /* We use the first dictionary entry to decide what create function
1101 to call. Not optimal but sufficient. */
1102 gdb_assert (mdict->dictionaries[0] != nullptr);
1103 switch (mdict->dictionaries[0]->vector->type)
1104 {
1105 case DICT_HASHED:
1106 case DICT_LINEAR:
1107 internal_error (_("create_new_language_dictionary: attempted to expand "
1108 "non-expandable multidictionary"));
1109
1112 break;
1113
1116 break;
1117 }
1118
1119 /* Grow the dictionary vector and save the new dictionary. */
1120 mdict->dictionaries
1121 = (struct dictionary **) xrealloc (mdict->dictionaries,
1122 (++mdict->n_allocated_dictionaries
1123 * sizeof (struct dictionary *)));
1124 mdict->dictionaries[mdict->n_allocated_dictionaries - 1] = retval;
1125
1126 return retval;
1127}
1128
1129/* See dictionary.h. */
1130
1131void
1132mdict_add_symbol (struct multidictionary *mdict, struct symbol *sym)
1133{
1134 struct dictionary *dict
1135 = find_language_dictionary (mdict, sym->language ());
1136
1137 if (dict == nullptr)
1138 {
1139 /* SYM is of a new language that we haven't previously seen.
1140 Create a new dictionary for it. */
1141 dict = create_new_language_dictionary (mdict, sym->language ());
1142 }
1143
1144 dict_add_symbol (dict, sym);
1145}
1146
1147/* See dictionary.h. */
1148
1149void
1151 const struct pending *symbol_list)
1152{
1153 std::unordered_map<enum language, std::vector<symbol *>> nsyms
1155
1156 for (const auto &pair : nsyms)
1157 {
1158 enum language language = pair.first;
1159 std::vector<symbol *> symlist = pair.second;
1160 struct dictionary *dict = find_language_dictionary (mdict, language);
1161
1162 if (dict == nullptr)
1163 {
1164 /* The language was not previously seen. Create a new dictionary
1165 for it. */
1167 }
1168
1169 dict_add_pending (dict, symlist);
1170 }
1171}
1172
1173/* See dictionary.h. */
1174
1175struct symbol *
1177 struct mdict_iterator *miterator)
1178{
1179 miterator->mdict = mdict;
1180 miterator->current_idx = 0;
1181
1182 for (unsigned short idx = miterator->current_idx;
1183 idx < mdict->n_allocated_dictionaries; ++idx)
1184 {
1185 struct symbol *result
1186 = dict_iterator_first (mdict->dictionaries[idx], &miterator->iterator);
1187
1188 if (result != nullptr)
1189 {
1190 miterator->current_idx = idx;
1191 return result;
1192 }
1193 }
1194
1195 return nullptr;
1196}
1197
1198/* See dictionary.h. */
1199
1200struct symbol *
1202{
1203 struct symbol *result = dict_iterator_next (&miterator->iterator);
1204
1205 if (result != nullptr)
1206 return result;
1207
1208 /* The current dictionary had no matches -- move to the next
1209 dictionary, if any. */
1210 for (unsigned short idx = ++miterator->current_idx;
1211 idx < miterator->mdict->n_allocated_dictionaries; ++idx)
1212 {
1213 result
1214 = dict_iterator_first (miterator->mdict->dictionaries[idx],
1215 &miterator->iterator);
1216 if (result != nullptr)
1217 {
1218 miterator->current_idx = idx;
1219 return result;
1220 }
1221 }
1222
1223 return nullptr;
1224}
1225
1226/* See dictionary.h. */
1227
1228struct symbol *
1230 const lookup_name_info &name,
1231 struct mdict_iterator *miterator)
1232{
1233 miterator->mdict = mdict;
1234 miterator->current_idx = 0;
1235
1236 for (unsigned short idx = miterator->current_idx;
1237 idx < mdict->n_allocated_dictionaries; ++idx)
1238 {
1239 struct symbol *result
1240 = dict_iter_match_first (mdict->dictionaries[idx], name,
1241 &miterator->iterator);
1242
1243 if (result != nullptr)
1244 return result;
1245 }
1246
1247 return nullptr;
1248}
1249
1250/* See dictionary.h. */
1251
1252struct symbol *
1254 struct mdict_iterator *miterator)
1255{
1256 /* Search the current dictionary. */
1257 struct symbol *result = dict_iter_match_next (name, &miterator->iterator);
1258
1259 if (result != nullptr)
1260 return result;
1261
1262 /* The current dictionary had no matches -- move to the next
1263 dictionary, if any. */
1264 for (unsigned short idx = ++miterator->current_idx;
1265 idx < miterator->mdict->n_allocated_dictionaries; ++idx)
1266 {
1267 result
1268 = dict_iter_match_first (miterator->mdict->dictionaries[idx],
1269 name, &miterator->iterator);
1270 if (result != nullptr)
1271 {
1272 miterator->current_idx = idx;
1273 return result;
1274 }
1275 }
1276
1277 return nullptr;
1278}
1279
1280/* See dictionary.h. */
1281
1282int
1283mdict_size (const struct multidictionary *mdict)
1284{
1285 int size = 0;
1286
1287 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1288 size += dict_size (mdict->dictionaries[idx]);
1289
1290 return size;
1291}
const char *const name
void xfree(void *)
void * xrealloc(void *ptr, size_t size)
Definition alloc.c:65
language
Definition defs.h:211
int mdict_size(const struct multidictionary *mdict)
static void dict_add_pending(struct dictionary *dict, const std::vector< symbol * > &symbol_list)
Definition dictionary.c:457
#define DICT_HASHED_BUCKET(d, i)
Definition dictionary.c:190
static struct dictionary * dict_create_linear_expandable(enum language language)
Definition dictionary.c:420
#define DICT_LINEAR_SYMS(d)
Definition dictionary.c:197
static struct dictionary * dict_create_hashed(struct obstack *obstack, enum language language, const std::vector< symbol * > &symbol_list)
Definition dictionary.c:351
static struct symbol * iterator_first_hashed(const struct dictionary *dict, struct dict_iterator *iterator)
Definition dictionary.c:531
static const struct dict_vector dict_linear_vector
Definition dictionary.c:312
#define DICT_VECTOR(d)
Definition dictionary.c:183
static struct symbol * iterator_hashed_advance(struct dict_iterator *iter)
Definition dictionary.c:556
void mdict_free(struct multidictionary *mdict)
static int size_hashed(const struct dictionary *dict)
Definition dictionary.c:651
#define DICT_ITERATOR_CURRENT(iter)
Definition dictionary.c:223
dict_type
Definition dictionary.c:93
@ DICT_HASHED_EXPANDABLE
Definition dictionary.c:97
@ DICT_HASHED
Definition dictionary.c:95
@ DICT_LINEAR_EXPANDABLE
Definition dictionary.c:101
@ DICT_LINEAR
Definition dictionary.c:99
static struct dictionary * find_language_dictionary(const struct multidictionary *mdict, enum language language)
static struct symbol * iter_match_next_hashed(const lookup_name_info &name, struct dict_iterator *iterator)
Definition dictionary.c:609
struct symbol * mdict_iterator_first(const multidictionary *mdict, struct mdict_iterator *miterator)
#define DICT_HASHED_EXPANDABLE_NSYMS(d)
Definition dictionary.c:192
static struct symbol * dict_iterator_next(struct dict_iterator *iterator)
Definition dictionary.c:479
static std::unordered_map< enum language, std::vector< symbol * > > collate_pending_symbols_by_language(const struct pending *symbol_list)
Definition dictionary.c:939
struct symbol * mdict_iter_match_next(const lookup_name_info &name, struct mdict_iterator *miterator)
static struct symbol * dict_iterator_first(const struct dictionary *dict, struct dict_iterator *iterator)
Definition dictionary.c:469
struct multidictionary * mdict_create_hashed_expandable(enum language language)
Definition dictionary.c:988
static struct dictionary * create_new_language_dictionary(struct multidictionary *mdict, enum language language)
struct multidictionary * mdict_create_linear_expandable(enum language language)
struct multidictionary * mdict_create_hashed(struct obstack *obstack, const struct pending *symbol_list)
Definition dictionary.c:959
#define DICT_LINEAR_SYM(d, i)
Definition dictionary.c:198
static const struct dict_vector dict_linear_expandable_vector
Definition dictionary.c:324
static struct dictionary * dict_create_linear(struct obstack *obstack, enum language language, const std::vector< symbol * > &symbol_list)
Definition dictionary.c:395
static int size_hashed_expandable(const struct dictionary *dict)
Definition dictionary.c:690
#define DICT_HASHED_NBUCKETS(d)
Definition dictionary.c:188
#define DICT_HASHED_BUCKETS(d)
Definition dictionary.c:189
static const struct dict_vector dict_hashed_vector
Definition dictionary.c:288
static struct symbol * iterator_next_hashed(struct dict_iterator *iterator)
Definition dictionary.c:540
#define DICT_LINEAR_EXPANDABLE_CAPACITY(d)
Definition dictionary.c:200
struct symbol * mdict_iter_match_first(const struct multidictionary *mdict, const lookup_name_info &name, struct mdict_iterator *miterator)
static struct symbol * iter_match_first_linear(const struct dictionary *dict, const lookup_name_info &name, struct dict_iterator *iterator)
Definition dictionary.c:831
static void add_symbol_nonexpandable(struct dictionary *dict, struct symbol *sym)
Definition dictionary.c:523
static struct symbol * iterator_next_linear(struct dict_iterator *iterator)
Definition dictionary.c:820
static struct symbol * dict_iter_match_next(const lookup_name_info &name, struct dict_iterator *iterator)
Definition dictionary.c:494
static void expand_hashtable(struct dictionary *dict)
Definition dictionary.c:696
static struct symbol * dict_iter_match_first(const struct dictionary *dict, const lookup_name_info &name, struct dict_iterator *iterator)
Definition dictionary.c:486
#define DICT_ITERATOR_DICT(iter)
Definition dictionary.c:217
#define DICT_LINEAR_NSYMS(d)
Definition dictionary.c:196
static void free_hashed_expandable(struct dictionary *dict)
Definition dictionary.c:670
static struct symbol * iterator_first_linear(const struct dictionary *dict, struct dict_iterator *iterator)
Definition dictionary.c:811
static int size_linear(const struct dictionary *dict)
Definition dictionary.c:870
static void free_linear_expandable(struct dictionary *dict)
Definition dictionary.c:878
#define DICT_HASHTABLE_SIZE(n)
Definition dictionary.c:210
static void add_symbol_hashed_expandable(struct dictionary *dict, struct symbol *sym)
Definition dictionary.c:677
static int dict_size(const struct dictionary *dict)
Definition dictionary.c:502
static struct dictionary * dict_create_hashed_expandable(enum language language)
Definition dictionary.c:378
static struct symbol * iter_match_first_hashed(const struct dictionary *dict, const lookup_name_info &name, struct dict_iterator *iterator)
Definition dictionary.c:578
static void dict_add_symbol(struct dictionary *dict, struct symbol *sym)
Definition dictionary.c:448
static void dict_free(struct dictionary *dict)
Definition dictionary.c:440
static const struct dict_vector dict_hashed_expandable_vector
Definition dictionary.c:300
void mdict_add_symbol(struct multidictionary *mdict, struct symbol *sym)
static void add_symbol_linear_expandable(struct dictionary *dict, struct symbol *sym)
Definition dictionary.c:886
static void insert_symbol_hashed(struct dictionary *dict, struct symbol *sym)
Definition dictionary.c:633
struct symbol * mdict_iterator_next(struct mdict_iterator *miterator)
static struct symbol * iter_match_next_linear(const lookup_name_info &name, struct dict_iterator *iterator)
Definition dictionary.c:842
#define DICT_EXPANDABLE_INITIAL_CAPACITY
Definition dictionary.c:205
struct multidictionary * mdict_create_linear(struct obstack *obstack, const struct pending *symbol_list)
#define DICT_LANGUAGE(d)
Definition dictionary.c:184
void mdict_add_pending(struct multidictionary *mdict, const struct pending *symbol_list)
#define DICT_ITERATOR_INDEX(iter)
Definition dictionary.c:220
static void free_obstack(struct dictionary *dict)
Definition dictionary.c:517
size_t size
Definition go32-nat.c:239
const struct language_defn * language_def(enum language lang)
Definition language.c:439
static void add_symbol(struct symbol *, struct symtab *, struct block *)
unsigned int msymbol_hash_iw(const char *string)
Definition minsyms.c:165
#define SYMBOL_HASH_NEXT(hash, c)
Definition minsyms.h:196
Definition aarch64.h:67
void(* add_symbol)(struct dictionary *dict, struct symbol *sym)
Definition dictionary.c:114
int(* size)(const struct dictionary *dict)
Definition dictionary.c:126
void(* free)(struct dictionary *dict)
Definition dictionary.c:112
enum dict_type type
Definition dictionary.c:110
struct symbol ** buckets
Definition dictionary.c:137
struct symbol ** syms
Definition dictionary.c:153
struct dictionary_hashed hashed
Definition dictionary.c:173
const struct dict_vector * vector
Definition dictionary.c:170
struct dictionary_linear linear
Definition dictionary.c:175
struct dictionary_linear_expandable linear_expandable
Definition dictionary.c:176
struct dictionary_hashed_expandable hashed_expandable
Definition dictionary.c:174
const struct language_defn * language
Definition dictionary.c:169
union dictionary::@38 data
struct obstack * obstack
Definition symtab.h:585
const char * search_name() const
Definition symtab.c:1106
enum language language() const
Definition symtab.h:502
enum language la_language
Definition language.h:275
symbol_name_matcher_ftype * get_symbol_name_matcher(const lookup_name_info &lookup_name) const
Definition language.c:666
virtual unsigned int search_name_hash(const char *name) const
Definition dictionary.c:732
struct dict_iterator iterator
Definition dictionary.h:120
const struct multidictionary * mdict
Definition dictionary.h:117
unsigned short current_idx
Definition dictionary.h:123
unsigned short n_allocated_dictionaries
Definition dictionary.c:916
struct dictionary ** dictionaries
Definition dictionary.c:912
struct pending * next
Definition buildsym.h:79
enum language argument_type
Definition dictionary.c:926
struct symbol * hash_next
Definition symtab.h:1524
unsigned int search_name_hash(enum language language, const char *search_name)
Definition symtab.c:1928
bool symbol_name_matcher_ftype(const char *symbol_search_name, const lookup_name_info &lookup_name, completion_match_result *comp_match_res)
Definition symtab.h:399