GDB (xrefs)
Loading...
Searching...
No Matches
/tmp/gdb-13.1/gdb/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 "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
168{
169 const struct language_defn *language;
170 const struct dict_vector *vector;
171 union
172 {
177 }
179};
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 return DICT_HASHED_NBUCKETS (dict);
654}
655
656/* Functions only for DICT_HASHED_EXPANDABLE. */
657
658static void
660{
661 xfree (DICT_HASHED_BUCKETS (dict));
662 xfree (dict);
663}
664
665static void
667 struct symbol *sym)
668{
669 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
670
671 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
672 expand_hashtable (dict);
673
674 insert_symbol_hashed (dict, sym);
675 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
676}
677
678static int
680{
681 return DICT_HASHED_EXPANDABLE_NSYMS (dict);
682}
683
684static void
686{
687 int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
688 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
689 int new_nbuckets = 2 * old_nbuckets + 1;
690 struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets);
691 int i;
692
693 DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
694 DICT_HASHED_BUCKETS (dict) = new_buckets;
695
696 for (i = 0; i < old_nbuckets; ++i)
697 {
698 struct symbol *sym, *next_sym;
699
700 sym = old_buckets[i];
701 if (sym != NULL)
702 {
703 for (next_sym = sym->hash_next;
704 next_sym != NULL;
705 next_sym = sym->hash_next)
706 {
707 insert_symbol_hashed (dict, sym);
708 sym = next_sym;
709 }
710
711 insert_symbol_hashed (dict, sym);
712 }
713 }
714
715 xfree (old_buckets);
716}
717
718/* See dictionary.h. */
719
720unsigned int
721language_defn::search_name_hash (const char *string0) const
722{
723 /* The Ada-encoded version of a name P1.P2...Pn has either the form
724 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
725 are lower-cased identifiers). The <suffix> (which can be empty)
726 encodes additional information about the denoted entity. This
727 routine hashes such names to msymbol_hash_iw(Pn). It actually
728 does this for a superset of both valid Pi and of <suffix>, but
729 in other cases it simply returns msymbol_hash_iw(STRING0). */
730
731 const char *string;
732 unsigned int hash;
733
734 string = string0;
735 if (*string == '_')
736 {
737 if (startswith (string, "_ada_"))
738 string += 5;
739 else
740 return msymbol_hash_iw (string0);
741 }
742
743 hash = 0;
744 while (*string)
745 {
746 switch (*string)
747 {
748 case '$':
749 case '.':
750 case 'X':
751 if (string0 == string)
752 return msymbol_hash_iw (string0);
753 else
754 return hash;
755 case ' ':
756 case '(':
757 return msymbol_hash_iw (string0);
758 case '_':
759 if (string[1] == '_' && string != string0)
760 {
761 int c = string[2];
762
763 if (c == 'B' && string[3] == '_')
764 {
765 for (string += 4; ISDIGIT (*string); ++string)
766 ;
767 continue;
768 }
769
770 if ((c < 'a' || c > 'z') && c != 'O')
771 return hash;
772 hash = 0;
773 string += 2;
774 continue;
775 }
776 break;
777 case 'T':
778 /* Ignore "TKB" suffixes.
779
780 These are used by Ada for subprograms implementing a task body.
781 For instance for a task T inside package Pck, the name of the
782 subprogram implementing T's body is `pck__tTKB'. We need to
783 ignore the "TKB" suffix because searches for this task body
784 subprogram are going to be performed using `pck__t' (the encoded
785 version of the natural name `pck.t'). */
786 if (strcmp (string, "TKB") == 0)
787 return hash;
788 break;
789 }
790
791 hash = SYMBOL_HASH_NEXT (hash, *string);
792 string += 1;
793 }
794 return hash;
795}
796
797/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
798
799static struct symbol *
801 struct dict_iterator *iterator)
802{
803 DICT_ITERATOR_DICT (iterator) = dict;
804 DICT_ITERATOR_INDEX (iterator) = 0;
805 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
806}
807
808static struct symbol *
810{
811 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
812
813 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
814 return NULL;
815 else
816 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
817}
818
819static struct symbol *
821 const lookup_name_info &name,
822 struct dict_iterator *iterator)
823{
824 DICT_ITERATOR_DICT (iterator) = dict;
825 DICT_ITERATOR_INDEX (iterator) = -1;
826
827 return iter_match_next_linear (name, iterator);
828}
829
830static struct symbol *
832 struct dict_iterator *iterator)
833{
834 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
835 const language_defn *lang = DICT_LANGUAGE (dict);
836 symbol_name_matcher_ftype *matches_name
838
839 int i, nsyms = DICT_LINEAR_NSYMS (dict);
840 struct symbol *sym, *retval = NULL;
841
842 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
843 {
844 sym = DICT_LINEAR_SYM (dict, i);
845
846 if (matches_name (sym->search_name (), name, NULL))
847 {
848 retval = sym;
849 break;
850 }
851 }
852
853 DICT_ITERATOR_INDEX (iterator) = i;
854
855 return retval;
856}
857
858static int
859size_linear (const struct dictionary *dict)
860{
861 return DICT_LINEAR_NSYMS (dict);
862}
863
864/* Functions only for DICT_LINEAR_EXPANDABLE. */
865
866static void
868{
869 xfree (DICT_LINEAR_SYMS (dict));
870 xfree (dict);
871}
872
873
874static void
876 struct symbol *sym)
877{
878 int nsyms = ++DICT_LINEAR_NSYMS (dict);
879
880 /* Do we have enough room? If not, grow it. */
881 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
882 {
884 DICT_LINEAR_SYMS (dict)
885 = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict),
887 }
888
889 DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
890}
891
892/* Multi-language dictionary support. */
893
894/* The structure describing a multi-language dictionary. */
895
897{
898 /* An array of dictionaries, one per language. All dictionaries
899 must be of the same type. This should be free'd for expandable
900 dictionary types. */
902
903 /* The number of language dictionaries currently allocated.
904 Only used for expandable dictionaries. */
906};
907
908/* A hasher for enum language. Injecting this into std is a convenience
909 when using unordered_map with C++11. */
910
911namespace std
912{
913 template<> struct hash<enum language>
914 {
916 typedef std::size_t result_type;
917
918 result_type operator() (const argument_type &l) const noexcept
919 {
920 return static_cast<result_type> (l);
921 }
922 };
923} /* namespace std */
924
925/* A helper function to collate symbols on the pending list by language. */
926
927static std::unordered_map<enum language, std::vector<symbol *>>
929{
930 std::unordered_map<enum language, std::vector<symbol *>> nsyms;
931
932 for (const pending *list_counter = symbol_list;
933 list_counter != nullptr; list_counter = list_counter->next)
934 {
935 for (int i = list_counter->nsyms - 1; i >= 0; --i)
936 {
937 enum language language = list_counter->symbol[i]->language ();
938 nsyms[language].push_back (list_counter->symbol[i]);
939 }
940 }
941
942 return nsyms;
943}
944
945/* See dictionary.h. */
946
947struct multidictionary *
948mdict_create_hashed (struct obstack *obstack,
949 const struct pending *symbol_list)
950{
951 struct multidictionary *retval
952 = XOBNEW (obstack, struct multidictionary);
953 std::unordered_map<enum language, std::vector<symbol *>> nsyms
955
956 /* Loop over all languages and create/populate dictionaries. */
957 retval->dictionaries
958 = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
959 retval->n_allocated_dictionaries = nsyms.size ();
960
961 int idx = 0;
962 for (const auto &pair : nsyms)
963 {
964 enum language language = pair.first;
965 std::vector<symbol *> symlist = pair.second;
966
967 retval->dictionaries[idx++]
968 = dict_create_hashed (obstack, language, symlist);
969 }
970
971 return retval;
972}
973
974/* See dictionary.h. */
975
976struct multidictionary *
978{
979 struct multidictionary *retval = XNEW (struct multidictionary);
980
981 /* We have no symbol list to populate, but we create an empty
982 dictionary of the requested language to populate later. */
983 retval->n_allocated_dictionaries = 1;
984 retval->dictionaries = XNEW (struct dictionary *);
986
987 return retval;
988}
989
990/* See dictionary.h. */
991
992struct multidictionary *
993mdict_create_linear (struct obstack *obstack,
994 const struct pending *symbol_list)
995{
996 struct multidictionary *retval
997 = XOBNEW (obstack, struct multidictionary);
998 std::unordered_map<enum language, std::vector<symbol *>> nsyms
1000
1001 /* Loop over all languages and create/populate dictionaries. */
1002 retval->dictionaries
1003 = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
1004 retval->n_allocated_dictionaries = nsyms.size ();
1005
1006 int idx = 0;
1007 for (const auto &pair : nsyms)
1008 {
1009 enum language language = pair.first;
1010 std::vector<symbol *> symlist = pair.second;
1011
1012 retval->dictionaries[idx++]
1013 = dict_create_linear (obstack, language, symlist);
1014 }
1015
1016 return retval;
1017}
1018
1019/* See dictionary.h. */
1020
1021struct multidictionary *
1023{
1024 struct multidictionary *retval = XNEW (struct multidictionary);
1025
1026 /* We have no symbol list to populate, but we create an empty
1027 dictionary to populate later. */
1028 retval->n_allocated_dictionaries = 1;
1029 retval->dictionaries = XNEW (struct dictionary *);
1031
1032 return retval;
1033}
1034
1035/* See dictionary.h. */
1036
1037void
1039{
1040 /* Grab the type of dictionary being used. */
1041 enum dict_type type = mdict->dictionaries[0]->vector->type;
1042
1043 /* Loop over all dictionaries and free them. */
1044 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1045 dict_free (mdict->dictionaries[idx]);
1046
1047 /* Free the dictionary list, if needed. */
1048 switch (type)
1049 {
1050 case DICT_HASHED:
1051 case DICT_LINEAR:
1052 /* Memory was allocated on an obstack when created. */
1053 break;
1054
1057 xfree (mdict->dictionaries);
1058 break;
1059 }
1060}
1061
1062/* Helper function to find the dictionary associated with LANGUAGE
1063 or NULL if there is no dictionary of that language. */
1064
1065static struct dictionary *
1067 enum language language)
1068{
1069 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1070 {
1071 if (DICT_LANGUAGE (mdict->dictionaries[idx])->la_language == language)
1072 return mdict->dictionaries[idx];
1073 }
1074
1075 return nullptr;
1076}
1077
1078/* Create a new language dictionary for LANGUAGE and add it to the
1079 multidictionary MDICT's list of dictionaries. If MDICT is not
1080 based on expandable dictionaries, this function throws an
1081 internal error. */
1082
1083static struct dictionary *
1085 enum language language)
1086{
1087 struct dictionary *retval = nullptr;
1088
1089 /* We use the first dictionary entry to decide what create function
1090 to call. Not optimal but sufficient. */
1091 gdb_assert (mdict->dictionaries[0] != nullptr);
1092 switch (mdict->dictionaries[0]->vector->type)
1093 {
1094 case DICT_HASHED:
1095 case DICT_LINEAR:
1096 internal_error (_("create_new_language_dictionary: attempted to expand "
1097 "non-expandable multidictionary"));
1098
1101 break;
1102
1105 break;
1106 }
1107
1108 /* Grow the dictionary vector and save the new dictionary. */
1109 mdict->dictionaries
1110 = (struct dictionary **) xrealloc (mdict->dictionaries,
1111 (++mdict->n_allocated_dictionaries
1112 * sizeof (struct dictionary *)));
1113 mdict->dictionaries[mdict->n_allocated_dictionaries - 1] = retval;
1114
1115 return retval;
1116}
1117
1118/* See dictionary.h. */
1119
1120void
1121mdict_add_symbol (struct multidictionary *mdict, struct symbol *sym)
1122{
1123 struct dictionary *dict
1124 = find_language_dictionary (mdict, sym->language ());
1125
1126 if (dict == nullptr)
1127 {
1128 /* SYM is of a new language that we haven't previously seen.
1129 Create a new dictionary for it. */
1130 dict = create_new_language_dictionary (mdict, sym->language ());
1131 }
1132
1133 dict_add_symbol (dict, sym);
1134}
1135
1136/* See dictionary.h. */
1137
1138void
1140 const struct pending *symbol_list)
1141{
1142 std::unordered_map<enum language, std::vector<symbol *>> nsyms
1144
1145 for (const auto &pair : nsyms)
1146 {
1147 enum language language = pair.first;
1148 std::vector<symbol *> symlist = pair.second;
1149 struct dictionary *dict = find_language_dictionary (mdict, language);
1150
1151 if (dict == nullptr)
1152 {
1153 /* The language was not previously seen. Create a new dictionary
1154 for it. */
1156 }
1157
1158 dict_add_pending (dict, symlist);
1159 }
1160}
1161
1162/* See dictionary.h. */
1163
1164struct symbol *
1166 struct mdict_iterator *miterator)
1167{
1168 miterator->mdict = mdict;
1169 miterator->current_idx = 0;
1170
1171 for (unsigned short idx = miterator->current_idx;
1172 idx < mdict->n_allocated_dictionaries; ++idx)
1173 {
1174 struct symbol *result
1175 = dict_iterator_first (mdict->dictionaries[idx], &miterator->iterator);
1176
1177 if (result != nullptr)
1178 {
1179 miterator->current_idx = idx;
1180 return result;
1181 }
1182 }
1183
1184 return nullptr;
1185}
1186
1187/* See dictionary.h. */
1188
1189struct symbol *
1191{
1192 struct symbol *result = dict_iterator_next (&miterator->iterator);
1193
1194 if (result != nullptr)
1195 return result;
1196
1197 /* The current dictionary had no matches -- move to the next
1198 dictionary, if any. */
1199 for (unsigned short idx = ++miterator->current_idx;
1200 idx < miterator->mdict->n_allocated_dictionaries; ++idx)
1201 {
1202 result
1203 = dict_iterator_first (miterator->mdict->dictionaries[idx],
1204 &miterator->iterator);
1205 if (result != nullptr)
1206 {
1207 miterator->current_idx = idx;
1208 return result;
1209 }
1210 }
1211
1212 return nullptr;
1213}
1214
1215/* See dictionary.h. */
1216
1217struct symbol *
1219 const lookup_name_info &name,
1220 struct mdict_iterator *miterator)
1221{
1222 miterator->mdict = mdict;
1223 miterator->current_idx = 0;
1224
1225 for (unsigned short idx = miterator->current_idx;
1226 idx < mdict->n_allocated_dictionaries; ++idx)
1227 {
1228 struct symbol *result
1229 = dict_iter_match_first (mdict->dictionaries[idx], name,
1230 &miterator->iterator);
1231
1232 if (result != nullptr)
1233 return result;
1234 }
1235
1236 return nullptr;
1237}
1238
1239/* See dictionary.h. */
1240
1241struct symbol *
1243 struct mdict_iterator *miterator)
1244{
1245 /* Search the current dictionary. */
1246 struct symbol *result = dict_iter_match_next (name, &miterator->iterator);
1247
1248 if (result != nullptr)
1249 return result;
1250
1251 /* The current dictionary had no matches -- move to the next
1252 dictionary, if any. */
1253 for (unsigned short idx = ++miterator->current_idx;
1254 idx < miterator->mdict->n_allocated_dictionaries; ++idx)
1255 {
1256 result
1257 = dict_iter_match_first (miterator->mdict->dictionaries[idx],
1258 name, &miterator->iterator);
1259 if (result != nullptr)
1260 {
1261 miterator->current_idx = idx;
1262 return result;
1263 }
1264 }
1265
1266 return nullptr;
1267}
1268
1269/* See dictionary.h. */
1270
1271int
1272mdict_size (const struct multidictionary *mdict)
1273{
1274 int size = 0;
1275
1276 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1277 size += dict_size (mdict->dictionaries[idx]);
1278
1279 return size;
1280}
const char *const name
Definition: aarch64-tdep.c:67
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)
Definition: dictionary.c:1272
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)
Definition: dictionary.c:1038
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)
Definition: dictionary.c:1066
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)
Definition: dictionary.c:1165
#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:928
struct symbol * mdict_iter_match_next(const lookup_name_info &name, struct mdict_iterator *miterator)
Definition: dictionary.c:1242
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:977
static struct dictionary * create_new_language_dictionary(struct multidictionary *mdict, enum language language)
Definition: dictionary.c:1084
struct multidictionary * mdict_create_linear_expandable(enum language language)
Definition: dictionary.c:1022
struct multidictionary * mdict_create_hashed(struct obstack *obstack, const struct pending *symbol_list)
Definition: dictionary.c:948
#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:679
#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)
Definition: dictionary.c:1218
static struct symbol * iter_match_first_linear(const struct dictionary *dict, const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:820
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:809
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:685
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:659
static struct symbol * iterator_first_linear(const struct dictionary *dict, struct dict_iterator *iterator)
Definition: dictionary.c:800
static int size_linear(const struct dictionary *dict)
Definition: dictionary.c:859
static void free_linear_expandable(struct dictionary *dict)
Definition: dictionary.c:867
#define DICT_HASHTABLE_SIZE(n)
Definition: dictionary.c:210
static void add_symbol_hashed_expandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:666
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)
Definition: dictionary.c:1121
static void add_symbol_linear_expandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:875
static void insert_symbol_hashed(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:633
struct symbol * mdict_iterator_next(struct mdict_iterator *miterator)
Definition: dictionary.c:1190
static struct symbol * iter_match_next_linear(const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:831
#define DICT_EXPANDABLE_INITIAL_CAPACITY
Definition: dictionary.c:205
struct multidictionary * mdict_create_linear(struct obstack *obstack, const struct pending *symbol_list)
Definition: dictionary.c:993
#define DICT_LANGUAGE(d)
Definition: dictionary.c:184
void mdict_add_pending(struct multidictionary *mdict, const struct pending *symbol_list)
Definition: dictionary.c:1139
#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:241
const struct language_defn * language_def(enum language lang)
Definition: language.c:442
static void add_symbol(struct symbol *, struct symtab *, struct block *)
Definition: mdebugread.c:4482
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:50
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:144
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
union dictionary::@36 data
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
struct obstack * obstack
Definition: symtab.h:568
const char * search_name() const
Definition: symtab.c:1077
enum language language() const
Definition: symtab.h:501
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:686
virtual unsigned int search_name_hash(const char *name) const
Definition: dictionary.c:721
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:905
struct dictionary ** dictionaries
Definition: dictionary.c:901
struct pending * next
Definition: buildsym.h:79
enum language argument_type
Definition: dictionary.c:915
struct symbol * hash_next
Definition: symtab.h:1485
Definition: gdbtypes.h:922
unsigned int search_name_hash(enum language language, const char *search_name)
Definition: symtab.c:1931
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:398