summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/Modules2
-rw-r--r--lib/slists.c231
-rw-r--r--lib/slists.h88
3 files changed, 321 insertions, 0 deletions
diff --git a/lib/Modules b/lib/Modules
index a1c1fd7f..ba743dae 100644
--- a/lib/Modules
+++ b/lib/Modules
@@ -20,3 +20,5 @@ xmalloc.c
printf.c
string.h
patmatch.c
+slists.c
+slists.h
diff --git a/lib/slists.c b/lib/slists.c
new file mode 100644
index 00000000..35774301
--- /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
diff --git a/lib/slists.h b/lib/slists.h
new file mode 100644
index 00000000..27520c9f
--- /dev/null
+++ b/lib/slists.h
@@ -0,0 +1,88 @@
+/*
+ * 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.
+ */
+
+#ifndef _BIRD_SLISTS_H_
+#define _BIRD_SLISTS_H_
+
+/*
+ * These linked lists work in a way similar to standard lists defined
+ * in lib/lists.h, but in addition to all usual list functions they
+ * provide fast deletion/insertion/everything-safe asynchronous
+ * walking.
+ *
+ * Example:
+ * slist l;
+ * siterator i;
+ * snode *n;
+ *
+ * s_init(&i, &l); // Initialize iteration
+ * ...
+ * n = s_get(&i); // Some time later, fetch present
+ * // value of the iterator and unlink it
+ * // from the list.
+ * while (n->next) {
+ * ...
+ * if (decided_to_stop) {
+ * s_put(&i, n); // Store current position (maybe even
+ * // that we stay at list end)
+ * return; // and return
+ * }
+ * ...
+ * }
+ * // After finishing, don't link the iterator back
+ */
+
+typedef struct snode {
+ struct snode *next, *prev;
+ struct siterator *readers;
+} snode;
+
+typedef struct slist { /* In fact two overlayed snodes */
+ struct snode *head, *null, *tail;
+ struct siterator *tail_readers;
+} slist;
+
+typedef struct siterator {
+ /*
+ * Caution: Layout of this structure depends hard on layout of the
+ * snode. Our `next' must be at position of snode `readers'
+ * field, our `null' must be at position of `prev' and it must
+ * contain NULL in order to distinguish between siterator
+ * and snode (snodes with NULL `prev' field never carry
+ * iterators). You are not expected to understand this.
+ */
+ struct siterator *prev, *null, *next;
+ /*
+ * For recently merged nodes this can be NULL, but then it's NULL
+ * for all successors as well. This is done to speed up iterator
+ * merging when there are lots of deletions.
+ */
+ snode *node;
+} siterator;
+
+#define SNODE (snode *)
+#define SHEAD(list) ((void *)((list).head))
+#define STAIL(list) ((void *)((list).tail))
+#define WALK_SLIST(n,list) for(n=SHEAD(list);(SNODE (n))->next; \
+ n=(void *)((SNODE (n))->next))
+#define WALK_SLIST_DELSAFE(n,nxt,list) \
+ for(n=SHEAD(list); nxt=(void *)((SNODE (n))->next); n=(void *) nxt)
+#define EMPTY_SLIST(list) (!(list).head->next)
+
+void s_add_tail(slist *, snode *);
+void s_add_head(slist *, snode *);
+void s_rem_node(snode *);
+void s_add_tail_list(slist *, slist *);
+void s_init_list(slist *);
+void s_insert_node(snode *, snode *);
+
+snode *s_get(siterator *);
+void s_put(siterator *, snode *n);
+static inline void s_init(siterator *i, slist *l) { s_put(i, SHEAD(*l)); }
+
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 21:37:48 +0000