gdb/dictionary.c

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