Implemented deletion/insertion/asynchronous-walk lists.

For example of their use, look at comments in lib/slists.h.

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