Implemented deletion/insertion/asynchronous-walk lists.

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

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