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