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