From 298dd2b1d1133d144dd4ec92034eff9dad8fa449 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 8 Nov 1999 23:30:02 +0000
Subject: [PATCH] New list functions from BIRD project.

---
 lib/lists.c |  44 ++++++++++-----------
 lib/lists.h | 110 ++++++++++++++--------------------------------------
 2 files changed, 51 insertions(+), 103 deletions(-)

diff --git a/lib/lists.c b/lib/lists.c
index b0d611df..8f4f0b4b 100644
--- a/lib/lists.c
+++ b/lib/lists.c
@@ -1,36 +1,37 @@
 /*
  *	Sherlock Library -- Linked Lists
  *
- *	(c) 1997 Martin Mares, <mj@atrey.karlin.mff.cuni.cz>
+ *	(c) 1997--1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
  */
 
 #include <stdio.h>
 
+#define _SHERLOCK_LISTS_C
 #include "lists.h"
 
-void
+LIST_INLINE void
 add_tail(list *l, node *n)
 {
-  node *z = l->tail.prev;
+  node *z = l->tail;
 
-  n->next = &l->tail;
+  n->next = (node *) &l->null;
   n->prev = z;
   z->next = n;
-  l->tail.prev = n;
+  l->tail = n;
 }
 
-void
+LIST_INLINE void
 add_head(list *l, node *n)
 {
-  node *z = l->head.next;
+  node *z = l->head;
 
   n->next = z;
-  n->prev = &l->head;
+  n->prev = (node *) &l->head;
   z->prev = n;
-  l->head.next = n;
+  l->head = n;
 }
 
-void
+LIST_INLINE void
 insert_node(node *n, node *after)
 {
   node *z = after->next;
@@ -41,7 +42,7 @@ insert_node(node *n, node *after)
   z->prev = n;
 }
 
-void
+LIST_INLINE void
 rem_node(node *n)
 {
   node *z = n->prev;
@@ -51,24 +52,23 @@ rem_node(node *n)
   x->prev = z;
 }
 
-void
+LIST_INLINE void
 init_list(list *l)
 {
-  l->head.next = &l->tail;
-  l->head.prev = NULL;
-  l->tail.next = NULL;
-  l->tail.prev = &l->head;
+  l->head = (node *) &l->null;
+  l->null = NULL;
+  l->tail = (node *) &l->head;
 }
 
-void
+LIST_INLINE void
 add_tail_list(list *to, list *l)
 {
-  node *p = to->tail.prev;
-  node *q = l->head.next;
+  node *p = to->tail;
+  node *q = l->head;
 
   p->next = q;
   q->prev = p;
-  q = l->tail.prev;
-  q->next = &to->tail;
-  to->tail.prev = q;
+  q = l->tail;
+  q->next = (node *) &to->null;
+  to->tail = q;
 }
diff --git a/lib/lists.h b/lib/lists.h
index 9c9cabf2..48b7de99 100644
--- a/lib/lists.h
+++ b/lib/lists.h
@@ -1,27 +1,34 @@
 /*
  *	Sherlock Library -- Linked Lists
  *
- *	(c) 1997 Martin Mares, <mj@atrey.karlin.mff.cuni.cz>
+ *	(c) 1997--1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
  */
 
-struct node {
+#ifndef _SHERLOCK_LISTS_H
+#define _SHERLOCK_LISTS_H
+
+typedef struct node {
   struct node *next, *prev;
-};
-typedef struct node node;
+} node;
 
-struct list {
-  struct node head, tail;
-};
-typedef struct list list;
+typedef struct list {			/* In fact two overlayed nodes */
+  struct node *head, *null, *tail;
+} list;
 
 #define NODE (node *)
-#define HEAD(list) ((void *)((list).head.next))
-#define TAIL(list) ((void *)((list).tail.prev))
-#define DO_FOR_ALL(n,list) for((n)=HEAD(list);(NODE (n))->next; \
-				 n=(void *)((NODE (n))->next))
-#define EMPTY_LIST(list) (!(list).head.next->next)
-#define OFFSETOF(s, i) ((unsigned int)&((s *)0)->i)
-#define SKIP_BACK(s, i, p) ((s *)((char *)p - OFFSETOF(s, i)))
+#define HEAD(list) ((void *)((list).head))
+#define TAIL(list) ((void *)((list).tail))
+#define WALK_LIST(n,list) for(n=HEAD(list);(NODE (n))->next; \
+				n=(void *)((NODE (n))->next))
+#define DO_FOR_ALL(n,list) WALK_LIST(n,list)
+#define WALK_LIST_DELSAFE(n,nxt,list) \
+     for(n=HEAD(list); nxt=(void *)((NODE (n))->next); n=(void *) nxt)
+#define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
+				n=(void *)((NODE (n))->prev))
+#define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
+     for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
+
+#define EMPTY_LIST(list) (!(list).head->next)
 
 void add_tail(list *, node *);
 void add_head(list *, node *);
@@ -30,71 +37,12 @@ void add_tail_list(list *, list *);
 void init_list(list *);
 void insert_node(node *, node *);
 
-#ifdef __GNUC__
-
-extern inline void
-add_tail(list *l, node *n)
-{
-  node *z = l->tail.prev;
-
-  n->next = &l->tail;
-  n->prev = z;
-  z->next = n;
-  l->tail.prev = n;
-}
-
-extern inline void
-add_head(list *l, node *n)
-{
-  node *z = l->head.next;
-
-  n->next = z;
-  n->prev = &l->head;
-  z->prev = n;
-  l->head.next = n;
-}
-
-extern inline void
-insert_node(node *n, node *after)
-{
-  node *z = after->next;
-
-  n->next = z;
-  n->prev = after;
-  after->next = n;
-  z->prev = n;
-}
-
-extern inline void
-rem_node(node *n)
-{
-  node *z = n->prev;
-  node *x = n->next;
-
-  z->next = x;
-  x->prev = z;
-}
-
-extern inline void
-init_list(list *l)
-{
-  l->head.next = &l->tail;
-  l->head.prev = NULL;
-  l->tail.next = NULL;
-  l->tail.prev = &l->head;
-}
-
-extern inline void
-add_tail_list(list *to, list *l)
-{
-  node *p = to->tail.prev;
-  node *q = l->head.next;
-
-  p->next = q;
-  q->prev = p;
-  q = l->tail.prev;
-  q->next = &to->tail;
-  to->tail.prev = q;
-}
+#if !defined(_SHERLOCK_LISTS_C) && defined(__GNUC__)
+#define LIST_INLINE extern inline
+#include "lib/lists.c"
+#undef LIST_INLINE
+#else
+#define LIST_INLINE
+#endif
 
 #endif
-- 
2.39.2