contrib/gdb-7/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 "gdb_obstack.h"
  25 #include "symtab.h"
  26 #include "buildsym.h"
  27 #include "gdb_assert.h"
  28 #include "dictionary.h"
  29
  30 /* This file implements dictionaries, which are tables that associate
  31    symbols to names.  They are represented by an opaque type 'struct
  32    dictionary'.  That type has various internal implementations, which
  33    you can choose between depending on what properties you need
  34    (e.g. fast lookup, order-preserving, expandable).
  35
  36    Each dictionary starts with a 'virtual function table' that
  37    contains the functions that actually implement the various
  38    operations that dictionaries provide.  (Note, however, that, for
  39    the sake of client code, we also provide some functions that can be
  40    implemented generically in terms of the functions in the vtable.)
  41
  42    To add a new dictionary implementation <impl>, what you should do
  43    is:
  44
  45    * Add a new element DICT_<IMPL> to dict_type.
  46
  47    * Create a new structure dictionary_<impl>.  If your new
  48    implementation is a variant of an existing one, make sure that
  49    their structs have the same initial data members.  Define accessor
  50    macros for your new data members.
  51
  52    * Implement all the functions in dict_vector as static functions,
  53    whose name is the same as the corresponding member of dict_vector
  54    plus _<impl>.  You don't have to do this for those members where
  55    you can reuse existing generic functions
  56    (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
  57    your new implementation is a variant of an existing implementation
  58    and where the variant doesn't affect the member function in
  59    question.
  60
  61    * Define a static const struct dict_vector dict_<impl>_vector.
  62
  63    * Define a function dict_create_<impl> to create these
  64    gizmos.  Add its declaration to dictionary.h.
  65
  66    To add a new operation <op> on all existing implementations, what
  67    you should do is:
  68
  69    * Add a new member <op> to struct dict_vector.
  70
  71    * If there is useful generic behavior <op>, define a static
  72    function <op>_something_informative that implements that behavior.
  73    (E.g. add_symbol_nonexpandable, free_obstack.)
  74
  75    * For every implementation <impl> that should have its own specific
  76    behavior for <op>, define a static function <op>_<impl>
  77    implementing it.
  78
  79    * Modify all existing dict_vector_<impl>'s to include the appropriate
  80    member.
  81
  82    * Define a function dict_<op> that looks up <op> in the dict_vector
  83    and calls the appropriate function.  Add a declaration for
  84    dict_<op> to dictionary.h.
  85
  86 */
  87
  88 /* An enum representing the various implementations of dictionaries.
  89    Used only for debugging.  */
  90
  91 enum dict_type
  92   {
  93     /* Symbols are stored in a fixed-size hash table.  */
  94     DICT_HASHED,
  95     /* Symbols are stored in an expandable hash table.  */
  96     DICT_HASHED_EXPANDABLE,
  97     /* Symbols are stored in a fixed-size array.  */
  98     DICT_LINEAR,
  99     /* Symbols are stored in an expandable array.  */
 100     DICT_LINEAR_EXPANDABLE
 101   };
 102
 103 /* The virtual function table.  */
 104
 105 struct dict_vector
 106 {
 107   /* The type of the dictionary.  This is only here to make debugging
 108      a bit easier; it's not actually used.  */
 109   enum dict_type type;
 110   /* The function to free a dictionary.  */
 111   void (*free) (struct dictionary *dict);
 112   /* Add a symbol to a dictionary, if possible.  */
 113   void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
 114   /* Iterator functions.  */
 115   struct symbol *(*iterator_first) (const struct dictionary *dict,
 116                                     struct dict_iterator *iterator);
 117   struct symbol *(*iterator_next) (struct dict_iterator *iterator);
 118   /* Functions to iterate over symbols with a given name.  */
 119   struct symbol *(*iter_name_first) (const struct dictionary *dict,
 120                                      const char *name,
 121                                      struct dict_iterator *iterator);
 122   struct symbol *(*iter_name_next) (const char *name,
 123                                     struct dict_iterator *iterator);
 124   /* A size function, for maint print symtabs.  */
 125   int (*size) (const struct dictionary *dict);
 126 };
 127
 128 /* Now comes the structs used to store the data for different
 129    implementations.  If two implementations have data in common, put
 130    the common data at the top of their structs, ordered in the same
 131    way.  */
 132
 133 struct dictionary_hashed
 134 {
 135   int nbuckets;
 136   struct symbol **buckets;
 137 };
 138
 139 struct dictionary_hashed_expandable
 140 {
 141   /* How many buckets we currently have.  */
 142   int nbuckets;
 143   struct symbol **buckets;
 144   /* How many syms we currently have; we need this so we will know
 145      when to add more buckets.  */
 146   int nsyms;
 147 };
 148
 149 struct dictionary_linear
 150 {
 151   int nsyms;
 152   struct symbol **syms;
 153 };
 154
 155 struct dictionary_linear_expandable
 156 {
 157   /* How many symbols we currently have.  */
 158   int nsyms;
 159   struct symbol **syms;
 160   /* How many symbols we can store before needing to reallocate.  */
 161   int capacity;
 162 };
 163
 164 /* And now, the star of our show.  */
 165
 166 struct dictionary
 167 {
 168   const struct dict_vector *vector;
 169   union
 170   {
 171     struct dictionary_hashed hashed;
 172     struct dictionary_hashed_expandable hashed_expandable;
 173     struct dictionary_linear linear;
 174     struct dictionary_linear_expandable linear_expandable;
 175   }
 176   data;
 177 };
 178
 179 /* Accessor macros.  */
 180
 181 #define DICT_VECTOR(d)                  (d)->vector
 182
 183 /* These can be used for DICT_HASHED_EXPANDABLE, too.  */
 184
 185 #define DICT_HASHED_NBUCKETS(d)         (d)->data.hashed.nbuckets
 186 #define DICT_HASHED_BUCKETS(d)          (d)->data.hashed.buckets
 187 #define DICT_HASHED_BUCKET(d,i)         DICT_HASHED_BUCKETS (d) [i]
 188
 189 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
 190
 191 /* These can be used for DICT_LINEAR_EXPANDABLEs, too.  */
 192
 193 #define DICT_LINEAR_NSYMS(d)            (d)->data.linear.nsyms
 194 #define DICT_LINEAR_SYMS(d)             (d)->data.linear.syms
 195 #define DICT_LINEAR_SYM(d,i)            DICT_LINEAR_SYMS (d) [i]
 196
 197 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
 198                 (d)->data.linear_expandable.capacity
 199
 200 /* The initial size of a DICT_*_EXPANDABLE dictionary.  */
 201
 202 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
 203
 204 /* This calculates the number of buckets we'll use in a hashtable,
 205    given the number of symbols that it will contain.  */
 206
 207 #define DICT_HASHTABLE_SIZE(n)  ((n)/5 + 1)
 208
 209 /* Accessor macros for dict_iterators; they're here rather than
 210    dictionary.h because code elsewhere should treat dict_iterators as
 211    opaque.  */
 212
 213 /* The dictionary that the iterator is associated to.  */
 214 #define DICT_ITERATOR_DICT(iter)                (iter)->dict
 215 /* For linear dictionaries, the index of the last symbol returned; for
 216    hashed dictionaries, the bucket of the last symbol returned.  */
 217 #define DICT_ITERATOR_INDEX(iter)               (iter)->index
 218 /* For hashed dictionaries, this points to the last symbol returned;
 219    otherwise, this is unused.  */
 220 #define DICT_ITERATOR_CURRENT(iter)             (iter)->current
 221
 222 /* Declarations of functions for vectors.  */
 223
 224 /* Functions that might work across a range of dictionary types.  */
 225
 226 static void add_symbol_nonexpandable (struct dictionary *dict,
 227                                       struct symbol *sym);
 228
 229 static void free_obstack (struct dictionary *dict);
 230
 231 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
 232    dictionaries.  */
 233
 234 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
 235                                              struct dict_iterator *iterator);
 236
 237 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
 238
 239 static struct symbol *iter_name_first_hashed (const struct dictionary *dict,
 240                                               const char *name,
 241                                               struct dict_iterator *iterator);
 242
 243 static struct symbol *iter_name_next_hashed (const char *name,
 244                                              struct dict_iterator *iterator);
 245
 246 /* Functions only for DICT_HASHED.  */
 247
 248 static int size_hashed (const struct dictionary *dict);
 249
 250 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 251
 252 static void free_hashed_expandable (struct dictionary *dict);
 253
 254 static void add_symbol_hashed_expandable (struct dictionary *dict,
 255                                           struct symbol *sym);
 256
 257 static int size_hashed_expandable (const struct dictionary *dict);
 258
 259 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
 260    dictionaries.  */
 261
 262 static struct symbol *iterator_first_linear (const struct dictionary *dict,
 263                                              struct dict_iterator *iterator);
 264
 265 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
 266
 267 static struct symbol *iter_name_first_linear (const struct dictionary *dict,
 268                                               const char *name,
 269                                               struct dict_iterator *iterator);
 270
 271 static struct symbol *iter_name_next_linear (const char *name,
 272                                              struct dict_iterator *iterator);
 273
 274 static int size_linear (const struct dictionary *dict);
 275
 276 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 277
 278 static void free_linear_expandable (struct dictionary *dict);
 279
 280 static void add_symbol_linear_expandable (struct dictionary *dict,
 281                                           struct symbol *sym);
 282
 283 /* Various vectors that we'll actually use.  */
 284
 285 static const struct dict_vector dict_hashed_vector =
 286   {
 287     DICT_HASHED,                        /* type */
 288     free_obstack,                       /* free */
 289     add_symbol_nonexpandable,           /* add_symbol */
 290     iterator_first_hashed,              /* iterator_first */
 291     iterator_next_hashed,               /* iterator_next */
 292     iter_name_first_hashed,             /* iter_name_first */
 293     iter_name_next_hashed,              /* iter_name_next */
 294     size_hashed,                        /* size */
 295   };
 296
 297 static const struct dict_vector dict_hashed_expandable_vector =
 298   {
 299     DICT_HASHED_EXPANDABLE,             /* type */
 300     free_hashed_expandable,             /* free */
 301     add_symbol_hashed_expandable,       /* add_symbol */
 302     iterator_first_hashed,              /* iterator_first */
 303     iterator_next_hashed,               /* iterator_next */
 304     iter_name_first_hashed,             /* iter_name_first */
 305     iter_name_next_hashed,              /* iter_name_next */
 306     size_hashed_expandable,             /* size */
 307   };
 308
 309 static const struct dict_vector dict_linear_vector =
 310   {
 311     DICT_LINEAR,                        /* type */
 312     free_obstack,                       /* free */
 313     add_symbol_nonexpandable,           /* add_symbol */
 314     iterator_first_linear,              /* iterator_first */
 315     iterator_next_linear,               /* iterator_next */
 316     iter_name_first_linear,             /* iter_name_first */
 317     iter_name_next_linear,              /* iter_name_next */
 318     size_linear,                        /* size */
 319   };
 320
 321 static const struct dict_vector dict_linear_expandable_vector =
 322   {
 323     DICT_LINEAR_EXPANDABLE,             /* type */
 324     free_linear_expandable,             /* free */
 325     add_symbol_linear_expandable,       /* add_symbol */
 326     iterator_first_linear,              /* iterator_first */
 327     iterator_next_linear,               /* iterator_next */
 328     iter_name_first_linear,             /* iter_name_first */
 329     iter_name_next_linear,              /* iter_name_next */
 330     size_linear,                        /* size */
 331   };
 332
 333 /* Declarations of helper functions (i.e. ones that don't go into
 334    vectors).  */
 335
 336 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
 337
 338 static void insert_symbol_hashed (struct dictionary *dict,
 339                                   struct symbol *sym);
 340
 341 static void expand_hashtable (struct dictionary *dict);
 342
 343 /* The creation functions.  */
 344
 345 /* Create a dictionary implemented via a fixed-size hashtable.  All
 346    memory it uses is allocated on OBSTACK; the environment is
 347    initialized from SYMBOL_LIST.  */
 348
 349 struct dictionary *
 350 dict_create_hashed (struct obstack *obstack,
 351                     const struct pending *symbol_list)
 352 {
 353   struct dictionary *retval;
 354   int nsyms = 0, nbuckets, i;
 355   struct symbol **buckets;
 356   const struct pending *list_counter;
 357
 358   retval = obstack_alloc (obstack, sizeof (struct dictionary));
 359   DICT_VECTOR (retval) = &dict_hashed_vector;
 360
 361   /* Calculate the number of symbols, and allocate space for them.  */
 362   for (list_counter = symbol_list;
 363        list_counter != NULL;
 364        list_counter = list_counter->next)
 365     {
 366       nsyms += list_counter->nsyms;
 367     }
 368   nbuckets = DICT_HASHTABLE_SIZE (nsyms);
 369   DICT_HASHED_NBUCKETS (retval) = nbuckets;
 370   buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
 371   memset (buckets, 0, nbuckets * sizeof (struct symbol *));
 372   DICT_HASHED_BUCKETS (retval) = buckets;
 373
 374   /* Now fill the buckets.  */
 375   for (list_counter = symbol_list;
 376        list_counter != NULL;
 377        list_counter = list_counter->next)
 378     {
 379       for (i = list_counter->nsyms - 1; i >= 0; --i)
 380         {
 381           insert_symbol_hashed (retval, list_counter->symbol[i]);
 382         }
 383     }
 384
 385   return retval;
 386 }
 387
 388 /* Create a dictionary implemented via a hashtable that grows as
 389    necessary.  The dictionary is initially empty; to add symbols to
 390    it, call dict_add_symbol().  Call dict_free() when you're done with
 391    it.  */
 392
 393 extern struct dictionary *
 394 dict_create_hashed_expandable (void)
 395 {
 396   struct dictionary *retval;
 397
 398   retval = xmalloc (sizeof (struct dictionary));
 399   DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
 400   DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
 401   DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
 402                                           sizeof (struct symbol *));
 403   DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
 404
 405   return retval;
 406 }
 407
 408 /* Create a dictionary implemented via a fixed-size array.  All memory
 409    it uses is allocated on OBSTACK; the environment is initialized
 410    from the SYMBOL_LIST.  The symbols are ordered in the same order
 411    that they're found in SYMBOL_LIST.  */
 412
 413 struct dictionary *
 414 dict_create_linear (struct obstack *obstack,
 415                     const struct pending *symbol_list)
 416 {
 417   struct dictionary *retval;
 418   int nsyms = 0, i, j;
 419   struct symbol **syms;
 420   const struct pending *list_counter;
 421
 422   retval = obstack_alloc (obstack, sizeof (struct dictionary));
 423   DICT_VECTOR (retval) = &dict_linear_vector;
 424
 425   /* Calculate the number of symbols, and allocate space for them.  */
 426   for (list_counter = symbol_list;
 427        list_counter != NULL;
 428        list_counter = list_counter->next)
 429     {
 430       nsyms += list_counter->nsyms;
 431     }
 432   DICT_LINEAR_NSYMS (retval) = nsyms;
 433   syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
 434   DICT_LINEAR_SYMS (retval) = syms;
 435
 436   /* Now fill in the symbols.  Start filling in from the back, so as
 437      to preserve the original order of the symbols.  */
 438   for (list_counter = symbol_list, j = nsyms - 1;
 439        list_counter != NULL;
 440        list_counter = list_counter->next)
 441     {
 442       for (i = list_counter->nsyms - 1;
 443            i >= 0;
 444            --i, --j)
 445         {
 446           syms[j] = list_counter->symbol[i];
 447         }
 448     }
 449
 450   return retval;
 451 }
 452
 453 /* Create a dictionary implemented via an array that grows as
 454    necessary.  The dictionary is initially empty; to add symbols to
 455    it, call dict_add_symbol().  Call dict_free() when you're done with
 456    it.  */
 457
 458 struct dictionary *
 459 dict_create_linear_expandable (void)
 460 {
 461   struct dictionary *retval;
 462
 463   retval = xmalloc (sizeof (struct dictionary));
 464   DICT_VECTOR (retval) = &dict_linear_expandable_vector;
 465   DICT_LINEAR_NSYMS (retval) = 0;
 466   DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
 467     = DICT_EXPANDABLE_INITIAL_CAPACITY;
 468   DICT_LINEAR_SYMS (retval)
 469     = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
 470                * sizeof (struct symbol *));
 471
 472   return retval;
 473 }
 474
 475 /* The functions providing the dictionary interface.  */
 476
 477 /* Free the memory used by a dictionary that's not on an obstack.  (If
 478    any.)  */
 479
 480 void
 481 dict_free (struct dictionary *dict)
 482 {
 483   (DICT_VECTOR (dict))->free (dict);
 484 }
 485
 486 /* Add SYM to DICT.  DICT had better be expandable.  */
 487
 488 void
 489 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
 490 {
 491   (DICT_VECTOR (dict))->add_symbol (dict, sym);
 492 }
 493
 494 /* Initialize ITERATOR to point at the first symbol in DICT, and
 495    return that first symbol, or NULL if DICT is empty.  */
 496
 497 struct symbol *
 498 dict_iterator_first (const struct dictionary *dict,
 499                      struct dict_iterator *iterator)
 500 {
 501   return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
 502 }
 503
 504 /* Advance ITERATOR, and return the next symbol, or NULL if there are
 505    no more symbols.  */
 506
 507 struct symbol *
 508 dict_iterator_next (struct dict_iterator *iterator)
 509 {
 510   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 511     ->iterator_next (iterator);
 512 }
 513
 514 struct symbol *
 515 dict_iter_name_first (const struct dictionary *dict,
 516                       const char *name,
 517                       struct dict_iterator *iterator)
 518 {
 519   return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
 520 }
 521
 522 struct symbol *
 523 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
 524 {
 525   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
 526     ->iter_name_next (name, iterator);
 527 }
 528
 529 int
 530 dict_size (const struct dictionary *dict)
 531 {
 532   return (DICT_VECTOR (dict))->size (dict);
 533 }
 534
 535 /* Now come functions (well, one function, currently) that are
 536    implemented generically by means of the vtable.  Typically, they're
 537    rarely used.  */
 538
 539 /* Test to see if DICT is empty.  */
 540
 541 int
 542 dict_empty (struct dictionary *dict)
 543 {
 544   struct dict_iterator iter;
 545
 546   return (dict_iterator_first (dict, &iter) == NULL);
 547 }
 548
 549
 550 /* The functions implementing the dictionary interface.  */
 551
 552 /* Generic functions, where appropriate.  */
 553
 554 static void
 555 free_obstack (struct dictionary *dict)
 556 {
 557   /* Do nothing!  */
 558 }
 559
 560 static void
 561 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
 562 {
 563   internal_error (__FILE__, __LINE__,
 564                   _("dict_add_symbol: non-expandable dictionary"));
 565 }
 566
 567 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE.  */
 568
 569 static struct symbol *
 570 iterator_first_hashed (const struct dictionary *dict,
 571                        struct dict_iterator *iterator)
 572 {
 573   DICT_ITERATOR_DICT (iterator) = dict;
 574   DICT_ITERATOR_INDEX (iterator) = -1;
 575   return iterator_hashed_advance (iterator);
 576 }
 577
 578 static struct symbol *
 579 iterator_next_hashed (struct dict_iterator *iterator)
 580 {
 581   struct symbol *next;
 582
 583   next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 584
 585   if (next == NULL)
 586     return iterator_hashed_advance (iterator);
 587   else
 588     {
 589       DICT_ITERATOR_CURRENT (iterator) = next;
 590       return next;
 591     }
 592 }
 593
 594 static struct symbol *
 595 iterator_hashed_advance (struct dict_iterator *iterator)
 596 {
 597   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 598   int nbuckets = DICT_HASHED_NBUCKETS (dict);
 599   int i;
 600
 601   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
 602     {
 603       struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
 604
 605       if (sym != NULL)
 606         {
 607           DICT_ITERATOR_INDEX (iterator) = i;
 608           DICT_ITERATOR_CURRENT (iterator) = sym;
 609           return sym;
 610         }
 611     }
 612
 613   return NULL;
 614 }
 615
 616 static struct symbol *
 617 iter_name_first_hashed (const struct dictionary *dict,
 618                         const char *name,
 619                         struct dict_iterator *iterator)
 620 {
 621   unsigned int hash_index
 622     = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
 623   struct symbol *sym;
 624
 625   DICT_ITERATOR_DICT (iterator) = dict;
 626
 627   /* Loop through the symbols in the given bucket, breaking when SYM
 628      first matches.  If SYM never matches, it will be set to NULL;
 629      either way, we have the right return value.  */
 630
 631   for (sym = DICT_HASHED_BUCKET (dict, hash_index);
 632        sym != NULL;
 633        sym = sym->hash_next)
 634     {
 635       /* Warning: the order of arguments to strcmp_iw matters!  */
 636       if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
 637         {
 638           break;
 639         }
 640
 641     }
 642
 643   DICT_ITERATOR_CURRENT (iterator) = sym;
 644   return sym;
 645 }
 646
 647 static struct symbol *
 648 iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
 649 {
 650   struct symbol *next;
 651
 652   for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 653        next != NULL;
 654        next = next->hash_next)
 655     {
 656       if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
 657         break;
 658     }
 659
 660   DICT_ITERATOR_CURRENT (iterator) = next;
 661
 662   return next;
 663 }
 664
 665 /* Insert SYM into DICT.  */
 666
 667 static void
 668 insert_symbol_hashed (struct dictionary *dict,
 669                       struct symbol *sym)
 670 {
 671   unsigned int hash_index;
 672   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 673
 674   hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
 675                 % DICT_HASHED_NBUCKETS (dict));
 676   sym->hash_next = buckets[hash_index];
 677   buckets[hash_index] = sym;
 678 }
 679
 680 static int
 681 size_hashed (const struct dictionary *dict)
 682 {
 683   return DICT_HASHED_NBUCKETS (dict);
 684 }
 685
 686 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 687
 688 static void
 689 free_hashed_expandable (struct dictionary *dict)
 690 {
 691   xfree (DICT_HASHED_BUCKETS (dict));
 692   xfree (dict);
 693 }
 694
 695 static void
 696 add_symbol_hashed_expandable (struct dictionary *dict,
 697                               struct symbol *sym)
 698 {
 699   int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
 700
 701   if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
 702     expand_hashtable (dict);
 703
 704   insert_symbol_hashed (dict, sym);
 705   DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
 706 }
 707
 708 static int
 709 size_hashed_expandable (const struct dictionary *dict)
 710 {
 711   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
 712 }
 713
 714 static void
 715 expand_hashtable (struct dictionary *dict)
 716 {
 717   int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
 718   struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
 719   int new_nbuckets = 2*old_nbuckets + 1;
 720   struct symbol **new_buckets = xcalloc (new_nbuckets,
 721                                          sizeof (struct symbol *));
 722   int i;
 723
 724   DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
 725   DICT_HASHED_BUCKETS (dict) = new_buckets;
 726
 727   for (i = 0; i < old_nbuckets; ++i)
 728     {
 729       struct symbol *sym, *next_sym;
 730
 731       sym = old_buckets[i];
 732       if (sym != NULL)
 733         {
 734           for (next_sym = sym->hash_next;
 735                next_sym != NULL;
 736                next_sym = sym->hash_next)
 737             {
 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     {
 829       DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
 830       DICT_LINEAR_SYMS (dict)
 831         = xrealloc (DICT_LINEAR_SYMS (dict),
 832                     DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
 833                     * sizeof (struct symbol *));
 834     }
 835
 836   DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
 837 }