From de4f826b0f698dc2858f6eda71f2613a89579c50 Mon Sep 17 00:00:00 2001 From: David Carlton Date: Wed, 11 Jun 2003 23:29:49 +0000 Subject: 2003-06-11 David Carlton * 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 * 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 * mi-cmd-stack.c: Include dictionary.h. (list_args_or_locals): Update use of ALL_BLOCK_SYMBOLS. --- gdb/dictionary.c | 836 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 836 insertions(+) create mode 100644 gdb/dictionary.c (limited to 'gdb/dictionary.c') 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 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 , what you should do + is: + + * Add a new element DICT_ to dict_type. + + * Create a new structure dictionary_. 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 _. 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__vector. + + * Define a function dict_create_ to create these + gizmos. Add its declaration to dictionary.h. + + To add a new operation on all existing implementations, what + you should do is: + + * Add a new member to struct dict_vector. + + * If there is useful generic behavior , define a static + function _something_informative that implements that behavior. + (E.g. add_symbol_nonexpandable, free_obstack.) + + * For every implementation that should have its own specific + behavior for , define a static function _ + implementing it. + + * Modify all existing dict_vector_'s to include the appropriate + member. + + * Define a function dict_ that looks up in the dict_vector + and calls the appropriate function. Add a declaration for + dict_ 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; +} -- cgit v1.1