gdb/dictionary.c

   1 /* Routines for name->symbol lookups in GDB.
   2
   3    Copyright (C) 2003-2017 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 = XOBNEW (obstack, 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 = XOBNEWVEC (obstack, struct symbol *, nbuckets);
 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 = XNEW (struct dictionary);
 403
 404   DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
 405   DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
 406   DICT_HASHED_BUCKETS (retval) = XCNEWVEC (struct symbol *,
 407                                            DICT_EXPANDABLE_INITIAL_CAPACITY);
 408   DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
 409
 410   return retval;
 411 }
 412
 413 /* Create a dictionary implemented via a fixed-size array.  All memory
 414    it uses is allocated on OBSTACK; the environment is initialized
 415    from the SYMBOL_LIST.  The symbols are ordered in the same order
 416    that they're found in SYMBOL_LIST.  */
 417
 418 struct dictionary *
 419 dict_create_linear (struct obstack *obstack,
 420                     const struct pending *symbol_list)
 421 {
 422   struct dictionary *retval;
 423   int nsyms = 0, i, j;
 424   struct symbol **syms;
 425   const struct pending *list_counter;
 426
 427   retval = XOBNEW (obstack, struct dictionary);
 428   DICT_VECTOR (retval) = &dict_linear_vector;
 429
 430   /* Calculate the number of symbols, and allocate space for them.  */
 431   for (list_counter = symbol_list;
 432        list_counter != NULL;
 433        list_counter = list_counter->next)
 434     {
 435       nsyms += list_counter->nsyms;
 436     }
 437   DICT_LINEAR_NSYMS (retval) = nsyms;
 438   syms = XOBNEWVEC (obstack, struct symbol *, nsyms );
 439   DICT_LINEAR_SYMS (retval) = syms;
 440
 441   /* Now fill in the symbols.  Start filling in from the back, so as
 442      to preserve the original order of the symbols.  */
 443   for (list_counter = symbol_list, j = nsyms - 1;
 444        list_counter != NULL;
 445        list_counter = list_counter->next)
 446     {
 447       for (i = list_counter->nsyms - 1;
 448            i >= 0;
 449            --i, --j)
 450         {
 451           syms[j] = list_counter->symbol[i];
 452         }
 453     }
 454
 455   return retval;
 456 }
 457
 458 /* Create a dictionary implemented via an array that grows as
 459    necessary.  The dictionary is initially empty; to add symbols to
 460    it, call dict_add_symbol().  Call dict_free() when you're done with
 461    it.  */
 462
 463 struct dictionary *
 464 dict_create_linear_expandable (void)
 465 {
 466   struct dictionary *retval = XNEW (struct dictionary);
 467
 468   DICT_VECTOR (retval) = &dict_linear_expandable_vector;
 469   DICT_LINEAR_NSYMS (retval) = 0;
 470   DICT_LINEAR_EXPANDABLE_CAPACITY (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
 471   DICT_LINEAR_SYMS (retval)
 472     = XNEWVEC (struct symbol *, DICT_LINEAR_EXPANDABLE_CAPACITY (retval));
 473
 474   return retval;
 475 }
 476
 477 /* The functions providing the dictionary interface.  */
 478
 479 /* Free the memory used by a dictionary that's not on an obstack.  (If
 480    any.)  */
 481
 482 void
 483 dict_free (struct dictionary *dict)
 484 {
 485   (DICT_VECTOR (dict))->free (dict);
 486 }
 487
 488 /* Add SYM to DICT.  DICT had better be expandable.  */
 489
 490 void
 491 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
 492 {
 493   (DICT_VECTOR (dict))->add_symbol (dict, sym);
 494 }
 495
 496 /* Utility to add a list of symbols to a dictionary.
 497    DICT must be an expandable dictionary.  */
 498
 499 void
 500 dict_add_pending (struct dictionary *dict, const struct pending *symbol_list)
 501 {
 502   const struct pending *list;
 503   int i;
 504
 505   for (list = symbol_list; list != NULL; list = list->next)
 506     {
 507       for (i = 0; i < list->nsyms; ++i)
 508         dict_add_symbol (dict, list->symbol[i]);
 509     }
 510 }
 511
 512 /* Initialize ITERATOR to point at the first symbol in DICT, and
 513    return that first symbol, or NULL if DICT is empty.  */
 514
 515 struct symbol *
 516 dict_iterator_first (const struct dictionary *dict,
 517                      struct dict_iterator *iterator)
 518 {
 519   return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
 520 }
 521
 522 /* Advance ITERATOR, and return the next symbol, or NULL if there are
 523    no more symbols.  */
 524
 525 struct symbol *
 526 dict_iterator_next (struct dict_iterator *iterator)
 527 {
 528   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 529     ->iterator_next (iterator);
 530 }
 531
 532 struct symbol *
 533 dict_iter_match_first (const struct dictionary *dict,
 534                        const char *name, symbol_compare_ftype *compare,
 535                        struct dict_iterator *iterator)
 536 {
 537   return (DICT_VECTOR (dict))->iter_match_first (dict, name,
 538                                                  compare, iterator);
 539 }
 540
 541 struct symbol *
 542 dict_iter_match_next (const char *name, symbol_compare_ftype *compare,
 543                       struct dict_iterator *iterator)
 544 {
 545   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 546     ->iter_match_next (name, compare, iterator);
 547 }
 548
 549 int
 550 dict_size (const struct dictionary *dict)
 551 {
 552   return (DICT_VECTOR (dict))->size (dict);
 553 }
 554
 555 /* Now come functions (well, one function, currently) that are
 556    implemented generically by means of the vtable.  Typically, they're
 557    rarely used.  */
 558
 559 /* Test to see if DICT is empty.  */
 560
 561 int
 562 dict_empty (struct dictionary *dict)
 563 {
 564   struct dict_iterator iter;
 565
 566   return (dict_iterator_first (dict, &iter) == NULL);
 567 }
 568
 569
 570 /* The functions implementing the dictionary interface.  */
 571
 572 /* Generic functions, where appropriate.  */
 573
 574 static void
 575 free_obstack (struct dictionary *dict)
 576 {
 577   /* Do nothing!  */
 578 }
 579
 580 static void
 581 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
 582 {
 583   internal_error (__FILE__, __LINE__,
 584                   _("dict_add_symbol: non-expandable dictionary"));
 585 }
 586
 587 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE.  */
 588
 589 static struct symbol *
 590 iterator_first_hashed (const struct dictionary *dict,
 591                        struct dict_iterator *iterator)
 592 {
 593   DICT_ITERATOR_DICT (iterator) = dict;
 594   DICT_ITERATOR_INDEX (iterator) = -1;
 595   return iterator_hashed_advance (iterator);
 596 }
 597
 598 static struct symbol *
 599 iterator_next_hashed (struct dict_iterator *iterator)
 600 {
 601   struct symbol *next;
 602
 603   next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 604
 605   if (next == NULL)
 606     return iterator_hashed_advance (iterator);
 607   else
 608     {
 609       DICT_ITERATOR_CURRENT (iterator) = next;
 610       return next;
 611     }
 612 }
 613
 614 static struct symbol *
 615 iterator_hashed_advance (struct dict_iterator *iterator)
 616 {
 617   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 618   int nbuckets = DICT_HASHED_NBUCKETS (dict);
 619   int i;
 620
 621   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
 622     {
 623       struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
 624
 625       if (sym != NULL)
 626         {
 627           DICT_ITERATOR_INDEX (iterator) = i;
 628           DICT_ITERATOR_CURRENT (iterator) = sym;
 629           return sym;
 630         }
 631     }
 632
 633   return NULL;
 634 }
 635
 636 static struct symbol *
 637 iter_match_first_hashed (const struct dictionary *dict, const char *name,
 638                          symbol_compare_ftype *compare,
 639                          struct dict_iterator *iterator)
 640 {
 641   unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
 642   struct symbol *sym;
 643
 644   DICT_ITERATOR_DICT (iterator) = dict;
 645
 646   /* Loop through the symbols in the given bucket, breaking when SYM
 647      first matches.  If SYM never matches, it will be set to NULL;
 648      either way, we have the right return value.  */
 649
 650   for (sym = DICT_HASHED_BUCKET (dict, hash_index);
 651        sym != NULL;
 652        sym = sym->hash_next)
 653     {
 654       /* Warning: the order of arguments to compare matters!  */
 655       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 656         {
 657           break;
 658         }
 659
 660     }
 661
 662   DICT_ITERATOR_CURRENT (iterator) = sym;
 663   return sym;
 664 }
 665
 666 static struct symbol *
 667 iter_match_next_hashed (const char *name, symbol_compare_ftype *compare,
 668                         struct dict_iterator *iterator)
 669 {
 670   struct symbol *next;
 671
 672   for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 673        next != NULL;
 674        next = next->hash_next)
 675     {
 676       if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
 677         break;
 678     }
 679
 680   DICT_ITERATOR_CURRENT (iterator) = next;
 681
 682   return next;
 683 }
 684
 685 /* Insert SYM into DICT.  */
 686
 687 static void
 688 insert_symbol_hashed (struct dictionary *dict,
 689                       struct symbol *sym)
 690 {
 691   unsigned int hash_index;
 692   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 693
 694   hash_index =
 695     dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
 696   sym->hash_next = buckets[hash_index];
 697   buckets[hash_index] = sym;
 698 }
 699
 700 static int
 701 size_hashed (const struct dictionary *dict)
 702 {
 703   return DICT_HASHED_NBUCKETS (dict);
 704 }
 705
 706 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 707
 708 static void
 709 free_hashed_expandable (struct dictionary *dict)
 710 {
 711   xfree (DICT_HASHED_BUCKETS (dict));
 712   xfree (dict);
 713 }
 714
 715 static void
 716 add_symbol_hashed_expandable (struct dictionary *dict,
 717                               struct symbol *sym)
 718 {
 719   int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
 720
 721   if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
 722     expand_hashtable (dict);
 723
 724   insert_symbol_hashed (dict, sym);
 725   DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
 726 }
 727
 728 static int
 729 size_hashed_expandable (const struct dictionary *dict)
 730 {
 731   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
 732 }
 733
 734 static void
 735 expand_hashtable (struct dictionary *dict)
 736 {
 737   int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
 738   struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
 739   int new_nbuckets = 2 * old_nbuckets + 1;
 740   struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets);
 741   int i;
 742
 743   DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
 744   DICT_HASHED_BUCKETS (dict) = new_buckets;
 745
 746   for (i = 0; i < old_nbuckets; ++i)
 747     {
 748       struct symbol *sym, *next_sym;
 749
 750       sym = old_buckets[i];
 751       if (sym != NULL)
 752         {
 753           for (next_sym = sym->hash_next;
 754                next_sym != NULL;
 755                next_sym = sym->hash_next)
 756             {
 757               insert_symbol_hashed (dict, sym);
 758               sym = next_sym;
 759             }
 760
 761           insert_symbol_hashed (dict, sym);
 762         }
 763     }
 764
 765   xfree (old_buckets);
 766 }
 767
 768 /* Produce an unsigned hash value from STRING0 that is consistent
 769    with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
 770    That is, two identifiers equivalent according to any of those three
 771    comparison operators hash to the same value.  */
 772
 773 static unsigned int
 774 dict_hash (const char *string0)
 775 {
 776   /* The Ada-encoded version of a name P1.P2...Pn has either the form
 777      P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
 778      are lower-cased identifiers).  The <suffix> (which can be empty)
 779      encodes additional information about the denoted entity.  This
 780      routine hashes such names to msymbol_hash_iw(Pn).  It actually
 781      does this for a superset of both valid Pi and of <suffix>, but
 782      in other cases it simply returns msymbol_hash_iw(STRING0).  */
 783
 784   const char *string;
 785   unsigned int hash;
 786
 787   string = string0;
 788   if (*string == '_')
 789     {
 790       if (startswith (string, "_ada_"))
 791         string += 5;
 792       else
 793         return msymbol_hash_iw (string0);
 794     }
 795
 796   hash = 0;
 797   while (*string)
 798     {
 799       /* Ignore "TKB" suffixes.
 800
 801          These are used by Ada for subprograms implementing a task body.
 802          For instance for a task T inside package Pck, the name of the
 803          subprogram implementing T's body is `pck__tTKB'.  We need to
 804          ignore the "TKB" suffix because searches for this task body
 805          subprogram are going to be performed using `pck__t' (the encoded
 806          version of the natural name `pck.t').  */
 807       if (strcmp (string, "TKB") == 0)
 808         return hash;
 809
 810       switch (*string)
 811         {
 812         case '$':
 813         case '.':
 814         case 'X':
 815           if (string0 == string)
 816             return msymbol_hash_iw (string0);
 817           else
 818             return hash;
 819         case ' ':
 820         case '(':
 821           return msymbol_hash_iw (string0);
 822         case '_':
 823           if (string[1] == '_' && string != string0)
 824             {
 825               int c = string[2];
 826
 827               if ((c < 'a' || c > 'z') && c != 'O')
 828                 return hash;
 829               hash = 0;
 830               string += 2;
 831               break;
 832             }
 833           /* FALL THROUGH */
 834         default:
 835           hash = SYMBOL_HASH_NEXT (hash, *string);
 836           string += 1;
 837           break;
 838         }
 839     }
 840   return hash;
 841 }
 842
 843 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 844
 845 static struct symbol *
 846 iterator_first_linear (const struct dictionary *dict,
 847                        struct dict_iterator *iterator)
 848 {
 849   DICT_ITERATOR_DICT (iterator) = dict;
 850   DICT_ITERATOR_INDEX (iterator) = 0;
 851   return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
 852 }
 853
 854 static struct symbol *
 855 iterator_next_linear (struct dict_iterator *iterator)
 856 {
 857   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 858
 859   if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
 860     return NULL;
 861   else
 862     return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
 863 }
 864
 865 static struct symbol *
 866 iter_match_first_linear (const struct dictionary *dict,
 867                          const char *name, symbol_compare_ftype *compare,
 868                          struct dict_iterator *iterator)
 869 {
 870   DICT_ITERATOR_DICT (iterator) = dict;
 871   DICT_ITERATOR_INDEX (iterator) = -1;
 872
 873   return iter_match_next_linear (name, compare, iterator);
 874 }
 875
 876 static struct symbol *
 877 iter_match_next_linear (const char *name, symbol_compare_ftype *compare,
 878                         struct dict_iterator *iterator)
 879 {
 880   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 881   int i, nsyms = DICT_LINEAR_NSYMS (dict);
 882   struct symbol *sym, *retval = NULL;
 883
 884   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
 885     {
 886       sym = DICT_LINEAR_SYM (dict, i);
 887       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 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 }