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.

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;