From c2f02c56a38a3e6d50b8ca2081db9d2de658b8ed Mon Sep 17 00:00:00 2001 From: Sergey Poznyakoff Date: Thu, 25 Aug 2016 16:06:58 +0300 Subject: 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): 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. --- src/list.c | 84 +++++++++++++++++++++++++++++++------------- src/symtab.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++------------ 2 files changed, 150 insertions(+), 47 deletions(-) (limited to 'src') 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) @@ -194,7 +226,9 @@ void * 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; @@ -219,7 +253,7 @@ grecs_list_compare(struct grecs_list *a, struct grecs_list *b) cmp = a->cmp ? a->cmp : _ptrcmp; 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; return 0; 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; } -- cgit v1.2.1