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) (ignore whitespace changes)
-rw-r--r--src/list.c84
-rw-r--r--src/symtab.c113
2 files changed, 150 insertions, 47 deletions
diff --git a/src/list.c b/src/list.c
index b2d9f13..afd1b5d 100644
--- a/src/list.c
+++ b/src/list.c
@@ -88,2 +88,42 @@ grecs_list_remove_entry(struct grecs_list *lp, struct grecs_list_entry *ent)
+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
@@ -125,3 +165,7 @@ 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) {
@@ -134,16 +178,2 @@ grecs_list_pop(struct grecs_list *lp)
-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
@@ -151,4 +181,7 @@ 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) {
@@ -173,8 +206,2 @@ grecs_list_free(struct grecs_list *lp)
-static int
-_ptrcmp(const void *a, const void *b)
-{
- return a != b;
-}
-
void *
@@ -183,3 +210,8 @@ 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;
@@ -196,3 +228,5 @@ 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--)
@@ -221,3 +255,3 @@ grecs_list_compare(struct grecs_list *a, struct grecs_list *b)
for (ap = a->head, bp = b->head; ap; ap = ap->next, bp = bp->next)
- if (cmp (ap->data, bp->data))
+ if (cmp(ap->data, bp->data))
return 1;
diff --git a/src/symtab.c b/src/symtab.c
index 540ea0f..3647a81 100644
--- a/src/symtab.c
+++ b/src/symtab.c
@@ -35,12 +35,32 @@ 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];
};
@@ -74,3 +94,13 @@ syment_alloc(struct grecs_symtab *st, void *key)
}
-
+
+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);
+}
@@ -103,4 +133,4 @@ 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);
}
@@ -220,2 +250,7 @@ grecs_symtab_remove(struct grecs_symtab *st, void *elt)
+ 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]);
@@ -233,3 +268,10 @@ grecs_symtab_remove(struct grecs_symtab *st, void *elt)
+ 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--;
@@ -314,3 +356,8 @@ grecs_symtab_lookup_or_install(struct grecs_symtab *st, void *key,
}
- st->tab[i] = ent;
+ if (st->itr_level) {
+ symtab_defer_op(st, defer_add, ent);
+ } else {
+ st->tab[i] = ent;
+ st->elcount++;
+ }
return ent;
@@ -318,2 +365,7 @@ grecs_symtab_lookup_or_install(struct grecs_symtab *st, void *key,
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;
}
@@ -339,2 +391,3 @@ grecs_symtab_clear(struct grecs_symtab *st)
}
+ st->elcount = 0;
}
@@ -352,2 +405,3 @@ grecs_symtab_create(size_t elsize,
st->elsize = elsize;
+ st->elcount = 0;
st->hash_fun = hash_fun ? hash_fun : def_hash;
@@ -383,2 +437,4 @@ grecs_symtab_free(struct grecs_symtab *st)
grecs_symtab_clear(st);
+ grecs_list_free(st->defer_list[defer_add]);
+ grecs_list_free(st->defer_list[defer_del]);
free(st->tab);
@@ -389,11 +445,5 @@ grecs_symtab_free(struct grecs_symtab *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;
}
@@ -401,12 +451,16 @@ grecs_symtab_count_entries(struct grecs_symtab *st)
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);
@@ -416,2 +470,17 @@ grecs_symtab_enumerate(struct grecs_symtab *st, grecs_symtab_enumerator_t fun,
}
+
+ 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.