contrib/gdb-7/gdb/dictionary.c

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