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, 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;