gdb/dictionary.c

   1 /* Routines for name->symbol lookups in GDB.
   2
   3    Copyright (C) 2003, 2007-2012 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 "gdb_assert.h"
  29 #include "dictionary.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 char *name,
 120                                       symbol_compare_ftype *equiv,
 121                                       struct dict_iterator *iterator);
 122   struct symbol *(*iter_match_next) (const char *name,
 123                                      symbol_compare_ftype *equiv,
 124                                      struct dict_iterator *iterator);
 125   /* A size function, for maint print symtabs.  */
 126   int (*size) (const struct dictionary *dict);
 127 };
 128
 129 /* Now comes the structs used to store the data for different
 130    implementations.  If two implementations have data in common, put
 131    the common data at the top of their structs, ordered in the same
 132    way.  */
 133
 134 struct dictionary_hashed
 135 {
 136   int nbuckets;
 137   struct symbol **buckets;
 138 };
 139
 140 struct dictionary_hashed_expandable
 141 {
 142   /* How many buckets we currently have.  */
 143   int nbuckets;
 144   struct symbol **buckets;
 145   /* How many syms we currently have; we need this so we will know
 146      when to add more buckets.  */
 147   int nsyms;
 148 };
 149
 150 struct dictionary_linear
 151 {
 152   int nsyms;
 153   struct symbol **syms;
 154 };
 155
 156 struct dictionary_linear_expandable
 157 {
 158   /* How many symbols we currently have.  */
 159   int nsyms;
 160   struct symbol **syms;
 161   /* How many symbols we can store before needing to reallocate.  */
 162   int capacity;
 163 };
 164
 165 /* And now, the star of our show.  */
 166
 167 struct dictionary
 168 {
 169   const struct 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
 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 char *name,
 242                                                symbol_compare_ftype *compare,
 243                                               struct dict_iterator *iterator);
 244
 245 static struct symbol *iter_match_next_hashed (const char *name,
 246                                               symbol_compare_ftype *compare,
 247                                               struct dict_iterator *iterator);
 248
 249 static unsigned int dict_hash (const char *string);
 250
 251 /* Functions only for DICT_HASHED.  */
 252
 253 static int size_hashed (const struct dictionary *dict);
 254
 255 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 256
 257 static void free_hashed_expandable (struct dictionary *dict);
 258
 259 static void add_symbol_hashed_expandable (struct dictionary *dict,
 260                                           struct symbol *sym);
 261
 262 static int size_hashed_expandable (const struct dictionary *dict);
 263
 264 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
 265    dictionaries.  */
 266
 267 static struct symbol *iterator_first_linear (const struct dictionary *dict,
 268                                              struct dict_iterator *iterator);
 269
 270 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
 271
 272 static struct symbol *iter_match_first_linear (const struct dictionary *dict,
 273                                                const char *name,
 274                                                symbol_compare_ftype *compare,
 275                                                struct dict_iterator *iterator);
 276
 277 static struct symbol *iter_match_next_linear (const char *name,
 278                                               symbol_compare_ftype *compare,
 279                                               struct dict_iterator *iterator);
 280
 281 static int size_linear (const struct dictionary *dict);
 282
 283 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 284
 285 static void free_linear_expandable (struct dictionary *dict);
 286
 287 static void add_symbol_linear_expandable (struct dictionary *dict,
 288                                           struct symbol *sym);
 289
 290 /* Various vectors that we'll actually use.  */
 291
 292 static const struct dict_vector dict_hashed_vector =
 293   {
 294     DICT_HASHED,                        /* type */
 295     free_obstack,                       /* free */
 296     add_symbol_nonexpandable,           /* add_symbol */
 297     iterator_first_hashed,              /* iterator_first */
 298     iterator_next_hashed,               /* iterator_next */
 299     iter_match_first_hashed,            /* iter_name_first */
 300     iter_match_next_hashed,             /* iter_name_next */
 301     size_hashed,                        /* size */
 302   };
 303
 304 static const struct dict_vector dict_hashed_expandable_vector =
 305   {
 306     DICT_HASHED_EXPANDABLE,             /* type */
 307     free_hashed_expandable,             /* free */
 308     add_symbol_hashed_expandable,       /* add_symbol */
 309     iterator_first_hashed,              /* iterator_first */
 310     iterator_next_hashed,               /* iterator_next */
 311     iter_match_first_hashed,            /* iter_name_first */
 312     iter_match_next_hashed,             /* iter_name_next */
 313     size_hashed_expandable,             /* size */
 314   };
 315
 316 static const struct dict_vector dict_linear_vector =
 317   {
 318     DICT_LINEAR,                        /* type */
 319     free_obstack,                       /* free */
 320     add_symbol_nonexpandable,           /* add_symbol */
 321     iterator_first_linear,              /* iterator_first */
 322     iterator_next_linear,               /* iterator_next */
 323     iter_match_first_linear,            /* iter_name_first */
 324     iter_match_next_linear,             /* iter_name_next */
 325     size_linear,                        /* size */
 326   };
 327
 328 static const struct dict_vector dict_linear_expandable_vector =
 329   {
 330     DICT_LINEAR_EXPANDABLE,             /* type */
 331     free_linear_expandable,             /* free */
 332     add_symbol_linear_expandable,       /* add_symbol */
 333     iterator_first_linear,              /* iterator_first */
 334     iterator_next_linear,               /* iterator_next */
 335     iter_match_first_linear,            /* iter_name_first */
 336     iter_match_next_linear,             /* iter_name_next */
 337     size_linear,                        /* size */
 338   };
 339
 340 /* Declarations of helper functions (i.e. ones that don't go into
 341    vectors).  */
 342
 343 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
 344
 345 static void insert_symbol_hashed (struct dictionary *dict,
 346                                   struct symbol *sym);
 347
 348 static void expand_hashtable (struct dictionary *dict);
 349
 350 /* The creation functions.  */
 351
 352 /* Create a dictionary implemented via a fixed-size hashtable.  All
 353    memory it uses is allocated on OBSTACK; the environment is
 354    initialized from SYMBOL_LIST.  */
 355
 356 struct dictionary *
 357 dict_create_hashed (struct obstack *obstack,
 358                     const struct pending *symbol_list)
 359 {
 360   struct dictionary *retval;
 361   int nsyms = 0, nbuckets, i;
 362   struct symbol **buckets;
 363   const struct pending *list_counter;
 364
 365   retval = obstack_alloc (obstack, sizeof (struct dictionary));
 366   DICT_VECTOR (retval) = &dict_hashed_vector;
 367
 368   /* Calculate the number of symbols, and allocate space for them.  */
 369   for (list_counter = symbol_list;
 370        list_counter != NULL;
 371        list_counter = list_counter->next)
 372     {
 373       nsyms += list_counter->nsyms;
 374     }
 375   nbuckets = DICT_HASHTABLE_SIZE (nsyms);
 376   DICT_HASHED_NBUCKETS (retval) = nbuckets;
 377   buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
 378   memset (buckets, 0, nbuckets * sizeof (struct symbol *));
 379   DICT_HASHED_BUCKETS (retval) = buckets;
 380
 381   /* Now fill the buckets.  */
 382   for (list_counter = symbol_list;
 383        list_counter != NULL;
 384        list_counter = list_counter->next)
 385     {
 386       for (i = list_counter->nsyms - 1; i >= 0; --i)
 387         {
 388           insert_symbol_hashed (retval, list_counter->symbol[i]);
 389         }
 390     }
 391
 392   return retval;
 393 }
 394
 395 /* Create a dictionary implemented via a hashtable that grows as
 396    necessary.  The dictionary is initially empty; to add symbols to
 397    it, call dict_add_symbol().  Call dict_free() when you're done with
 398    it.  */
 399
 400 extern struct dictionary *
 401 dict_create_hashed_expandable (void)
 402 {
 403   struct dictionary *retval;
 404
 405   retval = xmalloc (sizeof (struct dictionary));
 406   DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
 407   DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
 408   DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
 409                                           sizeof (struct symbol *));
 410   DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
 411
 412   return retval;
 413 }
 414
 415 /* Create a dictionary implemented via a fixed-size array.  All memory
 416    it uses is allocated on OBSTACK; the environment is initialized
 417    from the SYMBOL_LIST.  The symbols are ordered in the same order
 418    that they're found in SYMBOL_LIST.  */
 419
 420 struct dictionary *
 421 dict_create_linear (struct obstack *obstack,
 422                     const struct pending *symbol_list)
 423 {
 424   struct dictionary *retval;
 425   int nsyms = 0, i, j;
 426   struct symbol **syms;
 427   const struct pending *list_counter;
 428
 429   retval = obstack_alloc (obstack, sizeof (struct dictionary));
 430   DICT_VECTOR (retval) = &dict_linear_vector;
 431
 432   /* Calculate the number of symbols, and allocate space for them.  */
 433   for (list_counter = symbol_list;
 434        list_counter != NULL;
 435        list_counter = list_counter->next)
 436     {
 437       nsyms += list_counter->nsyms;
 438     }
 439   DICT_LINEAR_NSYMS (retval) = nsyms;
 440   syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
 441   DICT_LINEAR_SYMS (retval) = syms;
 442
 443   /* Now fill in the symbols.  Start filling in from the back, so as
 444      to preserve the original order of the symbols.  */
 445   for (list_counter = symbol_list, j = nsyms - 1;
 446        list_counter != NULL;
 447        list_counter = list_counter->next)
 448     {
 449       for (i = list_counter->nsyms - 1;
 450            i >= 0;
 451            --i, --j)
 452         {
 453           syms[j] = list_counter->symbol[i];
 454         }
 455     }
 456
 457   return retval;
 458 }
 459
 460 /* Create a dictionary implemented via an array that grows as
 461    necessary.  The dictionary is initially empty; to add symbols to
 462    it, call dict_add_symbol().  Call dict_free() when you're done with
 463    it.  */
 464
 465 struct dictionary *
 466 dict_create_linear_expandable (void)
 467 {
 468   struct dictionary *retval;
 469
 470   retval = xmalloc (sizeof (struct dictionary));
 471   DICT_VECTOR (retval) = &dict_linear_expandable_vector;
 472   DICT_LINEAR_NSYMS (retval) = 0;
 473   DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
 474     = DICT_EXPANDABLE_INITIAL_CAPACITY;
 475   DICT_LINEAR_SYMS (retval)
 476     = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
 477                * sizeof (struct symbol *));
 478
 479   return retval;
 480 }
 481
 482 /* The functions providing the dictionary interface.  */
 483
 484 /* Free the memory used by a dictionary that's not on an obstack.  (If
 485    any.)  */
 486
 487 void
 488 dict_free (struct dictionary *dict)
 489 {
 490   (DICT_VECTOR (dict))->free (dict);
 491 }
 492
 493 /* Add SYM to DICT.  DICT had better be expandable.  */
 494
 495 void
 496 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
 497 {
 498   (DICT_VECTOR (dict))->add_symbol (dict, sym);
 499 }
 500
 501 /* Initialize ITERATOR to point at the first symbol in DICT, and
 502    return that first symbol, or NULL if DICT is empty.  */
 503
 504 struct symbol *
 505 dict_iterator_first (const struct dictionary *dict,
 506                      struct dict_iterator *iterator)
 507 {
 508   return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
 509 }
 510
 511 /* Advance ITERATOR, and return the next symbol, or NULL if there are
 512    no more symbols.  */
 513
 514 struct symbol *
 515 dict_iterator_next (struct dict_iterator *iterator)
 516 {
 517   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 518     ->iterator_next (iterator);
 519 }
 520
 521 struct symbol *
 522 dict_iter_name_first (const struct dictionary *dict,
 523                       const char *name,
 524                       struct dict_iterator *iterator)
 525 {
 526   return dict_iter_match_first (dict, name, strcmp_iw, iterator);
 527 }
 528
 529 struct symbol *
 530 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
 531 {
 532   return dict_iter_match_next (name, strcmp_iw, iterator);
 533 }
 534
 535 struct symbol *
 536 dict_iter_match_first (const struct dictionary *dict,
 537                        const char *name, symbol_compare_ftype *compare,
 538                        struct dict_iterator *iterator)
 539 {
 540   return (DICT_VECTOR (dict))->iter_match_first (dict, name,
 541                                                  compare, iterator);
 542 }
 543
 544 struct symbol *
 545 dict_iter_match_next (const char *name, symbol_compare_ftype *compare,
 546                       struct dict_iterator *iterator)
 547 {
 548   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 549     ->iter_match_next (name, compare, iterator);
 550 }
 551
 552 int
 553 dict_size (const struct dictionary *dict)
 554 {
 555   return (DICT_VECTOR (dict))->size (dict);
 556 }
 557
 558 /* Now come functions (well, one function, currently) that are
 559    implemented generically by means of the vtable.  Typically, they're
 560    rarely used.  */
 561
 562 /* Test to see if DICT is empty.  */
 563
 564 int
 565 dict_empty (struct dictionary *dict)
 566 {
 567   struct dict_iterator iter;
 568
 569   return (dict_iterator_first (dict, &iter) == NULL);
 570 }
 571
 572
 573 /* The functions implementing the dictionary interface.  */
 574
 575 /* Generic functions, where appropriate.  */
 576
 577 static void
 578 free_obstack (struct dictionary *dict)
 579 {
 580   /* Do nothing!  */
 581 }
 582
 583 static void
 584 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
 585 {
 586   internal_error (__FILE__, __LINE__,
 587                   _("dict_add_symbol: non-expandable dictionary"));
 588 }
 589
 590 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE.  */
 591
 592 static struct symbol *
 593 iterator_first_hashed (const struct dictionary *dict,
 594                        struct dict_iterator *iterator)
 595 {
 596   DICT_ITERATOR_DICT (iterator) = dict;
 597   DICT_ITERATOR_INDEX (iterator) = -1;
 598   return iterator_hashed_advance (iterator);
 599 }
 600
 601 static struct symbol *
 602 iterator_next_hashed (struct dict_iterator *iterator)
 603 {
 604   struct symbol *next;
 605
 606   next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 607
 608   if (next == NULL)
 609     return iterator_hashed_advance (iterator);
 610   else
 611     {
 612       DICT_ITERATOR_CURRENT (iterator) = next;
 613       return next;
 614     }
 615 }
 616
 617 static struct symbol *
 618 iterator_hashed_advance (struct dict_iterator *iterator)
 619 {
 620   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 621   int nbuckets = DICT_HASHED_NBUCKETS (dict);
 622   int i;
 623
 624   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
 625     {
 626       struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
 627
 628       if (sym != NULL)
 629         {
 630           DICT_ITERATOR_INDEX (iterator) = i;
 631           DICT_ITERATOR_CURRENT (iterator) = sym;
 632           return sym;
 633         }
 634     }
 635
 636   return NULL;
 637 }
 638
 639 static struct symbol *
 640 iter_match_first_hashed (const struct dictionary *dict, const char *name,
 641                          symbol_compare_ftype *compare,
 642                          struct dict_iterator *iterator)
 643 {
 644   unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
 645   struct symbol *sym;
 646
 647   DICT_ITERATOR_DICT (iterator) = dict;
 648
 649   /* Loop through the symbols in the given bucket, breaking when SYM
 650      first matches.  If SYM never matches, it will be set to NULL;
 651      either way, we have the right return value.  */
 652
 653   for (sym = DICT_HASHED_BUCKET (dict, hash_index);
 654        sym != NULL;
 655        sym = sym->hash_next)
 656     {
 657       /* Warning: the order of arguments to compare matters!  */
 658       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 659         {
 660           break;
 661         }
 662
 663     }
 664
 665   DICT_ITERATOR_CURRENT (iterator) = sym;
 666   return sym;
 667 }
 668
 669 static struct symbol *
 670 iter_match_next_hashed (const char *name, symbol_compare_ftype *compare,
 671                         struct dict_iterator *iterator)
 672 {
 673   struct symbol *next;
 674
 675   for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 676        next != NULL;
 677        next = next->hash_next)
 678     {
 679       if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
 680         break;
 681     }
 682
 683   DICT_ITERATOR_CURRENT (iterator) = next;
 684
 685   return next;
 686 }
 687
 688 /* Insert SYM into DICT.  */
 689
 690 static void
 691 insert_symbol_hashed (struct dictionary *dict,
 692                       struct symbol *sym)
 693 {
 694   unsigned int hash_index;
 695   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 696
 697   hash_index =
 698     dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
 699   sym->hash_next = buckets[hash_index];
 700   buckets[hash_index] = sym;
 701 }
 702
 703 static int
 704 size_hashed (const struct dictionary *dict)
 705 {
 706   return DICT_HASHED_NBUCKETS (dict);
 707 }
 708
 709 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 710
 711 static void
 712 free_hashed_expandable (struct dictionary *dict)
 713 {
 714   xfree (DICT_HASHED_BUCKETS (dict));
 715   xfree (dict);
 716 }
 717
 718 static void
 719 add_symbol_hashed_expandable (struct dictionary *dict,
 720                               struct symbol *sym)
 721 {
 722   int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
 723
 724   if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
 725     expand_hashtable (dict);
 726
 727   insert_symbol_hashed (dict, sym);
 728   DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
 729 }
 730
 731 static int
 732 size_hashed_expandable (const struct dictionary *dict)
 733 {
 734   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
 735 }
 736
 737 static void
 738 expand_hashtable (struct dictionary *dict)
 739 {
 740   int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
 741   struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
 742   int new_nbuckets = 2*old_nbuckets + 1;
 743   struct symbol **new_buckets = xcalloc (new_nbuckets,
 744                                          sizeof (struct symbol *));
 745   int i;
 746
 747   DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
 748   DICT_HASHED_BUCKETS (dict) = new_buckets;
 749
 750   for (i = 0; i < old_nbuckets; ++i)
 751     {
 752       struct symbol *sym, *next_sym;
 753
 754       sym = old_buckets[i];
 755       if (sym != NULL)
 756         {
 757           for (next_sym = sym->hash_next;
 758                next_sym != NULL;
 759                next_sym = sym->hash_next)
 760             {
 761               insert_symbol_hashed (dict, sym);
 762               sym = next_sym;
 763             }
 764
 765           insert_symbol_hashed (dict, sym);
 766         }
 767     }
 768
 769   xfree (old_buckets);
 770 }
 771
 772 /* Produce an unsigned hash value from STRING0 that is consistent
 773    with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
 774    That is, two identifiers equivalent according to any of those three
 775    comparison operators hash to the same value.  */
 776
 777 static unsigned int
 778 dict_hash (const char *string0)
 779 {
 780   /* The Ada-encoded version of a name P1.P2...Pn has either the form
 781      P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
 782      are lower-cased identifiers).  The <suffix> (which can be empty)
 783      encodes additional information about the denoted entity.  This
 784      routine hashes such names to msymbol_hash_iw(Pn).  It actually
 785      does this for a superset of both valid Pi and of <suffix>, but
 786      in other cases it simply returns msymbol_hash_iw(STRING0).  */
 787
 788   const char *string;
 789   unsigned int hash;
 790
 791   string = string0;
 792   if (*string == '_')
 793     {
 794       if (strncmp (string, "_ada_", 5) == 0)
 795         string += 5;
 796       else
 797         return msymbol_hash_iw (string0);
 798     }
 799
 800   hash = 0;
 801   while (*string)
 802     {
 803       /* Ignore "TKB" suffixes.
 804
 805          These are used by Ada for subprograms implementing a task body.
 806          For instance for a task T inside package Pck, the name of the
 807          subprogram implementing T's body is `pck__tTKB'.  We need to
 808          ignore the "TKB" suffix because searches for this task body
 809          subprogram are going to be performed using `pck__t' (the encoded
 810          version of the natural name `pck.t').  */
 811       if (strcmp (string, "TKB") == 0)
 812         return hash;
 813
 814       switch (*string)
 815         {
 816         case '$':
 817         case '.':
 818         case 'X':
 819           if (string0 == string)
 820             return msymbol_hash_iw (string0);
 821           else
 822             return hash;
 823         case ' ':
 824         case '(':
 825           return msymbol_hash_iw (string0);
 826         case '_':
 827           if (string[1] == '_' && string != string0)
 828             {
 829               int c = string[2];
 830
 831               if ((c < 'a' || c > 'z') && c != 'O')
 832                 return hash;
 833               hash = 0;
 834               string += 2;
 835               break;
 836             }
 837           /* FALL THROUGH */
 838         default:
 839           hash = SYMBOL_HASH_NEXT (hash, *string);
 840           string += 1;
 841           break;
 842         }
 843     }
 844   return hash;
 845 }
 846
 847 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 848
 849 static struct symbol *
 850 iterator_first_linear (const struct dictionary *dict,
 851                        struct dict_iterator *iterator)
 852 {
 853   DICT_ITERATOR_DICT (iterator) = dict;
 854   DICT_ITERATOR_INDEX (iterator) = 0;
 855   return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
 856 }
 857
 858 static struct symbol *
 859 iterator_next_linear (struct dict_iterator *iterator)
 860 {
 861   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 862
 863   if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
 864     return NULL;
 865   else
 866     return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
 867 }
 868
 869 static struct symbol *
 870 iter_match_first_linear (const struct dictionary *dict,
 871                          const char *name, symbol_compare_ftype *compare,
 872                          struct dict_iterator *iterator)
 873 {
 874   DICT_ITERATOR_DICT (iterator) = dict;
 875   DICT_ITERATOR_INDEX (iterator) = -1;
 876
 877   return iter_match_next_linear (name, compare, iterator);
 878 }
 879
 880 static struct symbol *
 881 iter_match_next_linear (const char *name, symbol_compare_ftype *compare,
 882                         struct dict_iterator *iterator)
 883 {
 884   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 885   int i, nsyms = DICT_LINEAR_NSYMS (dict);
 886   struct symbol *sym, *retval = NULL;
 887
 888   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
 889     {
 890       sym = DICT_LINEAR_SYM (dict, i);
 891       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 892         {
 893           retval = sym;
 894           break;
 895         }
 896     }
 897
 898   DICT_ITERATOR_INDEX (iterator) = i;
 899
 900   return retval;
 901 }
 902
 903 static int
 904 size_linear (const struct dictionary *dict)
 905 {
 906   return DICT_LINEAR_NSYMS (dict);
 907 }
 908
 909 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 910
 911 static void
 912 free_linear_expandable (struct dictionary *dict)
 913 {
 914   xfree (DICT_LINEAR_SYMS (dict));
 915   xfree (dict);
 916 }
 917
 918
 919 static void
 920 add_symbol_linear_expandable (struct dictionary *dict,
 921                               struct symbol *sym)
 922 {
 923   int nsyms = ++DICT_LINEAR_NSYMS (dict);
 924
 925   /* Do we have enough room?  If not, grow it.  */
 926   if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
 927     {
 928       DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
 929       DICT_LINEAR_SYMS (dict)
 930         = xrealloc (DICT_LINEAR_SYMS (dict),
 931                     DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
 932                     * sizeof (struct symbol *));
 933     }
 934
 935   DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
 936 }