1/* Routines for name->symbol lookups in GDB. 2 3 Copyright (C) 2003-2020 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#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 92enum dict_type 93 { 94 /* Symbols are stored in a fixed-size hash table. */ 95 DICT_HASHED, 96 /* Symbols are stored in an expandable hash table. */ 97 DICT_HASHED_EXPANDABLE, 98 /* Symbols are stored in a fixed-size array. */ 99 DICT_LINEAR, 100 /* Symbols are stored in an expandable array. */ 101 DICT_LINEAR_EXPANDABLE 102 }; 103 104/* The virtual function table. */ 105 106struct dict_vector 107{ 108 /* The type of the dictionary. This is only here to make debugging 109 a bit easier; it's not actually used. */ 110 enum dict_type type; 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 134struct dictionary_hashed 135{ 136 int nbuckets; 137 struct symbol **buckets; 138}; 139 140struct dictionary_hashed_expandable 141{ 142 /* How many buckets we currently have. */ 143 int nbuckets; 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 150struct dictionary_linear 151{ 152 int nsyms; 153 struct symbol **syms; 154}; 155 156struct dictionary_linear_expandable 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. */ 162 int capacity; 163}; 164 165/* And now, the star of our show. */ 166 167struct dictionary 168{ 169 const struct language_defn *language; 170 const struct dict_vector *vector; 171 union 172 { 173 struct dictionary_hashed hashed; 174 struct dictionary_hashed_expandable hashed_expandable; 175 struct dictionary_linear linear; 176 struct dictionary_linear_expandable linear_expandable; 177 } 178 data; 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 246static struct symbol *iter_match_next_hashed (const lookup_name_info &name, 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 274static struct symbol *iter_match_next_linear (const lookup_name_info &name, 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 300static const struct dict_vector dict_hashed_expandable_vector = 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 324static const struct dict_vector dict_linear_expandable_vector = 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); 357 DICT_VECTOR (retval) = &dict_hashed_vector; 358 DICT_LANGUAGE (retval) = language_def (language); 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 * 378dict_create_hashed_expandable (enum language language) 379{ 380 struct dictionary *retval = XNEW (struct dictionary); 381 382 DICT_VECTOR (retval) = &dict_hashed_expandable_vector; 383 DICT_LANGUAGE (retval) = language_def (language); 384 DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY; 385 DICT_HASHED_BUCKETS (retval) = XCNEWVEC (struct symbol *, 386 DICT_EXPANDABLE_INITIAL_CAPACITY); 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); 400 DICT_VECTOR (retval) = &dict_linear_vector; 401 DICT_LANGUAGE (retval) = language_def (language); 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 * 420dict_create_linear_expandable (enum language language) 421{ 422 struct dictionary *retval = XNEW (struct dictionary); 423 424 DICT_VECTOR (retval) = &dict_linear_expandable_vector; 425 DICT_LANGUAGE (retval) = language_def (language); 426 DICT_LINEAR_NSYMS (retval) = 0; 427 DICT_LINEAR_EXPANDABLE_CAPACITY (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY; 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 457dict_add_pending (struct dictionary *dict, 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 * 479dict_iterator_next (struct dict_iterator *iterator) 480{ 481 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) 482 ->iterator_next (iterator); 483} 484 485static struct symbol * 486dict_iter_match_first (const struct dictionary *dict, 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 * 494dict_iter_match_next (const lookup_name_info &name, 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 517free_obstack (struct dictionary *dict) 518{ 519 /* Do nothing! */ 520} 521 522static void 523add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym) 524{ 525 internal_error (__FILE__, __LINE__, 526 _("dict_add_symbol: non-expandable dictionary")); 527} 528 529/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */ 530 531static struct symbol * 532iterator_first_hashed (const struct dictionary *dict, 533 struct dict_iterator *iterator) 534{ 535 DICT_ITERATOR_DICT (iterator) = dict; 536 DICT_ITERATOR_INDEX (iterator) = -1; 537 return iterator_hashed_advance (iterator); 538} 539 540static struct symbol * 541iterator_next_hashed (struct dict_iterator *iterator) 542{ 543 struct symbol *next; 544 545 next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 546 547 if (next == NULL) 548 return iterator_hashed_advance (iterator); 549 else 550 { 551 DICT_ITERATOR_CURRENT (iterator) = next; 552 return next; 553 } 554} 555 556static struct symbol * 557iterator_hashed_advance (struct dict_iterator *iterator) 558{ 559 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 560 int nbuckets = DICT_HASHED_NBUCKETS (dict); 561 int i; 562 563 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i) 564 { 565 struct symbol *sym = DICT_HASHED_BUCKET (dict, i); 566 567 if (sym != NULL) 568 { 569 DICT_ITERATOR_INDEX (iterator) = i; 570 DICT_ITERATOR_CURRENT (iterator) = sym; 571 return sym; 572 } 573 } 574 575 return NULL; 576} 577 578static struct symbol * 579iter_match_first_hashed (const struct dictionary *dict, 580 const lookup_name_info &name, 581 struct dict_iterator *iterator) 582{ 583 const language_defn *lang = DICT_LANGUAGE (dict); 584 unsigned int hash_index = (name.search_name_hash (lang->la_language) 585 % DICT_HASHED_NBUCKETS (dict)); 586 symbol_name_matcher_ftype *matches_name 587 = lang->get_symbol_name_matcher (name); 588 struct symbol *sym; 589 590 DICT_ITERATOR_DICT (iterator) = dict; 591 592 /* Loop through the symbols in the given bucket, breaking when SYM 593 first matches. If SYM never matches, it will be set to NULL; 594 either way, we have the right return value. */ 595 596 for (sym = DICT_HASHED_BUCKET (dict, hash_index); 597 sym != NULL; 598 sym = sym->hash_next) 599 { 600 /* Warning: the order of arguments to compare matters! */ 601 if (matches_name (sym->search_name (), name, NULL)) 602 break; 603 } 604 605 DICT_ITERATOR_CURRENT (iterator) = sym; 606 return sym; 607} 608 609static struct symbol * 610iter_match_next_hashed (const lookup_name_info &name, 611 struct dict_iterator *iterator) 612{ 613 const language_defn *lang = DICT_LANGUAGE (DICT_ITERATOR_DICT (iterator)); 614 symbol_name_matcher_ftype *matches_name 615 = lang->get_symbol_name_matcher (name); 616 struct symbol *next; 617 618 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 619 next != NULL; 620 next = next->hash_next) 621 { 622 if (matches_name (next->search_name (), name, NULL)) 623 break; 624 } 625 626 DICT_ITERATOR_CURRENT (iterator) = next; 627 628 return next; 629} 630 631/* Insert SYM into DICT. */ 632 633static void 634insert_symbol_hashed (struct dictionary *dict, 635 struct symbol *sym) 636{ 637 unsigned int hash_index; 638 unsigned int hash; 639 struct symbol **buckets = DICT_HASHED_BUCKETS (dict); 640 641 /* We don't want to insert a symbol into a dictionary of a different 642 language. The two may not use the same hashing algorithm. */ 643 gdb_assert (sym->language () == DICT_LANGUAGE (dict)->la_language); 644 645 hash = search_name_hash (sym->language (), sym->search_name ()); 646 hash_index = hash % DICT_HASHED_NBUCKETS (dict); 647 sym->hash_next = buckets[hash_index]; 648 buckets[hash_index] = sym; 649} 650 651static int 652size_hashed (const struct dictionary *dict) 653{ 654 return DICT_HASHED_NBUCKETS (dict); 655} 656 657/* Functions only for DICT_HASHED_EXPANDABLE. */ 658 659static void 660free_hashed_expandable (struct dictionary *dict) 661{ 662 xfree (DICT_HASHED_BUCKETS (dict)); 663 xfree (dict); 664} 665 666static void 667add_symbol_hashed_expandable (struct dictionary *dict, 668 struct symbol *sym) 669{ 670 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict); 671 672 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict)) 673 expand_hashtable (dict); 674 675 insert_symbol_hashed (dict, sym); 676 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms; 677} 678 679static int 680size_hashed_expandable (const struct dictionary *dict) 681{ 682 return DICT_HASHED_EXPANDABLE_NSYMS (dict); 683} 684 685static void 686expand_hashtable (struct dictionary *dict) 687{ 688 int old_nbuckets = DICT_HASHED_NBUCKETS (dict); 689 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict); 690 int new_nbuckets = 2 * old_nbuckets + 1; 691 struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets); 692 int i; 693 694 DICT_HASHED_NBUCKETS (dict) = new_nbuckets; 695 DICT_HASHED_BUCKETS (dict) = new_buckets; 696 697 for (i = 0; i < old_nbuckets; ++i) 698 { 699 struct symbol *sym, *next_sym; 700 701 sym = old_buckets[i]; 702 if (sym != NULL) 703 { 704 for (next_sym = sym->hash_next; 705 next_sym != NULL; 706 next_sym = sym->hash_next) 707 { 708 insert_symbol_hashed (dict, sym); 709 sym = next_sym; 710 } 711 712 insert_symbol_hashed (dict, sym); 713 } 714 } 715 716 xfree (old_buckets); 717} 718 719/* See dictionary.h. */ 720 721unsigned int 722language_defn::search_name_hash (const char *string0) const 723{ 724 /* The Ada-encoded version of a name P1.P2...Pn has either the form 725 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi 726 are lower-cased identifiers). The <suffix> (which can be empty) 727 encodes additional information about the denoted entity. This 728 routine hashes such names to msymbol_hash_iw(Pn). It actually 729 does this for a superset of both valid Pi and of <suffix>, but 730 in other cases it simply returns msymbol_hash_iw(STRING0). */ 731 732 const char *string; 733 unsigned int hash; 734 735 string = string0; 736 if (*string == '_') 737 { 738 if (startswith (string, "_ada_")) 739 string += 5; 740 else 741 return msymbol_hash_iw (string0); 742 } 743 744 hash = 0; 745 while (*string) 746 { 747 switch (*string) 748 { 749 case '$': 750 case '.': 751 case 'X': 752 if (string0 == string) 753 return msymbol_hash_iw (string0); 754 else 755 return hash; 756 case ' ': 757 case '(': 758 return msymbol_hash_iw (string0); 759 case '_': 760 if (string[1] == '_' && string != string0) 761 { 762 int c = string[2]; 763 764 if ((c < 'a' || c > 'z') && c != 'O') 765 return hash; 766 hash = 0; 767 string += 2; 768 continue; 769 } 770 break; 771 case 'T': 772 /* Ignore "TKB" suffixes. 773 774 These are used by Ada for subprograms implementing a task body. 775 For instance for a task T inside package Pck, the name of the 776 subprogram implementing T's body is `pck__tTKB'. We need to 777 ignore the "TKB" suffix because searches for this task body 778 subprogram are going to be performed using `pck__t' (the encoded 779 version of the natural name `pck.t'). */ 780 if (strcmp (string, "TKB") == 0) 781 return hash; 782 break; 783 } 784 785 hash = SYMBOL_HASH_NEXT (hash, *string); 786 string += 1; 787 } 788 return hash; 789} 790 791/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */ 792 793static struct symbol * 794iterator_first_linear (const struct dictionary *dict, 795 struct dict_iterator *iterator) 796{ 797 DICT_ITERATOR_DICT (iterator) = dict; 798 DICT_ITERATOR_INDEX (iterator) = 0; 799 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL; 800} 801 802static struct symbol * 803iterator_next_linear (struct dict_iterator *iterator) 804{ 805 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 806 807 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict)) 808 return NULL; 809 else 810 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator)); 811} 812 813static struct symbol * 814iter_match_first_linear (const struct dictionary *dict, 815 const lookup_name_info &name, 816 struct dict_iterator *iterator) 817{ 818 DICT_ITERATOR_DICT (iterator) = dict; 819 DICT_ITERATOR_INDEX (iterator) = -1; 820 821 return iter_match_next_linear (name, iterator); 822} 823 824static struct symbol * 825iter_match_next_linear (const lookup_name_info &name, 826 struct dict_iterator *iterator) 827{ 828 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 829 const language_defn *lang = DICT_LANGUAGE (dict); 830 symbol_name_matcher_ftype *matches_name 831 = lang->get_symbol_name_matcher (name); 832 833 int i, nsyms = DICT_LINEAR_NSYMS (dict); 834 struct symbol *sym, *retval = NULL; 835 836 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i) 837 { 838 sym = DICT_LINEAR_SYM (dict, i); 839 840 if (matches_name (sym->search_name (), name, NULL)) 841 { 842 retval = sym; 843 break; 844 } 845 } 846 847 DICT_ITERATOR_INDEX (iterator) = i; 848 849 return retval; 850} 851 852static int 853size_linear (const struct dictionary *dict) 854{ 855 return DICT_LINEAR_NSYMS (dict); 856} 857 858/* Functions only for DICT_LINEAR_EXPANDABLE. */ 859 860static void 861free_linear_expandable (struct dictionary *dict) 862{ 863 xfree (DICT_LINEAR_SYMS (dict)); 864 xfree (dict); 865} 866 867 868static void 869add_symbol_linear_expandable (struct dictionary *dict, 870 struct symbol *sym) 871{ 872 int nsyms = ++DICT_LINEAR_NSYMS (dict); 873 874 /* Do we have enough room? If not, grow it. */ 875 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) 876 { 877 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2; 878 DICT_LINEAR_SYMS (dict) 879 = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict), 880 DICT_LINEAR_EXPANDABLE_CAPACITY (dict)); 881 } 882 883 DICT_LINEAR_SYM (dict, nsyms - 1) = sym; 884} 885 886/* Multi-language dictionary support. */ 887 888/* The structure describing a multi-language dictionary. */ 889 890struct multidictionary 891{ 892 /* An array of dictionaries, one per language. All dictionaries 893 must be of the same type. This should be free'd for expandable 894 dictionary types. */ 895 struct dictionary **dictionaries; 896 897 /* The number of language dictionaries currently allocated. 898 Only used for expandable dictionaries. */ 899 unsigned short n_allocated_dictionaries; 900}; 901 902/* A hasher for enum language. Injecting this into std is a convenience 903 when using unordered_map with C++11. */ 904 905namespace std 906{ 907 template<> struct hash<enum language> 908 { 909 typedef enum language argument_type; 910 typedef std::size_t result_type; 911 912 result_type operator() (const argument_type &l) const noexcept 913 { 914 return static_cast<result_type> (l); 915 } 916 }; 917} /* namespace std */ 918 919/* A helper function to collate symbols on the pending list by language. */ 920 921static std::unordered_map<enum language, std::vector<symbol *>> 922collate_pending_symbols_by_language (const struct pending *symbol_list) 923{ 924 std::unordered_map<enum language, std::vector<symbol *>> nsyms; 925 926 for (const pending *list_counter = symbol_list; 927 list_counter != nullptr; list_counter = list_counter->next) 928 { 929 for (int i = list_counter->nsyms - 1; i >= 0; --i) 930 { 931 enum language language = list_counter->symbol[i]->language (); 932 nsyms[language].push_back (list_counter->symbol[i]); 933 } 934 } 935 936 return nsyms; 937} 938 939/* See dictionary.h. */ 940 941struct multidictionary * 942mdict_create_hashed (struct obstack *obstack, 943 const struct pending *symbol_list) 944{ 945 struct multidictionary *retval 946 = XOBNEW (obstack, struct multidictionary); 947 std::unordered_map<enum language, std::vector<symbol *>> nsyms 948 = collate_pending_symbols_by_language (symbol_list); 949 950 /* Loop over all languages and create/populate dictionaries. */ 951 retval->dictionaries 952 = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ()); 953 retval->n_allocated_dictionaries = nsyms.size (); 954 955 int idx = 0; 956 for (const auto &pair : nsyms) 957 { 958 enum language language = pair.first; 959 std::vector<symbol *> symlist = pair.second; 960 961 retval->dictionaries[idx++] 962 = dict_create_hashed (obstack, language, symlist); 963 } 964 965 return retval; 966} 967 968/* See dictionary.h. */ 969 970struct multidictionary * 971mdict_create_hashed_expandable (enum language language) 972{ 973 struct multidictionary *retval = XNEW (struct multidictionary); 974 975 /* We have no symbol list to populate, but we create an empty 976 dictionary of the requested language to populate later. */ 977 retval->n_allocated_dictionaries = 1; 978 retval->dictionaries = XNEW (struct dictionary *); 979 retval->dictionaries[0] = dict_create_hashed_expandable (language); 980 981 return retval; 982} 983 984/* See dictionary.h. */ 985 986struct multidictionary * 987mdict_create_linear (struct obstack *obstack, 988 const struct pending *symbol_list) 989{ 990 struct multidictionary *retval 991 = XOBNEW (obstack, struct multidictionary); 992 std::unordered_map<enum language, std::vector<symbol *>> nsyms 993 = collate_pending_symbols_by_language (symbol_list); 994 995 /* Loop over all languages and create/populate dictionaries. */ 996 retval->dictionaries 997 = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ()); 998 retval->n_allocated_dictionaries = nsyms.size (); 999 1000 int idx = 0; 1001 for (const auto &pair : nsyms) 1002 { 1003 enum language language = pair.first; 1004 std::vector<symbol *> symlist = pair.second; 1005 1006 retval->dictionaries[idx++] 1007 = dict_create_linear (obstack, language, symlist); 1008 } 1009 1010 return retval; 1011} 1012 1013/* See dictionary.h. */ 1014 1015struct multidictionary * 1016mdict_create_linear_expandable (enum language language) 1017{ 1018 struct multidictionary *retval = XNEW (struct multidictionary); 1019 1020 /* We have no symbol list to populate, but we create an empty 1021 dictionary to populate later. */ 1022 retval->n_allocated_dictionaries = 1; 1023 retval->dictionaries = XNEW (struct dictionary *); 1024 retval->dictionaries[0] = dict_create_linear_expandable (language); 1025 1026 return retval; 1027} 1028 1029/* See dictionary.h. */ 1030 1031void 1032mdict_free (struct multidictionary *mdict) 1033{ 1034 /* Grab the type of dictionary being used. */ 1035 enum dict_type type = mdict->dictionaries[0]->vector->type; 1036 1037 /* Loop over all dictionaries and free them. */ 1038 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx) 1039 dict_free (mdict->dictionaries[idx]); 1040 1041 /* Free the dictionary list, if needed. */ 1042 switch (type) 1043 { 1044 case DICT_HASHED: 1045 case DICT_LINEAR: 1046 /* Memory was allocated on an obstack when created. */ 1047 break; 1048 1049 case DICT_HASHED_EXPANDABLE: 1050 case DICT_LINEAR_EXPANDABLE: 1051 xfree (mdict->dictionaries); 1052 break; 1053 } 1054} 1055 1056/* Helper function to find the dictionary associated with LANGUAGE 1057 or NULL if there is no dictionary of that language. */ 1058 1059static struct dictionary * 1060find_language_dictionary (const struct multidictionary *mdict, 1061 enum language language) 1062{ 1063 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx) 1064 { 1065 if (DICT_LANGUAGE (mdict->dictionaries[idx])->la_language == language) 1066 return mdict->dictionaries[idx]; 1067 } 1068 1069 return nullptr; 1070} 1071 1072/* Create a new language dictionary for LANGUAGE and add it to the 1073 multidictionary MDICT's list of dictionaries. If MDICT is not 1074 based on expandable dictionaries, this function throws an 1075 internal error. */ 1076 1077static struct dictionary * 1078create_new_language_dictionary (struct multidictionary *mdict, 1079 enum language language) 1080{ 1081 struct dictionary *retval = nullptr; 1082 1083 /* We use the first dictionary entry to decide what create function 1084 to call. Not optimal but sufficient. */ 1085 gdb_assert (mdict->dictionaries[0] != nullptr); 1086 switch (mdict->dictionaries[0]->vector->type) 1087 { 1088 case DICT_HASHED: 1089 case DICT_LINEAR: 1090 internal_error (__FILE__, __LINE__, 1091 _("create_new_language_dictionary: attempted to expand " 1092 "non-expandable multidictionary")); 1093 1094 case DICT_HASHED_EXPANDABLE: 1095 retval = dict_create_hashed_expandable (language); 1096 break; 1097 1098 case DICT_LINEAR_EXPANDABLE: 1099 retval = dict_create_linear_expandable (language); 1100 break; 1101 } 1102 1103 /* Grow the dictionary vector and save the new dictionary. */ 1104 mdict->dictionaries 1105 = (struct dictionary **) xrealloc (mdict->dictionaries, 1106 (++mdict->n_allocated_dictionaries 1107 * sizeof (struct dictionary *))); 1108 mdict->dictionaries[mdict->n_allocated_dictionaries - 1] = retval; 1109 1110 return retval; 1111} 1112 1113/* See dictionary.h. */ 1114 1115void 1116mdict_add_symbol (struct multidictionary *mdict, struct symbol *sym) 1117{ 1118 struct dictionary *dict 1119 = find_language_dictionary (mdict, sym->language ()); 1120 1121 if (dict == nullptr) 1122 { 1123 /* SYM is of a new language that we haven't previously seen. 1124 Create a new dictionary for it. */ 1125 dict = create_new_language_dictionary (mdict, sym->language ()); 1126 } 1127 1128 dict_add_symbol (dict, sym); 1129} 1130 1131/* See dictionary.h. */ 1132 1133void 1134mdict_add_pending (struct multidictionary *mdict, 1135 const struct pending *symbol_list) 1136{ 1137 std::unordered_map<enum language, std::vector<symbol *>> nsyms 1138 = collate_pending_symbols_by_language (symbol_list); 1139 1140 for (const auto &pair : nsyms) 1141 { 1142 enum language language = pair.first; 1143 std::vector<symbol *> symlist = pair.second; 1144 struct dictionary *dict = find_language_dictionary (mdict, language); 1145 1146 if (dict == nullptr) 1147 { 1148 /* The language was not previously seen. Create a new dictionary 1149 for it. */ 1150 dict = create_new_language_dictionary (mdict, language); 1151 } 1152 1153 dict_add_pending (dict, symlist); 1154 } 1155} 1156 1157/* See dictionary.h. */ 1158 1159struct symbol * 1160mdict_iterator_first (const multidictionary *mdict, 1161 struct mdict_iterator *miterator) 1162{ 1163 miterator->mdict = mdict; 1164 miterator->current_idx = 0; 1165 1166 for (unsigned short idx = miterator->current_idx; 1167 idx < mdict->n_allocated_dictionaries; ++idx) 1168 { 1169 struct symbol *result 1170 = dict_iterator_first (mdict->dictionaries[idx], &miterator->iterator); 1171 1172 if (result != nullptr) 1173 { 1174 miterator->current_idx = idx; 1175 return result; 1176 } 1177 } 1178 1179 return nullptr; 1180} 1181 1182/* See dictionary.h. */ 1183 1184struct symbol * 1185mdict_iterator_next (struct mdict_iterator *miterator) 1186{ 1187 struct symbol *result = dict_iterator_next (&miterator->iterator); 1188 1189 if (result != nullptr) 1190 return result; 1191 1192 /* The current dictionary had no matches -- move to the next 1193 dictionary, if any. */ 1194 for (unsigned short idx = ++miterator->current_idx; 1195 idx < miterator->mdict->n_allocated_dictionaries; ++idx) 1196 { 1197 result 1198 = dict_iterator_first (miterator->mdict->dictionaries[idx], 1199 &miterator->iterator); 1200 if (result != nullptr) 1201 { 1202 miterator->current_idx = idx; 1203 return result; 1204 } 1205 } 1206 1207 return nullptr; 1208} 1209 1210/* See dictionary.h. */ 1211 1212struct symbol * 1213mdict_iter_match_first (const struct multidictionary *mdict, 1214 const lookup_name_info &name, 1215 struct mdict_iterator *miterator) 1216{ 1217 miterator->mdict = mdict; 1218 miterator->current_idx = 0; 1219 1220 for (unsigned short idx = miterator->current_idx; 1221 idx < mdict->n_allocated_dictionaries; ++idx) 1222 { 1223 struct symbol *result 1224 = dict_iter_match_first (mdict->dictionaries[idx], name, 1225 &miterator->iterator); 1226 1227 if (result != nullptr) 1228 return result; 1229 } 1230 1231 return nullptr; 1232} 1233 1234/* See dictionary.h. */ 1235 1236struct symbol * 1237mdict_iter_match_next (const lookup_name_info &name, 1238 struct mdict_iterator *miterator) 1239{ 1240 /* Search the current dictionary. */ 1241 struct symbol *result = dict_iter_match_next (name, &miterator->iterator); 1242 1243 if (result != nullptr) 1244 return result; 1245 1246 /* The current dictionary had no matches -- move to the next 1247 dictionary, if any. */ 1248 for (unsigned short idx = ++miterator->current_idx; 1249 idx < miterator->mdict->n_allocated_dictionaries; ++idx) 1250 { 1251 result 1252 = dict_iter_match_first (miterator->mdict->dictionaries[idx], 1253 name, &miterator->iterator); 1254 if (result != nullptr) 1255 { 1256 miterator->current_idx = idx; 1257 return result; 1258 } 1259 } 1260 1261 return nullptr; 1262} 1263 1264/* See dictionary.h. */ 1265 1266int 1267mdict_size (const struct multidictionary *mdict) 1268{ 1269 int size = 0; 1270 1271 for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx) 1272 size += dict_size (mdict->dictionaries[idx]); 1273 1274 return size; 1275} 1276