X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Flists.h;h=39036913f8d99a3d8eac7bdb0c1c1cce1ace083a;hb=08ec58075cd87236ea502c2c3b89e38126478167;hp=4f605697eb6b4587a71a5e7e735da0bce19618e2;hpb=03846211ba84582b133a985200502a39462dfe66;p=libucw.git

diff --git a/lib/lists.h b/lib/lists.h
index 4f605697..39036913 100644
--- a/lib/lists.h
+++ b/lib/lists.h
@@ -1,25 +1,50 @@
 /*
- *	Sherlock Library -- Linked Lists
+ *	UCW Library -- Linked Lists
  *
- *	(c) 1997 Martin Mares, <mj@atrey.karlin.mff.cuni.cz>
+ *	(c) 1997--1999 Martin Mares <mj@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
  */
 
-struct node {
+#ifndef _UCW_LISTS_H
+#define _UCW_LISTS_H
+
+/*
+ * I admit the list structure is very tricky and also somewhat awkward,
+ * but it's both efficient and easy to manipulate once one understands the
+ * basic trick: The list head always contains two synthetic nodes which are
+ * always present in the list: the head and the tail. But as the `next'
+ * entry of the tail and the `prev' entry of the head are both NULL, the
+ * nodes can overlap each other:
+ *
+ *     head    head_node.next
+ *     null    head_node.prev  tail_node.next
+ *     tail                    tail_node.prev
+ */
+
+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 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 *);
@@ -28,71 +53,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(_UCW_LISTS_C) && defined(__GNUC__)
+#define LIST_INLINE extern inline
+#include "lib/lists.c"
+#undef LIST_INLINE
+#else
+#define LIST_INLINE
+#endif
 
 #endif