#include "defs.h"
#include "gdb_obstack.h"
#include "symtab.h"
#include "buildsym.h"
#include "gdb_assert.h"
#include "dictionary.h"
enum dict_type
{
DICT_HASHED,
DICT_HASHED_EXPANDABLE,
DICT_LINEAR,
DICT_LINEAR_EXPANDABLE
};
struct dict_vector
{
enum dict_type type;
void (*free) (struct dictionary *dict);
void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
struct symbol *(*iterator_first) (const struct dictionary *dict,
struct dict_iterator *iterator);
struct symbol *(*iterator_next) (struct dict_iterator *iterator);
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);
int (*size) (const struct dictionary *dict);
};
struct dictionary_hashed
{
int nbuckets;
struct symbol **buckets;
};
struct dictionary_hashed_expandable
{
int nbuckets;
struct symbol **buckets;
int nsyms;
};
struct dictionary_linear
{
int nsyms;
struct symbol **syms;
};
struct dictionary_linear_expandable
{
int nsyms;
struct symbol **syms;
int capacity;
};
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;
};
#define DICT_VECTOR(d) (d)->vector
#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
#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
#define DICT_EXPANDABLE_INITIAL_CAPACITY 10
#define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
#define DICT_ITERATOR_DICT(iter) (iter)->dict
#define DICT_ITERATOR_INDEX(iter) (iter)->index
#define DICT_ITERATOR_CURRENT(iter) (iter)->current
static void add_symbol_nonexpandable (struct dictionary *dict,
struct symbol *sym);
static void free_obstack (struct dictionary *dict);
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);
static int size_hashed (const struct dictionary *dict);
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);
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);
static void free_linear_expandable (struct dictionary *dict);
static void add_symbol_linear_expandable (struct dictionary *dict,
struct symbol *sym);
static const struct dict_vector dict_hashed_vector =
{
DICT_HASHED,
free_obstack,
add_symbol_nonexpandable,
iterator_first_hashed,
iterator_next_hashed,
iter_name_first_hashed,
iter_name_next_hashed,
size_hashed,
};
static const struct dict_vector dict_hashed_expandable_vector =
{
DICT_HASHED_EXPANDABLE,
free_hashed_expandable,
add_symbol_hashed_expandable,
iterator_first_hashed,
iterator_next_hashed,
iter_name_first_hashed,
iter_name_next_hashed,
size_hashed_expandable,
};
static const struct dict_vector dict_linear_vector =
{
DICT_LINEAR,
free_obstack,
add_symbol_nonexpandable,
iterator_first_linear,
iterator_next_linear,
iter_name_first_linear,
iter_name_next_linear,
size_linear,
};
static const struct dict_vector dict_linear_expandable_vector =
{
DICT_LINEAR_EXPANDABLE,
free_linear_expandable,
add_symbol_linear_expandable,
iterator_first_linear,
iterator_next_linear,
iter_name_first_linear,
iter_name_next_linear,
size_linear,
};
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);
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;
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;
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;
}
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;
}
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;
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;
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;
}
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;
}
void
dict_free (struct dictionary *dict)
{
(DICT_VECTOR (dict))->free (dict);
}
void
dict_add_symbol (struct dictionary *dict, struct symbol *sym)
{
(DICT_VECTOR (dict))->add_symbol (dict, sym);
}
struct symbol *
dict_iterator_first (const struct dictionary *dict,
struct dict_iterator *iterator)
{
return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
}
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);
}
int
dict_empty (struct dictionary *dict)
{
struct dict_iterator iter;
return (dict_iterator_first (dict, &iter) == NULL);
}
static void
free_obstack (struct dictionary *dict)
{
}
static void
add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
{
internal_error (__FILE__, __LINE__,
_("dict_add_symbol: non-expandable dictionary"));
}
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;
for (sym = DICT_HASHED_BUCKET (dict, hash_index);
sym != NULL;
sym = sym->hash_next)
{
if (strcmp_iw (SYMBOL_SEARCH_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_SEARCH_NAME (next), name) == 0)
break;
}
DICT_ITERATOR_CURRENT (iterator) = next;
return next;
}
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_SEARCH_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);
}
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);
}
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_SEARCH_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);
}
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);
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;
}