gdb/dictionary.c

   1 /* Routines for name->symbol lookups in GDB.
   2
   3    Copyright (C) 2003-2021 Free Software Foundation, Inc.
   4
   5    Contributed by David Carlton <[email protected]> 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
  92 enum 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
 106 struct 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
 134 struct dictionary_hashed
 135 {
 136   int nbuckets;
 137   struct symbol **buckets;
 138 };
 139
 140 struct 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
 150 struct dictionary_linear
 151 {
 152   int nsyms;
 153   struct symbol **syms;
 154 };
 155
 156 struct 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
 167 struct 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
 229 static void add_symbol_nonexpandable (struct dictionary *dict,
 230                                       struct symbol *sym);
 231
 232 static void free_obstack (struct dictionary *dict);
 233
 234 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
 235    dictionaries.  */
 236
 237 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
 238                                              struct dict_iterator *iterator);
 239
 240 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
 241
 242 static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
 243                                                const lookup_name_info &name,
 244                                               struct dict_iterator *iterator);
 245
 246 static struct symbol *iter_match_next_hashed (const lookup_name_info &name,
 247                                               struct dict_iterator *iterator);
 248
 249 /* Functions only for DICT_HASHED.  */
 250
 251 static int size_hashed (const struct dictionary *dict);
 252
 253 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 254
 255 static void free_hashed_expandable (struct dictionary *dict);
 256
 257 static void add_symbol_hashed_expandable (struct dictionary *dict,
 258                                           struct symbol *sym);
 259
 260 static int size_hashed_expandable (const struct dictionary *dict);
 261
 262 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
 263    dictionaries.  */
 264
 265 static struct symbol *iterator_first_linear (const struct dictionary *dict,
 266                                              struct dict_iterator *iterator);
 267
 268 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
 269
 270 static struct symbol *iter_match_first_linear (const struct dictionary *dict,
 271                                                const lookup_name_info &name,
 272                                                struct dict_iterator *iterator);
 273
 274 static struct symbol *iter_match_next_linear (const lookup_name_info &name,
 275                                               struct dict_iterator *iterator);
 276
 277 static int size_linear (const struct dictionary *dict);
 278
 279 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 280
 281 static void free_linear_expandable (struct dictionary *dict);
 282
 283 static void add_symbol_linear_expandable (struct dictionary *dict,
 284                                           struct symbol *sym);
 285
 286 /* Various vectors that we'll actually use.  */
 287
 288 static 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
 300 static 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
 312 static 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
 324 static 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
 339 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
 340
 341 static void insert_symbol_hashed (struct dictionary *dict,
 342                                   struct symbol *sym);
 343
 344 static void expand_hashtable (struct dictionary *dict);
 345
 346 /* The creation functions.  */
 347
 348 /* Create a hashed dictionary of a given language.  */
 349
 350 static struct dictionary *
 351 dict_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
 377 static struct dictionary *
 378 dict_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
 394 static struct dictionary *
 395 dict_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
 419 static struct dictionary *
 420 dict_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
 439 static void
 440 dict_free (struct dictionary *dict)
 441 {
 442   (DICT_VECTOR (dict))->free (dict);
 443 }
 444
 445 /* Add SYM to DICT.  DICT had better be expandable.  */
 446
 447 static void
 448 dict_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
 456 static void
 457 dict_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
 468 static struct symbol *
 469 dict_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
 478 static struct symbol *
 479 dict_iterator_next (struct dict_iterator *iterator)
 480 {
 481   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 482     ->iterator_next (iterator);
 483 }
 484
 485 static struct symbol *
 486 dict_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
 493 static struct symbol *
 494 dict_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
 501 static int
 502 dict_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
 516 static void
 517 free_obstack (struct dictionary *dict)
 518 {
 519   /* Do nothing!  */
 520 }
 521
 522 static void
 523 add_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
 531 static struct symbol *
 532 iterator_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
 540 static struct symbol *
 541 iterator_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
 556 static struct symbol *
 557 iterator_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
 578 static struct symbol *
 579 iter_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
 609 static struct symbol *
 610 iter_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
 633 static void
 634 insert_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
 651 static int
 652 size_hashed (const struct dictionary *dict)
 653 {
 654   return DICT_HASHED_NBUCKETS (dict);
 655 }
 656
 657 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 658
 659 static void
 660 free_hashed_expandable (struct dictionary *dict)
 661 {
 662   xfree (DICT_HASHED_BUCKETS (dict));
 663   xfree (dict);
 664 }
 665
 666 static void
 667 add_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
 679 static int
 680 size_hashed_expandable (const struct dictionary *dict)
 681 {
 682   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
 683 }
 684
 685 static void
 686 expand_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
 721 unsigned int
 722 language_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 == 'B' && string[3] == '_')
 765                 {
 766                   for (string += 4; ISDIGIT (*string); ++string)
 767                     ;
 768                   continue;
 769                 }
 770
 771               if ((c < 'a' || c > 'z') && c != 'O')
 772                 return hash;
 773               hash = 0;
 774               string += 2;
 775               continue;
 776             }
 777           break;
 778         case 'T':
 779           /* Ignore "TKB" suffixes.
 780
 781              These are used by Ada for subprograms implementing a task body.
 782              For instance for a task T inside package Pck, the name of the
 783              subprogram implementing T's body is `pck__tTKB'.  We need to
 784              ignore the "TKB" suffix because searches for this task body
 785              subprogram are going to be performed using `pck__t' (the encoded
 786              version of the natural name `pck.t').  */
 787           if (strcmp (string, "TKB") == 0)
 788             return hash;
 789           break;
 790         }
 791
 792       hash = SYMBOL_HASH_NEXT (hash, *string);
 793       string += 1;
 794     }
 795   return hash;
 796 }
 797
 798 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 799
 800 static struct symbol *
 801 iterator_first_linear (const struct dictionary *dict,
 802                        struct dict_iterator *iterator)
 803 {
 804   DICT_ITERATOR_DICT (iterator) = dict;
 805   DICT_ITERATOR_INDEX (iterator) = 0;
 806   return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
 807 }
 808
 809 static struct symbol *
 810 iterator_next_linear (struct dict_iterator *iterator)
 811 {
 812   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 813
 814   if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
 815     return NULL;
 816   else
 817     return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
 818 }
 819
 820 static struct symbol *
 821 iter_match_first_linear (const struct dictionary *dict,
 822                          const lookup_name_info &name,
 823                          struct dict_iterator *iterator)
 824 {
 825   DICT_ITERATOR_DICT (iterator) = dict;
 826   DICT_ITERATOR_INDEX (iterator) = -1;
 827
 828   return iter_match_next_linear (name, iterator);
 829 }
 830
 831 static struct symbol *
 832 iter_match_next_linear (const lookup_name_info &name,
 833                         struct dict_iterator *iterator)
 834 {
 835   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 836   const language_defn *lang = DICT_LANGUAGE (dict);
 837   symbol_name_matcher_ftype *matches_name
 838     = lang->get_symbol_name_matcher (name);
 839
 840   int i, nsyms = DICT_LINEAR_NSYMS (dict);
 841   struct symbol *sym, *retval = NULL;
 842
 843   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
 844     {
 845       sym = DICT_LINEAR_SYM (dict, i);
 846
 847       if (matches_name (sym->search_name (), name, NULL))
 848         {
 849           retval = sym;
 850           break;
 851         }
 852     }
 853
 854   DICT_ITERATOR_INDEX (iterator) = i;
 855
 856   return retval;
 857 }
 858
 859 static int
 860 size_linear (const struct dictionary *dict)
 861 {
 862   return DICT_LINEAR_NSYMS (dict);
 863 }
 864
 865 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 866
 867 static void
 868 free_linear_expandable (struct dictionary *dict)
 869 {
 870   xfree (DICT_LINEAR_SYMS (dict));
 871   xfree (dict);
 872 }
 873
 874
 875 static void
 876 add_symbol_linear_expandable (struct dictionary *dict,
 877                               struct symbol *sym)
 878 {
 879   int nsyms = ++DICT_LINEAR_NSYMS (dict);
 880
 881   /* Do we have enough room?  If not, grow it.  */
 882   if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
 883     {
 884       DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
 885       DICT_LINEAR_SYMS (dict)
 886         = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict),
 887                       DICT_LINEAR_EXPANDABLE_CAPACITY (dict));
 888     }
 889
 890   DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
 891 }
 892
 893 /* Multi-language dictionary support.  */
 894
 895 /* The structure describing a multi-language dictionary.  */
 896
 897 struct multidictionary
 898 {
 899   /* An array of dictionaries, one per language.  All dictionaries
 900      must be of the same type.  This should be free'd for expandable
 901      dictionary types.  */
 902   struct dictionary **dictionaries;
 903
 904   /* The number of language dictionaries currently allocated.
 905      Only used for expandable dictionaries.  */
 906   unsigned short n_allocated_dictionaries;
 907 };
 908
 909 /* A hasher for enum language.  Injecting this into std is a convenience
 910    when using unordered_map with C++11.  */
 911
 912 namespace std
 913 {
 914   template<> struct hash<enum language>
 915   {
 916     typedef enum language argument_type;
 917     typedef std::size_t result_type;
 918
 919     result_type operator() (const argument_type &l) const noexcept
 920     {
 921       return static_cast<result_type> (l);
 922     }
 923   };
 924 } /* namespace std */
 925
 926 /* A helper function to collate symbols on the pending list by language.  */
 927
 928 static std::unordered_map<enum language, std::vector<symbol *>>
 929 collate_pending_symbols_by_language (const struct pending *symbol_list)
 930 {
 931   std::unordered_map<enum language, std::vector<symbol *>> nsyms;
 932
 933   for (const pending *list_counter = symbol_list;
 934        list_counter != nullptr; list_counter = list_counter->next)
 935     {
 936       for (int i = list_counter->nsyms - 1; i >= 0; --i)
 937         {
 938           enum language language = list_counter->symbol[i]->language ();
 939           nsyms[language].push_back (list_counter->symbol[i]);
 940         }
 941     }
 942
 943   return nsyms;
 944 }
 945
 946 /* See dictionary.h.  */
 947
 948 struct multidictionary *
 949 mdict_create_hashed (struct obstack *obstack,
 950                      const struct pending *symbol_list)
 951 {
 952   struct multidictionary *retval
 953     = XOBNEW (obstack, struct multidictionary);
 954   std::unordered_map<enum language, std::vector<symbol *>> nsyms
 955     = collate_pending_symbols_by_language (symbol_list);
 956
 957   /* Loop over all languages and create/populate dictionaries.  */
 958   retval->dictionaries
 959     = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
 960   retval->n_allocated_dictionaries = nsyms.size ();
 961
 962   int idx = 0;
 963   for (const auto &pair : nsyms)
 964     {
 965       enum language language = pair.first;
 966       std::vector<symbol *> symlist = pair.second;
 967
 968       retval->dictionaries[idx++]
 969         = dict_create_hashed (obstack, language, symlist);
 970     }
 971
 972   return retval;
 973 }
 974
 975 /* See dictionary.h.  */
 976
 977 struct multidictionary *
 978 mdict_create_hashed_expandable (enum language language)
 979 {
 980   struct multidictionary *retval = XNEW (struct multidictionary);
 981
 982   /* We have no symbol list to populate, but we create an empty
 983      dictionary of the requested language to populate later.  */
 984   retval->n_allocated_dictionaries = 1;
 985   retval->dictionaries = XNEW (struct dictionary *);
 986   retval->dictionaries[0] = dict_create_hashed_expandable (language);
 987
 988   return retval;
 989 }
 990
 991 /* See dictionary.h.  */
 992
 993 struct multidictionary *
 994 mdict_create_linear (struct obstack *obstack,
 995                      const struct pending *symbol_list)
 996 {
 997   struct multidictionary *retval
 998     = XOBNEW (obstack, struct multidictionary);
 999   std::unordered_map<enum language, std::vector<symbol *>> nsyms
1000     = collate_pending_symbols_by_language (symbol_list);
1001
1002   /* Loop over all languages and create/populate dictionaries.  */
1003   retval->dictionaries
1004     = XOBNEWVEC (obstack, struct dictionary *, nsyms.size ());
1005   retval->n_allocated_dictionaries = nsyms.size ();
1006
1007   int idx = 0;
1008   for (const auto &pair : nsyms)
1009     {
1010       enum language language = pair.first;
1011       std::vector<symbol *> symlist = pair.second;
1012
1013       retval->dictionaries[idx++]
1014         = dict_create_linear (obstack, language, symlist);
1015     }
1016
1017   return retval;
1018 }
1019
1020 /* See dictionary.h.  */
1021
1022 struct multidictionary *
1023 mdict_create_linear_expandable (enum language language)
1024 {
1025   struct multidictionary *retval = XNEW (struct multidictionary);
1026
1027   /* We have no symbol list to populate, but we create an empty
1028      dictionary to populate later.  */
1029   retval->n_allocated_dictionaries = 1;
1030   retval->dictionaries = XNEW (struct dictionary *);
1031   retval->dictionaries[0] = dict_create_linear_expandable (language);
1032
1033   return retval;
1034 }
1035
1036 /* See dictionary.h.  */
1037
1038 void
1039 mdict_free (struct multidictionary *mdict)
1040 {
1041   /* Grab the type of dictionary being used.  */
1042   enum dict_type type = mdict->dictionaries[0]->vector->type;
1043
1044   /* Loop over all dictionaries and free them.  */
1045   for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1046     dict_free (mdict->dictionaries[idx]);
1047
1048   /* Free the dictionary list, if needed.  */
1049   switch (type)
1050     {
1051     case DICT_HASHED:
1052     case DICT_LINEAR:
1053       /* Memory was allocated on an obstack when created.  */
1054       break;
1055
1056     case DICT_HASHED_EXPANDABLE:
1057     case DICT_LINEAR_EXPANDABLE:
1058       xfree (mdict->dictionaries);
1059       break;
1060     }
1061 }
1062
1063 /* Helper function to find the dictionary associated with LANGUAGE
1064    or NULL if there is no dictionary of that language.  */
1065
1066 static struct dictionary *
1067 find_language_dictionary (const struct multidictionary *mdict,
1068                           enum language language)
1069 {
1070   for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1071     {
1072       if (DICT_LANGUAGE (mdict->dictionaries[idx])->la_language == language)
1073         return mdict->dictionaries[idx];
1074     }
1075
1076   return nullptr;
1077 }
1078
1079 /* Create a new language dictionary for LANGUAGE and add it to the
1080    multidictionary MDICT's list of dictionaries.  If MDICT is not
1081    based on expandable dictionaries, this function throws an
1082    internal error.  */
1083
1084 static struct dictionary *
1085 create_new_language_dictionary (struct multidictionary *mdict,
1086                                 enum language language)
1087 {
1088   struct dictionary *retval = nullptr;
1089
1090   /* We use the first dictionary entry to decide what create function
1091      to call.  Not optimal but sufficient.  */
1092   gdb_assert (mdict->dictionaries[0] != nullptr);
1093   switch (mdict->dictionaries[0]->vector->type)
1094     {
1095     case DICT_HASHED:
1096     case DICT_LINEAR:
1097       internal_error (__FILE__, __LINE__,
1098                       _("create_new_language_dictionary: attempted to expand "
1099                         "non-expandable multidictionary"));
1100
1101     case DICT_HASHED_EXPANDABLE:
1102       retval = dict_create_hashed_expandable (language);
1103       break;
1104
1105     case DICT_LINEAR_EXPANDABLE:
1106       retval = dict_create_linear_expandable (language);
1107       break;
1108     }
1109
1110   /* Grow the dictionary vector and save the new dictionary.  */
1111   mdict->dictionaries
1112     = (struct dictionary **) xrealloc (mdict->dictionaries,
1113                                        (++mdict->n_allocated_dictionaries
1114                                         * sizeof (struct dictionary *)));
1115   mdict->dictionaries[mdict->n_allocated_dictionaries - 1] = retval;
1116
1117   return retval;
1118 }
1119
1120 /* See dictionary.h.  */
1121
1122 void
1123 mdict_add_symbol (struct multidictionary *mdict, struct symbol *sym)
1124 {
1125   struct dictionary *dict
1126     = find_language_dictionary (mdict, sym->language ());
1127
1128   if (dict == nullptr)
1129     {
1130       /* SYM is of a new language that we haven't previously seen.
1131          Create a new dictionary for it.  */
1132       dict = create_new_language_dictionary (mdict, sym->language ());
1133     }
1134
1135   dict_add_symbol (dict, sym);
1136 }
1137
1138 /* See dictionary.h.  */
1139
1140 void
1141 mdict_add_pending (struct multidictionary *mdict,
1142                    const struct pending *symbol_list)
1143 {
1144   std::unordered_map<enum language, std::vector<symbol *>> nsyms
1145     = collate_pending_symbols_by_language (symbol_list);
1146
1147   for (const auto &pair : nsyms)
1148     {
1149       enum language language = pair.first;
1150       std::vector<symbol *> symlist = pair.second;
1151       struct dictionary *dict = find_language_dictionary (mdict, language);
1152
1153       if (dict == nullptr)
1154         {
1155           /* The language was not previously seen.  Create a new dictionary
1156              for it.  */
1157           dict = create_new_language_dictionary (mdict, language);
1158         }
1159
1160       dict_add_pending (dict, symlist);
1161     }
1162 }
1163
1164 /* See dictionary.h.  */
1165
1166 struct symbol *
1167 mdict_iterator_first (const multidictionary *mdict,
1168                       struct mdict_iterator *miterator)
1169 {
1170   miterator->mdict = mdict;
1171   miterator->current_idx = 0;
1172
1173   for (unsigned short idx = miterator->current_idx;
1174        idx < mdict->n_allocated_dictionaries; ++idx)
1175     {
1176       struct symbol *result
1177         = dict_iterator_first (mdict->dictionaries[idx], &miterator->iterator);
1178
1179       if (result != nullptr)
1180         {
1181           miterator->current_idx = idx;
1182           return result;
1183         }
1184     }
1185
1186   return nullptr;
1187 }
1188
1189 /* See dictionary.h.  */
1190
1191 struct symbol *
1192 mdict_iterator_next (struct mdict_iterator *miterator)
1193 {
1194   struct symbol *result = dict_iterator_next (&miterator->iterator);
1195
1196   if (result != nullptr)
1197     return result;
1198
1199   /* The current dictionary had no matches -- move to the next
1200      dictionary, if any.  */
1201   for (unsigned short idx = ++miterator->current_idx;
1202        idx < miterator->mdict->n_allocated_dictionaries; ++idx)
1203     {
1204       result
1205         = dict_iterator_first (miterator->mdict->dictionaries[idx],
1206                                &miterator->iterator);
1207       if (result != nullptr)
1208         {
1209           miterator->current_idx = idx;
1210           return result;
1211         }
1212     }
1213
1214   return nullptr;
1215 }
1216
1217 /* See dictionary.h.  */
1218
1219 struct symbol *
1220 mdict_iter_match_first (const struct multidictionary *mdict,
1221                         const lookup_name_info &name,
1222                         struct mdict_iterator *miterator)
1223 {
1224   miterator->mdict = mdict;
1225   miterator->current_idx = 0;
1226
1227   for (unsigned short idx = miterator->current_idx;
1228        idx < mdict->n_allocated_dictionaries; ++idx)
1229     {
1230       struct symbol *result
1231         = dict_iter_match_first (mdict->dictionaries[idx], name,
1232                                  &miterator->iterator);
1233
1234       if (result != nullptr)
1235         return result;
1236     }
1237
1238   return nullptr;
1239 }
1240
1241 /* See dictionary.h.  */
1242
1243 struct symbol *
1244 mdict_iter_match_next (const lookup_name_info &name,
1245                        struct mdict_iterator *miterator)
1246 {
1247   /* Search the current dictionary.  */
1248   struct symbol *result = dict_iter_match_next (name, &miterator->iterator);
1249
1250   if (result != nullptr)
1251     return result;
1252
1253   /* The current dictionary had no matches -- move to the next
1254      dictionary, if any.  */
1255   for (unsigned short idx = ++miterator->current_idx;
1256        idx < miterator->mdict->n_allocated_dictionaries; ++idx)
1257     {
1258       result
1259         = dict_iter_match_first (miterator->mdict->dictionaries[idx],
1260                                  name, &miterator->iterator);
1261       if (result != nullptr)
1262         {
1263           miterator->current_idx = idx;
1264           return result;
1265         }
1266     }
1267
1268   return nullptr;
1269 }
1270
1271 /* See dictionary.h.  */
1272
1273 int
1274 mdict_size (const struct multidictionary *mdict)
1275 {
1276   int size = 0;
1277
1278   for (unsigned short idx = 0; idx < mdict->n_allocated_dictionaries; ++idx)
1279     size += dict_size (mdict->dictionaries[idx]);
1280
1281   return size;
1282 }