gdb/dictionary.c

   1 /* Routines for name->symbol lookups in GDB.
   2
   3    Copyright (C) 2003-2016 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_name_first (const struct dictionary *dict,
 534                       const char *name,
 535                       struct dict_iterator *iterator)
 536 {
 537   return dict_iter_match_first (dict, name, strcmp_iw, iterator);
 538 }
 539
 540 struct symbol *
 541 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
 542 {
 543   return dict_iter_match_next (name, strcmp_iw, iterator);
 544 }
 545
 546 struct symbol *
 547 dict_iter_match_first (const struct dictionary *dict,
 548                        const char *name, symbol_compare_ftype *compare,
 549                        struct dict_iterator *iterator)
 550 {
 551   return (DICT_VECTOR (dict))->iter_match_first (dict, name,
 552                                                  compare, iterator);
 553 }
 554
 555 struct symbol *
 556 dict_iter_match_next (const char *name, symbol_compare_ftype *compare,
 557                       struct dict_iterator *iterator)
 558 {
 559   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 560     ->iter_match_next (name, compare, iterator);
 561 }
 562
 563 int
 564 dict_size (const struct dictionary *dict)
 565 {
 566   return (DICT_VECTOR (dict))->size (dict);
 567 }
 568
 569 /* Now come functions (well, one function, currently) that are
 570    implemented generically by means of the vtable.  Typically, they're
 571    rarely used.  */
 572
 573 /* Test to see if DICT is empty.  */
 574
 575 int
 576 dict_empty (struct dictionary *dict)
 577 {
 578   struct dict_iterator iter;
 579
 580   return (dict_iterator_first (dict, &iter) == NULL);
 581 }
 582
 583
 584 /* The functions implementing the dictionary interface.  */
 585
 586 /* Generic functions, where appropriate.  */
 587
 588 static void
 589 free_obstack (struct dictionary *dict)
 590 {
 591   /* Do nothing!  */
 592 }
 593
 594 static void
 595 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
 596 {
 597   internal_error (__FILE__, __LINE__,
 598                   _("dict_add_symbol: non-expandable dictionary"));
 599 }
 600
 601 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE.  */
 602
 603 static struct symbol *
 604 iterator_first_hashed (const struct dictionary *dict,
 605                        struct dict_iterator *iterator)
 606 {
 607   DICT_ITERATOR_DICT (iterator) = dict;
 608   DICT_ITERATOR_INDEX (iterator) = -1;
 609   return iterator_hashed_advance (iterator);
 610 }
 611
 612 static struct symbol *
 613 iterator_next_hashed (struct dict_iterator *iterator)
 614 {
 615   struct symbol *next;
 616
 617   next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 618
 619   if (next == NULL)
 620     return iterator_hashed_advance (iterator);
 621   else
 622     {
 623       DICT_ITERATOR_CURRENT (iterator) = next;
 624       return next;
 625     }
 626 }
 627
 628 static struct symbol *
 629 iterator_hashed_advance (struct dict_iterator *iterator)
 630 {
 631   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 632   int nbuckets = DICT_HASHED_NBUCKETS (dict);
 633   int i;
 634
 635   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
 636     {
 637       struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
 638
 639       if (sym != NULL)
 640         {
 641           DICT_ITERATOR_INDEX (iterator) = i;
 642           DICT_ITERATOR_CURRENT (iterator) = sym;
 643           return sym;
 644         }
 645     }
 646
 647   return NULL;
 648 }
 649
 650 static struct symbol *
 651 iter_match_first_hashed (const struct dictionary *dict, const char *name,
 652                          symbol_compare_ftype *compare,
 653                          struct dict_iterator *iterator)
 654 {
 655   unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
 656   struct symbol *sym;
 657
 658   DICT_ITERATOR_DICT (iterator) = dict;
 659
 660   /* Loop through the symbols in the given bucket, breaking when SYM
 661      first matches.  If SYM never matches, it will be set to NULL;
 662      either way, we have the right return value.  */
 663
 664   for (sym = DICT_HASHED_BUCKET (dict, hash_index);
 665        sym != NULL;
 666        sym = sym->hash_next)
 667     {
 668       /* Warning: the order of arguments to compare matters!  */
 669       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 670         {
 671           break;
 672         }
 673
 674     }
 675
 676   DICT_ITERATOR_CURRENT (iterator) = sym;
 677   return sym;
 678 }
 679
 680 static struct symbol *
 681 iter_match_next_hashed (const char *name, symbol_compare_ftype *compare,
 682                         struct dict_iterator *iterator)
 683 {
 684   struct symbol *next;
 685
 686   for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 687        next != NULL;
 688        next = next->hash_next)
 689     {
 690       if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
 691         break;
 692     }
 693
 694   DICT_ITERATOR_CURRENT (iterator) = next;
 695
 696   return next;
 697 }
 698
 699 /* Insert SYM into DICT.  */
 700
 701 static void
 702 insert_symbol_hashed (struct dictionary *dict,
 703                       struct symbol *sym)
 704 {
 705   unsigned int hash_index;
 706   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 707
 708   hash_index =
 709     dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
 710   sym->hash_next = buckets[hash_index];
 711   buckets[hash_index] = sym;
 712 }
 713
 714 static int
 715 size_hashed (const struct dictionary *dict)
 716 {
 717   return DICT_HASHED_NBUCKETS (dict);
 718 }
 719
 720 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 721
 722 static void
 723 free_hashed_expandable (struct dictionary *dict)
 724 {
 725   xfree (DICT_HASHED_BUCKETS (dict));
 726   xfree (dict);
 727 }
 728
 729 static void
 730 add_symbol_hashed_expandable (struct dictionary *dict,
 731                               struct symbol *sym)
 732 {
 733   int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
 734
 735   if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
 736     expand_hashtable (dict);
 737
 738   insert_symbol_hashed (dict, sym);
 739   DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
 740 }
 741
 742 static int
 743 size_hashed_expandable (const struct dictionary *dict)
 744 {
 745   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
 746 }
 747
 748 static void
 749 expand_hashtable (struct dictionary *dict)
 750 {
 751   int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
 752   struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
 753   int new_nbuckets = 2 * old_nbuckets + 1;
 754   struct symbol **new_buckets = XCNEWVEC (struct symbol *, new_nbuckets);
 755   int i;
 756
 757   DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
 758   DICT_HASHED_BUCKETS (dict) = new_buckets;
 759
 760   for (i = 0; i < old_nbuckets; ++i)
 761     {
 762       struct symbol *sym, *next_sym;
 763
 764       sym = old_buckets[i];
 765       if (sym != NULL)
 766         {
 767           for (next_sym = sym->hash_next;
 768                next_sym != NULL;
 769                next_sym = sym->hash_next)
 770             {
 771               insert_symbol_hashed (dict, sym);
 772               sym = next_sym;
 773             }
 774
 775           insert_symbol_hashed (dict, sym);
 776         }
 777     }
 778
 779   xfree (old_buckets);
 780 }
 781
 782 /* Produce an unsigned hash value from STRING0 that is consistent
 783    with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
 784    That is, two identifiers equivalent according to any of those three
 785    comparison operators hash to the same value.  */
 786
 787 static unsigned int
 788 dict_hash (const char *string0)
 789 {
 790   /* The Ada-encoded version of a name P1.P2...Pn has either the form
 791      P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
 792      are lower-cased identifiers).  The <suffix> (which can be empty)
 793      encodes additional information about the denoted entity.  This
 794      routine hashes such names to msymbol_hash_iw(Pn).  It actually
 795      does this for a superset of both valid Pi and of <suffix>, but
 796      in other cases it simply returns msymbol_hash_iw(STRING0).  */
 797
 798   const char *string;
 799   unsigned int hash;
 800
 801   string = string0;
 802   if (*string == '_')
 803     {
 804       if (startswith (string, "_ada_"))
 805         string += 5;
 806       else
 807         return msymbol_hash_iw (string0);
 808     }
 809
 810   hash = 0;
 811   while (*string)
 812     {
 813       /* Ignore "TKB" suffixes.
 814
 815          These are used by Ada for subprograms implementing a task body.
 816          For instance for a task T inside package Pck, the name of the
 817          subprogram implementing T's body is `pck__tTKB'.  We need to
 818          ignore the "TKB" suffix because searches for this task body
 819          subprogram are going to be performed using `pck__t' (the encoded
 820          version of the natural name `pck.t').  */
 821       if (strcmp (string, "TKB") == 0)
 822         return hash;
 823
 824       switch (*string)
 825         {
 826         case '$':
 827         case '.':
 828         case 'X':
 829           if (string0 == string)
 830             return msymbol_hash_iw (string0);
 831           else
 832             return hash;
 833         case ' ':
 834         case '(':
 835           return msymbol_hash_iw (string0);
 836         case '_':
 837           if (string[1] == '_' && string != string0)
 838             {
 839               int c = string[2];
 840
 841               if ((c < 'a' || c > 'z') && c != 'O')
 842                 return hash;
 843               hash = 0;
 844               string += 2;
 845               break;
 846             }
 847           /* FALL THROUGH */
 848         default:
 849           hash = SYMBOL_HASH_NEXT (hash, *string);
 850           string += 1;
 851           break;
 852         }
 853     }
 854   return hash;
 855 }
 856
 857 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 858
 859 static struct symbol *
 860 iterator_first_linear (const struct dictionary *dict,
 861                        struct dict_iterator *iterator)
 862 {
 863   DICT_ITERATOR_DICT (iterator) = dict;
 864   DICT_ITERATOR_INDEX (iterator) = 0;
 865   return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
 866 }
 867
 868 static struct symbol *
 869 iterator_next_linear (struct dict_iterator *iterator)
 870 {
 871   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 872
 873   if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
 874     return NULL;
 875   else
 876     return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
 877 }
 878
 879 static struct symbol *
 880 iter_match_first_linear (const struct dictionary *dict,
 881                          const char *name, symbol_compare_ftype *compare,
 882                          struct dict_iterator *iterator)
 883 {
 884   DICT_ITERATOR_DICT (iterator) = dict;
 885   DICT_ITERATOR_INDEX (iterator) = -1;
 886
 887   return iter_match_next_linear (name, compare, iterator);
 888 }
 889
 890 static struct symbol *
 891 iter_match_next_linear (const char *name, symbol_compare_ftype *compare,
 892                         struct dict_iterator *iterator)
 893 {
 894   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 895   int i, nsyms = DICT_LINEAR_NSYMS (dict);
 896   struct symbol *sym, *retval = NULL;
 897
 898   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
 899     {
 900       sym = DICT_LINEAR_SYM (dict, i);
 901       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
 902         {
 903           retval = sym;
 904           break;
 905         }
 906     }
 907
 908   DICT_ITERATOR_INDEX (iterator) = i;
 909
 910   return retval;
 911 }
 912
 913 static int
 914 size_linear (const struct dictionary *dict)
 915 {
 916   return DICT_LINEAR_NSYMS (dict);
 917 }
 918
 919 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 920
 921 static void
 922 free_linear_expandable (struct dictionary *dict)
 923 {
 924   xfree (DICT_LINEAR_SYMS (dict));
 925   xfree (dict);
 926 }
 927
 928
 929 static void
 930 add_symbol_linear_expandable (struct dictionary *dict,
 931                               struct symbol *sym)
 932 {
 933   int nsyms = ++DICT_LINEAR_NSYMS (dict);
 934
 935   /* Do we have enough room?  If not, grow it.  */
 936   if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
 937     {
 938       DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
 939       DICT_LINEAR_SYMS (dict)
 940         = XRESIZEVEC (struct symbol *, DICT_LINEAR_SYMS (dict),
 941                       DICT_LINEAR_EXPANDABLE_CAPACITY (dict));
 942     }
 943
 944   DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
 945 }