gdb/dictionary.c

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