aboutsummaryrefslogtreecommitdiff
path: root/gdb/dictionary.c
diff options
context:
space:
mode:
authorDavid Carlton <carlton@bactrian.org>2003-06-11 23:29:49 +0000
committerDavid Carlton <carlton@bactrian.org>2003-06-11 23:29:49 +0000
commitde4f826b0f698dc2858f6eda71f2613a89579c50 (patch)
tree13525aa41c328ee4018f4feb9c45ad204fee014f /gdb/dictionary.c
parentcdfbf930b96d5ae51342f34dd180323a8011f8ef (diff)
downloadgdb-de4f826b0f698dc2858f6eda71f2613a89579c50.zip
gdb-de4f826b0f698dc2858f6eda71f2613a89579c50.tar.gz
gdb-de4f826b0f698dc2858f6eda71f2613a89579c50.tar.bz2
2003-06-11 David Carlton <carlton@bactrian.org>
* dictionary.h: New. * dictionary.c: New. * block.h: Add opaque declaration for struct dictionary. (struct block): Add 'dict' member; delete 'hashtable', 'nsyms', 'sym' members. (BLOCK_DICT): New macro. Delete macros BLOCK_HASHTABLE, BLOCK_NSYMS, BLOCK_SYM, BLOCK_BUCKETS, BLOCK_BUCKET, BLOCK_HASHTABLE_SIZE, BLOCK_SHOULD_SORT. (ALL_BLOCK_SYMBOLS): Update definition. * Makefile.in (SFILES): Add dictionary.c. (dictionary_h): New. (COMMON_OBS): Add dictionary.o. (dictionary.o): New. (ada-lang.o): Depend on dictionary_h. (buildsym.o, coffread.o, jv-lang.o, mdebugread.o, objfiles.o) (stack.o, symmisc.o, symtab.o, tracepoint.o, valops.o) (mi-cmd-stack.o): Ditto. (gdbtk-cmds.o): Update dependencies. (gdbtk-stack.o): Ditto. * ada-lang.c: Include dictionary.h. (symtab_for_sym): Update uses of ALL_BLOCK_SYMBOLS. (fill_in_ada_prototype, debug_print_block): Ditto. (ada_add_block_symbols): Update uses of ALL_BLOCK_SYMBOLS; replace explicit iteration by use of ALL_BLOCK_SYMBOLS. Delete variable 'is_sorted'. * mdebugread.c: Include dictionary.h. (struct parse_stack): Delete 'maxsyms' member. (parse_symbol): Update calls to new_block. Delete calls to shrink_block. Use dictionary methods. (psymtab_to_symtab_1): Delete calls to sort_symtab_syms. Update calls to new_symtab. Don't maintain maxsyms data. (mylookup_symbol): Update use of ALL_BLOCK_SYMBOLS. (add_symbol): Just call dict_add_symbol. (new_symtab): Delete 'maxsyms' argument. (new_symtab): Update calls to new_block. (new_block): Delete 'maxsyms' argument; add 'function' argument. (shrink_block): Delete function. (fixup_sigtramp): Update call to new_block. Add symbol via dict_add_symbol. * jv-lang.c: Include dictionary.h. (get_java_class_symtab): Set the BLOCK_DICT of the blocks appropriately. Set class_symtab->free_func. Make sure the blockvector is big enough to hold two blocks. (add_class_symtab_symbol): Use dictionary methods. (free_class_block): New function. (type_from_class): Replace explicit iteration by ALL_BLOCK_SYMBOLS. * symtab.h (struct symtab): Replace 'free_ptr' method by 'free_func'. * dwarf2read.c (psymtab_to_symtab_1): Delete call to sort_symtab_syms. * dwarfread.c (psymtab_to_symtab_1): Delete call to sort_symtab_syms. * coffread.c (coff_symfile_read): Delete call to sort_symtab_syms. Include dictionary.h. (patch_opaque_types): Update use of ALL_BLOCK_SYMBOLS. * dbxread.c (dbx_psymtab_to_symtab_1): Delete call to sort_symtab_syms. * objfiles.c: Include dictionary.h. (objfile_relocate): Update use of ALL_BLOCK_SYMBOLS. * buildsym.c: Include dictionary.h. (finish_block): Use dictionary methods. (end_symtab): Set free_func to NULL, not free_ptr. * tracepoint.c: Include dictionary.h. (add_local_symbols): Update use of ALL_BLOCK_SYMBOLS. (scope_info): Ditto. * stack.c: Include dictionary.h. (print_block_frame_locals): Update use of ALL_BLOCK_SYMBOLS. (print_block_frame_labels, print_frame_arg_vars) (print_frame_args): Ditto. * symmisc.c (free_symtab_block): Use dictionary methods. (dump_symtab): Ditto. (free_symtab): Replace use of 'free_ptr' by 'free_func'. Include dictionary.h. * symfile.h: Delete declarations of sort_block_syms, sort_symtab_syms. * symfile.c (sort_block_syms): Delete. (sort_symtab_syms): Delete. * symtab.c: Include dictionary.h. (lookup_block_symbol): Use dictionary iterators. (find_pc_sect_symtab): Update use of ALL_BLOCK_SYMBOLS. (search_symbols, make_symbol_completion_list): Ditto. (make_symbol_overload_list): Ditto. * valops.c (value_of_local): Use dict_empty. Include dictionary.h. 2003-06-11 David Carlton <carlton@bactrian.org> * generic/gdbtk-stack.c: Include dictionary.h. (gdb_block_vars): Update use of ALL_BLOCK_SYMBOLS. (gdb_get_blocks, gdb_get_vars_command): Ditto. * generic/gdbtk-cmds.c: Include dictionary.h. (gdb_listfuncs): Update use of ALL_BLOCK_SYMBOLS. 2003-06-11 David Carlton <carlton@bactrian.org> * mi-cmd-stack.c: Include dictionary.h. (list_args_or_locals): Update use of ALL_BLOCK_SYMBOLS.
Diffstat (limited to 'gdb/dictionary.c')
-rw-r--r--gdb/dictionary.c836
1 files changed, 836 insertions, 0 deletions
diff --git a/gdb/dictionary.c b/gdb/dictionary.c
new file mode 100644
index 0000000..3802000
--- /dev/null
+++ b/gdb/dictionary.c
@@ -0,0 +1,836 @@
+/* Routines for name->symbol lookups in GDB.
+
+ Copyright 2003 Free Software Foundation, Inc.
+
+ Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
+ Inc.
+
+ This file is part of GDB.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+#include "defs.h"
+#include "gdb_obstack.h"
+#include "symtab.h"
+#include "buildsym.h"
+#include "gdb_assert.h"
+#include "dictionary.h"
+
+/* This file implements dictionaries, which are tables that associate
+ symbols to names. They are represented by an opaque type 'struct
+ dictionary'. That type has various internal implementations, which
+ you can choose between depending on what properties you need
+ (e.g. fast lookup, order-preserving, expandable).
+
+ Each dictionary starts with a 'virtual function table' that
+ contains the functions that actually implement the various
+ operations that dictionaries provide. (Note, however, that, for
+ the sake of client code, we also provide some functions that can be
+ implemented generically in terms of the functions in the vtable.)
+
+ To add a new dictionary implementation <impl>, what you should do
+ is:
+
+ * Add a new element DICT_<IMPL> to dict_type.
+
+ * Create a new structure dictionary_<impl>. If your new
+ implementation is a variant of an existing one, make sure that
+ their structs have the same initial data members. Define accessor
+ macros for your new data members.
+
+ * Implement all the functions in dict_vector as static functions,
+ whose name is the same as the corresponding member of dict_vector
+ plus _<impl>. You don't have to do this for those members where
+ you can reuse existing generic functions
+ (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
+ your new implementation is a variant of an existing implementation
+ and where the variant doesn't affect the member function in
+ question.
+
+ * Define a static const struct dict_vector dict_<impl>_vector.
+
+ * Define a function dict_create_<impl> to create these
+ gizmos. Add its declaration to dictionary.h.
+
+ To add a new operation <op> on all existing implementations, what
+ you should do is:
+
+ * Add a new member <op> to struct dict_vector.
+
+ * If there is useful generic behavior <op>, define a static
+ function <op>_something_informative that implements that behavior.
+ (E.g. add_symbol_nonexpandable, free_obstack.)
+
+ * For every implementation <impl> that should have its own specific
+ behavior for <op>, define a static function <op>_<impl>
+ implementing it.
+
+ * Modify all existing dict_vector_<impl>'s to include the appropriate
+ member.
+
+ * Define a function dict_<op> that looks up <op> in the dict_vector
+ and calls the appropriate function. Add a declaration for
+ dict_<op> to dictionary.h.
+
+*/
+
+/* An enum representing the various implementations of dictionaries.
+ Used only for debugging. */
+
+enum dict_type
+ {
+ /* Symbols are stored in a fixed-size hash table. */
+ DICT_HASHED,
+ /* Symbols are stored in an expandable hash table. */
+ DICT_HASHED_EXPANDABLE,
+ /* Symbols are stored in a fixed-size array. */
+ DICT_LINEAR,
+ /* Symbols are stored in an expandable array. */
+ DICT_LINEAR_EXPANDABLE,
+ };
+
+/* The virtual function table. */
+
+struct dict_vector
+{
+ /* The type of the dictionary. This is only here to make debugging
+ a bit easier; it's not actually used. */
+ enum dict_type type;
+ /* The function to free a dictionary. */
+ void (*free) (struct dictionary *dict);
+ /* Add a symbol to a dictionary, if possible. */
+ void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
+ /* Iterator functions. */
+ struct symbol *(*iterator_first) (const struct dictionary *dict,
+ struct dict_iterator *iterator);
+ struct symbol *(*iterator_next) (struct dict_iterator *iterator);
+ /* Functions to iterate over symbols with a given name. */
+ struct symbol *(*iter_name_first) (const struct dictionary *dict,
+ const char *name,
+ struct dict_iterator *iterator);
+ struct symbol *(*iter_name_next) (const char *name,
+ struct dict_iterator *iterator);
+ /* A size function, for maint print symtabs. */
+ int (*size) (const struct dictionary *dict);
+};
+
+/* Now comes the structs used to store the data for different
+ implementations. If two implementations have data in common, put
+ the common data at the top of their structs, ordered in the same
+ way. */
+
+struct dictionary_hashed
+{
+ int nbuckets;
+ struct symbol **buckets;
+};
+
+struct dictionary_hashed_expandable
+{
+ /* How many buckets we currently have. */
+ int nbuckets;
+ struct symbol **buckets;
+ /* How many syms we currently have; we need this so we will know
+ when to add more buckets. */
+ int nsyms;
+};
+
+struct dictionary_linear
+{
+ int nsyms;
+ struct symbol **syms;
+};
+
+struct dictionary_linear_expandable
+{
+ /* How many symbols we currently have. */
+ int nsyms;
+ struct symbol **syms;
+ /* How many symbols we can store before needing to reallocate. */
+ int capacity;
+};
+
+/* And now, the star of our show. */
+
+struct dictionary
+{
+ const struct dict_vector *vector;
+ union
+ {
+ struct dictionary_hashed hashed;
+ struct dictionary_hashed_expandable hashed_expandable;
+ struct dictionary_linear linear;
+ struct dictionary_linear_expandable linear_expandable;
+ }
+ data;
+};
+
+/* Accessor macros. */
+
+#define DICT_VECTOR(d) (d)->vector
+
+/* These can be used for DICT_HASHED_EXPANDABLE, too. */
+
+#define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
+#define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
+#define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
+
+#define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
+
+/* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
+
+#define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
+#define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
+#define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
+
+#define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
+ (d)->data.linear_expandable.capacity
+
+/* The initial size of a DICT_*_EXPANDABLE dictionary. */
+
+#define DICT_EXPANDABLE_INITIAL_CAPACITY 10
+
+/* This calculates the number of buckets we'll use in a hashtable,
+ given the number of symbols that it will contain. */
+
+#define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
+
+/* Accessor macros for dict_iterators; they're here rather than
+ dictionary.h because code elsewhere should treat dict_iterators as
+ opaque. */
+
+/* The dictionary that the iterator is associated to. */
+#define DICT_ITERATOR_DICT(iter) (iter)->dict
+/* For linear dictionaries, the index of the last symbol returned; for
+ hashed dictionaries, the bucket of the last symbol returned. */
+#define DICT_ITERATOR_INDEX(iter) (iter)->index
+/* For hashed dictionaries, this points to the last symbol returned;
+ otherwise, this is unused. */
+#define DICT_ITERATOR_CURRENT(iter) (iter)->current
+
+/* Declarations of functions for vectors. */
+
+/* Functions that might work across a range of dictionary types. */
+
+static void add_symbol_nonexpandable (struct dictionary *dict,
+ struct symbol *sym);
+
+static void free_obstack (struct dictionary *dict);
+
+/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
+ dictionaries. */
+
+static struct symbol *iterator_first_hashed (const struct dictionary *dict,
+ struct dict_iterator *iterator);
+
+static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
+
+static struct symbol *iter_name_first_hashed (const struct dictionary *dict,
+ const char *name,
+ struct dict_iterator *iterator);
+
+static struct symbol *iter_name_next_hashed (const char *name,
+ struct dict_iterator *iterator);
+
+/* Functions only for DICT_HASHED. */
+
+static int size_hashed (const struct dictionary *dict);
+
+/* Functions only for DICT_HASHED_EXPANDABLE. */
+
+static void free_hashed_expandable (struct dictionary *dict);
+
+static void add_symbol_hashed_expandable (struct dictionary *dict,
+ struct symbol *sym);
+
+static int size_hashed_expandable (const struct dictionary *dict);
+
+/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
+ dictionaries. */
+
+static struct symbol *iterator_first_linear (const struct dictionary *dict,
+ struct dict_iterator *iterator);
+
+static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
+
+static struct symbol *iter_name_first_linear (const struct dictionary *dict,
+ const char *name,
+ struct dict_iterator *iterator);
+
+static struct symbol *iter_name_next_linear (const char *name,
+ struct dict_iterator *iterator);
+
+static int size_linear (const struct dictionary *dict);
+
+/* Functions only for DICT_LINEAR_EXPANDABLE. */
+
+static void free_linear_expandable (struct dictionary *dict);
+
+static void add_symbol_linear_expandable (struct dictionary *dict,
+ struct symbol *sym);
+
+/* Various vectors that we'll actually use. */
+
+static const struct dict_vector dict_hashed_vector =
+ {
+ DICT_HASHED, /* type */
+ free_obstack, /* free */
+ add_symbol_nonexpandable, /* add_symbol */
+ iterator_first_hashed, /* iteractor_first */
+ iterator_next_hashed, /* iterator_next */
+ iter_name_first_hashed, /* iter_name_first */
+ iter_name_next_hashed, /* iter_name_next */
+ size_hashed, /* size */
+ };
+
+static const struct dict_vector dict_hashed_expandable_vector =
+ {
+ DICT_HASHED_EXPANDABLE, /* type */
+ free_hashed_expandable, /* free */
+ add_symbol_hashed_expandable, /* add_symbol */
+ iterator_first_hashed, /* iteractor_first */
+ iterator_next_hashed, /* iterator_next */
+ iter_name_first_hashed, /* iter_name_first */
+ iter_name_next_hashed, /* iter_name_next */
+ size_hashed_expandable, /* size */
+ };
+
+static const struct dict_vector dict_linear_vector =
+ {
+ DICT_LINEAR, /* type */
+ free_obstack, /* free */
+ add_symbol_nonexpandable, /* add_symbol */
+ iterator_first_linear, /* iteractor_first */
+ iterator_next_linear, /* iterator_next */
+ iter_name_first_linear, /* iter_name_first */
+ iter_name_next_linear, /* iter_name_next */
+ size_linear, /* size */
+ };
+
+static const struct dict_vector dict_linear_expandable_vector =
+ {
+ DICT_LINEAR_EXPANDABLE, /* type */
+ free_linear_expandable, /* free */
+ add_symbol_linear_expandable, /* add_symbol */
+ iterator_first_linear, /* iteractor_first */
+ iterator_next_linear, /* iterator_next */
+ iter_name_first_linear, /* iter_name_first */
+ iter_name_next_linear, /* iter_name_next */
+ size_linear, /* size */
+ };
+
+/* Declarations of helper functions (i.e. ones that don't go into
+ vectors). */
+
+static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
+
+static void insert_symbol_hashed (struct dictionary *dict,
+ struct symbol *sym);
+
+static void expand_hashtable (struct dictionary *dict);
+
+/* The creation functions. */
+
+/* Create a dictionary implemented via a fixed-size hashtable. All
+ memory it uses is allocated on OBSTACK; the environment is
+ initialized from SYMBOL_LIST. */
+
+struct dictionary *
+dict_create_hashed (struct obstack *obstack,
+ const struct pending *symbol_list)
+{
+ struct dictionary *retval;
+ int nsyms = 0, nbuckets, i;
+ struct symbol **buckets;
+ const struct pending *list_counter;
+
+ retval = obstack_alloc (obstack, sizeof (struct dictionary));
+ DICT_VECTOR (retval) = &dict_hashed_vector;
+
+ /* Calculate the number of symbols, and allocate space for them. */
+ for (list_counter = symbol_list;
+ list_counter != NULL;
+ list_counter = list_counter->next)
+ {
+ nsyms += list_counter->nsyms;
+ }
+ nbuckets = DICT_HASHTABLE_SIZE (nsyms);
+ DICT_HASHED_NBUCKETS (retval) = nbuckets;
+ buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
+ memset (buckets, 0, nbuckets * sizeof (struct symbol *));
+ DICT_HASHED_BUCKETS (retval) = buckets;
+
+ /* Now fill the buckets. */
+ for (list_counter = symbol_list;
+ list_counter != NULL;
+ list_counter = list_counter->next)
+ {
+ for (i = list_counter->nsyms - 1; i >= 0; --i)
+ {
+ insert_symbol_hashed (retval, list_counter->symbol[i]);
+ }
+ }
+
+ return retval;
+}
+
+/* Create a dictionary implemented via a hashtable that grows as
+ necessary. The dictionary is initially empty; to add symbols to
+ it, call dict_add_symbol(). Call dict_free() when you're done with
+ it. */
+
+extern struct dictionary *
+dict_create_hashed_expandable (void)
+{
+ struct dictionary *retval;
+
+ retval = xmalloc (sizeof (struct dictionary));
+ DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
+ DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
+ DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
+ sizeof (struct symbol *));
+ DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
+
+ return retval;
+}
+
+/* Create a dictionary implemented via a fixed-size array. All memory
+ it uses is allocated on OBSTACK; the environment is initialized
+ from the SYMBOL_LIST. The symbols are ordered in the same order
+ that they're found in SYMBOL_LIST. */
+
+struct dictionary *
+dict_create_linear (struct obstack *obstack,
+ const struct pending *symbol_list)
+{
+ struct dictionary *retval;
+ int nsyms = 0, i, j;
+ struct symbol **syms;
+ const struct pending *list_counter;
+
+ retval = obstack_alloc (obstack, sizeof (struct dictionary));
+ DICT_VECTOR (retval) = &dict_linear_vector;
+
+ /* Calculate the number of symbols, and allocate space for them. */
+ for (list_counter = symbol_list;
+ list_counter != NULL;
+ list_counter = list_counter->next)
+ {
+ nsyms += list_counter->nsyms;
+ }
+ DICT_LINEAR_NSYMS (retval) = nsyms;
+ syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
+ DICT_LINEAR_SYMS (retval) = syms;
+
+ /* Now fill in the symbols. Start filling in from the back, so as
+ to preserve the original order of the symbols. */
+ for (list_counter = symbol_list, j = nsyms - 1;
+ list_counter != NULL;
+ list_counter = list_counter->next)
+ {
+ for (i = list_counter->nsyms - 1;
+ i >= 0;
+ --i, --j)
+ {
+ syms[j] = list_counter->symbol[i];
+ }
+ }
+
+ return retval;
+}
+
+/* Create a dictionary implemented via an array that grows as
+ necessary. The dictionary is initially empty; to add symbols to
+ it, call dict_add_symbol(). Call dict_free() when you're done with
+ it. */
+
+struct dictionary *
+dict_create_linear_expandable (void)
+{
+ struct dictionary *retval;
+
+ retval = xmalloc (sizeof (struct dictionary));
+ DICT_VECTOR (retval) = &dict_linear_expandable_vector;
+ DICT_LINEAR_NSYMS (retval) = 0;
+ DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
+ = DICT_EXPANDABLE_INITIAL_CAPACITY;
+ DICT_LINEAR_SYMS (retval)
+ = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
+ * sizeof (struct symbol *));
+
+ return retval;
+}
+
+/* The functions providing the dictionary interface. */
+
+/* Free the memory used by a dictionary that's not on an obstack. (If
+ any.) */
+
+void
+dict_free (struct dictionary *dict)
+{
+ (DICT_VECTOR (dict))->free (dict);
+}
+
+/* Add SYM to DICT. DICT had better be expandable. */
+
+void
+dict_add_symbol (struct dictionary *dict, struct symbol *sym)
+{
+ (DICT_VECTOR (dict))->add_symbol (dict, sym);
+}
+
+/* Initialize ITERATOR to point at the first symbol in DICT, and
+ return that first symbol, or NULL if DICT is empty. */
+
+struct symbol *
+dict_iterator_first (const struct dictionary *dict,
+ struct dict_iterator *iterator)
+{
+ return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
+}
+
+/* Advance ITERATOR, and return the next symbol, or NULL if there are
+ no more symbols. */
+
+struct symbol *
+dict_iterator_next (struct dict_iterator *iterator)
+{
+ return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
+ ->iterator_next (iterator);
+}
+
+struct symbol *
+dict_iter_name_first (const struct dictionary *dict,
+ const char *name,
+ struct dict_iterator *iterator)
+{
+ return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
+}
+
+struct symbol *
+dict_iter_name_next (const char *name, struct dict_iterator *iterator)
+{
+ return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
+ ->iter_name_next (name, iterator);
+}
+
+int
+dict_size (const struct dictionary *dict)
+{
+ return (DICT_VECTOR (dict))->size (dict);
+}
+
+/* Now come functions (well, one function, currently) that are
+ implemented generically by means of the vtable. Typically, they're
+ rarely used. */
+
+/* Test to see if DICT is empty. */
+
+int
+dict_empty (struct dictionary *dict)
+{
+ struct dict_iterator iter;
+
+ return (dict_iterator_first (dict, &iter) == NULL);
+}
+
+
+/* The functions implementing the dictionary interface. */
+
+/* Generic functions, where appropriate. */
+
+static void
+free_obstack (struct dictionary *dict)
+{
+ /* Do nothing! */
+}
+
+static void
+add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
+{
+ internal_error (__FILE__, __LINE__,
+ "dict_add_symbol: non-expandable dictionary");
+}
+
+/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
+
+static struct symbol *
+iterator_first_hashed (const struct dictionary *dict,
+ struct dict_iterator *iterator)
+{
+ DICT_ITERATOR_DICT (iterator) = dict;
+ DICT_ITERATOR_INDEX (iterator) = -1;
+ return iterator_hashed_advance (iterator);
+}
+
+static struct symbol *
+iterator_next_hashed (struct dict_iterator *iterator)
+{
+ const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
+ struct symbol *next;
+
+ next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
+
+ if (next == NULL)
+ return iterator_hashed_advance (iterator);
+ else
+ {
+ DICT_ITERATOR_CURRENT (iterator) = next;
+ return next;
+ }
+}
+
+static struct symbol *
+iterator_hashed_advance (struct dict_iterator *iterator)
+{
+ const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
+ int nbuckets = DICT_HASHED_NBUCKETS (dict);
+ int i;
+
+ for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
+ {
+ struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
+
+ if (sym != NULL)
+ {
+ DICT_ITERATOR_INDEX (iterator) = i;
+ DICT_ITERATOR_CURRENT (iterator) = sym;
+ return sym;
+ }
+ }
+
+ return NULL;
+}
+
+static struct symbol *
+iter_name_first_hashed (const struct dictionary *dict,
+ const char *name,
+ struct dict_iterator *iterator)
+{
+ unsigned int hash_index
+ = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
+ struct symbol *sym;
+
+ DICT_ITERATOR_DICT (iterator) = dict;
+
+ /* Loop through the symbols in the given bucket, breaking when SYM
+ first matches. If SYM never matches, it will be set to NULL;
+ either way, we have the right return value. */
+
+ for (sym = DICT_HASHED_BUCKET (dict, hash_index);
+ sym != NULL;
+ sym = sym->hash_next)
+ {
+ /* Warning: the order of arguments to strcmp_iw matters! */
+ if (strcmp_iw (SYMBOL_NATURAL_NAME (sym), name) == 0)
+ {
+ break;
+ }
+
+ }
+
+ DICT_ITERATOR_CURRENT (iterator) = sym;
+ return sym;
+}
+
+static struct symbol *
+iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
+{
+ struct symbol *next;
+
+ for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
+ next != NULL;
+ next = next->hash_next)
+ {
+ if (strcmp_iw (SYMBOL_NATURAL_NAME (next), name) == 0)
+ break;
+ }
+
+ DICT_ITERATOR_CURRENT (iterator) = next;
+
+ return next;
+}
+
+/* Insert SYM into DICT. */
+
+static void
+insert_symbol_hashed (struct dictionary *dict,
+ struct symbol *sym)
+{
+ unsigned int hash_index;
+ struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
+
+ hash_index = (msymbol_hash_iw (SYMBOL_NATURAL_NAME (sym))
+ % DICT_HASHED_NBUCKETS (dict));
+ sym->hash_next = buckets[hash_index];
+ buckets[hash_index] = sym;
+}
+
+static int
+size_hashed (const struct dictionary *dict)
+{
+ return DICT_HASHED_NBUCKETS (dict);
+}
+
+/* Functions only for DICT_HASHED_EXPANDABLE. */
+
+static void
+free_hashed_expandable (struct dictionary *dict)
+{
+ xfree (DICT_HASHED_BUCKETS (dict));
+ xfree (dict);
+}
+
+static void
+add_symbol_hashed_expandable (struct dictionary *dict,
+ struct symbol *sym)
+{
+ int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
+
+ if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
+ expand_hashtable (dict);
+
+ insert_symbol_hashed (dict, sym);
+ DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
+}
+
+static int
+size_hashed_expandable (const struct dictionary *dict)
+{
+ return DICT_HASHED_EXPANDABLE_NSYMS (dict);
+}
+
+static void
+expand_hashtable (struct dictionary *dict)
+{
+ int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
+ struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
+ int new_nbuckets = 2*old_nbuckets + 1;
+ struct symbol **new_buckets = xcalloc (new_nbuckets,
+ sizeof (struct symbol *));
+ int i;
+
+ DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
+ DICT_HASHED_BUCKETS (dict) = new_buckets;
+
+ for (i = 0; i < old_nbuckets; ++i) {
+ struct symbol *sym, *next_sym;
+
+ sym = old_buckets[i];
+ if (sym != NULL) {
+ for (next_sym = sym->hash_next;
+ next_sym != NULL;
+ next_sym = sym->hash_next) {
+ insert_symbol_hashed (dict, sym);
+ sym = next_sym;
+ }
+
+ insert_symbol_hashed (dict, sym);
+ }
+ }
+
+ xfree (old_buckets);
+}
+
+/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
+
+static struct symbol *
+iterator_first_linear (const struct dictionary *dict,
+ struct dict_iterator *iterator)
+{
+ DICT_ITERATOR_DICT (iterator) = dict;
+ DICT_ITERATOR_INDEX (iterator) = 0;
+ return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
+}
+
+static struct symbol *
+iterator_next_linear (struct dict_iterator *iterator)
+{
+ const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
+
+ if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
+ return NULL;
+ else
+ return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
+}
+
+static struct symbol *
+iter_name_first_linear (const struct dictionary *dict,
+ const char *name,
+ struct dict_iterator *iterator)
+{
+ DICT_ITERATOR_DICT (iterator) = dict;
+ DICT_ITERATOR_INDEX (iterator) = -1;
+
+ return iter_name_next_linear (name, iterator);
+}
+
+static struct symbol *
+iter_name_next_linear (const char *name, struct dict_iterator *iterator)
+{
+ const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
+ int i, nsyms = DICT_LINEAR_NSYMS (dict);
+ struct symbol *sym, *retval = NULL;
+
+ for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
+ {
+ sym = DICT_LINEAR_SYM (dict, i);
+ if (strcmp_iw (SYMBOL_NATURAL_NAME (sym), name) == 0)
+ {
+ retval = sym;
+ break;
+ }
+ }
+
+ DICT_ITERATOR_INDEX (iterator) = i;
+
+ return retval;
+}
+
+static int
+size_linear (const struct dictionary *dict)
+{
+ return DICT_LINEAR_NSYMS (dict);
+}
+
+/* Functions only for DICT_LINEAR_EXPANDABLE. */
+
+static void
+free_linear_expandable (struct dictionary *dict)
+{
+ xfree (DICT_LINEAR_SYMS (dict));
+ xfree (dict);
+}
+
+
+static void
+add_symbol_linear_expandable (struct dictionary *dict,
+ struct symbol *sym)
+{
+ int nsyms = ++DICT_LINEAR_NSYMS (dict);
+
+ /* Do we have enough room? If not, grow it. */
+ if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) {
+ DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
+ DICT_LINEAR_SYMS (dict)
+ = xrealloc (DICT_LINEAR_SYMS (dict),
+ DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
+ * sizeof (struct symbol *));
+ }
+
+ DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
+}