aboutsummaryrefslogtreecommitdiff
path: root/src/symtab.c
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org.ua>2016-08-25 16:06:58 +0300
committerSergey Poznyakoff <gray@gnu.org.ua>2016-08-25 16:06:58 +0300
commitc2f02c56a38a3e6d50b8ca2081db9d2de658b8ed (patch)
treea6c80fd81a6b5aad899d8fb0e3e41ece650eed9b /src/symtab.c
parent102d1b9c1a94548dfa0c498845c77933db6a7738 (diff)
downloadgrecs-c2f02c56a38a3e6d50b8ca2081db9d2de658b8ed.tar.gz
grecs-c2f02c56a38a3e6d50b8ca2081db9d2de658b8ed.tar.bz2
symtabs: allow to modify the list during iteration over it.
* include/grecs/list.h (grecs_list_remove): New proto. * include/grecs/symtab.h (grecs_symtab_count_entries): Rename to grecs_symtab_count. * src/list.c (grecs_list_remove): New function. (grecs_list_remove_tail, grecs_list_clear) (grecs_list_locate,grecs_list_index): Treat NULL list as empty list. * src/symtab.c: Defer table modifications during iteration (symtab_defer_type): New enum. (grecs_symtab)<elcount,itr_level,defer_list>: New members. (symtab_defer_op): New static function. (grecs_symtab_remove): When called during iteration, add the entry to the defer_del deferment list, unless it is already in defer_add, in which case remove it from there. Update elcount. (grecs_symtab_lookup_or_install): Defer addition when iterating. Update elcount. (grecs_symtab_clear): Reset elcount to 0. (grecs_symtab_create): Initialize elcount. (grecs_symtab_foreach): Process deferred modifications.
Diffstat (limited to 'src/symtab.c')
-rw-r--r--src/symtab.c113
1 files changed, 91 insertions, 22 deletions
diff --git a/src/symtab.c b/src/symtab.c
index 540ea0f..3647a81 100644
--- a/src/symtab.c
+++ b/src/symtab.c
@@ -33,16 +33,36 @@ static unsigned int hash_size[] = {
/* |max_rehash| keeps the number of entries in |hash_size| table. */
static unsigned int max_rehash = sizeof(hash_size) / sizeof(hash_size[0]);
+enum symtab_defer_type {
+ defer_add,
+ defer_del
+};
+
struct grecs_symtab {
int flags;
- unsigned int hash_num; /* Index to hash_size table */
- size_t elsize; /* Size of an element */
- struct grecs_syment **tab;
- unsigned (*hash_fun)(void *, unsigned long hash_num);
+ unsigned int hash_num; /* Index to hash_size table */
+ size_t elsize; /* Size of an element */
+ size_t elcount; /* Number of elements in use */
+ struct grecs_syment **tab; /* Table of element pointers */
+
+ /* Functions that can be overridden when creating the symtab: */
+ unsigned (*hash_fun)(void *, unsigned long);
int (*cmp_fun)(const void *, const void *);
int (*copy_fun)(void *, void *);
- void *(*syment_alloc_fun)(size_t size);
+ void *(*syment_alloc_fun)(size_t);
void (*syment_free_fun) (void *);
+
+ /* Support for deferred operations. When an insertion or deletion
+ is requested while the symtab is being iterated over, this operation
+ is deferred until the iteration is finished. */
+
+ /* Iteration level. Gets increased upon entry to grecs_symtab_foreach,
+ and decreased right before leaving it. */
+ unsigned int itr_level;
+ /* Two deferment lists keep track of the deferred additions and
+ removals:
+ */
+ grecs_list_ptr_t defer_list[2];
};
static void
@@ -72,7 +92,17 @@ syment_alloc(struct grecs_symtab *st, void *key)
}
return ent;
}
-
+
+static void
+symtab_defer_op(struct grecs_symtab *st, enum symtab_defer_type type,
+ struct grecs_syment *ent)
+{
+ if (!st->defer_list[type]) {
+ st->defer_list[type] = grecs_list_create();
+ st->defer_list[type]->cmp = st->cmp_fun;
+ }
+ grecs_list_append(st->defer_list[type], ent);
+}
unsigned
grecs_hash_string(const char *name, unsigned long hashsize)
@@ -101,8 +131,8 @@ grecs_hash_string_ci(const char *name, unsigned long hashsize)
static unsigned
def_hash(void *data, unsigned long hashsize)
{
- struct grecs_syment *sym = data;
- return grecs_hash_string(sym->name, hashsize);
+ struct grecs_syment *sym = data;
+ return grecs_hash_string(sym->name, hashsize);
}
static int
@@ -218,6 +248,11 @@ grecs_symtab_remove(struct grecs_symtab *st, void *elt)
unsigned int pos, i, j, r;
struct grecs_syment *entry;
+ if (st->itr_level) {
+ if (grecs_list_remove(st->defer_list[defer_add], elt) == 0)
+ return 0;
+ }
+
pos = st->hash_fun(elt, hash_size[st->hash_num]);
for (i = pos; (entry = st->tab[i]);) {
if (st->cmp_fun(entry, elt) == 0)
@@ -231,7 +266,14 @@ grecs_symtab_remove(struct grecs_symtab *st, void *elt)
if (!entry)
return ENOENT;
+ if (st->itr_level) {
+ symtab_defer_op(st, defer_del, entry);
+ //FIXME: mark the entry as deleted
+ return 0;
+ }
+
syment_free(st, entry);
+ st->elcount--;
for (;;) {
st->tab[i] = NULL;
@@ -312,10 +354,20 @@ grecs_symtab_lookup_or_install(struct grecs_symtab *st, void *key,
errno = ENOMEM;
return NULL;
}
- st->tab[i] = ent;
+ if (st->itr_level) {
+ symtab_defer_op(st, defer_add, ent);
+ } else {
+ st->tab[i] = ent;
+ st->elcount++;
+ }
return ent;
} else
return st->tab[i];
+ } else if (rc == ENOENT && st->itr_level) {
+ void *ptr = grecs_list_locate(st->defer_list[defer_add], key);
+ if (ptr)
+ return ptr;
+ rc = ENOENT;
}
errno = rc;
return NULL;
@@ -337,6 +389,7 @@ grecs_symtab_clear(struct grecs_symtab *st)
st->tab[i] = NULL;
}
}
+ st->elcount = 0;
}
struct grecs_symtab *
@@ -350,6 +403,7 @@ grecs_symtab_create(size_t elsize,
if (st) {
memset(st, 0, sizeof(*st));
st->elsize = elsize;
+ st->elcount = 0;
st->hash_fun = hash_fun ? hash_fun : def_hash;
st->cmp_fun = cmp_fun ? cmp_fun : def_cmp;
st->copy_fun = copy_fun ? copy_fun : def_copy;
@@ -381,39 +435,54 @@ grecs_symtab_free(struct grecs_symtab *st)
{
if (st) {
grecs_symtab_clear(st);
+ grecs_list_free(st->defer_list[defer_add]);
+ grecs_list_free(st->defer_list[defer_del]);
free(st->tab);
free(st);
}
}
size_t
-grecs_symtab_count_entries(struct grecs_symtab *st)
+grecs_symtab_count(struct grecs_symtab *st)
{
- unsigned i;
- size_t count = 0;
-
- for (i = 0; i < hash_size[st->hash_num]; i++)
- if (st->tab[i])
- count++;
- return count;
+ return st->elcount;
}
int
-grecs_symtab_enumerate(struct grecs_symtab *st, grecs_symtab_enumerator_t fun,
- void *data)
+grecs_symtab_foreach(struct grecs_symtab *st, grecs_symtab_enumerator_t fun,
+ void *data)
{
unsigned i;
-
+ struct grecs_syment *ep;
+
if (!st)
return 0;
+
+ ++st->itr_level;
+
for (i = 0; i < hash_size[st->hash_num]; i++) {
- struct grecs_syment *ep = st->tab[i];
- if (ep) {
+ ep = st->tab[i];
+ if (ep && !grecs_list_locate(st->defer_list[defer_del], ep)) {
int rc = fun(ep, data);
if (rc)
return rc;
}
}
+
+ if (--st->itr_level == 0) {
+ while ((ep = grecs_list_pop(st->defer_list[defer_del])) != NULL)
+ grecs_symtab_remove(st, ep);
+
+ while ((ep = grecs_list_pop(st->defer_list[defer_add])) != NULL) {
+ int install = 1;
+ if (grecs_symtab_get_index(&i, st, ep,
+ &install) == 0) {
+ st->tab[i] = ep;
+ st->elcount++;
+ }
+ }
+ }
+
return 0;
}

Return to:

Send suggestions and report system problems to the System administrator.