aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/grecs/list.h1
-rw-r--r--include/grecs/symtab.h6
-rw-r--r--src/list.c84
-rw-r--r--src/symtab.c113
4 files changed, 154 insertions, 50 deletions
diff --git a/include/grecs/list.h b/include/grecs/list.h
index a5840db..f950176 100644
--- a/include/grecs/list.h
+++ b/include/grecs/list.h
@@ -41,6 +41,7 @@ void *grecs_list_locate(grecs_list_ptr_t, void *);
void *grecs_list_index(grecs_list_ptr_t, size_t);
void *grecs_list_remove_tail(grecs_list_ptr_t);
void grecs_list_remove_entry(grecs_list_ptr_t, grecs_list_entry_ptr_t);
+int grecs_list_remove(struct grecs_list *lp, void *data);
void grecs_list_clear(grecs_list_ptr_t);
void grecs_list_free(grecs_list_ptr_t);
void grecs_list_add(grecs_list_ptr_t, grecs_list_ptr_t);
diff --git a/include/grecs/symtab.h b/include/grecs/symtab.h
index 3008b17..e079ea5 100644
--- a/include/grecs/symtab.h
+++ b/include/grecs/symtab.h
@@ -42,10 +42,10 @@ grecs_symtab_ptr_t grecs_symtab_create_default(size_t elsize);
void grecs_symtab_free(grecs_symtab_ptr_t pst);
int grecs_symtab_remove(grecs_symtab_ptr_t st, void *elt);
int grecs_symtab_replace(grecs_symtab_ptr_t st, void *ent, void **old_ent);
-int grecs_symtab_enumerate(grecs_symtab_ptr_t st,
- grecs_symtab_enumerator_t fun, void *data);
+int grecs_symtab_foreach(grecs_symtab_ptr_t st,
+ grecs_symtab_enumerator_t fun, void *data);
-size_t grecs_symtab_count_entries(grecs_symtab_ptr_t st);
+size_t grecs_symtab_count(grecs_symtab_ptr_t st);
unsigned grecs_hash_string(const char *name, unsigned long hashsize);
unsigned grecs_hash_string_ci(const char *name, unsigned long hashsize);
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;
}

Return to:

Send suggestions and report system problems to the System administrator.