gdb/dictionary.c

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