1 files changed, 91 insertions, 22 deletions

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