gdb/dictionary.c

   1 /* Routines for name->symbol lookups in GDB.
   2
   3    Copyright (C) 2003-2018 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
  31 /* This file implements dictionaries, which are tables that associate
  32    symbols to names.  They are represented by an opaque type 'struct
  33    dictionary'.  That type has various internal implementations, which
  34    you can choose between depending on what properties you need
  35    (e.g. fast lookup, order-preserving, expandable).
  36
  37    Each dictionary starts with a 'virtual function table' that
  38    contains the functions that actually implement the various
  39    operations that dictionaries provide.  (Note, however, that, for
  40    the sake of client code, we also provide some functions that can be
  41    implemented generically in terms of the functions in the vtable.)
  42
  43    To add a new dictionary implementation <impl>, what you should do
  44    is:
  45
  46    * Add a new element DICT_<IMPL> to dict_type.
  47
  48    * Create a new structure dictionary_<impl>.  If your new
  49    implementation is a variant of an existing one, make sure that
  50    their structs have the same initial data members.  Define accessor
  51    macros for your new data members.
  52
  53    * Implement all the functions in dict_vector as static functions,
  54    whose name is the same as the corresponding member of dict_vector
  55    plus _<impl>.  You don't have to do this for those members where
  56    you can reuse existing generic functions
  57    (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
  58    your new implementation is a variant of an existing implementation
  59    and where the variant doesn't affect the member function in
  60    question.
  61
  62    * Define a static const struct dict_vector dict_<impl>_vector.
  63
  64    * Define a function dict_create_<impl> to create these
  65    gizmos.  Add its declaration to dictionary.h.
  66
  67    To add a new operation <op> on all existing implementations, what
  68    you should do is:
  69
  70    * Add a new member <op> to struct dict_vector.
  71
  72    * If there is useful generic behavior <op>, define a static
  73    function <op>_something_informative that implements that behavior.
  74    (E.g. add_symbol_nonexpandable, free_obstack.)
  75
  76    * For every implementation <impl> that should have its own specific
  77    behavior for <op>, define a static function <op>_<impl>
  78    implementing it.
  79
  80    * Modify all existing dict_vector_<impl>'s to include the appropriate
  81    member.
  82
  83    * Define a function dict_<op> that looks up <op> in the dict_vector
  84    and calls the appropriate function.  Add a declaration for
  85    dict_<op> to dictionary.h.  */
  86
  87 /* An enum representing the various implementations of dictionaries.
  88    Used only for debugging.  */
  89
  90 enum dict_type
  91   {
  92     /* Symbols are stored in a fixed-size hash table.  */
  93     DICT_HASHED,
  94     /* Symbols are stored in an expandable hash table.  */
  95     DICT_HASHED_EXPANDABLE,
  96     /* Symbols are stored in a fixed-size array.  */
  97     DICT_LINEAR,
  98     /* Symbols are stored in an expandable array.  */
  99     DICT_LINEAR_EXPANDABLE
 100   };
 101
 102 /* The virtual function table.  */
 103
 104 struct dict_vector
 105 {
 106   /* The type of the dictionary.  This is only here to make debugging
 107      a bit easier; it's not actually used.  */
 108   enum dict_type type;
 109   /* The function to free a dictionary.  */
 110   void (*free) (struct dictionary *dict);
 111   /* Add a symbol to a dictionary, if possible.  */
 112   void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
 113   /* Iterator functions.  */
 114   struct symbol *(*iterator_first) (const struct dictionary *dict,
 115                                     struct dict_iterator *iterator);
 116   struct symbol *(*iterator_next) (struct dict_iterator *iterator);
 117   /* Functions to iterate over symbols with a given name.  */
 118   struct symbol *(*iter_match_first) (const struct dictionary *dict,
 119                                       const lookup_name_info &name,
 120                                       struct dict_iterator *iterator);
 121   struct symbol *(*iter_match_next) (const lookup_name_info &name,
 122                                      struct dict_iterator *iterator);
 123   /* A size function, for maint print symtabs.  */
 124   int (*size) (const struct dictionary *dict);
 125 };
 126
 127 /* Now comes the structs used to store the data for different
 128    implementations.  If two implementations have data in common, put
 129    the common data at the top of their structs, ordered in the same
 130    way.  */
 131
 132 struct dictionary_hashed
 133 {
 134   int nbuckets;
 135   struct symbol **buckets;
 136 };
 137
 138 struct dictionary_hashed_expandable
 139 {
 140   /* How many buckets we currently have.  */
 141   int nbuckets;
 142   struct symbol **buckets;
 143   /* How many syms we currently have; we need this so we will know
 144      when to add more buckets.  */
 145   int nsyms;
 146 };
 147
 148 struct dictionary_linear
 149 {
 150   int nsyms;
 151   struct symbol **syms;
 152 };
 153
 154 struct dictionary_linear_expandable
 155 {
 156   /* How many symbols we currently have.  */
 157   int nsyms;
 158   struct symbol **syms;
 159   /* How many symbols we can store before needing to reallocate.  */
 160   int capacity;
 161 };
 162
 163 /* And now, the star of our show.  */
 164
 165 struct dictionary
 166 {
 167   const struct language_defn *language;
 168   const struct dict_vector *vector;
 169   union
 170   {
 171     struct dictionary_hashed hashed;
 172     struct dictionary_hashed_expandable hashed_expandable;
 173     struct dictionary_linear linear;
 174     struct dictionary_linear_expandable linear_expandable;
 175   }
 176   data;
 177 };
 178
 179 /* Accessor macros.  */
 180
 181 #define DICT_VECTOR(d)                  (d)->vector
 182 #define DICT_LANGUAGE(d)                (d)->language
 183
 184 /* These can be used for DICT_HASHED_EXPANDABLE, too.  */
 185
 186 #define DICT_HASHED_NBUCKETS(d)         (d)->data.hashed.nbuckets
 187 #define DICT_HASHED_BUCKETS(d)          (d)->data.hashed.buckets
 188 #define DICT_HASHED_BUCKET(d,i)         DICT_HASHED_BUCKETS (d) [i]
 189
 190 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
 191
 192 /* These can be used for DICT_LINEAR_EXPANDABLEs, too.  */
 193
 194 #define DICT_LINEAR_NSYMS(d)            (d)->data.linear.nsyms
 195 #define DICT_LINEAR_SYMS(d)             (d)->data.linear.syms
 196 #define DICT_LINEAR_SYM(d,i)            DICT_LINEAR_SYMS (d) [i]
 197
 198 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
 199                 (d)->data.linear_expandable.capacity
 200
 201 /* The initial size of a DICT_*_EXPANDABLE dictionary.  */
 202
 203 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
 204
 205 /* This calculates the number of buckets we'll use in a hashtable,
 206    given the number of symbols that it will contain.  */
 207
 208 #define DICT_HASHTABLE_SIZE(n)  ((n)/5 + 1)
 209
 210 /* Accessor macros for dict_iterators; they're here rather than
 211    dictionary.h because code elsewhere should treat dict_iterators as
 212    opaque.  */
 213
 214 /* The dictionary that the iterator is associated to.  */
 215 #define DICT_ITERATOR_DICT(iter)                (iter)->dict
 216 /* For linear dictionaries, the index of the last symbol returned; for
 217    hashed dictionaries, the bucket of the last symbol returned.  */
 218 #define DICT_ITERATOR_INDEX(iter)               (iter)->index
 219 /* For hashed dictionaries, this points to the last symbol returned;
 220    otherwise, this is unused.  */
 221 #define DICT_ITERATOR_CURRENT(iter)             (iter)->current
 222
 223 /* Declarations of functions for vectors.  */
 224
 225 /* Functions that might work across a range of dictionary types.  */
 226
 227 static void add_symbol_nonexpandable (struct dictionary *dict,
 228                                       struct symbol *sym);
 229
 230 static void free_obstack (struct dictionary *dict);
 231
 232 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
 233    dictionaries.  */
 234
 235 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
 236                                              struct dict_iterator *iterator);
 237
 238 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
 239
 240 static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
 241                                                const lookup_name_info &name,
 242                                               struct dict_iterator *iterator);
 243
 244 static struct symbol *iter_match_next_hashed (const lookup_name_info &name,
 245                                               struct dict_iterator *iterator);
 246
 247 /* Functions only for DICT_HASHED.  */
 248
 249 static int size_hashed (const struct dictionary *dict);
 250
 251 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 252
 253 static void free_hashed_expandable (struct dictionary *dict);
 254
 255 static void add_symbol_hashed_expandable (struct dictionary *dict,
 256                                           struct symbol *sym);
 257
 258 static int size_hashed_expandable (const struct dictionary *dict);
 259
 260 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
 261    dictionaries.  */
 262
 263 static struct symbol *iterator_first_linear (const struct dictionary *dict,
 264                                              struct dict_iterator *iterator);
 265
 266 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
 267
 268 static struct symbol *iter_match_first_linear (const struct dictionary *dict,
 269                                                const lookup_name_info &name,
 270                                                struct dict_iterator *iterator);
 271
 272 static struct symbol *iter_match_next_linear (const lookup_name_info &name,
 273                                               struct dict_iterator *iterator);
 274
 275 static int size_linear (const struct dictionary *dict);
 276
 277 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 278
 279 static void free_linear_expandable (struct dictionary *dict);
 280
 281 static void add_symbol_linear_expandable (struct dictionary *dict,
 282                                           struct symbol *sym);
 283
 284 /* Various vectors that we'll actually use.  */
 285
 286 static const struct dict_vector dict_hashed_vector =
 287   {
 288     DICT_HASHED,                        /* type */
 289     free_obstack,                       /* free */
 290     add_symbol_nonexpandable,           /* add_symbol */
 291     iterator_first_hashed,              /* iterator_first */
 292     iterator_next_hashed,               /* iterator_next */
 293     iter_match_first_hashed,            /* iter_name_first */
 294     iter_match_next_hashed,             /* iter_name_next */
 295     size_hashed,                        /* size */
 296   };
 297
 298 static const struct dict_vector dict_hashed_expandable_vector =
 299   {
 300     DICT_HASHED_EXPANDABLE,             /* type */
 301     free_hashed_expandable,             /* free */
 302     add_symbol_hashed_expandable,       /* add_symbol */
 303     iterator_first_hashed,              /* iterator_first */
 304     iterator_next_hashed,               /* iterator_next */
 305     iter_match_first_hashed,            /* iter_name_first */
 306     iter_match_next_hashed,             /* iter_name_next */
 307     size_hashed_expandable,             /* size */
 308   };
 309
 310 static const struct dict_vector dict_linear_vector =
 311   {
 312     DICT_LINEAR,                        /* type */
 313     free_obstack,                       /* free */
 314     add_symbol_nonexpandable,           /* add_symbol */
 315     iterator_first_linear,              /* iterator_first */
 316     iterator_next_linear,               /* iterator_next */
 317     iter_match_first_linear,            /* iter_name_first */
 318     iter_match_next_linear,             /* iter_name_next */
 319     size_linear,                        /* size */
 320   };
 321
 322 static const struct dict_vector dict_linear_expandable_vector =
 323   {
 324     DICT_LINEAR_EXPANDABLE,             /* type */
 325     free_linear_expandable,             /* free */
 326     add_symbol_linear_expandable,       /* add_symbol */
 327     iterator_first_linear,              /* iterator_first */
 328     iterator_next_linear,               /* iterator_next */
 329     iter_match_first_linear,            /* iter_name_first */
 330     iter_match_next_linear,             /* iter_name_next */
 331     size_linear,                        /* size */
 332   };
 333
 334 /* Declarations of helper functions (i.e. ones that don't go into
 335    vectors).  */
 336
 337 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
 338
 339 static void insert_symbol_hashed (struct dictionary *dict,
 340                                   struct symbol *sym);
 341
 342 static void expand_hashtable (struct dictionary *dict);
 343
 344 /* The creation functions.  */
 345
 346 /* See dictionary.h.  */
 347
 348 struct dictionary *
 349 dict_create_hashed (struct obstack *obstack,
 350                     enum language language,
 351                     const struct pending *symbol_list)
 352 {
 353   struct dictionary *retval;
 354   int nsyms = 0, nbuckets, i;
 355   struct symbol **buckets;
 356   const struct pending *list_counter;
 357
 358   retval = XOBNEW (obstack, struct dictionary);
 359   DICT_VECTOR (retval) = &dict_hashed_vector;
 360   DICT_LANGUAGE (retval) = language_def (language);
 361
 362   /* Calculate the number of symbols, and allocate space for them.  */
 363   for (list_counter = symbol_list;
 364        list_counter != NULL;
 365        list_counter = list_counter->next)
 366     {
 367       nsyms += list_counter->nsyms;
 368     }
 369   nbuckets = DICT_HASHTABLE_SIZE (nsyms);
 370   DICT_HASHED_NBUCKETS (retval) = nbuckets;
 371   buckets = XOBNEWVEC (obstack, struct symbol *, nbuckets);
 372   memset (buckets, 0, nbuckets * sizeof (struct symbol *));
 373   DICT_HASHED_BUCKETS (retval) = buckets;
 374
 375   /* Now fill the buckets.  */
 376   for (list_counter = symbol_list;
 377        list_counter != NULL;
 378        list_counter = list_counter->next)
 379     {
 380       for (i = list_counter->nsyms - 1; i >= 0; --i)
 381         {
 382           insert_symbol_hashed (retval, list_counter->symbol[i]);
 383         }
 384     }
 385
 386   return retval;
 387 }
 388
 389 /* See dictionary.h.  */
 390
 391 extern struct dictionary *
 392 dict_create_hashed_expandable (enum language language)
 393 {
 394   struct dictionary *retval = XNEW (struct dictionary);
 395
 396   DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
 397   DICT_LANGUAGE (retval) = language_def (language);
 398   DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
 399   DICT_HASHED_BUCKETS (retval) = XCNEWVEC (struct symbol *,
 400                                            DICT_EXPANDABLE_INITIAL_CAPACITY);
 401   DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
 402
 403   return retval;
 404 }
 405
 406 /* See dictionary.h.  */
 407
 408 struct dictionary *
 409 dict_create_linear (struct obstack *obstack,
 410                     enum language language,
 411                     const struct pending *symbol_list)
 412 {
 413   struct dictionary *retval;
 414   int nsyms = 0, i, j;
 415   struct symbol **syms;
 416   const struct pending *list_counter;
 417
 418   retval = XOBNEW (obstack, struct dictionary);
 419   DICT_VECTOR (retval) = &dict_linear_vector;
 420   DICT_LANGUAGE (retval) = language_def (language);
 421
 422   /* Calculate the number of symbols, and allocate space for them.  */
 423   for (list_counter = symbol_list;
 424        list_counter != NULL;
 425        list_counter = list_counter->next)
 426     {
 427       nsyms += list_counter->nsyms;
 428     }
 429   DICT_LINEAR_NSYMS (retval) = nsyms;
 430   syms = XOBNEWVEC (obstack, struct symbol *, nsyms );
 431   DICT_LINEAR_SYMS (retval) = syms;
 432
 433   /* Now fill in the symbols.  Start filling in from the back, so as
 434      to preserve the original order of the symbols.  */
 435   for (list_counter = symbol_list, j = nsyms - 1;
 436        list_counter != NULL;
 437        list_counter = list_counter->next)
 438     {
 439       for (i = list_counter->nsyms - 1;
 440            i >= 0;
 441            --i, --j)
 442         {
 443           syms[j] = list_counter->symbol[i];
 444         }
 445     }
 446
 447   return retval;
 448 }
 449
 450 /* See dictionary.h.  */
 451
 452 struct dictionary *
 453 dict_create_linear_expandable (enum language language)
 454 {
 455   struct dictionary *retval = XNEW (struct dictionary);
 456
 457   DICT_VECTOR (retval) = &dict_linear_expandable_vector;
 458   DICT_LANGUAGE (retval) = language_def (language);
 459   DICT_LINEAR_NSYMS (retval) = 0;
 460   DICT_LINEAR_EXPANDABLE_CAPACITY (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
 461   DICT_LINEAR_SYMS (retval)
 462     = XNEWVEC (struct symbol *, DICT_LINEAR_EXPANDABLE_CAPACITY (retval));
 463
 464   return retval;
 465 }
 466
 467 /* The functions providing the dictionary interface.  */
 468
 469 /* Free the memory used by a dictionary that's not on an obstack.  (If
 470    any.)  */
 471
 472 void
 473 dict_free (struct dictionary *dict)
 474 {
 475   (DICT_VECTOR (dict))->free (dict);
 476 }
 477
 478 /* Add SYM to DICT.  DICT had better be expandable.  */
 479
 480 void
 481 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
 482 {
 483   (DICT_VECTOR (dict))->add_symbol (dict, sym);
 484 }
 485
 486 /* Utility to add a list of symbols to a dictionary.
 487    DICT must be an expandable dictionary.  */
 488
 489 void
 490 dict_add_pending (struct dictionary *dict, const struct pending *symbol_list)
 491 {
 492   const struct pending *list;
 493   int i;
 494
 495   for (list = symbol_list; list != NULL; list = list->next)
 496     {
 497       for (i = 0; i < list->nsyms; ++i)
 498         dict_add_symbol (dict, list->symbol[i]);
 499     }
 500 }
 501
 502 /* Initialize ITERATOR to point at the first symbol in DICT, and
 503    return that first symbol, or NULL if DICT is empty.  */
 504
 505 struct symbol *
 506 dict_iterator_first (const struct dictionary *dict,
 507                      struct dict_iterator *iterator)
 508 {
 509   return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
 510 }
 511
 512 /* Advance ITERATOR, and return the next symbol, or NULL if there are
 513    no more symbols.  */
 514
 515 struct symbol *
 516 dict_iterator_next (struct dict_iterator *iterator)
 517 {
 518   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 519     ->iterator_next (iterator);
 520 }
 521
 522 struct symbol *
 523 dict_iter_match_first (const struct dictionary *dict,
 524                        const lookup_name_info &name,
 525                        struct dict_iterator *iterator)
 526 {
 527   return (DICT_VECTOR (dict))->iter_match_first (dict, name, iterator);
 528 }
 529
 530 struct symbol *
 531 dict_iter_match_next (const lookup_name_info &name,
 532                       struct dict_iterator *iterator)
 533 {
 534   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 535     ->iter_match_next (name, iterator);
 536 }
 537
 538 int
 539 dict_size (const struct dictionary *dict)
 540 {
 541   return (DICT_VECTOR (dict))->size (dict);
 542 }
 543
 544 /* Now come functions (well, one function, currently) that are
 545    implemented generically by means of the vtable.  Typically, they're
 546    rarely used.  */
 547
 548 /* Test to see if DICT is empty.  */
 549
 550 int
 551 dict_empty (struct dictionary *dict)
 552 {
 553   struct dict_iterator iter;
 554
 555   return (dict_iterator_first (dict, &iter) == NULL);
 556 }
 557
 558
 559 /* The functions implementing the dictionary interface.  */
 560
 561 /* Generic functions, where appropriate.  */
 562
 563 static void
 564 free_obstack (struct dictionary *dict)
 565 {
 566   /* Do nothing!  */
 567 }
 568
 569 static void
 570 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
 571 {
 572   internal_error (__FILE__, __LINE__,
 573                   _("dict_add_symbol: non-expandable dictionary"));
 574 }
 575
 576 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE.  */
 577
 578 static struct symbol *
 579 iterator_first_hashed (const struct dictionary *dict,
 580                        struct dict_iterator *iterator)
 581 {
 582   DICT_ITERATOR_DICT (iterator) = dict;
 583   DICT_ITERATOR_INDEX (iterator) = -1;
 584   return iterator_hashed_advance (iterator);
 585 }
 586
 587 static struct symbol *
 588 iterator_next_hashed (struct dict_iterator *iterator)
 589 {
 590   struct symbol *next;
 591
 592   next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 593
 594   if (next == NULL)
 595     return iterator_hashed_advance (iterator);
 596   else
 597     {
 598       DICT_ITERATOR_CURRENT (iterator) = next;
 599       return next;
 600     }
 601 }
 602
 603 static struct symbol *
 604 iterator_hashed_advance (struct dict_iterator *iterator)
 605 {
 606   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 607   int nbuckets = DICT_HASHED_NBUCKETS (dict);
 608   int i;
 609
 610   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
 611     {
 612       struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
 613
 614       if (sym != NULL)
 615         {
 616           DICT_ITERATOR_INDEX (iterator) = i;
 617           DICT_ITERATOR_CURRENT (iterator) = sym;
 618           return sym;
 619         }
 620     }
 621
 622   return NULL;
 623 }
 624
 625 static struct symbol *
 626 iter_match_first_hashed (const struct dictionary *dict,
 627                          const lookup_name_info &name,
 628                          struct dict_iterator *iterator)
 629 {
 630   const language_defn *lang = DICT_LANGUAGE (dict);
 631   unsigned int hash_index = (name.search_name_hash (lang->la_language)
 632                              % DICT_HASHED_NBUCKETS (dict));
 633   symbol_name_matcher_ftype *matches_name
 634     = get_symbol_name_matcher (lang, name);
 635   struct symbol *sym;
 636
 637   DICT_ITERATOR_DICT (iterator) = dict;
 638
 639   /* Loop through the symbols in the given bucket, breaking when SYM
 640      first matches.  If SYM never matches, it will be set to NULL;
 641      either way, we have the right return value.  */
 642
 643   for (sym = DICT_HASHED_BUCKET (dict, hash_index);
 644        sym != NULL;
 645        sym = sym->hash_next)
 646     {
 647       /* Warning: the order of arguments to compare matters!  */
 648       if (matches_name (SYMBOL_SEARCH_NAME (sym), name, NULL))
 649         break;
 650     }
 651
 652   DICT_ITERATOR_CURRENT (iterator) = sym;
 653   return sym;
 654 }
 655
 656 static struct symbol *
 657 iter_match_next_hashed (const lookup_name_info &name,
 658                         struct dict_iterator *iterator)
 659 {
 660   const language_defn *lang = DICT_LANGUAGE (DICT_ITERATOR_DICT (iterator));
 661   symbol_name_matcher_ftype *matches_name
 662     = get_symbol_name_matcher (lang, name);
 663   struct symbol *next;
 664
 665   for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 666        next != NULL;
 667        next = next->hash_next)
 668     {
 669       if (matches_name (SYMBOL_SEARCH_NAME (next), name, NULL))
 670         break;
 671     }
 672
 673   DICT_ITERATOR_CURRENT (iterator) = next;
 674
 675   return next;
 676 }
 677
 678 /* Insert SYM into DICT.  */
 679
 680 static void
 681 insert_symbol_hashed (struct dictionary *dict,
 682                       struct symbol *sym)
 683 {
 684   unsigned int hash_index;
 685   unsigned int hash;
 686   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 687
 688   /* We don't want to insert a symbol into a dictionary of a different
 689      language.  The two may not use the same hashing algorithm.  */
 690   gdb_assert (SYMBOL_LANGUAGE (sym) == DICT_LANGUAGE (dict)->la_language);
 691
 692   hash = search_name_hash (SYMBOL_LANGUAGE (sym), SYMBOL_SEARCH_NAME (sym));
 693   hash_index = hash % DICT_HASHED_NBUCKETS (dict);
 694   sym->hash_next = buckets[hash_index];
 695   buckets[hash_index] = sym;
 696 }
 697
 698 static int
 699 size_hashed (const struct dictionary *dict)
 700 {
 701   return DICT_HASHED_NBUCKETS (dict);
 702 }
 703
 704 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 705
 706 static void
 707 free_hashed_expandable (struct dictionary *dict)
 708 {
 709   xfree (DICT_HASHED_BUCKETS (dict));
 710   xfree (dict);
 711 }
 712
 713 static void
 714 add_symbol_hashed_expandable (struct dictionary *dict,
 715                               struct symbol *sym)
 716 {
 717   int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
 718
 719   if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
 720     expand_hashtable (dict);
 721
 722   insert_symbol_hashed (dict, sym);
 723   DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
 724 }
 725
 726 static int
 727 size_hashed_expandable (const struct dictionary *dict)
 728 {
 729   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
 730 }
 731
 732 static void
 733 expand_hashtable (struct dictionary *dict)
 734 {
 735   int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
 736   struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
 737   int new_nbuckets = 2 * old_nbuckets + 1;
 738   struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets);
 739   int i;
 740
 741   DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
 742   DICT_HASHED_BUCKETS (dict) = new_buckets;
 743
 744   for (i = 0; i < old_nbuckets; ++i)
 745     {
 746       struct symbol *sym, *next_sym;
 747
 748       sym = old_buckets[i];
 749       if (sym != NULL)
 750         {
 751           for (next_sym = sym->hash_next;
 752                next_sym != NULL;
 753                next_sym = sym->hash_next)
 754             {
 755               insert_symbol_hashed (dict, sym);
 756               sym = next_sym;
 757             }
 758
 759           insert_symbol_hashed (dict, sym);
 760         }
 761     }
 762
 763   xfree (old_buckets);
 764 }
 765
 766 /* See dictionary.h.  */
 767
 768 unsigned int
 769 default_search_name_hash (const char *string0)
 770 {
 771   /* The Ada-encoded version of a name P1.P2...Pn has either the form
 772      P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
 773      are lower-cased identifiers).  The <suffix> (which can be empty)
 774      encodes additional information about the denoted entity.  This
 775      routine hashes such names to msymbol_hash_iw(Pn).  It actually
 776      does this for a superset of both valid Pi and of <suffix>, but
 777      in other cases it simply returns msymbol_hash_iw(STRING0).  */
 778
 779   const char *string;
 780   unsigned int hash;
 781
 782   string = string0;
 783   if (*string == '_')
 784     {
 785       if (startswith (string, "_ada_"))
 786         string += 5;
 787       else
 788         return msymbol_hash_iw (string0);
 789     }
 790
 791   hash = 0;
 792   while (*string)
 793     {
 794       switch (*string)
 795         {
 796         case '$':
 797         case '.':
 798         case 'X':
 799           if (string0 == string)
 800             return msymbol_hash_iw (string0);
 801           else
 802             return hash;
 803         case ' ':
 804         case '(':
 805           return msymbol_hash_iw (string0);
 806         case '_':
 807           if (string[1] == '_' && string != string0)
 808             {
 809               int c = string[2];
 810
 811               if ((c < 'a' || c > 'z') && c != 'O')
 812                 return hash;
 813               hash = 0;
 814               string += 2;
 815               continue;
 816             }
 817           break;
 818         case 'T':
 819           /* Ignore "TKB" suffixes.
 820
 821              These are used by Ada for subprograms implementing a task body.
 822              For instance for a task T inside package Pck, the name of the
 823              subprogram implementing T's body is `pck__tTKB'.  We need to
 824              ignore the "TKB" suffix because searches for this task body
 825              subprogram are going to be performed using `pck__t' (the encoded
 826              version of the natural name `pck.t').  */
 827           if (strcmp (string, "TKB") == 0)
 828             return hash;
 829           break;
 830         }
 831
 832       hash = SYMBOL_HASH_NEXT (hash, *string);
 833       string += 1;
 834     }
 835   return hash;
 836 }
 837
 838 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 839
 840 static struct symbol *
 841 iterator_first_linear (const struct dictionary *dict,
 842                        struct dict_iterator *iterator)
 843 {
 844   DICT_ITERATOR_DICT (iterator) = dict;
 845   DICT_ITERATOR_INDEX (iterator) = 0;
 846   return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
 847 }
 848
 849 static struct symbol *
 850 iterator_next_linear (struct dict_iterator *iterator)
 851 {
 852   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 853
 854   if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
 855     return NULL;
 856   else
 857     return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
 858 }
 859
 860 static struct symbol *
 861 iter_match_first_linear (const struct dictionary *dict,
 862                          const lookup_name_info &name,
 863                          struct dict_iterator *iterator)
 864 {
 865   DICT_ITERATOR_DICT (iterator) = dict;
 866   DICT_ITERATOR_INDEX (iterator) = -1;
 867
 868   return iter_match_next_linear (name, iterator);
 869 }
 870
 871 static struct symbol *
 872 iter_match_next_linear (const lookup_name_info &name,
 873                         struct dict_iterator *iterator)
 874 {
 875   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 876   const language_defn *lang = DICT_LANGUAGE (dict);
 877   symbol_name_matcher_ftype *matches_name
 878     = get_symbol_name_matcher (lang, name);
 879
 880   int i, nsyms = DICT_LINEAR_NSYMS (dict);
 881   struct symbol *sym, *retval = NULL;
 882
 883   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
 884     {
 885       sym = DICT_LINEAR_SYM (dict, i);
 886
 887       if (matches_name (SYMBOL_SEARCH_NAME (sym), name, NULL))
 888         {
 889           retval = sym;
 890           break;
 891         }
 892     }
 893
 894   DICT_ITERATOR_INDEX (iterator) = i;
 895
 896   return retval;
 897 }
 898
 899 static int
 900 size_linear (const struct dictionary *dict)
 901 {
 902   return DICT_LINEAR_NSYMS (dict);
 903 }
 904
 905 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 906
 907 static void
 908 free_linear_expandable (struct dictionary *dict)
 909 {
 910   xfree (DICT_LINEAR_SYMS (dict));
 911   xfree (dict);
 912 }
 913
 914
 915 static void
 916 add_symbol_linear_expandable (struct dictionary *dict,
 917                               struct symbol *sym)
 918 {
 919   int nsyms = ++DICT_LINEAR_NSYMS (dict);
 920
 921   /* Do we have enough room?  If not, grow it.  */
 922   if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
 923     {
 924       DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
 925       DICT_LINEAR_SYMS (dict)
 926         = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict),
 927                       DICT_LINEAR_EXPANDABLE_CAPACITY (dict));
 928     }
 929
 930   DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
 931 }