gdb/dictionary.c

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