gdb/dictionary.c - gdb

Global variables defined

Data types defined

Functions defined

Macros defined

Source code

  1. /* Routines for name->symbol lookups in GDB.

  3.    Copyright (C) 2003-2015 Free Software Foundation, Inc.

  5.    Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
  6.    Inc.

  8.    This file is part of GDB.

  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.

  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.

  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/>.  */

  23. #include "defs.h"
  24. #include <ctype.h>
  25. #include "gdb_obstack.h"
  26. #include "symtab.h"
  27. #include "buildsym.h"
  28. #include "dictionary.h"

  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).

  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.)

  42.    To add a new dictionary implementation <impl>, what you should do
  43.    is:

  45.    * Add a new element DICT_<IMPL> to dict_type.

  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.

  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.

  61.    * Define a static const struct dict_vector dict_<impl>_vector.

  63.    * Define a function dict_create_<impl> to create these
  64.    gizmos.  Add its declaration to dictionary.h.

  66.    To add a new operation <op> on all existing implementations, what
  67.    you should do is:

  69.    * Add a new member <op> to struct dict_vector.

  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.)

  75.    * For every implementation <impl> that should have its own specific
  76.    behavior for <op>, define a static function <op>_<impl>
  77.    implementing it.

  79.    * Modify all existing dict_vector_<impl>'s to include the appropriate
  80.    member.

  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.  */

  86. /* An enum representing the various implementations of dictionaries.
  87.    Used only for debugging.  */

  89. ‌enum dict_type
  90.   {
  91.     /* Symbols are stored in a fixed-size hash table.  */
  92.     DICT_HASHED,
  93.     /* Symbols are stored in an expandable hash table.  */
  94.     DICT_HASHED_EXPANDABLE,
  95.     /* Symbols are stored in a fixed-size array.  */
  96.     DICT_LINEAR,
  97.     /* Symbols are stored in an expandable array.  */
  98.     DICT_LINEAR_EXPANDABLE
  99.   };

  101. /* The virtual function table.  */

  103. ‌struct dict_vector
  104. {
  105.   /* The type of the dictionary.  This is only here to make debugging
  106.      a bit easier; it's not actually used.  */
  107.   enum dict_type type;
  108.   /* The function to free a dictionary.  */
  109.   void (*free) (struct dictionary *dict);
  110.   /* Add a symbol to a dictionary, if possible.  */
  111.   void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
  112.   /* Iterator functions.  */
  113.   struct symbol *(*iterator_first) (const struct dictionary *dict,
  114.                                     struct dict_iterator *iterator);
  115.   struct symbol *(*iterator_next) (struct dict_iterator *iterator);
  116.   /* Functions to iterate over symbols with a given name.  */
  117.   struct symbol *(*iter_match_first) (const struct dictionary *dict,
  118.                                       const char *name,
  119.                                       symbol_compare_ftype *equiv,
  120.                                       struct dict_iterator *iterator);
  121.   struct symbol *(*iter_match_next) (const char *name,
  122.                                      symbol_compare_ftype *equiv,
  123.                                      struct dict_iterator *iterator);
  124.   /* A size function, for maint print symtabs.  */
  125.   int (*size) (const struct dictionary *dict);
  126. };

  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.  */

  133. ‌struct dictionary_hashed
  134. {
  135.   int nbuckets;
  136.   struct symbol **buckets;
  137. };

  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. };

  149. ‌struct dictionary_linear
  150. {
  151.   int nsyms;
  152.   struct symbol **syms;
  153. };

  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. };

  164. /* And now, the star of our show.  */

  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. };

  179. /* Accessor macros.  */

  181. ‌#define DICT_VECTOR(d)                        (d)->vector

  183. /* These can be used for DICT_HASHED_EXPANDABLE, too.  */

  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]

  189. ‌#define DICT_HASHED_EXPANDABLE_NSYMS(d)        (d)->data.hashed_expandable.nsyms

  191. /* These can be used for DICT_LINEAR_EXPANDABLEs, too.  */

  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]

  197. ‌#define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
  198.                 (d)->data.linear_expandable.capacity

  200. /* The initial size of a DICT_*_EXPANDABLE dictionary.  */

  202. ‌#define DICT_EXPANDABLE_INITIAL_CAPACITY 10

  204. /* This calculates the number of buckets we'll use in a hashtable,
  205.    given the number of symbols that it will contain.  */

  207. ‌#define DICT_HASHTABLE_SIZE(n)        ((n)/5 + 1)

  209. /* Accessor macros for dict_iterators; they're here rather than
  210.    dictionary.h because code elsewhere should treat dict_iterators as
  211.    opaque.  */

  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

  222. /* Declarations of functions for vectors.  */

  224. /* Functions that might work across a range of dictionary types.  */

  226. static void add_symbol_nonexpandable (struct dictionary *dict,
  227.                                       struct symbol *sym);

  229. static void free_obstack (struct dictionary *dict);

  231. /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
  232.    dictionaries.  */

  234. static struct symbol *iterator_first_hashed (const struct dictionary *dict,
  235.                                              struct dict_iterator *iterator);

  237. static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);

  239. static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
  240.                                                const char *name,
  241.                                                symbol_compare_ftype *compare,
  242.                                               struct dict_iterator *iterator);

  244. static struct symbol *iter_match_next_hashed (const char *name,
  245.                                               symbol_compare_ftype *compare,
  246.                                               struct dict_iterator *iterator);

  248. static unsigned int dict_hash (const char *string);

  250. /* Functions only for DICT_HASHED.  */

  252. static int size_hashed (const struct dictionary *dict);

  254. /* Functions only for DICT_HASHED_EXPANDABLE.  */

  256. static void free_hashed_expandable (struct dictionary *dict);

  258. static void add_symbol_hashed_expandable (struct dictionary *dict,
  259.                                           struct symbol *sym);

  261. static int size_hashed_expandable (const struct dictionary *dict);

  263. /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
  264.    dictionaries.  */

  266. static struct symbol *iterator_first_linear (const struct dictionary *dict,
  267.                                              struct dict_iterator *iterator);

  269. static struct symbol *iterator_next_linear (struct dict_iterator *iterator);

  271. static struct symbol *iter_match_first_linear (const struct dictionary *dict,
  272.                                                const char *name,
  273.                                                symbol_compare_ftype *compare,
  274.                                                struct dict_iterator *iterator);

  276. static struct symbol *iter_match_next_linear (const char *name,
  277.                                               symbol_compare_ftype *compare,
  278.                                               struct dict_iterator *iterator);

  280. static int size_linear (const struct dictionary *dict);

  282. /* Functions only for DICT_LINEAR_EXPANDABLE.  */

  284. static void free_linear_expandable (struct dictionary *dict);

  286. static void add_symbol_linear_expandable (struct dictionary *dict,
  287.                                           struct symbol *sym);

  289. /* Various vectors that we'll actually use.  */

  291. ‌static const struct dict_vector dict_hashed_vector =
  292.   {
  293.     DICT_HASHED,                        /* type */
  294.     free_obstack,                        /* free */
  295.     add_symbol_nonexpandable,                /* add_symbol */
  296.     iterator_first_hashed,                /* iterator_first */
  297.     iterator_next_hashed,                /* iterator_next */
  298.     iter_match_first_hashed,                /* iter_name_first */
  299.     iter_match_next_hashed,                /* iter_name_next */
  300.     size_hashed,                        /* size */
  301.   };

  303. ‌static const struct dict_vector dict_hashed_expandable_vector =
  304.   {
  305.     DICT_HASHED_EXPANDABLE,                /* type */
  306.     free_hashed_expandable,                /* free */
  307.     add_symbol_hashed_expandable,        /* add_symbol */
  308.     iterator_first_hashed,                /* iterator_first */
  309.     iterator_next_hashed,                /* iterator_next */
  310.     iter_match_first_hashed,                /* iter_name_first */
  311.     iter_match_next_hashed,                /* iter_name_next */
  312.     size_hashed_expandable,                /* size */
  313.   };

  315. ‌static const struct dict_vector dict_linear_vector =
  316.   {
  317.     DICT_LINEAR,                        /* type */
  318.     free_obstack,                        /* free */
  319.     add_symbol_nonexpandable,                /* add_symbol */
  320.     iterator_first_linear,                /* iterator_first */
  321.     iterator_next_linear,                /* iterator_next */
  322.     iter_match_first_linear,                /* iter_name_first */
  323.     iter_match_next_linear,                /* iter_name_next */
  324.     size_linear,                        /* size */
  325.   };

  327. ‌static const struct dict_vector dict_linear_expandable_vector =
  328.   {
  329.     DICT_LINEAR_EXPANDABLE,                /* type */
  330.     free_linear_expandable,                /* free */
  331.     add_symbol_linear_expandable,        /* add_symbol */
  332.     iterator_first_linear,                /* iterator_first */
  333.     iterator_next_linear,                /* iterator_next */
  334.     iter_match_first_linear,                /* iter_name_first */
  335.     iter_match_next_linear,                /* iter_name_next */
  336.     size_linear,                        /* size */
  337.   };

  339. /* Declarations of helper functions (i.e. ones that don't go into
  340.    vectors).  */

  342. static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);

  344. static void insert_symbol_hashed (struct dictionary *dict,
  345.                                   struct symbol *sym);

  347. static void expand_hashtable (struct dictionary *dict);

  349. /* The creation functions.  */

  351. /* Create a dictionary implemented via a fixed-size hashtable.  All
  352.    memory it uses is allocated on OBSTACK; the environment is
  353.    initialized from SYMBOL_LIST.  */

  355. struct dictionary *
  356. ‌dict_create_hashed (struct obstack *obstack,
  357.                     const struct pending *symbol_list)
  358. {
  359.   struct dictionary *retval;
  360.   int nsyms = 0, nbuckets, i;
  361.   struct symbol **buckets;
  362.   const struct pending *list_counter;

  364.   retval = obstack_alloc (obstack, sizeof (struct dictionary));
  365.   DICT_VECTOR (retval) = &dict_hashed_vector;

  367.   /* Calculate the number of symbols, and allocate space for them.  */
  368.   for (list_counter = symbol_list;
  369.        list_counter != NULL;
  370.        list_counter = list_counter->next)
  371.     {
  372.       nsyms += list_counter->nsyms;
  373.     }
  374.   nbuckets = DICT_HASHTABLE_SIZE (nsyms);
  375.   DICT_HASHED_NBUCKETS (retval) = nbuckets;
  376.   buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
  377.   memset (buckets, 0, nbuckets * sizeof (struct symbol *));
  378.   DICT_HASHED_BUCKETS (retval) = buckets;

  380.   /* Now fill the buckets.  */
  381.   for (list_counter = symbol_list;
  382.        list_counter != NULL;
  383.        list_counter = list_counter->next)
  384.     {
  385.       for (i = list_counter->nsyms - 1; i >= 0; --i)
  386.         {
  387.           insert_symbol_hashed (retval, list_counter->symbol[i]);
  388.         }
  389.     }

  391.   return retval;
  392. }

  394. /* Create a dictionary implemented via a hashtable that grows as
  395.    necessary.  The dictionary is initially empty; to add symbols to
  396.    it, call dict_add_symbol().  Call dict_free() when you're done with
  397.    it.  */

  399. extern struct dictionary *
  400. ‌dict_create_hashed_expandable (void)
  401. {
  402.   struct dictionary *retval;

  404.   retval = xmalloc (sizeof (struct dictionary));
  405.   DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
  406.   DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
  407.   DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
  408.                                           sizeof (struct symbol *));
  409.   DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;

  411.   return retval;
  412. }

  414. /* Create a dictionary implemented via a fixed-size array.  All memory
  415.    it uses is allocated on OBSTACK; the environment is initialized
  416.    from the SYMBOL_LIST.  The symbols are ordered in the same order
  417.    that they're found in SYMBOL_LIST.  */

  419. struct dictionary *
  420. ‌dict_create_linear (struct obstack *obstack,
  421.                     const struct pending *symbol_list)
  422. {
  423.   struct dictionary *retval;
  424.   int nsyms = 0, i, j;
  425.   struct symbol **syms;
  426.   const struct pending *list_counter;

  428.   retval = obstack_alloc (obstack, sizeof (struct dictionary));
  429.   DICT_VECTOR (retval) = &dict_linear_vector;

  431.   /* Calculate the number of symbols, and allocate space for them.  */
  432.   for (list_counter = symbol_list;
  433.        list_counter != NULL;
  434.        list_counter = list_counter->next)
  435.     {
  436.       nsyms += list_counter->nsyms;
  437.     }
  438.   DICT_LINEAR_NSYMS (retval) = nsyms;
  439.   syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
  440.   DICT_LINEAR_SYMS (retval) = syms;

  442.   /* Now fill in the symbols.  Start filling in from the back, so as
  443.      to preserve the original order of the symbols.  */
  444.   for (list_counter = symbol_list, j = nsyms - 1;
  445.        list_counter != NULL;
  446.        list_counter = list_counter->next)
  447.     {
  448.       for (i = list_counter->nsyms - 1;
  449.            i >= 0;
  450.            --i, --j)
  451.         {
  452.           syms[j] = list_counter->symbol[i];
  453.         }
  454.     }

  456.   return retval;
  457. }

  459. /* Create a dictionary implemented via an array that grows as
  460.    necessary.  The dictionary is initially empty; to add symbols to
  461.    it, call dict_add_symbol().  Call dict_free() when you're done with
  462.    it.  */

  464. struct dictionary *
  465. ‌dict_create_linear_expandable (void)
  466. {
  467.   struct dictionary *retval;

  469.   retval = xmalloc (sizeof (struct dictionary));
  470.   DICT_VECTOR (retval) = &dict_linear_expandable_vector;
  471.   DICT_LINEAR_NSYMS (retval) = 0;
  472.   DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
  473.     = DICT_EXPANDABLE_INITIAL_CAPACITY;
  474.   DICT_LINEAR_SYMS (retval)
  475.     = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
  476.                * sizeof (struct symbol *));

  478.   return retval;
  479. }

  481. /* The functions providing the dictionary interface.  */

  483. /* Free the memory used by a dictionary that's not on an obstack.  (If
  484.    any.)  */

  486. void
  487. ‌dict_free (struct dictionary *dict)
  488. {
  489.   (DICT_VECTOR (dict))->free (dict);
  490. }

  492. /* Add SYM to DICT.  DICT had better be expandable.  */

  494. void
  495. ‌dict_add_symbol (struct dictionary *dict, struct symbol *sym)
  496. {
  497.   (DICT_VECTOR (dict))->add_symbol (dict, sym);
  498. }

  500. /* Utility to add a list of symbols to a dictionary.
  501.    DICT must be an expandable dictionary.  */

  503. void
  504. ‌dict_add_pending (struct dictionary *dict, const struct pending *symbol_list)
  505. {
  506.   const struct pending *list;
  507.   int i;

  509.   for (list = symbol_list; list != NULL; list = list->next)
  510.     {
  511.       for (i = 0; i < list->nsyms; ++i)
  512.         dict_add_symbol (dict, list->symbol[i]);
  513.     }
  514. }

  516. /* Initialize ITERATOR to point at the first symbol in DICT, and
  517.    return that first symbol, or NULL if DICT is empty.  */

  519. struct symbol *
  520. ‌dict_iterator_first (const struct dictionary *dict,
  521.                      struct dict_iterator *iterator)
  522. {
  523.   return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
  524. }

  526. /* Advance ITERATOR, and return the next symbol, or NULL if there are
  527.    no more symbols.  */

  529. struct symbol *
  530. ‌dict_iterator_next (struct dict_iterator *iterator)
  531. {
  532.   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
  533.     ->iterator_next (iterator);
  534. }

  536. struct symbol *
  537. ‌dict_iter_name_first (const struct dictionary *dict,
  538.                       const char *name,
  539.                       struct dict_iterator *iterator)
  540. {
  541.   return dict_iter_match_first (dict, name, strcmp_iw, iterator);
  542. }

  544. struct symbol *
  545. ‌dict_iter_name_next (const char *name, struct dict_iterator *iterator)
  546. {
  547.   return dict_iter_match_next (name, strcmp_iw, iterator);
  548. }

  550. struct symbol *
  551. ‌dict_iter_match_first (const struct dictionary *dict,
  552.                        const char *name, symbol_compare_ftype *compare,
  553.                        struct dict_iterator *iterator)
  554. {
  555.   return (DICT_VECTOR (dict))->iter_match_first (dict, name,
  556.                                                  compare, iterator);
  557. }

  559. struct symbol *
  560. ‌dict_iter_match_next (const char *name, symbol_compare_ftype *compare,
  561.                       struct dict_iterator *iterator)
  562. {
  563.   return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
  564.     ->iter_match_next (name, compare, iterator);
  565. }

  567. int
  568. ‌dict_size (const struct dictionary *dict)
  569. {
  570.   return (DICT_VECTOR (dict))->size (dict);
  571. }

  573. /* Now come functions (well, one function, currently) that are
  574.    implemented generically by means of the vtable.  Typically, they're
  575.    rarely used.  */

  577. /* Test to see if DICT is empty.  */

  579. int
  580. ‌dict_empty (struct dictionary *dict)
  581. {
  582.   struct dict_iterator iter;

  584.   return (dict_iterator_first (dict, &iter) == NULL);
  585. }


  588. /* The functions implementing the dictionary interface.  */

  590. /* Generic functions, where appropriate.  */

  592. static void
  593. ‌free_obstack (struct dictionary *dict)
  594. {
  595.   /* Do nothing!  */
  596. }

  598. static void
  599. ‌add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
  600. {
  601.   internal_error (__FILE__, __LINE__,
  602.                   _("dict_add_symbol: non-expandable dictionary"));
  603. }

  605. /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE.  */

  607. static struct symbol *
  608. ‌iterator_first_hashed (const struct dictionary *dict,
  609.                        struct dict_iterator *iterator)
  610. {
  611.   DICT_ITERATOR_DICT (iterator) = dict;
  612.   DICT_ITERATOR_INDEX (iterator) = -1;
  613.   return iterator_hashed_advance (iterator);
  614. }

  616. static struct symbol *
  617. ‌iterator_next_hashed (struct dict_iterator *iterator)
  618. {
  619.   struct symbol *next;

  621.   next = DICT_ITERATOR_CURRENT (iterator)->hash_next;

  623.   if (next == NULL)
  624.     return iterator_hashed_advance (iterator);
  625.   else
  626.     {
  627.       DICT_ITERATOR_CURRENT (iterator) = next;
  628.       return next;
  629.     }
  630. }

  632. static struct symbol *
  633. ‌iterator_hashed_advance (struct dict_iterator *iterator)
  634. {
  635.   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
  636.   int nbuckets = DICT_HASHED_NBUCKETS (dict);
  637.   int i;

  639.   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
  640.     {
  641.       struct symbol *sym = DICT_HASHED_BUCKET (dict, i);

  643.       if (sym != NULL)
  644.         {
  645.           DICT_ITERATOR_INDEX (iterator) = i;
  646.           DICT_ITERATOR_CURRENT (iterator) = sym;
  647.           return sym;
  648.         }
  649.     }

  651.   return NULL;
  652. }

  654. static struct symbol *
  655. ‌iter_match_first_hashed (const struct dictionary *dict, const char *name,
  656.                          symbol_compare_ftype *compare,
  657.                          struct dict_iterator *iterator)
  658. {
  659.   unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
  660.   struct symbol *sym;

  662.   DICT_ITERATOR_DICT (iterator) = dict;

  664.   /* Loop through the symbols in the given bucket, breaking when SYM
  665.      first matches.  If SYM never matches, it will be set to NULL;
  666.      either way, we have the right return value.  */

  668.   for (sym = DICT_HASHED_BUCKET (dict, hash_index);
  669.        sym != NULL;
  670.        sym = sym->hash_next)
  671.     {
  672.       /* Warning: the order of arguments to compare matters!  */
  673.       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
  674.         {
  675.           break;
  676.         }

  678.     }

  680.   DICT_ITERATOR_CURRENT (iterator) = sym;
  681.   return sym;
  682. }

  684. static struct symbol *
  685. ‌iter_match_next_hashed (const char *name, symbol_compare_ftype *compare,
  686.                         struct dict_iterator *iterator)
  687. {
  688.   struct symbol *next;

  690.   for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
  691.        next != NULL;
  692.        next = next->hash_next)
  693.     {
  694.       if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
  695.         break;
  696.     }

  698.   DICT_ITERATOR_CURRENT (iterator) = next;

  700.   return next;
  701. }

  703. /* Insert SYM into DICT.  */

  705. static void
  706. ‌insert_symbol_hashed (struct dictionary *dict,
  707.                       struct symbol *sym)
  708. {
  709.   unsigned int hash_index;
  710.   struct symbol **buckets = DICT_HASHED_BUCKETS (dict);

  712.   hash_index =
  713.     dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
  714.   sym->hash_next = buckets[hash_index];
  715.   buckets[hash_index] = sym;
  716. }

  718. static int
  719. ‌size_hashed (const struct dictionary *dict)
  720. {
  721.   return DICT_HASHED_NBUCKETS (dict);
  722. }

  724. /* Functions only for DICT_HASHED_EXPANDABLE.  */

  726. static void
  727. ‌free_hashed_expandable (struct dictionary *dict)
  728. {
  729.   xfree (DICT_HASHED_BUCKETS (dict));
  730.   xfree (dict);
  731. }

  733. static void
  734. ‌add_symbol_hashed_expandable (struct dictionary *dict,
  735.                               struct symbol *sym)
  736. {
  737.   int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);

  739.   if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
  740.     expand_hashtable (dict);

  742.   insert_symbol_hashed (dict, sym);
  743.   DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
  744. }

  746. static int
  747. ‌size_hashed_expandable (const struct dictionary *dict)
  748. {
  749.   return DICT_HASHED_EXPANDABLE_NSYMS (dict);
  750. }

  752. static void
  753. ‌expand_hashtable (struct dictionary *dict)
  754. {
  755.   int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
  756.   struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
  757.   int new_nbuckets = 2*old_nbuckets + 1;
  758.   struct symbol **new_buckets = xcalloc (new_nbuckets,
  759.                                          sizeof (struct symbol *));
  760.   int i;

  762.   DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
  763.   DICT_HASHED_BUCKETS (dict) = new_buckets;

  765.   for (i = 0; i < old_nbuckets; ++i)
  766.     {
  767.       struct symbol *sym, *next_sym;

  769.       sym = old_buckets[i];
  770.       if (sym != NULL)
  771.         {
  772.           for (next_sym = sym->hash_next;
  773.                next_sym != NULL;
  774.                next_sym = sym->hash_next)
  775.             {
  776.               insert_symbol_hashed (dict, sym);
  777.               sym = next_sym;
  778.             }

  780.           insert_symbol_hashed (dict, sym);
  781.         }
  782.     }

  784.   xfree (old_buckets);
  785. }

  787. /* Produce an unsigned hash value from STRING0 that is consistent
  788.    with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
  789.    That is, two identifiers equivalent according to any of those three
  790.    comparison operators hash to the same value.  */

  792. static unsigned int
  793. ‌dict_hash (const char *string0)
  794. {
  795.   /* The Ada-encoded version of a name P1.P2...Pn has either the form
  796.      P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
  797.      are lower-cased identifiers).  The <suffix> (which can be empty)
  798.      encodes additional information about the denoted entity.  This
  799.      routine hashes such names to msymbol_hash_iw(Pn).  It actually
  800.      does this for a superset of both valid Pi and of <suffix>, but
  801.      in other cases it simply returns msymbol_hash_iw(STRING0).  */

  803.   const char *string;
  804.   unsigned int hash;

  806.   string = string0;
  807.   if (*string == '_')
  808.     {
  809.       if (strncmp (string, "_ada_", 5) == 0)
  810.         string += 5;
  811.       else
  812.         return msymbol_hash_iw (string0);
  813.     }

  815.   hash = 0;
  816.   while (*string)
  817.     {
  818.       /* Ignore "TKB" suffixes.

  820.          These are used by Ada for subprograms implementing a task body.
  821.          For instance for a task T inside package Pck, the name of the
  822.          subprogram implementing T's body is `pck__tTKB'.  We need to
  823.          ignore the "TKB" suffix because searches for this task body
  824.          subprogram are going to be performed using `pck__t' (the encoded
  825.          version of the natural name `pck.t').  */
  826.       if (strcmp (string, "TKB") == 0)
  827.         return hash;

  829.       switch (*string)
  830.         {
  831.         case '$':
  832.         case '.':
  833.         case 'X':
  834.           if (string0 == string)
  835.             return msymbol_hash_iw (string0);
  836.           else
  837.             return hash;
  838.         case ' ':
  839.         case '(':
  840.           return msymbol_hash_iw (string0);
  841.         case '_':
  842.           if (string[1] == '_' && string != string0)
  843.             {
  844.               int c = string[2];

  846.               if ((c < 'a' || c > 'z') && c != 'O')
  847.                 return hash;
  848.               hash = 0;
  849.               string += 2;
  850.               break;
  851.             }
  852.           /* FALL THROUGH */
  853.         default:
  854.           hash = SYMBOL_HASH_NEXT (hash, *string);
  855.           string += 1;
  856.           break;
  857.         }
  858.     }
  859.   return hash;
  860. }

  862. /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */

  864. static struct symbol *
  865. ‌iterator_first_linear (const struct dictionary *dict,
  866.                        struct dict_iterator *iterator)
  867. {
  868.   DICT_ITERATOR_DICT (iterator) = dict;
  869.   DICT_ITERATOR_INDEX (iterator) = 0;
  870.   return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
  871. }

  873. static struct symbol *
  874. ‌iterator_next_linear (struct dict_iterator *iterator)
  875. {
  876.   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);

  878.   if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
  879.     return NULL;
  880.   else
  881.     return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
  882. }

  884. static struct symbol *
  885. ‌iter_match_first_linear (const struct dictionary *dict,
  886.                          const char *name, symbol_compare_ftype *compare,
  887.                          struct dict_iterator *iterator)
  888. {
  889.   DICT_ITERATOR_DICT (iterator) = dict;
  890.   DICT_ITERATOR_INDEX (iterator) = -1;

  892.   return iter_match_next_linear (name, compare, iterator);
  893. }

  895. static struct symbol *
  896. ‌iter_match_next_linear (const char *name, symbol_compare_ftype *compare,
  897.                         struct dict_iterator *iterator)
  898. {
  899.   const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
  900.   int i, nsyms = DICT_LINEAR_NSYMS (dict);
  901.   struct symbol *sym, *retval = NULL;

  903.   for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
  904.     {
  905.       sym = DICT_LINEAR_SYM (dict, i);
  906.       if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
  907.         {
  908.           retval = sym;
  909.           break;
  910.         }
  911.     }

  913.   DICT_ITERATOR_INDEX (iterator) = i;

  915.   return retval;
  916. }

  918. static int
  919. ‌size_linear (const struct dictionary *dict)
  920. {
  921.   return DICT_LINEAR_NSYMS (dict);
  922. }

  924. /* Functions only for DICT_LINEAR_EXPANDABLE.  */

  926. static void
  927. ‌free_linear_expandable (struct dictionary *dict)
  928. {
  929.   xfree (DICT_LINEAR_SYMS (dict));
  930.   xfree (dict);
  931. }


  934. static void
  935. ‌add_symbol_linear_expandable (struct dictionary *dict,
  936.                               struct symbol *sym)
  937. {
  938.   int nsyms = ++DICT_LINEAR_NSYMS (dict);

  940.   /* Do we have enough room?  If not, grow it.  */
  941.   if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
  942.     {
  943.       DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
  944.       DICT_LINEAR_SYMS (dict)
  945.         = xrealloc (DICT_LINEAR_SYMS (dict),
  946.                     DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
  947.                     * sizeof (struct symbol *));
  948.     }

  950.   DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
  951. }