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   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 582   struct symbol *next;
 583
 584   next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 585
 586   if (next == NULL)
 587     return iterator_hashed_advance (iterator);
 588   else
 589     {
 590       DICT_ITERATOR_CURRENT (iterator) = next;
 591       return next;
 592     }
 593 }
 594
 595 static struct symbol *
 596 iterator_hashed_advance (struct dict_iterator *iterator)
 597 {
 598   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 599   int nbuckets = DICT_HASHED_NBUCKETS (dict);
 600   int i;
 601
 602   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
 603     {
 604       struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
 605
 606       if (sym != NULL)
 607         {
 608           DICT_ITERATOR_INDEX (iterator) = i;
 609           DICT_ITERATOR_CURRENT (iterator) = sym;
 610           return sym;
 611         }
 612     }
 613
 614   return NULL;
 615 }
 616
 617 static struct symbol *
 618 iter_name_first_hashed (const struct dictionary *dict,
 619                         const char *name,
 620                         struct dict_iterator *iterator)
 621 {
 622   unsigned int hash_index
 623     = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
 624   struct symbol *sym;
 625
 626   DICT_ITERATOR_DICT (iterator) = dict;
 627
 628   /* Loop through the symbols in the given bucket, breaking when SYM
 629      first matches.  If SYM never matches, it will be set to NULL;
 630      either way, we have the right return value.  */
 631
 632   for (sym = DICT_HASHED_BUCKET (dict, hash_index);
 633        sym != NULL;
 634        sym = sym->hash_next)
 635     {
 636       /* Warning: the order of arguments to strcmp_iw matters!  */
 637       if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
 638         {
 639           break;
 640         }
 641
 642     }
 643
 644   DICT_ITERATOR_CURRENT (iterator) = sym;
 645   return sym;
 646 }
 647
 648 static struct symbol *
 649 iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
 650 {
 651   struct symbol *next;
 652
 653   for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
 654        next != NULL;
 655        next = next->hash_next)
 656     {
 657       if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
 658         break;
 659     }
 660
 661   DICT_ITERATOR_CURRENT (iterator) = next;
 662
 663   return next;
 664 }
 665
 666 /* Insert SYM into DICT.  */
 667
 668 static void
 669 insert_symbol_hashed (struct dictionary *dict,
 670                       struct symbol *sym)
 671 {
 672   unsigned int hash_index;
 673   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
 674
 675   hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
 676                 % DICT_HASHED_NBUCKETS (dict));
 677   sym->hash_next = buckets[hash_index];
 678   buckets[hash_index] = sym;
 679 }
 680
 681 static int
 682 size_hashed (const struct dictionary *dict)
 683 {
 684   return DICT_HASHED_NBUCKETS (dict);
 685 }
 686
 687 /* Functions only for DICT_HASHED_EXPANDABLE.  */
 688
 689 static void
 690 free_hashed_expandable (struct dictionary *dict)
 691 {
 692   xfree (DICT_HASHED_BUCKETS (dict));
 693   xfree (dict);
 694 }
 695
 696 static void
 697 add_symbol_hashed_expandable (struct dictionary *dict,
 698                               struct symbol *sym)
 699 {
 700   int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
 701
 702   if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
 703     expand_hashtable (dict);
 704
 705   insert_symbol_hashed (dict, sym);
 706   DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
 707 }
 708
 709 static int
 710 size_hashed_expandable (const struct dictionary *dict)
 711 {
 712   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
 713 }
 714
 715 static void
 716 expand_hashtable (struct dictionary *dict)
 717 {
 718   int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
 719   struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
 720   int new_nbuckets = 2*old_nbuckets + 1;
 721   struct symbol **new_buckets = xcalloc (new_nbuckets,
 722                                          sizeof (struct symbol *));
 723   int i;
 724
 725   DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
 726   DICT_HASHED_BUCKETS (dict) = new_buckets;
 727
 728   for (i = 0; i < old_nbuckets; ++i) {
 729     struct symbol *sym, *next_sym;
 730
 731     sym = old_buckets[i];
 732     if (sym != NULL) {
 733       for (next_sym = sym->hash_next;
 734            next_sym != NULL;
 735            next_sym = sym->hash_next) {
 736         insert_symbol_hashed (dict, sym);
 737         sym = next_sym;
 738       }
 739
 740       insert_symbol_hashed (dict, sym);
 741     }
 742   }
 743
 744   xfree (old_buckets);
 745 }
 746
 747 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
 748
 749 static struct symbol *
 750 iterator_first_linear (const struct dictionary *dict,
 751                        struct dict_iterator *iterator)
 752 {
 753   DICT_ITERATOR_DICT (iterator) = dict;
 754   DICT_ITERATOR_INDEX (iterator) = 0;
 755   return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
 756 }
 757
 758 static struct symbol *
 759 iterator_next_linear (struct dict_iterator *iterator)
 760 {
 761   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 762
 763   if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
 764     return NULL;
 765   else
 766     return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
 767 }
 768
 769 static struct symbol *
 770 iter_name_first_linear (const struct dictionary *dict,
 771                         const char *name,
 772                         struct dict_iterator *iterator)
 773 {
 774   DICT_ITERATOR_DICT (iterator) = dict;
 775   DICT_ITERATOR_INDEX (iterator) = -1;
 776
 777   return iter_name_next_linear (name, iterator);
 778 }
 779
 780 static struct symbol *
 781 iter_name_next_linear (const char *name, struct dict_iterator *iterator)
 782 {
 783   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
 784   int i, nsyms = DICT_LINEAR_NSYMS (dict);
 785   struct symbol *sym, *retval = NULL;
 786
 787   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
 788     {
 789       sym = DICT_LINEAR_SYM (dict, i);
 790       if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
 791         {
 792           retval = sym;
 793           break;
 794         }
 795     }
 796
 797   DICT_ITERATOR_INDEX (iterator) = i;
 798
 799   return retval;
 800 }
 801
 802 static int
 803 size_linear (const struct dictionary *dict)
 804 {
 805   return DICT_LINEAR_NSYMS (dict);
 806 }
 807
 808 /* Functions only for DICT_LINEAR_EXPANDABLE.  */
 809
 810 static void
 811 free_linear_expandable (struct dictionary *dict)
 812 {
 813   xfree (DICT_LINEAR_SYMS (dict));
 814   xfree (dict);
 815 }
 816
 817
 818 static void
 819 add_symbol_linear_expandable (struct dictionary *dict,
 820                               struct symbol *sym)
 821 {
 822   int nsyms = ++DICT_LINEAR_NSYMS (dict);
 823
 824   /* Do we have enough room?  If not, grow it.  */
 825   if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) {
 826     DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
 827     DICT_LINEAR_SYMS (dict)
 828       = xrealloc (DICT_LINEAR_SYMS (dict),
 829                   DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
 830                   * sizeof (struct symbol *));
 831   }
 832
 833   DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
 834 }