aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/list.c84
-rw-r--r--src/symtab.c113
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
@@ -83,12 +83,52 @@ grecs_list_remove_entry(struct grecs_list *lp, struct grecs_list_entry *ent)
else
lp->tail = ent->prev;
grecs_free(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)
{
struct grecs_list_entry *ep = grecs_malloc(sizeof(*ep));
ep->data = val;
grecs_list_insert_entry(lp, lp->tail, ep, 0);
@@ -120,40 +160,33 @@ grecs_list_push(struct grecs_list *lp, void *val)
}
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);
} else
data = NULL;
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)
lp->free_entry(ep->data);
grecs_free(ep);
ep = next;
@@ -168,36 +201,37 @@ grecs_list_free(struct grecs_list *lp)
if (lp) {
grecs_list_clear(lp);
grecs_free(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)
return ep->data;
}
return NULL;
}
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;
}
int
@@ -216,12 +250,12 @@ grecs_list_compare(struct grecs_list *a, struct grecs_list *b)
if (a->cmp != b->cmp)
return 1;
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
@@ -30,22 +30,42 @@ static unsigned int hash_size[] = {
7, 17, 37, 101, 229, 487, 1009, 2039, 4091, 8191, 16411
};
/* |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
syment_free(struct grecs_symtab *st, void *ptr)
{
if (st->syment_free_fun)
@@ -69,13 +89,23 @@ syment_alloc(struct grecs_symtab *st, void *key)
errno = ec;
return NULL;
}
}
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)
{
unsigned i;
@@ -98,14 +128,14 @@ grecs_hash_string_ci(const char *name, unsigned long hashsize)
return i % 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
def_cmp(const void *a, const void *b)
{
struct grecs_syment const *syma = a;
@@ -215,12 +245,17 @@ grecs_symtab_strerror(int rc)
int
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)
break;
if (++i >= hash_size[st->hash_num])
i = 0;
@@ -228,13 +263,20 @@ grecs_symtab_remove(struct grecs_symtab *st, void *elt)
return ENOENT;
}
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;
j = i;
do {
@@ -309,16 +351,26 @@ grecs_symtab_lookup_or_install(struct grecs_symtab *st, void *key,
if (install && *install == 1) {
struct grecs_syment *ent = syment_alloc(st, key);
if (!ent) {
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;
}
void
@@ -334,12 +386,13 @@ grecs_symtab_clear(struct grecs_symtab *st)
struct grecs_syment *elem = st->tab[i];
if (elem) {
syment_free(st, elem);
st->tab[i] = NULL;
}
}
+ st->elcount = 0;
}
struct grecs_symtab *
grecs_symtab_create(size_t elsize,
unsigned (*hash_fun)(void *, unsigned long),
int (*cmp_fun)(const void *, const void *),
@@ -347,12 +400,13 @@ grecs_symtab_create(size_t elsize,
void *(*alloc_fun)(size_t), void (*free_fun)(void *))
{
struct grecs_symtab *st = malloc(sizeof(*st));
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;
st->syment_alloc_fun = alloc_fun;
if (free_fun)
st->syment_free_fun = free_fun;
@@ -378,45 +432,60 @@ grecs_symtab_create_default(size_t elsize)
void
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.

Generated by cgit.