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