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