/* Routines for name->symbol lookups in GDB.
|
/* Routines for name->symbol lookups in GDB.
|
|
|
Copyright (C) 2003, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
Copyright (C) 2003, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
|
|
Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
|
Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
|
Inc.
|
Inc.
|
|
|
This file is part of GDB.
|
This file is part of GDB.
|
|
|
This program is free software; you can redistribute it and/or modify
|
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
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3 of the License, or
|
the Free Software Foundation; either version 3 of the License, or
|
(at your option) any later version.
|
(at your option) any later version.
|
|
|
This program is distributed in the hope that it will be useful,
|
This program is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with this program. If not, see <http://www.gnu.org/licenses/>. */
|
along with this program. If not, see <http://www.gnu.org/licenses/>. */
|
|
|
#include "defs.h"
|
#include "defs.h"
|
#include "gdb_obstack.h"
|
#include "gdb_obstack.h"
|
#include "symtab.h"
|
#include "symtab.h"
|
#include "buildsym.h"
|
#include "buildsym.h"
|
#include "gdb_assert.h"
|
#include "gdb_assert.h"
|
#include "dictionary.h"
|
#include "dictionary.h"
|
|
|
/* This file implements dictionaries, which are tables that associate
|
/* This file implements dictionaries, which are tables that associate
|
symbols to names. They are represented by an opaque type 'struct
|
symbols to names. They are represented by an opaque type 'struct
|
dictionary'. That type has various internal implementations, which
|
dictionary'. That type has various internal implementations, which
|
you can choose between depending on what properties you need
|
you can choose between depending on what properties you need
|
(e.g. fast lookup, order-preserving, expandable).
|
(e.g. fast lookup, order-preserving, expandable).
|
|
|
Each dictionary starts with a 'virtual function table' that
|
Each dictionary starts with a 'virtual function table' that
|
contains the functions that actually implement the various
|
contains the functions that actually implement the various
|
operations that dictionaries provide. (Note, however, that, for
|
operations that dictionaries provide. (Note, however, that, for
|
the sake of client code, we also provide some functions that can be
|
the sake of client code, we also provide some functions that can be
|
implemented generically in terms of the functions in the vtable.)
|
implemented generically in terms of the functions in the vtable.)
|
|
|
To add a new dictionary implementation <impl>, what you should do
|
To add a new dictionary implementation <impl>, what you should do
|
is:
|
is:
|
|
|
* Add a new element DICT_<IMPL> to dict_type.
|
* Add a new element DICT_<IMPL> to dict_type.
|
|
|
* Create a new structure dictionary_<impl>. If your new
|
* Create a new structure dictionary_<impl>. If your new
|
implementation is a variant of an existing one, make sure that
|
implementation is a variant of an existing one, make sure that
|
their structs have the same initial data members. Define accessor
|
their structs have the same initial data members. Define accessor
|
macros for your new data members.
|
macros for your new data members.
|
|
|
* Implement all the functions in dict_vector as static functions,
|
* Implement all the functions in dict_vector as static functions,
|
whose name is the same as the corresponding member of dict_vector
|
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
|
plus _<impl>. You don't have to do this for those members where
|
you can reuse existing generic functions
|
you can reuse existing generic functions
|
(e.g. add_symbol_nonexpandable, free_obstack) or in the case where
|
(e.g. add_symbol_nonexpandable, free_obstack) or in the case where
|
your new implementation is a variant of an existing implementation
|
your new implementation is a variant of an existing implementation
|
and where the variant doesn't affect the member function in
|
and where the variant doesn't affect the member function in
|
question.
|
question.
|
|
|
* Define a static const struct dict_vector dict_<impl>_vector.
|
* Define a static const struct dict_vector dict_<impl>_vector.
|
|
|
* Define a function dict_create_<impl> to create these
|
* Define a function dict_create_<impl> to create these
|
gizmos. Add its declaration to dictionary.h.
|
gizmos. Add its declaration to dictionary.h.
|
|
|
To add a new operation <op> on all existing implementations, what
|
To add a new operation <op> on all existing implementations, what
|
you should do is:
|
you should do is:
|
|
|
* Add a new member <op> to struct dict_vector.
|
* Add a new member <op> to struct dict_vector.
|
|
|
* If there is useful generic behavior <op>, define a static
|
* If there is useful generic behavior <op>, define a static
|
function <op>_something_informative that implements that behavior.
|
function <op>_something_informative that implements that behavior.
|
(E.g. add_symbol_nonexpandable, free_obstack.)
|
(E.g. add_symbol_nonexpandable, free_obstack.)
|
|
|
* For every implementation <impl> that should have its own specific
|
* For every implementation <impl> that should have its own specific
|
behavior for <op>, define a static function <op>_<impl>
|
behavior for <op>, define a static function <op>_<impl>
|
implementing it.
|
implementing it.
|
|
|
* Modify all existing dict_vector_<impl>'s to include the appropriate
|
* Modify all existing dict_vector_<impl>'s to include the appropriate
|
member.
|
member.
|
|
|
* Define a function dict_<op> that looks up <op> in the dict_vector
|
* Define a function dict_<op> that looks up <op> in the dict_vector
|
and calls the appropriate function. Add a declaration for
|
and calls the appropriate function. Add a declaration for
|
dict_<op> to dictionary.h.
|
dict_<op> to dictionary.h.
|
|
|
*/
|
*/
|
|
|
/* An enum representing the various implementations of dictionaries.
|
/* An enum representing the various implementations of dictionaries.
|
Used only for debugging. */
|
Used only for debugging. */
|
|
|
enum dict_type
|
enum dict_type
|
{
|
{
|
/* Symbols are stored in a fixed-size hash table. */
|
/* Symbols are stored in a fixed-size hash table. */
|
DICT_HASHED,
|
DICT_HASHED,
|
/* Symbols are stored in an expandable hash table. */
|
/* Symbols are stored in an expandable hash table. */
|
DICT_HASHED_EXPANDABLE,
|
DICT_HASHED_EXPANDABLE,
|
/* Symbols are stored in a fixed-size array. */
|
/* Symbols are stored in a fixed-size array. */
|
DICT_LINEAR,
|
DICT_LINEAR,
|
/* Symbols are stored in an expandable array. */
|
/* Symbols are stored in an expandable array. */
|
DICT_LINEAR_EXPANDABLE
|
DICT_LINEAR_EXPANDABLE
|
};
|
};
|
|
|
/* The virtual function table. */
|
/* The virtual function table. */
|
|
|
struct dict_vector
|
struct dict_vector
|
{
|
{
|
/* The type of the dictionary. This is only here to make debugging
|
/* The type of the dictionary. This is only here to make debugging
|
a bit easier; it's not actually used. */
|
a bit easier; it's not actually used. */
|
enum dict_type type;
|
enum dict_type type;
|
/* The function to free a dictionary. */
|
/* The function to free a dictionary. */
|
void (*free) (struct dictionary *dict);
|
void (*free) (struct dictionary *dict);
|
/* Add a symbol to a dictionary, if possible. */
|
/* Add a symbol to a dictionary, if possible. */
|
void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
|
void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
|
/* Iterator functions. */
|
/* Iterator functions. */
|
struct symbol *(*iterator_first) (const struct dictionary *dict,
|
struct symbol *(*iterator_first) (const struct dictionary *dict,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
struct symbol *(*iterator_next) (struct dict_iterator *iterator);
|
struct symbol *(*iterator_next) (struct dict_iterator *iterator);
|
/* Functions to iterate over symbols with a given name. */
|
/* Functions to iterate over symbols with a given name. */
|
struct symbol *(*iter_name_first) (const struct dictionary *dict,
|
struct symbol *(*iter_name_first) (const struct dictionary *dict,
|
const char *name,
|
const char *name,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
struct symbol *(*iter_name_next) (const char *name,
|
struct symbol *(*iter_name_next) (const char *name,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
/* A size function, for maint print symtabs. */
|
/* A size function, for maint print symtabs. */
|
int (*size) (const struct dictionary *dict);
|
int (*size) (const struct dictionary *dict);
|
};
|
};
|
|
|
/* Now comes the structs used to store the data for different
|
/* Now comes the structs used to store the data for different
|
implementations. If two implementations have data in common, put
|
implementations. If two implementations have data in common, put
|
the common data at the top of their structs, ordered in the same
|
the common data at the top of their structs, ordered in the same
|
way. */
|
way. */
|
|
|
struct dictionary_hashed
|
struct dictionary_hashed
|
{
|
{
|
int nbuckets;
|
int nbuckets;
|
struct symbol **buckets;
|
struct symbol **buckets;
|
};
|
};
|
|
|
struct dictionary_hashed_expandable
|
struct dictionary_hashed_expandable
|
{
|
{
|
/* How many buckets we currently have. */
|
/* How many buckets we currently have. */
|
int nbuckets;
|
int nbuckets;
|
struct symbol **buckets;
|
struct symbol **buckets;
|
/* How many syms we currently have; we need this so we will know
|
/* How many syms we currently have; we need this so we will know
|
when to add more buckets. */
|
when to add more buckets. */
|
int nsyms;
|
int nsyms;
|
};
|
};
|
|
|
struct dictionary_linear
|
struct dictionary_linear
|
{
|
{
|
int nsyms;
|
int nsyms;
|
struct symbol **syms;
|
struct symbol **syms;
|
};
|
};
|
|
|
struct dictionary_linear_expandable
|
struct dictionary_linear_expandable
|
{
|
{
|
/* How many symbols we currently have. */
|
/* How many symbols we currently have. */
|
int nsyms;
|
int nsyms;
|
struct symbol **syms;
|
struct symbol **syms;
|
/* How many symbols we can store before needing to reallocate. */
|
/* How many symbols we can store before needing to reallocate. */
|
int capacity;
|
int capacity;
|
};
|
};
|
|
|
/* And now, the star of our show. */
|
/* And now, the star of our show. */
|
|
|
struct dictionary
|
struct dictionary
|
{
|
{
|
const struct dict_vector *vector;
|
const struct dict_vector *vector;
|
union
|
union
|
{
|
{
|
struct dictionary_hashed hashed;
|
struct dictionary_hashed hashed;
|
struct dictionary_hashed_expandable hashed_expandable;
|
struct dictionary_hashed_expandable hashed_expandable;
|
struct dictionary_linear linear;
|
struct dictionary_linear linear;
|
struct dictionary_linear_expandable linear_expandable;
|
struct dictionary_linear_expandable linear_expandable;
|
}
|
}
|
data;
|
data;
|
};
|
};
|
|
|
/* Accessor macros. */
|
/* Accessor macros. */
|
|
|
#define DICT_VECTOR(d) (d)->vector
|
#define DICT_VECTOR(d) (d)->vector
|
|
|
/* These can be used for DICT_HASHED_EXPANDABLE, too. */
|
/* These can be used for DICT_HASHED_EXPANDABLE, too. */
|
|
|
#define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
|
#define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
|
#define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
|
#define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
|
#define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
|
#define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
|
|
|
#define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
|
#define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
|
|
|
/* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
|
/* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
|
|
|
#define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
|
#define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
|
#define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
|
#define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
|
#define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
|
#define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
|
|
|
#define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
|
#define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
|
(d)->data.linear_expandable.capacity
|
(d)->data.linear_expandable.capacity
|
|
|
/* The initial size of a DICT_*_EXPANDABLE dictionary. */
|
/* The initial size of a DICT_*_EXPANDABLE dictionary. */
|
|
|
#define DICT_EXPANDABLE_INITIAL_CAPACITY 10
|
#define DICT_EXPANDABLE_INITIAL_CAPACITY 10
|
|
|
/* This calculates the number of buckets we'll use in a hashtable,
|
/* This calculates the number of buckets we'll use in a hashtable,
|
given the number of symbols that it will contain. */
|
given the number of symbols that it will contain. */
|
|
|
#define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
|
#define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
|
|
|
/* Accessor macros for dict_iterators; they're here rather than
|
/* Accessor macros for dict_iterators; they're here rather than
|
dictionary.h because code elsewhere should treat dict_iterators as
|
dictionary.h because code elsewhere should treat dict_iterators as
|
opaque. */
|
opaque. */
|
|
|
/* The dictionary that the iterator is associated to. */
|
/* The dictionary that the iterator is associated to. */
|
#define DICT_ITERATOR_DICT(iter) (iter)->dict
|
#define DICT_ITERATOR_DICT(iter) (iter)->dict
|
/* For linear dictionaries, the index of the last symbol returned; for
|
/* For linear dictionaries, the index of the last symbol returned; for
|
hashed dictionaries, the bucket of the last symbol returned. */
|
hashed dictionaries, the bucket of the last symbol returned. */
|
#define DICT_ITERATOR_INDEX(iter) (iter)->index
|
#define DICT_ITERATOR_INDEX(iter) (iter)->index
|
/* For hashed dictionaries, this points to the last symbol returned;
|
/* For hashed dictionaries, this points to the last symbol returned;
|
otherwise, this is unused. */
|
otherwise, this is unused. */
|
#define DICT_ITERATOR_CURRENT(iter) (iter)->current
|
#define DICT_ITERATOR_CURRENT(iter) (iter)->current
|
|
|
/* Declarations of functions for vectors. */
|
/* Declarations of functions for vectors. */
|
|
|
/* Functions that might work across a range of dictionary types. */
|
/* Functions that might work across a range of dictionary types. */
|
|
|
static void add_symbol_nonexpandable (struct dictionary *dict,
|
static void add_symbol_nonexpandable (struct dictionary *dict,
|
struct symbol *sym);
|
struct symbol *sym);
|
|
|
static void free_obstack (struct dictionary *dict);
|
static void free_obstack (struct dictionary *dict);
|
|
|
/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
|
/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
|
dictionaries. */
|
dictionaries. */
|
|
|
static struct symbol *iterator_first_hashed (const struct dictionary *dict,
|
static struct symbol *iterator_first_hashed (const struct dictionary *dict,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
|
|
static struct symbol *iterator_next_hashed (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,
|
static struct symbol *iter_name_first_hashed (const struct dictionary *dict,
|
const char *name,
|
const char *name,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
|
|
static struct symbol *iter_name_next_hashed (const char *name,
|
static struct symbol *iter_name_next_hashed (const char *name,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
|
|
/* Functions only for DICT_HASHED. */
|
/* Functions only for DICT_HASHED. */
|
|
|
static int size_hashed (const struct dictionary *dict);
|
static int size_hashed (const struct dictionary *dict);
|
|
|
/* Functions only for DICT_HASHED_EXPANDABLE. */
|
/* Functions only for DICT_HASHED_EXPANDABLE. */
|
|
|
static void free_hashed_expandable (struct dictionary *dict);
|
static void free_hashed_expandable (struct dictionary *dict);
|
|
|
static void add_symbol_hashed_expandable (struct dictionary *dict,
|
static void add_symbol_hashed_expandable (struct dictionary *dict,
|
struct symbol *sym);
|
struct symbol *sym);
|
|
|
static int size_hashed_expandable (const struct dictionary *dict);
|
static int size_hashed_expandable (const struct dictionary *dict);
|
|
|
/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
|
/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
|
dictionaries. */
|
dictionaries. */
|
|
|
static struct symbol *iterator_first_linear (const struct dictionary *dict,
|
static struct symbol *iterator_first_linear (const struct dictionary *dict,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
|
|
static struct symbol *iterator_next_linear (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,
|
static struct symbol *iter_name_first_linear (const struct dictionary *dict,
|
const char *name,
|
const char *name,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
|
|
static struct symbol *iter_name_next_linear (const char *name,
|
static struct symbol *iter_name_next_linear (const char *name,
|
struct dict_iterator *iterator);
|
struct dict_iterator *iterator);
|
|
|
static int size_linear (const struct dictionary *dict);
|
static int size_linear (const struct dictionary *dict);
|
|
|
/* Functions only for DICT_LINEAR_EXPANDABLE. */
|
/* Functions only for DICT_LINEAR_EXPANDABLE. */
|
|
|
static void free_linear_expandable (struct dictionary *dict);
|
static void free_linear_expandable (struct dictionary *dict);
|
|
|
static void add_symbol_linear_expandable (struct dictionary *dict,
|
static void add_symbol_linear_expandable (struct dictionary *dict,
|
struct symbol *sym);
|
struct symbol *sym);
|
|
|
/* Various vectors that we'll actually use. */
|
/* Various vectors that we'll actually use. */
|
|
|
static const struct dict_vector dict_hashed_vector =
|
static const struct dict_vector dict_hashed_vector =
|
{
|
{
|
DICT_HASHED, /* type */
|
DICT_HASHED, /* type */
|
free_obstack, /* free */
|
free_obstack, /* free */
|
add_symbol_nonexpandable, /* add_symbol */
|
add_symbol_nonexpandable, /* add_symbol */
|
iterator_first_hashed, /* iterator_first */
|
iterator_first_hashed, /* iterator_first */
|
iterator_next_hashed, /* iterator_next */
|
iterator_next_hashed, /* iterator_next */
|
iter_name_first_hashed, /* iter_name_first */
|
iter_name_first_hashed, /* iter_name_first */
|
iter_name_next_hashed, /* iter_name_next */
|
iter_name_next_hashed, /* iter_name_next */
|
size_hashed, /* size */
|
size_hashed, /* size */
|
};
|
};
|
|
|
static const struct dict_vector dict_hashed_expandable_vector =
|
static const struct dict_vector dict_hashed_expandable_vector =
|
{
|
{
|
DICT_HASHED_EXPANDABLE, /* type */
|
DICT_HASHED_EXPANDABLE, /* type */
|
free_hashed_expandable, /* free */
|
free_hashed_expandable, /* free */
|
add_symbol_hashed_expandable, /* add_symbol */
|
add_symbol_hashed_expandable, /* add_symbol */
|
iterator_first_hashed, /* iterator_first */
|
iterator_first_hashed, /* iterator_first */
|
iterator_next_hashed, /* iterator_next */
|
iterator_next_hashed, /* iterator_next */
|
iter_name_first_hashed, /* iter_name_first */
|
iter_name_first_hashed, /* iter_name_first */
|
iter_name_next_hashed, /* iter_name_next */
|
iter_name_next_hashed, /* iter_name_next */
|
size_hashed_expandable, /* size */
|
size_hashed_expandable, /* size */
|
};
|
};
|
|
|
static const struct dict_vector dict_linear_vector =
|
static const struct dict_vector dict_linear_vector =
|
{
|
{
|
DICT_LINEAR, /* type */
|
DICT_LINEAR, /* type */
|
free_obstack, /* free */
|
free_obstack, /* free */
|
add_symbol_nonexpandable, /* add_symbol */
|
add_symbol_nonexpandable, /* add_symbol */
|
iterator_first_linear, /* iterator_first */
|
iterator_first_linear, /* iterator_first */
|
iterator_next_linear, /* iterator_next */
|
iterator_next_linear, /* iterator_next */
|
iter_name_first_linear, /* iter_name_first */
|
iter_name_first_linear, /* iter_name_first */
|
iter_name_next_linear, /* iter_name_next */
|
iter_name_next_linear, /* iter_name_next */
|
size_linear, /* size */
|
size_linear, /* size */
|
};
|
};
|
|
|
static const struct dict_vector dict_linear_expandable_vector =
|
static const struct dict_vector dict_linear_expandable_vector =
|
{
|
{
|
DICT_LINEAR_EXPANDABLE, /* type */
|
DICT_LINEAR_EXPANDABLE, /* type */
|
free_linear_expandable, /* free */
|
free_linear_expandable, /* free */
|
add_symbol_linear_expandable, /* add_symbol */
|
add_symbol_linear_expandable, /* add_symbol */
|
iterator_first_linear, /* iterator_first */
|
iterator_first_linear, /* iterator_first */
|
iterator_next_linear, /* iterator_next */
|
iterator_next_linear, /* iterator_next */
|
iter_name_first_linear, /* iter_name_first */
|
iter_name_first_linear, /* iter_name_first */
|
iter_name_next_linear, /* iter_name_next */
|
iter_name_next_linear, /* iter_name_next */
|
size_linear, /* size */
|
size_linear, /* size */
|
};
|
};
|
|
|
/* Declarations of helper functions (i.e. ones that don't go into
|
/* Declarations of helper functions (i.e. ones that don't go into
|
vectors). */
|
vectors). */
|
|
|
static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
|
static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
|
|
|
static void insert_symbol_hashed (struct dictionary *dict,
|
static void insert_symbol_hashed (struct dictionary *dict,
|
struct symbol *sym);
|
struct symbol *sym);
|
|
|
static void expand_hashtable (struct dictionary *dict);
|
static void expand_hashtable (struct dictionary *dict);
|
|
|
/* The creation functions. */
|
/* The creation functions. */
|
|
|
/* Create a dictionary implemented via a fixed-size hashtable. All
|
/* Create a dictionary implemented via a fixed-size hashtable. All
|
memory it uses is allocated on OBSTACK; the environment is
|
memory it uses is allocated on OBSTACK; the environment is
|
initialized from SYMBOL_LIST. */
|
initialized from SYMBOL_LIST. */
|
|
|
struct dictionary *
|
struct dictionary *
|
dict_create_hashed (struct obstack *obstack,
|
dict_create_hashed (struct obstack *obstack,
|
const struct pending *symbol_list)
|
const struct pending *symbol_list)
|
{
|
{
|
struct dictionary *retval;
|
struct dictionary *retval;
|
int nsyms = 0, nbuckets, i;
|
int nsyms = 0, nbuckets, i;
|
struct symbol **buckets;
|
struct symbol **buckets;
|
const struct pending *list_counter;
|
const struct pending *list_counter;
|
|
|
retval = obstack_alloc (obstack, sizeof (struct dictionary));
|
retval = obstack_alloc (obstack, sizeof (struct dictionary));
|
DICT_VECTOR (retval) = &dict_hashed_vector;
|
DICT_VECTOR (retval) = &dict_hashed_vector;
|
|
|
/* Calculate the number of symbols, and allocate space for them. */
|
/* Calculate the number of symbols, and allocate space for them. */
|
for (list_counter = symbol_list;
|
for (list_counter = symbol_list;
|
list_counter != NULL;
|
list_counter != NULL;
|
list_counter = list_counter->next)
|
list_counter = list_counter->next)
|
{
|
{
|
nsyms += list_counter->nsyms;
|
nsyms += list_counter->nsyms;
|
}
|
}
|
nbuckets = DICT_HASHTABLE_SIZE (nsyms);
|
nbuckets = DICT_HASHTABLE_SIZE (nsyms);
|
DICT_HASHED_NBUCKETS (retval) = nbuckets;
|
DICT_HASHED_NBUCKETS (retval) = nbuckets;
|
buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
|
buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
|
memset (buckets, 0, nbuckets * sizeof (struct symbol *));
|
memset (buckets, 0, nbuckets * sizeof (struct symbol *));
|
DICT_HASHED_BUCKETS (retval) = buckets;
|
DICT_HASHED_BUCKETS (retval) = buckets;
|
|
|
/* Now fill the buckets. */
|
/* Now fill the buckets. */
|
for (list_counter = symbol_list;
|
for (list_counter = symbol_list;
|
list_counter != NULL;
|
list_counter != NULL;
|
list_counter = list_counter->next)
|
list_counter = list_counter->next)
|
{
|
{
|
for (i = list_counter->nsyms - 1; i >= 0; --i)
|
for (i = list_counter->nsyms - 1; i >= 0; --i)
|
{
|
{
|
insert_symbol_hashed (retval, list_counter->symbol[i]);
|
insert_symbol_hashed (retval, list_counter->symbol[i]);
|
}
|
}
|
}
|
}
|
|
|
return retval;
|
return retval;
|
}
|
}
|
|
|
/* Create a dictionary implemented via a hashtable that grows as
|
/* Create a dictionary implemented via a hashtable that grows as
|
necessary. The dictionary is initially empty; to add symbols to
|
necessary. The dictionary is initially empty; to add symbols to
|
it, call dict_add_symbol(). Call dict_free() when you're done with
|
it, call dict_add_symbol(). Call dict_free() when you're done with
|
it. */
|
it. */
|
|
|
extern struct dictionary *
|
extern struct dictionary *
|
dict_create_hashed_expandable (void)
|
dict_create_hashed_expandable (void)
|
{
|
{
|
struct dictionary *retval;
|
struct dictionary *retval;
|
|
|
retval = xmalloc (sizeof (struct dictionary));
|
retval = xmalloc (sizeof (struct dictionary));
|
DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
|
DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
|
DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
|
DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
|
DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
|
DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
|
sizeof (struct symbol *));
|
sizeof (struct symbol *));
|
DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
|
DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
|
|
|
return retval;
|
return retval;
|
}
|
}
|
|
|
/* Create a dictionary implemented via a fixed-size array. All memory
|
/* Create a dictionary implemented via a fixed-size array. All memory
|
it uses is allocated on OBSTACK; the environment is initialized
|
it uses is allocated on OBSTACK; the environment is initialized
|
from the SYMBOL_LIST. The symbols are ordered in the same order
|
from the SYMBOL_LIST. The symbols are ordered in the same order
|
that they're found in SYMBOL_LIST. */
|
that they're found in SYMBOL_LIST. */
|
|
|
struct dictionary *
|
struct dictionary *
|
dict_create_linear (struct obstack *obstack,
|
dict_create_linear (struct obstack *obstack,
|
const struct pending *symbol_list)
|
const struct pending *symbol_list)
|
{
|
{
|
struct dictionary *retval;
|
struct dictionary *retval;
|
int nsyms = 0, i, j;
|
int nsyms = 0, i, j;
|
struct symbol **syms;
|
struct symbol **syms;
|
const struct pending *list_counter;
|
const struct pending *list_counter;
|
|
|
retval = obstack_alloc (obstack, sizeof (struct dictionary));
|
retval = obstack_alloc (obstack, sizeof (struct dictionary));
|
DICT_VECTOR (retval) = &dict_linear_vector;
|
DICT_VECTOR (retval) = &dict_linear_vector;
|
|
|
/* Calculate the number of symbols, and allocate space for them. */
|
/* Calculate the number of symbols, and allocate space for them. */
|
for (list_counter = symbol_list;
|
for (list_counter = symbol_list;
|
list_counter != NULL;
|
list_counter != NULL;
|
list_counter = list_counter->next)
|
list_counter = list_counter->next)
|
{
|
{
|
nsyms += list_counter->nsyms;
|
nsyms += list_counter->nsyms;
|
}
|
}
|
DICT_LINEAR_NSYMS (retval) = nsyms;
|
DICT_LINEAR_NSYMS (retval) = nsyms;
|
syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
|
syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
|
DICT_LINEAR_SYMS (retval) = syms;
|
DICT_LINEAR_SYMS (retval) = syms;
|
|
|
/* Now fill in the symbols. Start filling in from the back, so as
|
/* Now fill in the symbols. Start filling in from the back, so as
|
to preserve the original order of the symbols. */
|
to preserve the original order of the symbols. */
|
for (list_counter = symbol_list, j = nsyms - 1;
|
for (list_counter = symbol_list, j = nsyms - 1;
|
list_counter != NULL;
|
list_counter != NULL;
|
list_counter = list_counter->next)
|
list_counter = list_counter->next)
|
{
|
{
|
for (i = list_counter->nsyms - 1;
|
for (i = list_counter->nsyms - 1;
|
i >= 0;
|
i >= 0;
|
--i, --j)
|
--i, --j)
|
{
|
{
|
syms[j] = list_counter->symbol[i];
|
syms[j] = list_counter->symbol[i];
|
}
|
}
|
}
|
}
|
|
|
return retval;
|
return retval;
|
}
|
}
|
|
|
/* Create a dictionary implemented via an array that grows as
|
/* Create a dictionary implemented via an array that grows as
|
necessary. The dictionary is initially empty; to add symbols to
|
necessary. The dictionary is initially empty; to add symbols to
|
it, call dict_add_symbol(). Call dict_free() when you're done with
|
it, call dict_add_symbol(). Call dict_free() when you're done with
|
it. */
|
it. */
|
|
|
struct dictionary *
|
struct dictionary *
|
dict_create_linear_expandable (void)
|
dict_create_linear_expandable (void)
|
{
|
{
|
struct dictionary *retval;
|
struct dictionary *retval;
|
|
|
retval = xmalloc (sizeof (struct dictionary));
|
retval = xmalloc (sizeof (struct dictionary));
|
DICT_VECTOR (retval) = &dict_linear_expandable_vector;
|
DICT_VECTOR (retval) = &dict_linear_expandable_vector;
|
DICT_LINEAR_NSYMS (retval) = 0;
|
DICT_LINEAR_NSYMS (retval) = 0;
|
DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
|
DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
|
= DICT_EXPANDABLE_INITIAL_CAPACITY;
|
= DICT_EXPANDABLE_INITIAL_CAPACITY;
|
DICT_LINEAR_SYMS (retval)
|
DICT_LINEAR_SYMS (retval)
|
= xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
|
= xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
|
* sizeof (struct symbol *));
|
* sizeof (struct symbol *));
|
|
|
return retval;
|
return retval;
|
}
|
}
|
|
|
/* The functions providing the dictionary interface. */
|
/* The functions providing the dictionary interface. */
|
|
|
/* Free the memory used by a dictionary that's not on an obstack. (If
|
/* Free the memory used by a dictionary that's not on an obstack. (If
|
any.) */
|
any.) */
|
|
|
void
|
void
|
dict_free (struct dictionary *dict)
|
dict_free (struct dictionary *dict)
|
{
|
{
|
(DICT_VECTOR (dict))->free (dict);
|
(DICT_VECTOR (dict))->free (dict);
|
}
|
}
|
|
|
/* Add SYM to DICT. DICT had better be expandable. */
|
/* Add SYM to DICT. DICT had better be expandable. */
|
|
|
void
|
void
|
dict_add_symbol (struct dictionary *dict, struct symbol *sym)
|
dict_add_symbol (struct dictionary *dict, struct symbol *sym)
|
{
|
{
|
(DICT_VECTOR (dict))->add_symbol (dict, sym);
|
(DICT_VECTOR (dict))->add_symbol (dict, sym);
|
}
|
}
|
|
|
/* Initialize ITERATOR to point at the first symbol in DICT, and
|
/* Initialize ITERATOR to point at the first symbol in DICT, and
|
return that first symbol, or NULL if DICT is empty. */
|
return that first symbol, or NULL if DICT is empty. */
|
|
|
struct symbol *
|
struct symbol *
|
dict_iterator_first (const struct dictionary *dict,
|
dict_iterator_first (const struct dictionary *dict,
|
struct dict_iterator *iterator)
|
struct dict_iterator *iterator)
|
{
|
{
|
return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
|
return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
|
}
|
}
|
|
|
/* Advance ITERATOR, and return the next symbol, or NULL if there are
|
/* Advance ITERATOR, and return the next symbol, or NULL if there are
|
no more symbols. */
|
no more symbols. */
|
|
|
struct symbol *
|
struct symbol *
|
dict_iterator_next (struct dict_iterator *iterator)
|
dict_iterator_next (struct dict_iterator *iterator)
|
{
|
{
|
return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
|
return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
|
->iterator_next (iterator);
|
->iterator_next (iterator);
|
}
|
}
|
|
|
struct symbol *
|
struct symbol *
|
dict_iter_name_first (const struct dictionary *dict,
|
dict_iter_name_first (const struct dictionary *dict,
|
const char *name,
|
const char *name,
|
struct dict_iterator *iterator)
|
struct dict_iterator *iterator)
|
{
|
{
|
return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
|
return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
|
}
|
}
|
|
|
struct symbol *
|
struct symbol *
|
dict_iter_name_next (const char *name, struct dict_iterator *iterator)
|
dict_iter_name_next (const char *name, struct dict_iterator *iterator)
|
{
|
{
|
return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
|
return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
|
->iter_name_next (name, iterator);
|
->iter_name_next (name, iterator);
|
}
|
}
|
|
|
int
|
int
|
dict_size (const struct dictionary *dict)
|
dict_size (const struct dictionary *dict)
|
{
|
{
|
return (DICT_VECTOR (dict))->size (dict);
|
return (DICT_VECTOR (dict))->size (dict);
|
}
|
}
|
|
|
/* Now come functions (well, one function, currently) that are
|
/* Now come functions (well, one function, currently) that are
|
implemented generically by means of the vtable. Typically, they're
|
implemented generically by means of the vtable. Typically, they're
|
rarely used. */
|
rarely used. */
|
|
|
/* Test to see if DICT is empty. */
|
/* Test to see if DICT is empty. */
|
|
|
int
|
int
|
dict_empty (struct dictionary *dict)
|
dict_empty (struct dictionary *dict)
|
{
|
{
|
struct dict_iterator iter;
|
struct dict_iterator iter;
|
|
|
return (dict_iterator_first (dict, &iter) == NULL);
|
return (dict_iterator_first (dict, &iter) == NULL);
|
}
|
}
|
|
|
|
|
/* The functions implementing the dictionary interface. */
|
/* The functions implementing the dictionary interface. */
|
|
|
/* Generic functions, where appropriate. */
|
/* Generic functions, where appropriate. */
|
|
|
static void
|
static void
|
free_obstack (struct dictionary *dict)
|
free_obstack (struct dictionary *dict)
|
{
|
{
|
/* Do nothing! */
|
/* Do nothing! */
|
}
|
}
|
|
|
static void
|
static void
|
add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
|
add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
|
{
|
{
|
internal_error (__FILE__, __LINE__,
|
internal_error (__FILE__, __LINE__,
|
_("dict_add_symbol: non-expandable dictionary"));
|
_("dict_add_symbol: non-expandable dictionary"));
|
}
|
}
|
|
|
/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
|
/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
|
|
|
static struct symbol *
|
static struct symbol *
|
iterator_first_hashed (const struct dictionary *dict,
|
iterator_first_hashed (const struct dictionary *dict,
|
struct dict_iterator *iterator)
|
struct dict_iterator *iterator)
|
{
|
{
|
DICT_ITERATOR_DICT (iterator) = dict;
|
DICT_ITERATOR_DICT (iterator) = dict;
|
DICT_ITERATOR_INDEX (iterator) = -1;
|
DICT_ITERATOR_INDEX (iterator) = -1;
|
return iterator_hashed_advance (iterator);
|
return iterator_hashed_advance (iterator);
|
}
|
}
|
|
|
static struct symbol *
|
static struct symbol *
|
iterator_next_hashed (struct dict_iterator *iterator)
|
iterator_next_hashed (struct dict_iterator *iterator)
|
{
|
{
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
struct symbol *next;
|
struct symbol *next;
|
|
|
next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
|
next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
|
|
|
if (next == NULL)
|
if (next == NULL)
|
return iterator_hashed_advance (iterator);
|
return iterator_hashed_advance (iterator);
|
else
|
else
|
{
|
{
|
DICT_ITERATOR_CURRENT (iterator) = next;
|
DICT_ITERATOR_CURRENT (iterator) = next;
|
return next;
|
return next;
|
}
|
}
|
}
|
}
|
|
|
static struct symbol *
|
static struct symbol *
|
iterator_hashed_advance (struct dict_iterator *iterator)
|
iterator_hashed_advance (struct dict_iterator *iterator)
|
{
|
{
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
int nbuckets = DICT_HASHED_NBUCKETS (dict);
|
int nbuckets = DICT_HASHED_NBUCKETS (dict);
|
int i;
|
int i;
|
|
|
for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
|
for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
|
{
|
{
|
struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
|
struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
|
|
|
if (sym != NULL)
|
if (sym != NULL)
|
{
|
{
|
DICT_ITERATOR_INDEX (iterator) = i;
|
DICT_ITERATOR_INDEX (iterator) = i;
|
DICT_ITERATOR_CURRENT (iterator) = sym;
|
DICT_ITERATOR_CURRENT (iterator) = sym;
|
return sym;
|
return sym;
|
}
|
}
|
}
|
}
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
static struct symbol *
|
static struct symbol *
|
iter_name_first_hashed (const struct dictionary *dict,
|
iter_name_first_hashed (const struct dictionary *dict,
|
const char *name,
|
const char *name,
|
struct dict_iterator *iterator)
|
struct dict_iterator *iterator)
|
{
|
{
|
unsigned int hash_index
|
unsigned int hash_index
|
= msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
|
= msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
|
struct symbol *sym;
|
struct symbol *sym;
|
|
|
DICT_ITERATOR_DICT (iterator) = dict;
|
DICT_ITERATOR_DICT (iterator) = dict;
|
|
|
/* Loop through the symbols in the given bucket, breaking when SYM
|
/* Loop through the symbols in the given bucket, breaking when SYM
|
first matches. If SYM never matches, it will be set to NULL;
|
first matches. If SYM never matches, it will be set to NULL;
|
either way, we have the right return value. */
|
either way, we have the right return value. */
|
|
|
for (sym = DICT_HASHED_BUCKET (dict, hash_index);
|
for (sym = DICT_HASHED_BUCKET (dict, hash_index);
|
sym != NULL;
|
sym != NULL;
|
sym = sym->hash_next)
|
sym = sym->hash_next)
|
{
|
{
|
/* Warning: the order of arguments to strcmp_iw matters! */
|
/* Warning: the order of arguments to strcmp_iw matters! */
|
if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
|
if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
|
{
|
{
|
break;
|
break;
|
}
|
}
|
|
|
}
|
}
|
|
|
DICT_ITERATOR_CURRENT (iterator) = sym;
|
DICT_ITERATOR_CURRENT (iterator) = sym;
|
return sym;
|
return sym;
|
}
|
}
|
|
|
static struct symbol *
|
static struct symbol *
|
iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
|
iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
|
{
|
{
|
struct symbol *next;
|
struct symbol *next;
|
|
|
for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
|
for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
|
next != NULL;
|
next != NULL;
|
next = next->hash_next)
|
next = next->hash_next)
|
{
|
{
|
if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
|
if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
|
break;
|
break;
|
}
|
}
|
|
|
DICT_ITERATOR_CURRENT (iterator) = next;
|
DICT_ITERATOR_CURRENT (iterator) = next;
|
|
|
return next;
|
return next;
|
}
|
}
|
|
|
/* Insert SYM into DICT. */
|
/* Insert SYM into DICT. */
|
|
|
static void
|
static void
|
insert_symbol_hashed (struct dictionary *dict,
|
insert_symbol_hashed (struct dictionary *dict,
|
struct symbol *sym)
|
struct symbol *sym)
|
{
|
{
|
unsigned int hash_index;
|
unsigned int hash_index;
|
struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
|
struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
|
|
|
hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
|
hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
|
% DICT_HASHED_NBUCKETS (dict));
|
% DICT_HASHED_NBUCKETS (dict));
|
sym->hash_next = buckets[hash_index];
|
sym->hash_next = buckets[hash_index];
|
buckets[hash_index] = sym;
|
buckets[hash_index] = sym;
|
}
|
}
|
|
|
static int
|
static int
|
size_hashed (const struct dictionary *dict)
|
size_hashed (const struct dictionary *dict)
|
{
|
{
|
return DICT_HASHED_NBUCKETS (dict);
|
return DICT_HASHED_NBUCKETS (dict);
|
}
|
}
|
|
|
/* Functions only for DICT_HASHED_EXPANDABLE. */
|
/* Functions only for DICT_HASHED_EXPANDABLE. */
|
|
|
static void
|
static void
|
free_hashed_expandable (struct dictionary *dict)
|
free_hashed_expandable (struct dictionary *dict)
|
{
|
{
|
xfree (DICT_HASHED_BUCKETS (dict));
|
xfree (DICT_HASHED_BUCKETS (dict));
|
xfree (dict);
|
xfree (dict);
|
}
|
}
|
|
|
static void
|
static void
|
add_symbol_hashed_expandable (struct dictionary *dict,
|
add_symbol_hashed_expandable (struct dictionary *dict,
|
struct symbol *sym)
|
struct symbol *sym)
|
{
|
{
|
int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
|
int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
|
|
|
if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
|
if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
|
expand_hashtable (dict);
|
expand_hashtable (dict);
|
|
|
insert_symbol_hashed (dict, sym);
|
insert_symbol_hashed (dict, sym);
|
DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
|
DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
|
}
|
}
|
|
|
static int
|
static int
|
size_hashed_expandable (const struct dictionary *dict)
|
size_hashed_expandable (const struct dictionary *dict)
|
{
|
{
|
return DICT_HASHED_EXPANDABLE_NSYMS (dict);
|
return DICT_HASHED_EXPANDABLE_NSYMS (dict);
|
}
|
}
|
|
|
static void
|
static void
|
expand_hashtable (struct dictionary *dict)
|
expand_hashtable (struct dictionary *dict)
|
{
|
{
|
int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
|
int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
|
struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
|
struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
|
int new_nbuckets = 2*old_nbuckets + 1;
|
int new_nbuckets = 2*old_nbuckets + 1;
|
struct symbol **new_buckets = xcalloc (new_nbuckets,
|
struct symbol **new_buckets = xcalloc (new_nbuckets,
|
sizeof (struct symbol *));
|
sizeof (struct symbol *));
|
int i;
|
int i;
|
|
|
DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
|
DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
|
DICT_HASHED_BUCKETS (dict) = new_buckets;
|
DICT_HASHED_BUCKETS (dict) = new_buckets;
|
|
|
for (i = 0; i < old_nbuckets; ++i) {
|
for (i = 0; i < old_nbuckets; ++i) {
|
struct symbol *sym, *next_sym;
|
struct symbol *sym, *next_sym;
|
|
|
sym = old_buckets[i];
|
sym = old_buckets[i];
|
if (sym != NULL) {
|
if (sym != NULL) {
|
for (next_sym = sym->hash_next;
|
for (next_sym = sym->hash_next;
|
next_sym != NULL;
|
next_sym != NULL;
|
next_sym = sym->hash_next) {
|
next_sym = sym->hash_next) {
|
insert_symbol_hashed (dict, sym);
|
insert_symbol_hashed (dict, sym);
|
sym = next_sym;
|
sym = next_sym;
|
}
|
}
|
|
|
insert_symbol_hashed (dict, sym);
|
insert_symbol_hashed (dict, sym);
|
}
|
}
|
}
|
}
|
|
|
xfree (old_buckets);
|
xfree (old_buckets);
|
}
|
}
|
|
|
/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
|
/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
|
|
|
static struct symbol *
|
static struct symbol *
|
iterator_first_linear (const struct dictionary *dict,
|
iterator_first_linear (const struct dictionary *dict,
|
struct dict_iterator *iterator)
|
struct dict_iterator *iterator)
|
{
|
{
|
DICT_ITERATOR_DICT (iterator) = dict;
|
DICT_ITERATOR_DICT (iterator) = dict;
|
DICT_ITERATOR_INDEX (iterator) = 0;
|
DICT_ITERATOR_INDEX (iterator) = 0;
|
return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
|
return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
|
}
|
}
|
|
|
static struct symbol *
|
static struct symbol *
|
iterator_next_linear (struct dict_iterator *iterator)
|
iterator_next_linear (struct dict_iterator *iterator)
|
{
|
{
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
|
|
if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
|
if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
|
return NULL;
|
return NULL;
|
else
|
else
|
return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
|
return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
|
}
|
}
|
|
|
static struct symbol *
|
static struct symbol *
|
iter_name_first_linear (const struct dictionary *dict,
|
iter_name_first_linear (const struct dictionary *dict,
|
const char *name,
|
const char *name,
|
struct dict_iterator *iterator)
|
struct dict_iterator *iterator)
|
{
|
{
|
DICT_ITERATOR_DICT (iterator) = dict;
|
DICT_ITERATOR_DICT (iterator) = dict;
|
DICT_ITERATOR_INDEX (iterator) = -1;
|
DICT_ITERATOR_INDEX (iterator) = -1;
|
|
|
return iter_name_next_linear (name, iterator);
|
return iter_name_next_linear (name, iterator);
|
}
|
}
|
|
|
static struct symbol *
|
static struct symbol *
|
iter_name_next_linear (const char *name, struct dict_iterator *iterator)
|
iter_name_next_linear (const char *name, struct dict_iterator *iterator)
|
{
|
{
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
|
int i, nsyms = DICT_LINEAR_NSYMS (dict);
|
int i, nsyms = DICT_LINEAR_NSYMS (dict);
|
struct symbol *sym, *retval = NULL;
|
struct symbol *sym, *retval = NULL;
|
|
|
for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
|
for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
|
{
|
{
|
sym = DICT_LINEAR_SYM (dict, i);
|
sym = DICT_LINEAR_SYM (dict, i);
|
if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
|
if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
|
{
|
{
|
retval = sym;
|
retval = sym;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
DICT_ITERATOR_INDEX (iterator) = i;
|
DICT_ITERATOR_INDEX (iterator) = i;
|
|
|
return retval;
|
return retval;
|
}
|
}
|
|
|
static int
|
static int
|
size_linear (const struct dictionary *dict)
|
size_linear (const struct dictionary *dict)
|
{
|
{
|
return DICT_LINEAR_NSYMS (dict);
|
return DICT_LINEAR_NSYMS (dict);
|
}
|
}
|
|
|
/* Functions only for DICT_LINEAR_EXPANDABLE. */
|
/* Functions only for DICT_LINEAR_EXPANDABLE. */
|
|
|
static void
|
static void
|
free_linear_expandable (struct dictionary *dict)
|
free_linear_expandable (struct dictionary *dict)
|
{
|
{
|
xfree (DICT_LINEAR_SYMS (dict));
|
xfree (DICT_LINEAR_SYMS (dict));
|
xfree (dict);
|
xfree (dict);
|
}
|
}
|
|
|
|
|
static void
|
static void
|
add_symbol_linear_expandable (struct dictionary *dict,
|
add_symbol_linear_expandable (struct dictionary *dict,
|
struct symbol *sym)
|
struct symbol *sym)
|
{
|
{
|
int nsyms = ++DICT_LINEAR_NSYMS (dict);
|
int nsyms = ++DICT_LINEAR_NSYMS (dict);
|
|
|
/* Do we have enough room? If not, grow it. */
|
/* Do we have enough room? If not, grow it. */
|
if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) {
|
if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) {
|
DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
|
DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
|
DICT_LINEAR_SYMS (dict)
|
DICT_LINEAR_SYMS (dict)
|
= xrealloc (DICT_LINEAR_SYMS (dict),
|
= xrealloc (DICT_LINEAR_SYMS (dict),
|
DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
|
DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
|
* sizeof (struct symbol *));
|
* sizeof (struct symbol *));
|
}
|
}
|
|
|
DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
|
DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
|
}
|
}
|
|
|
