summaryrefslogtreecommitdiffabout
path: root/src
authorSergey Poznyakoff <gray@gnu.org.ua>2016-08-25 13:06:58 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2016-08-25 13:06:58 (GMT)
commitc2f02c56a38a3e6d50b8ca2081db9d2de658b8ed (patch) (side-by-side diff)
treea6c80fd81a6b5aad899d8fb0e3e41ece650eed9b /src
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') (more/less context) (show whitespace changes)
-rw-r--r--src/list.c80
-rw-r--r--src/symtab.c97
2 files changed, 140 insertions, 37 deletions
diff --git a/src/list.c b/src/list.c
index b2d9f13..afd1b5d 100644
--- a/src/list.c
+++ b/src/list.c
@@ -86,6 +86,46 @@ grecs_list_remove_entry(struct grecs_list *lp, struct grecs_list_entry *ent)
lp->count--;
}
+void *
+grecs_list_remove_tail(struct grecs_list *lp)
+{
+ void *data;
+ struct grecs_list_entry *ep;
+
+ if (!lp || !lp->tail)
+ return NULL;
+ ep = lp->tail;
+ data = lp->tail->data;
+ grecs_list_remove_entry(lp, ep);
+ return data;
+}
+
+static int
+_ptrcmp(const void *a, const void *b)
+{
+ return a != b;
+}
+
+int
+grecs_list_remove(struct grecs_list *lp, void *data)
+{
+ struct grecs_list_entry *ep;
+ int (*cmp)(const void *, const void *);
+
+
+ if (!lp)
+ return 1;
+
+ cmp = lp->cmp ? lp->cmp : _ptrcmp;
+ for (ep = lp->head; ep; ep = ep->next) {
+ if (cmp(ep->data, data) == 0) {
+ grecs_list_remove_entry(lp, ep);
+ return 0;
+ }
+ }
+ return 1;
+}
+
void
grecs_list_append(struct grecs_list *lp, void *val)
{
@@ -123,7 +163,11 @@ void *
grecs_list_pop(struct grecs_list *lp)
{
void *data;
- struct grecs_list_entry *ep = lp->head;
+ struct grecs_list_entry *ep;
+
+ if (!lp)
+ return NULL;
+ ep = lp->head;
if (ep) {
data = ep->data;
grecs_list_remove_entry(lp, ep);
@@ -132,25 +176,14 @@ grecs_list_pop(struct grecs_list *lp)
return data;
}
-void *
-grecs_list_remove_tail(struct grecs_list *lp)
-{
- void *data;
- struct grecs_list_entry *ep;
-
- if (!lp->tail)
- return NULL;
- ep = lp->tail;
- data = lp->tail->data;
- grecs_list_remove_entry(lp, ep);
- return data;
-}
-
void
grecs_list_clear(struct grecs_list *lp)
{
- struct grecs_list_entry *ep = lp->head;
+ struct grecs_list_entry *ep;
+ if (!lp)
+ return;
+ ep = lp->head;
while (ep) {
struct grecs_list_entry *next = ep->next;
if (lp->free_entry)
@@ -171,17 +204,16 @@ grecs_list_free(struct grecs_list *lp)
}
}
-static int
-_ptrcmp(const void *a, const void *b)
-{
- return a != b;
-}
-
void *
grecs_list_locate(struct grecs_list *lp, void *data)
{
struct grecs_list_entry *ep;
- int (*cmp)(const void *, const void *) = lp->cmp ? lp->cmp : _ptrcmp;
+ int (*cmp)(const void *, const void *);
+
+ if (!lp)
+ return NULL;
+
+ cmp = lp->cmp ? lp->cmp : _ptrcmp;
for (ep = lp->head; ep; ep = ep->next) {
if (cmp(ep->data, data) == 0)
@@ -195,6 +227,8 @@ grecs_list_index(struct grecs_list *lp, size_t idx)
{
struct grecs_list_entry *ep;
+ if (!lp)
+ return NULL;
for (ep = lp->head; ep && idx; ep = ep->next, idx--)
;
return ep ? ep->data : NULL;
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);
+ 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
@@ -73,6 +93,16 @@ 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)
@@ -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;
}
+ 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,
+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.