gdb/dictionary.c

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