diff options
Diffstat (limited to 'lib/slists.c')
| -rw-r--r-- | lib/slists.c | 231 |
1 files changed, 231 insertions, 0 deletions
diff --git a/lib/slists.c b/lib/slists.c new file mode 100644 index 0000000..3577430 --- /dev/null +++ b/lib/slists.c @@ -0,0 +1,231 @@ +/* + * BIRD Library -- Safe Linked Lists + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#define _BIRD_SLISTS_C_ + +#include "nest/bird.h" +#include "lib/slists.h" + +static inline void +s_merge(snode *from, snode *to) +{ + siterator *f, *g; + + if (!(f = from->readers)) + return; + if (!(g = to->readers)) + { + /* Fast path */ + to->readers = f; + f->prev = (siterator *) to; + fixup: + while (f && f->node) + { + f->node = NULL; + f = f->next; + } + return; + } + /* Really merging */ + while (g->next) + g = g->next; + g->next = f; + f->prev = g; + goto fixup; +} + +snode * +s_get(siterator *i) +{ + siterator *f, *g; + snode *n; + + if (!(n = i->node)) + { + /* + * No node found. We have to walk the iterator list backwards + * to find where are we linked. + */ + f = i; + while (!f->null) + f = f->prev; + n = (snode *) f; + } + f = i->prev; /* Maybe the snode itself */ + g = i->next; + f->next = g; + if (g) + g->prev = f; + return n; +} + +void +s_put(siterator *i, snode *n) +{ + siterator *f; + + i->node = n; + if (f = n->readers) + f->prev = i; + i->next = f; + n->readers = i; + i->prev = (siterator *) n; + i->null = NULL; +} + +void +s_add_tail(slist *l, snode *n) +{ + snode *z = l->tail; + + n->next = (snode *) &l->null; + n->prev = z; + z->next = n; + l->tail = n; + n->readers = NULL; +} + +void +s_add_head(slist *l, snode *n) +{ + snode *z = l->head; + + n->next = z; + n->prev = (snode *) &l->head; + z->prev = n; + l->head = n; + n->readers = NULL; +} + +void +s_insert_node(snode *n, snode *after) +{ + snode *z = after->next; + + n->next = z; + n->prev = after; + after->next = n; + z->prev = n; + n->readers = NULL; +} + +void +s_rem_node(snode *n) +{ + snode *z = n->prev; + snode *x = n->next; + + z->next = x; + x->prev = z; + s_merge(n, x); +} + +void +s_init_list(slist *l) +{ + l->head = (snode *) &l->null; + l->null = NULL; + l->tail = (snode *) &l->head; + l->tail_readers = NULL; +} + +void +s_add_tail_list(slist *to, slist *l) +{ + snode *p = to->tail; + snode *q = l->head; + + p->next = q; + q->prev = p; + q = l->tail; + q->next = (snode *) &to->null; + to->tail = q; + s_merge((snode *) &l->null, (snode *) &to->null); +} + +#ifdef TEST + +#include "lib/resource.h" +#include <stdio.h> + +void dump(char *c, slist *a) +{ + snode *x; + + puts(c); + for(x=SHEAD(*a); x; x=x->next) + { + siterator *i, *j; + printf("%p", x); + j = (siterator *) x; + for(i=x->readers; i; i=i->next) + { + if (i->prev != j) + printf(" ???"); + j = i; + printf(" [%p:%p]", i, i->node); + } + putchar('\n'); + } + puts("---"); +} + +int main(void) +{ + slist a, b; + snode *x, *y; + siterator i, j; + + s_init_list(&a); + s_init_list(&b); + x = xmalloc(sizeof(*x)); + s_add_tail(&a, x); + x = xmalloc(sizeof(*x)); + s_add_tail(&a, x); + x = xmalloc(sizeof(*x)); + s_add_tail(&a, x); + dump("1", &a); + + s_init(&i, &a); + s_init(&j, &a); + dump("2", &a); + + x = s_get(&i); + printf("Got %p\n", x); + dump("3", &a); + + s_put(&i, x->next); + dump("4", &a); + + y = s_get(&j); + while (y) + { + s_put(&j, y); + dump("5*", &a); + y = s_get(&j)->next; + } + + dump("5 done", &a); + + s_rem_node(a.head->next); + dump("6 (deletion)", &a); + + s_put(&i, s_get(&i)->next); + dump("6 (relink)", &a); + + x = xmalloc(sizeof(*x)); + s_add_tail(&b, x); + dump("7 (second list)", &b); + + s_add_tail_list(&b, &a); + dump("8 (after merge)", &b); + + return 0; +} + +#endif |