GDB (xrefs)

/tmp/gdb-8.1/gdb/dictionary.c
Go to the documentation of this file.
1 /* Routines for name->symbol lookups in GDB.
2
3 Copyright (C) 2003-2018 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 "gdb_obstack.h"
26 #include "symtab.h"
27 #include "buildsym.h"
28 #include "dictionary.h"
29 #include "safe-ctype.h"
30
31 /* This file implements dictionaries, which are tables that associate
32 symbols to names. They are represented by an opaque type 'struct
33 dictionary'. That type has various internal implementations, which
34 you can choose between depending on what properties you need
35 (e.g. fast lookup, order-preserving, expandable).
36
37 Each dictionary starts with a 'virtual function table' that
38 contains the functions that actually implement the various
39 operations that dictionaries provide. (Note, however, that, for
40 the sake of client code, we also provide some functions that can be
41 implemented generically in terms of the functions in the vtable.)
42
43 To add a new dictionary implementation <impl>, what you should do
44 is:
45
46 * Add a new element DICT_<IMPL> to dict_type.
47
48 * Create a new structure dictionary_<impl>. If your new
49 implementation is a variant of an existing one, make sure that
50 their structs have the same initial data members. Define accessor
51 macros for your new data members.
52
53 * Implement all the functions in dict_vector as static functions,
54 whose name is the same as the corresponding member of dict_vector
55 plus _<impl>. You don't have to do this for those members where
56 you can reuse existing generic functions
57 (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
58 your new implementation is a variant of an existing implementation
59 and where the variant doesn't affect the member function in
60 question.
61
62 * Define a static const struct dict_vector dict_<impl>_vector.
63
64 * Define a function dict_create_<impl> to create these
65 gizmos. Add its declaration to dictionary.h.
66
67 To add a new operation <op> on all existing implementations, what
68 you should do is:
69
70 * Add a new member <op> to struct dict_vector.
71
72 * If there is useful generic behavior <op>, define a static
73 function <op>_something_informative that implements that behavior.
74 (E.g. add_symbol_nonexpandable, free_obstack.)
75
76 * For every implementation <impl> that should have its own specific
77 behavior for <op>, define a static function <op>_<impl>
78 implementing it.
79
80 * Modify all existing dict_vector_<impl>'s to include the appropriate
81 member.
82
83 * Define a function dict_<op> that looks up <op> in the dict_vector
84 and calls the appropriate function. Add a declaration for
85 dict_<op> to dictionary.h. */
86
87 /* An enum representing the various implementations of dictionaries.
88 Used only for debugging. */
89
90 enum dict_type
91 {
92 /* Symbols are stored in a fixed-size hash table. */
93 DICT_HASHED,
94 /* Symbols are stored in an expandable hash table. */
95 DICT_HASHED_EXPANDABLE,
96 /* Symbols are stored in a fixed-size array. */
97 DICT_LINEAR,
98 /* Symbols are stored in an expandable array. */
99 DICT_LINEAR_EXPANDABLE
100 };
101
102 /* The virtual function table. */
103
104 struct dict_vector
105 {
106 /* The type of the dictionary. This is only here to make debugging
107 a bit easier; it's not actually used. */
108 enum dict_type type;
109 /* The function to free a dictionary. */
110 void (*free) (struct dictionary *dict);
111 /* Add a symbol to a dictionary, if possible. */
112 void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
113 /* Iterator functions. */
114 struct symbol *(*iterator_first) (const struct dictionary *dict,
115 struct dict_iterator *iterator);
116 struct symbol *(*iterator_next) (struct dict_iterator *iterator);
117 /* Functions to iterate over symbols with a given name. */
118 struct symbol *(*iter_match_first) (const struct dictionary *dict,
119 const lookup_name_info &name,
120 struct dict_iterator *iterator);
121 struct symbol *(*iter_match_next) (const lookup_name_info &name,
122 struct dict_iterator *iterator);
123 /* A size function, for maint print symtabs. */
124 int (*size) (const struct dictionary *dict);
125 };
126
127 /* Now comes the structs used to store the data for different
128 implementations. If two implementations have data in common, put
129 the common data at the top of their structs, ordered in the same
130 way. */
131
132 struct dictionary_hashed
133 {
134 int nbuckets;
135 struct symbol **buckets;
136 };
137
138 struct dictionary_hashed_expandable
139 {
140 /* How many buckets we currently have. */
141 int nbuckets;
142 struct symbol **buckets;
143 /* How many syms we currently have; we need this so we will know
144 when to add more buckets. */
145 int nsyms;
146 };
147
148 struct dictionary_linear
149 {
150 int nsyms;
151 struct symbol **syms;
152 };
153
154 struct dictionary_linear_expandable
155 {
156 /* How many symbols we currently have. */
157 int nsyms;
158 struct symbol **syms;
159 /* How many symbols we can store before needing to reallocate. */
160 int capacity;
161 };
162
163 /* And now, the star of our show. */
164
165 struct dictionary
166 {
167 const struct language_defn *language;
168 const struct dict_vector *vector;
169 union
170 {
171 struct dictionary_hashed hashed;
172 struct dictionary_hashed_expandable hashed_expandable;
173 struct dictionary_linear linear;
174 struct dictionary_linear_expandable linear_expandable;
175 }
176 data;
177 };
178
179 /* Accessor macros. */
180
181 #define DICT_VECTOR(d) (d)->vector
182 #define DICT_LANGUAGE(d) (d)->language
183
184 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
185
186 #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
187 #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
188 #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
189
190 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
191
192 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
193
194 #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
195 #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
196 #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
197
198 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
199 (d)->data.linear_expandable.capacity
200
201 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
202
203 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
204
205 /* This calculates the number of buckets we'll use in a hashtable,
206 given the number of symbols that it will contain. */
207
208 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
209
210 /* Accessor macros for dict_iterators; they're here rather than
211 dictionary.h because code elsewhere should treat dict_iterators as
212 opaque. */
213
214 /* The dictionary that the iterator is associated to. */
215 #define DICT_ITERATOR_DICT(iter) (iter)->dict
216 /* For linear dictionaries, the index of the last symbol returned; for
217 hashed dictionaries, the bucket of the last symbol returned. */
218 #define DICT_ITERATOR_INDEX(iter) (iter)->index
219 /* For hashed dictionaries, this points to the last symbol returned;
220 otherwise, this is unused. */
221 #define DICT_ITERATOR_CURRENT(iter) (iter)->current
222
223 /* Declarations of functions for vectors. */
224
225 /* Functions that might work across a range of dictionary types. */
226
227 static void add_symbol_nonexpandable (struct dictionary *dict,
228 struct symbol *sym);
229
230 static void free_obstack (struct dictionary *dict);
231
232 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
233 dictionaries. */
234
235 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
236 struct dict_iterator *iterator);
237
238 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
239
240 static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
241 const lookup_name_info &name,
242 struct dict_iterator *iterator);
243
244 static struct symbol *iter_match_next_hashed (const lookup_name_info &name,
245 struct dict_iterator *iterator);
246
247 /* Functions only for DICT_HASHED. */
248
249 static int size_hashed (const struct dictionary *dict);
250
251 /* Functions only for DICT_HASHED_EXPANDABLE. */
252
253 static void free_hashed_expandable (struct dictionary *dict);
254
255 static void add_symbol_hashed_expandable (struct dictionary *dict,
256 struct symbol *sym);
257
258 static int size_hashed_expandable (const struct dictionary *dict);
259
260 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
261 dictionaries. */
262
263 static struct symbol *iterator_first_linear (const struct dictionary *dict,
264 struct dict_iterator *iterator);
265
266 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
267
268 static struct symbol *iter_match_first_linear (const struct dictionary *dict,
269 const lookup_name_info &name,
270 struct dict_iterator *iterator);
271
272 static struct symbol *iter_match_next_linear (const lookup_name_info &name,
273 struct dict_iterator *iterator);
274
275 static int size_linear (const struct dictionary *dict);
276
277 /* Functions only for DICT_LINEAR_EXPANDABLE. */
278
279 static void free_linear_expandable (struct dictionary *dict);
280
281 static void add_symbol_linear_expandable (struct dictionary *dict,
282 struct symbol *sym);
283
284 /* Various vectors that we'll actually use. */
285
286 static const struct dict_vector dict_hashed_vector =
287 {
288 DICT_HASHED, /* type */
289 free_obstack, /* free */
290 add_symbol_nonexpandable, /* add_symbol */
291 iterator_first_hashed, /* iterator_first */
292 iterator_next_hashed, /* iterator_next */
293 iter_match_first_hashed, /* iter_name_first */
294 iter_match_next_hashed, /* iter_name_next */
295 size_hashed, /* size */
296 };
297
298 static const struct dict_vector dict_hashed_expandable_vector =
299 {
300 DICT_HASHED_EXPANDABLE, /* type */
301 free_hashed_expandable, /* free */
302 add_symbol_hashed_expandable, /* add_symbol */
303 iterator_first_hashed, /* iterator_first */
304 iterator_next_hashed, /* iterator_next */
305 iter_match_first_hashed, /* iter_name_first */
306 iter_match_next_hashed, /* iter_name_next */
307 size_hashed_expandable, /* size */
308 };
309
310 static const struct dict_vector dict_linear_vector =
311 {
312 DICT_LINEAR, /* type */
313 free_obstack, /* free */
314 add_symbol_nonexpandable, /* add_symbol */
315 iterator_first_linear, /* iterator_first */
316 iterator_next_linear, /* iterator_next */
317 iter_match_first_linear, /* iter_name_first */
318 iter_match_next_linear, /* iter_name_next */
319 size_linear, /* size */
320 };
321
322 static const struct dict_vector dict_linear_expandable_vector =
323 {
324 DICT_LINEAR_EXPANDABLE, /* type */
325 free_linear_expandable, /* free */
326 add_symbol_linear_expandable, /* add_symbol */
327 iterator_first_linear, /* iterator_first */
328 iterator_next_linear, /* iterator_next */
329 iter_match_first_linear, /* iter_name_first */
330 iter_match_next_linear, /* iter_name_next */
331 size_linear, /* size */
332 };
333
334 /* Declarations of helper functions (i.e. ones that don't go into
335 vectors). */
336
337 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
338
339 static void insert_symbol_hashed (struct dictionary *dict,
340 struct symbol *sym);
341
342 static void expand_hashtable (struct dictionary *dict);
343
344 /* The creation functions. */
345
346 /* See dictionary.h. */
347
348 struct dictionary *
349 dict_create_hashed (struct obstack *obstack,
350 enum language language,
351 const struct pending *symbol_list)
352 {
353 struct dictionary *retval;
354 int nsyms = 0, nbuckets, i;
355 struct symbol **buckets;
356 const struct pending *list_counter;
357
358 retval = XOBNEW (obstack, struct dictionary);
359 DICT_VECTOR (retval) = &dict_hashed_vector;
360 DICT_LANGUAGE (retval) = language_def (language);
361
362 /* Calculate the number of symbols, and allocate space for them. */
363 for (list_counter = symbol_list;
364 list_counter != NULL;
365 list_counter = list_counter->next)
366 {
367 nsyms += list_counter->nsyms;
368 }
369 nbuckets = DICT_HASHTABLE_SIZE (nsyms);
370 DICT_HASHED_NBUCKETS (retval) = nbuckets;
371 buckets = XOBNEWVEC (obstack, struct symbol *, nbuckets);
372 memset (buckets, 0, nbuckets * sizeof (struct symbol *));
373 DICT_HASHED_BUCKETS (retval) = buckets;
374
375 /* Now fill the buckets. */
376 for (list_counter = symbol_list;
377 list_counter != NULL;
378 list_counter = list_counter->next)
379 {
380 for (i = list_counter->nsyms - 1; i >= 0; --i)
381 {
382 insert_symbol_hashed (retval, list_counter->symbol[i]);
383 }
384 }
385
386 return retval;
387 }
388
389 /* See dictionary.h. */
390
391 extern struct dictionary *
392 dict_create_hashed_expandable (enum language language)
393 {
394 struct dictionary *retval = XNEW (struct dictionary);
395
396 DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
397 DICT_LANGUAGE (retval) = language_def (language);
398 DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
399 DICT_HASHED_BUCKETS (retval) = XCNEWVEC (struct symbol *,
400 DICT_EXPANDABLE_INITIAL_CAPACITY);
401 DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
402
403 return retval;
404 }
405
406 /* See dictionary.h. */
407
408 struct dictionary *
409 dict_create_linear (struct obstack *obstack,
410 enum language language,
411 const struct pending *symbol_list)
412 {
413 struct dictionary *retval;
414 int nsyms = 0, i, j;
415 struct symbol **syms;
416 const struct pending *list_counter;
417
418 retval = XOBNEW (obstack, struct dictionary);
419 DICT_VECTOR (retval) = &dict_linear_vector;
420 DICT_LANGUAGE (retval) = language_def (language);
421
422 /* Calculate the number of symbols, and allocate space for them. */
423 for (list_counter = symbol_list;
424 list_counter != NULL;
425 list_counter = list_counter->next)
426 {
427 nsyms += list_counter->nsyms;
428 }
429 DICT_LINEAR_NSYMS (retval) = nsyms;
430 syms = XOBNEWVEC (obstack, struct symbol *, nsyms );
431 DICT_LINEAR_SYMS (retval) = syms;
432
433 /* Now fill in the symbols. Start filling in from the back, so as
434 to preserve the original order of the symbols. */
435 for (list_counter = symbol_list, j = nsyms - 1;
436 list_counter != NULL;
437 list_counter = list_counter->next)
438 {
439 for (i = list_counter->nsyms - 1;
440 i >= 0;
441 --i, --j)
442 {
443 syms[j] = list_counter->symbol[i];
444 }
445 }
446
447 return retval;
448 }
449
450 /* See dictionary.h. */
451
452 struct dictionary *
453 dict_create_linear_expandable (enum language language)
454 {
455 struct dictionary *retval = XNEW (struct dictionary);
456
457 DICT_VECTOR (retval) = &dict_linear_expandable_vector;
458 DICT_LANGUAGE (retval) = language_def (language);
459 DICT_LINEAR_NSYMS (retval) = 0;
460 DICT_LINEAR_EXPANDABLE_CAPACITY (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
461 DICT_LINEAR_SYMS (retval)
462 = XNEWVEC (struct symbol *, DICT_LINEAR_EXPANDABLE_CAPACITY (retval));
463
464 return retval;
465 }
466
467 /* The functions providing the dictionary interface. */
468
469 /* Free the memory used by a dictionary that's not on an obstack. (If
470 any.) */
471
472 void
473 dict_free (struct dictionary *dict)
474 {
475 (DICT_VECTOR (dict))->free (dict);
476 }
477
478 /* Add SYM to DICT. DICT had better be expandable. */
479
480 void
481 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
482 {
483 (DICT_VECTOR (dict))->add_symbol (dict, sym);
484 }
485
486 /* Utility to add a list of symbols to a dictionary.
487 DICT must be an expandable dictionary. */
488
489 void
490 dict_add_pending (struct dictionary *dict, const struct pending *symbol_list)
491 {
492 const struct pending *list;
493 int i;
494
495 for (list = symbol_list; list != NULL; list = list->next)
496 {
497 for (i = 0; i < list->nsyms; ++i)
498 dict_add_symbol (dict, list->symbol[i]);
499 }
500 }
501
502 /* Initialize ITERATOR to point at the first symbol in DICT, and
503 return that first symbol, or NULL if DICT is empty. */
504
505 struct symbol *
506 dict_iterator_first (const struct dictionary *dict,
507 struct dict_iterator *iterator)
508 {
509 return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
510 }
511
512 /* Advance ITERATOR, and return the next symbol, or NULL if there are
513 no more symbols. */
514
515 struct symbol *
516 dict_iterator_next (struct dict_iterator *iterator)
517 {
518 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
519 ->iterator_next (iterator);
520 }
521
522 struct symbol *
523 dict_iter_match_first (const struct dictionary *dict,
524 const lookup_name_info &name,
525 struct dict_iterator *iterator)
526 {
527 return (DICT_VECTOR (dict))->iter_match_first (dict, name, iterator);
528 }
529
530 struct symbol *
531 dict_iter_match_next (const lookup_name_info &name,
532 struct dict_iterator *iterator)
533 {
534 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
535 ->iter_match_next (name, iterator);
536 }
537
538 int
539 dict_size (const struct dictionary *dict)
540 {
541 return (DICT_VECTOR (dict))->size (dict);
542 }
543
544 /* Now come functions (well, one function, currently) that are
545 implemented generically by means of the vtable. Typically, they're
546 rarely used. */
547
548 /* Test to see if DICT is empty. */
549
550 int
551 dict_empty (struct dictionary *dict)
552 {
553 struct dict_iterator iter;
554
555 return (dict_iterator_first (dict, &iter) == NULL);
556 }
557
558
559 /* The functions implementing the dictionary interface. */
560
561 /* Generic functions, where appropriate. */
562
563 static void
564 free_obstack (struct dictionary *dict)
565 {
566 /* Do nothing! */
567 }
568
569 static void
570 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
571 {
572 internal_error (__FILE__, __LINE__,
573 _("dict_add_symbol: non-expandable dictionary"));
574 }
575
576 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
577
578 static struct symbol *
579 iterator_first_hashed (const struct dictionary *dict,
580 struct dict_iterator *iterator)
581 {
582 DICT_ITERATOR_DICT (iterator) = dict;
583 DICT_ITERATOR_INDEX (iterator) = -1;
584 return iterator_hashed_advance (iterator);
585 }
586
587 static struct symbol *
588 iterator_next_hashed (struct dict_iterator *iterator)
589 {
590 struct symbol *next;
591
592 next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
593
594 if (next == NULL)
595 return iterator_hashed_advance (iterator);
596 else
597 {
598 DICT_ITERATOR_CURRENT (iterator) = next;
599 return next;
600 }
601 }
602
603 static struct symbol *
604 iterator_hashed_advance (struct dict_iterator *iterator)
605 {
606 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
607 int nbuckets = DICT_HASHED_NBUCKETS (dict);
608 int i;
609
610 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
611 {
612 struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
613
614 if (sym != NULL)
615 {
616 DICT_ITERATOR_INDEX (iterator) = i;
617 DICT_ITERATOR_CURRENT (iterator) = sym;
618 return sym;
619 }
620 }
621
622 return NULL;
623 }
624
625 static struct symbol *
626 iter_match_first_hashed (const struct dictionary *dict,
627 const lookup_name_info &name,
628 struct dict_iterator *iterator)
629 {
630 const language_defn *lang = DICT_LANGUAGE (dict);
631 unsigned int hash_index = (name.search_name_hash (lang->la_language)
632 % DICT_HASHED_NBUCKETS (dict));
633 symbol_name_matcher_ftype *matches_name
634 = get_symbol_name_matcher (lang, name);
635 struct symbol *sym;
636
637 DICT_ITERATOR_DICT (iterator) = dict;
638
639 /* Loop through the symbols in the given bucket, breaking when SYM
640 first matches. If SYM never matches, it will be set to NULL;
641 either way, we have the right return value. */
642
643 for (sym = DICT_HASHED_BUCKET (dict, hash_index);
644 sym != NULL;
645 sym = sym->hash_next)
646 {
647 /* Warning: the order of arguments to compare matters! */
648 if (matches_name (SYMBOL_SEARCH_NAME (sym), name, NULL))
649 break;
650 }
651
652 DICT_ITERATOR_CURRENT (iterator) = sym;
653 return sym;
654 }
655
656 static struct symbol *
657 iter_match_next_hashed (const lookup_name_info &name,
658 struct dict_iterator *iterator)
659 {
660 const language_defn *lang = DICT_LANGUAGE (DICT_ITERATOR_DICT (iterator));
661 symbol_name_matcher_ftype *matches_name
662 = get_symbol_name_matcher (lang, name);
663 struct symbol *next;
664
665 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
666 next != NULL;
667 next = next->hash_next)
668 {
669 if (matches_name (SYMBOL_SEARCH_NAME (next), name, NULL))
670 break;
671 }
672
673 DICT_ITERATOR_CURRENT (iterator) = next;
674
675 return next;
676 }
677
678 /* Insert SYM into DICT. */
679
680 static void
681 insert_symbol_hashed (struct dictionary *dict,
682 struct symbol *sym)
683 {
684 unsigned int hash_index;
685 unsigned int hash;
686 struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
687
688 /* We don't want to insert a symbol into a dictionary of a different
689 language. The two may not use the same hashing algorithm. */
690 gdb_assert (SYMBOL_LANGUAGE (sym) == DICT_LANGUAGE (dict)->la_language);
691
692 hash = search_name_hash (SYMBOL_LANGUAGE (sym), SYMBOL_SEARCH_NAME (sym));
693 hash_index = hash % DICT_HASHED_NBUCKETS (dict);
694 sym->hash_next = buckets[hash_index];
695 buckets[hash_index] = sym;
696 }
697
698 static int
699 size_hashed (const struct dictionary *dict)
700 {
701 return DICT_HASHED_NBUCKETS (dict);
702 }
703
704 /* Functions only for DICT_HASHED_EXPANDABLE. */
705
706 static void
707 free_hashed_expandable (struct dictionary *dict)
708 {
709 xfree (DICT_HASHED_BUCKETS (dict));
710 xfree (dict);
711 }
712
713 static void
714 add_symbol_hashed_expandable (struct dictionary *dict,
715 struct symbol *sym)
716 {
717 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
718
719 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
720 expand_hashtable (dict);
721
722 insert_symbol_hashed (dict, sym);
723 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
724 }
725
726 static int
727 size_hashed_expandable (const struct dictionary *dict)
728 {
729 return DICT_HASHED_EXPANDABLE_NSYMS (dict);
730 }
731
732 static void
733 expand_hashtable (struct dictionary *dict)
734 {
735 int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
736 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
737 int new_nbuckets = 2 * old_nbuckets + 1;
738 struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets);
739 int i;
740
741 DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
742 DICT_HASHED_BUCKETS (dict) = new_buckets;
743
744 for (i = 0; i < old_nbuckets; ++i)
745 {
746 struct symbol *sym, *next_sym;
747
748 sym = old_buckets[i];
749 if (sym != NULL)
750 {
751 for (next_sym = sym->hash_next;
752 next_sym != NULL;
753 next_sym = sym->hash_next)
754 {
755 insert_symbol_hashed (dict, sym);
756 sym = next_sym;
757 }
758
759 insert_symbol_hashed (dict, sym);
760 }
761 }
762
763 xfree (old_buckets);
764 }
765
766 /* See dictionary.h. */
767
768 unsigned int
769 default_search_name_hash (const char *string0)
770 {
771 /* The Ada-encoded version of a name P1.P2...Pn has either the form
772 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
773 are lower-cased identifiers). The <suffix> (which can be empty)
774 encodes additional information about the denoted entity. This
775 routine hashes such names to msymbol_hash_iw(Pn). It actually
776 does this for a superset of both valid Pi and of <suffix>, but
777 in other cases it simply returns msymbol_hash_iw(STRING0). */
778
779 const char *string;
780 unsigned int hash;
781
782 string = string0;
783 if (*string == '_')
784 {
785 if (startswith (string, "_ada_"))
786 string += 5;
787 else
788 return msymbol_hash_iw (string0);
789 }
790
791 hash = 0;
792 while (*string)
793 {
794 switch (*string)
795 {
796 case '$':
797 case '.':
798 case 'X':
799 if (string0 == string)
800 return msymbol_hash_iw (string0);
801 else
802 return hash;
803 case ' ':
804 case '(':
805 return msymbol_hash_iw (string0);
806 case '_':
807 if (string[1] == '_' && string != string0)
808 {
809 int c = string[2];
810
811 if ((c < 'a' || c > 'z') && c != 'O')
812 return hash;
813 hash = 0;
814 string += 2;
815 continue;
816 }
817 break;
818 case 'T':
819 /* Ignore "TKB" suffixes.
820
821 These are used by Ada for subprograms implementing a task body.
822 For instance for a task T inside package Pck, the name of the
823 subprogram implementing T's body is `pck__tTKB'. We need to
824 ignore the "TKB" suffix because searches for this task body
825 subprogram are going to be performed using `pck__t' (the encoded
826 version of the natural name `pck.t'). */
827 if (strcmp (string, "TKB") == 0)
828 return hash;
829 break;
830 }
831
832 hash = SYMBOL_HASH_NEXT (hash, *string);
833 string += 1;
834 }
835 return hash;
836 }
837
838 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
839
840 static struct symbol *
841 iterator_first_linear (const struct dictionary *dict,
842 struct dict_iterator *iterator)
843 {
844 DICT_ITERATOR_DICT (iterator) = dict;
845 DICT_ITERATOR_INDEX (iterator) = 0;
846 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
847 }
848
849 static struct symbol *
850 iterator_next_linear (struct dict_iterator *iterator)
851 {
852 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
853
854 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
855 return NULL;
856 else
857 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
858 }
859
860 static struct symbol *
861 iter_match_first_linear (const struct dictionary *dict,
862 const lookup_name_info &name,
863 struct dict_iterator *iterator)
864 {
865 DICT_ITERATOR_DICT (iterator) = dict;
866 DICT_ITERATOR_INDEX (iterator) = -1;
867
868 return iter_match_next_linear (name, iterator);
869 }
870
871 static struct symbol *
872 iter_match_next_linear (const lookup_name_info &name,
873 struct dict_iterator *iterator)
874 {
875 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
876 const language_defn *lang = DICT_LANGUAGE (dict);
877 symbol_name_matcher_ftype *matches_name
878 = get_symbol_name_matcher (lang, name);
879
880 int i, nsyms = DICT_LINEAR_NSYMS (dict);
881 struct symbol *sym, *retval = NULL;
882
883 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
884 {
885 sym = DICT_LINEAR_SYM (dict, i);
886
887 if (matches_name (SYMBOL_SEARCH_NAME (sym), name, NULL))
888 {
889 retval = sym;
890 break;
891 }
892 }
893
894 DICT_ITERATOR_INDEX (iterator) = i;
895
896 return retval;
897 }
898
899 static int
900 size_linear (const struct dictionary *dict)
901 {
902 return DICT_LINEAR_NSYMS (dict);
903 }
904
905 /* Functions only for DICT_LINEAR_EXPANDABLE. */
906
907 static void
908 free_linear_expandable (struct dictionary *dict)
909 {
910 xfree (DICT_LINEAR_SYMS (dict));
911 xfree (dict);
912 }
913
914
915 static void
916 add_symbol_linear_expandable (struct dictionary *dict,
917 struct symbol *sym)
918 {
919 int nsyms = ++DICT_LINEAR_NSYMS (dict);
920
921 /* Do we have enough room? If not, grow it. */
922 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
923 {
924 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
925 DICT_LINEAR_SYMS (dict)
926 = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict),
927 DICT_LINEAR_EXPANDABLE_CAPACITY (dict));
928 }
929
930 DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
931 }
string
const char * string
Definition: signals.c:50
iterator_first_linear
static struct symbol * iterator_first_linear(const struct dictionary *dict, struct dict_iterator *iterator)
Definition: dictionary.c:841
DICT_HASHED_EXPANDABLE_NSYMS
#define DICT_HASHED_EXPANDABLE_NSYMS(d)
Definition: dictionary.c:190
dict_linear_expandable_vector
static const struct dict_vector dict_linear_expandable_vector
Definition: dictionary.c:322
DICT_LINEAR_SYM
#define DICT_LINEAR_SYM(d, i)
Definition: dictionary.c:196
dict_iter_match_next
struct symbol * dict_iter_match_next(const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:531
gdb_obstack.h
DICT_LANGUAGE
#define DICT_LANGUAGE(d)
Definition: dictionary.c:182
dictionary_hashed_expandable
Definition: dictionary.c:138
dictionary_hashed
Definition: dictionary.c:132
dict_free
void dict_free(struct dictionary *dict)
Definition: dictionary.c:473
default_search_name_hash
unsigned int default_search_name_hash(const char *string0)
Definition: dictionary.c:769
xfree
void xfree(void *)
dictionary::hashed_expandable
struct dictionary_hashed_expandable hashed_expandable
Definition: dictionary.c:172
symbol::hash_next
struct symbol * hash_next
Definition: symtab.h:1127
dictionary::vector
const struct dict_vector * vector
Definition: dictionary.c:168
symbol_list
static struct @23 symbol_list[]
get_symbol_name_matcher
symbol_name_matcher_ftype * get_symbol_name_matcher(const language_defn *lang, const lookup_name_info &lookup_name)
Definition: language.c:730
dict_create_linear
struct dictionary * dict_create_linear(struct obstack *obstack, enum language language, const struct pending *symbol_list)
Definition: dictionary.c:409
expand_hashtable
static void expand_hashtable(struct dictionary *dict)
Definition: dictionary.c:733
dictionary_linear_expandable::capacity
int capacity
Definition: dictionary.c:160
iterator_hashed_advance
static struct symbol * iterator_hashed_advance(struct dict_iterator *iter)
Definition: dictionary.c:604
memset
void * memset(T *s, int c, size_t n)=delete
internal_error
void internal_error(const char *file, int line, const char *fmt,...)
Definition: errors.c:50
dict_vector
Definition: dictionary.c:104
language_def
const struct language_defn * language_def(enum language lang)
Definition: language.c:494
dict_vector::size
int(* size)(const struct dictionary *dict)
Definition: dictionary.c:124
DICT_HASHED_BUCKET
#define DICT_HASHED_BUCKET(d, i)
Definition: dictionary.c:188
dictionary_linear::nsyms
int nsyms
Definition: dictionary.c:150
symbol_name_matcher_ftype
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:324
DICT_LINEAR_SYMS
#define DICT_LINEAR_SYMS(d)
Definition: dictionary.c:195
dict_vector::add_symbol
void(* add_symbol)(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:112
pending::symbol
struct symbol * symbol[PENDINGSIZE]
Definition: buildsym.h:105
DICT_ITERATOR_CURRENT
#define DICT_ITERATOR_CURRENT(iter)
Definition: dictionary.c:221
language_defn::la_language
enum language la_language
Definition: language.h:144
add_symbol_linear_expandable
static void add_symbol_linear_expandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:916
_
#define _(String)
Definition: gdb_locale.h:35
DICT_ITERATOR_DICT
#define DICT_ITERATOR_DICT(iter)
Definition: dictionary.c:215
defs.h
DICT_HASHED_NBUCKETS
#define DICT_HASHED_NBUCKETS(d)
Definition: dictionary.c:186
dict_linear_vector
static const struct dict_vector dict_linear_vector
Definition: dictionary.c:310
dictionary::language
const struct language_defn * language
Definition: dictionary.c:167
free_hashed_expandable
static void free_hashed_expandable(struct dictionary *dict)
Definition: dictionary.c:707
language_defn
Definition: language.h:132
XNEW
#define XNEW(T)
Definition: poison.h:109
XCNEWVEC
#define XCNEWVEC(T, N)
Definition: poison.h:157
symtab.h
dict_type
dict_type
Definition: dictionary.c:90
name
const char *const name
Definition: aarch64-tdep.c:76
dict_iter_match_first
struct symbol * dict_iter_match_first(const struct dictionary *dict, const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:523
dictionary_linear::syms
struct symbol ** syms
Definition: dictionary.c:151
dictionary::hashed
struct dictionary_hashed hashed
Definition: dictionary.c:171
DICT_LINEAR_NSYMS
#define DICT_LINEAR_NSYMS(d)
Definition: dictionary.c:194
pending::nsyms
int nsyms
Definition: buildsym.h:104
dictionary_linear_expandable::syms
struct symbol ** syms
Definition: dictionary.c:158
DICT_HASHED_EXPANDABLE
Definition: dictionary.c:95
pending::next
struct pending * next
Definition: buildsym.h:103
dict_add_pending
void dict_add_pending(struct dictionary *dict, const struct pending *symbol_list)
Definition: dictionary.c:490
DICT_EXPANDABLE_INITIAL_CAPACITY
#define DICT_EXPANDABLE_INITIAL_CAPACITY
Definition: dictionary.c:203
buildsym.h
DICT_HASHED
Definition: dictionary.c:93
iterator_next_hashed
static struct symbol * iterator_next_hashed(struct dict_iterator *iterator)
Definition: dictionary.c:588
dict_hashed_expandable_vector
static const struct dict_vector dict_hashed_expandable_vector
Definition: dictionary.c:298
SYMBOL_HASH_NEXT
#define SYMBOL_HASH_NEXT(hash, c)
Definition: minsyms.h:184
DICT_LINEAR_EXPANDABLE_CAPACITY
#define DICT_LINEAR_EXPANDABLE_CAPACITY(d)
Definition: dictionary.c:198
dictionary_hashed_expandable::buckets
struct symbol ** buckets
Definition: dictionary.c:142
pending
Definition: buildsym.h:101
dictionary_hashed::buckets
struct symbol ** buckets
Definition: dictionary.c:135
free
void free(T *ptr)=delete
size_linear
static int size_linear(const struct dictionary *dict)
Definition: dictionary.c:900
startswith
static int startswith(const char *string, const char *pattern)
Definition: common-utils.h:107
dictionary
Definition: dictionary.c:165
iterator_first_hashed
static struct symbol * iterator_first_hashed(const struct dictionary *dict, struct dict_iterator *iterator)
Definition: dictionary.c:579
dictionary_hashed_expandable::nbuckets
int nbuckets
Definition: dictionary.c:141
add_symbol
static void add_symbol(struct symbol *, struct symtab *, struct block *)
Definition: mdebugread.c:4584
dict_empty
int dict_empty(struct dictionary *dict)
Definition: dictionary.c:551
XRESIZEVEC
#define XRESIZEVEC(T, P, N)
Definition: poison.h:169
DICT_LINEAR
Definition: dictionary.c:97
dict_iterator_next
struct symbol * dict_iterator_next(struct dict_iterator *iterator)
Definition: dictionary.c:516
dict_create_linear_expandable
struct dictionary * dict_create_linear_expandable(enum language language)
Definition: dictionary.c:453
DICT_LINEAR_EXPANDABLE
Definition: dictionary.c:99
dictionary_hashed::nbuckets
int nbuckets
Definition: dictionary.c:134
gdb_assert
#define gdb_assert(expr)
Definition: gdb_assert.h:32
dict_iterator
Definition: dictionary.h:106
dict_vector::type
enum dict_type type
Definition: dictionary.c:108
hash
unsigned long hash(const void *addr, int length)
Definition: bcache.c:98
dictionary_linear_expandable
Definition: dictionary.c:154
add_symbol_hashed_expandable
static void add_symbol_hashed_expandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:714
free_linear_expandable
static void free_linear_expandable(struct dictionary *dict)
Definition: dictionary.c:908
dictionary::data
union dictionary::@35 data
iter_match_next_linear
static struct symbol * iter_match_next_linear(const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:872
DICT_VECTOR
#define DICT_VECTOR(d)
Definition: dictionary.c:181
XNEWVEC
#define XNEWVEC(T, N)
Definition: poison.h:145
dictionary::linear
struct dictionary_linear linear
Definition: dictionary.c:173
dict_vector::free
void(* free)(struct dictionary *dict)
Definition: dictionary.c:110
dict_add_symbol
void dict_add_symbol(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:481
dictionary_hashed_expandable::nsyms
int nsyms
Definition: dictionary.c:145
search_name_hash
unsigned int search_name_hash(enum language language, const char *search_name)
Definition: symtab.c:1859
SYMBOL_LANGUAGE
#define SYMBOL_LANGUAGE(symbol)
Definition: symtab.h:469
iter_match_first_linear
static struct symbol * iter_match_first_linear(const struct dictionary *dict, const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:861
dict_create_hashed
struct dictionary * dict_create_hashed(struct obstack *obstack, enum language language, const struct pending *symbol_list)
Definition: dictionary.c:349
size_hashed_expandable
static int size_hashed_expandable(const struct dictionary *dict)
Definition: dictionary.c:727
insert_symbol_hashed
static void insert_symbol_hashed(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:681
dict_hashed_vector
static const struct dict_vector dict_hashed_vector
Definition: dictionary.c:286
SYMBOL_SEARCH_NAME
#define SYMBOL_SEARCH_NAME(symbol)
Definition: symtab.h:551
language
language
Definition: defs.h:203
iter_match_first_hashed
static struct symbol * iter_match_first_hashed(const struct dictionary *dict, const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:626
dictionary_linear_expandable::nsyms
int nsyms
Definition: dictionary.c:157
symbol
Definition: symtab.h:1049
dict_size
int dict_size(const struct dictionary *dict)
Definition: dictionary.c:539
DICT_HASHTABLE_SIZE
#define DICT_HASHTABLE_SIZE(n)
Definition: dictionary.c:208
dict_create_hashed_expandable
struct dictionary * dict_create_hashed_expandable(enum language language)
Definition: dictionary.c:392
dict_iterator::dict
const struct dictionary * dict
Definition: dictionary.h:109
iter_match_next_hashed
static struct symbol * iter_match_next_hashed(const lookup_name_info &name, struct dict_iterator *iterator)
Definition: dictionary.c:657
lookup_name_info
Definition: symtab.h:179
add_symbol_nonexpandable
static void add_symbol_nonexpandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:570
size_hashed
static int size_hashed(const struct dictionary *dict)
Definition: dictionary.c:699
dictionary::linear_expandable
struct dictionary_linear_expandable linear_expandable
Definition: dictionary.c:174
free_obstack
static void free_obstack(struct dictionary *dict)
Definition: dictionary.c:564
dictionary.h
dictionary_linear
Definition: dictionary.c:148
dict_iterator_first
struct symbol * dict_iterator_first(const struct dictionary *dict, struct dict_iterator *iterator)
Definition: dictionary.c:506
msymbol_hash_iw
unsigned int msymbol_hash_iw(const char *string)
Definition: minsyms.c:107
iterator_next_linear
static struct symbol * iterator_next_linear(struct dict_iterator *iterator)
Definition: dictionary.c:850
DICT_HASHED_BUCKETS
#define DICT_HASHED_BUCKETS(d)
Definition: dictionary.c:187
DICT_ITERATOR_INDEX
#define DICT_ITERATOR_INDEX(iter)
Definition: dictionary.c:218