From d650b928acb735258f1efb06b9b930a755282f45 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 15 Jun 2003 20:20:51 +0000
Subject: [PATCH] Added a straigtforward implementation of circular linked
 lists. They are a small bit less efficient than our lists.h lists (testing
 against zero is faster than testing against list head), but they are nicer
 and they save one pointer per list head which makes them better for hash
 tables etc.

---
 lib/clists.h | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)
 create mode 100644 lib/clists.h

diff --git a/lib/clists.h b/lib/clists.h
new file mode 100644
index 00000000..e9826eb6
--- /dev/null
+++ b/lib/clists.h
@@ -0,0 +1,76 @@
+/*
+ *	Sherlock Library -- Circular Linked Lists
+ *
+ *	(c) 2003 Martin Mares <mj@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
+ */
+
+#ifndef _SHERLOCK_CLISTS_H
+#define _SHERLOCK_CLISTS_H
+
+typedef struct cnode {
+  struct cnode *next, *prev;
+} cnode;
+
+typedef struct clist {
+  struct cnode head;
+} clist;
+
+static inline void *clist_head(clist *l)
+{
+  return (l->head.next != &l->head) ? l->head.next : NULL;
+}
+
+static inline void *clist_tail(clist *l)
+{
+  return (l->head.prev != &l->head) ? l->head.prev : NULL;
+}
+
+static inline void *clist_next(clist *l, cnode *n)
+{
+  return (n->next != &l->head) ? (void *) n->next : NULL;
+}
+
+static inline void *clist_prev(clist *l, cnode *n)
+{
+  return (n->prev != &l->head) ? (void *) n->prev : NULL;
+}
+
+#define CLIST_WALK(n,list) for(n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
+
+static inline void clist_insert(cnode *what, cnode *after)
+{
+  cnode *before = after->next;
+  what->next = before;
+  what->prev = before->prev;
+  before->prev = what;
+  after->next = what;
+}
+
+static inline void clist_add_tail(clist *l, cnode *n)
+{
+  clist_insert(n, l->head.prev);
+}
+
+static inline void clist_add_head(clist *l, cnode *n)
+{
+  clist_insert(n, &l->head);
+}
+
+static inline void clist_remove(cnode *n)
+{
+  cnode *before = n->prev;
+  cnode *after = n->next;
+  before->next = after;
+  after->prev = before;
+}
+
+static inline void clist_init(clist *l)
+{
+  cnode *head = &l->head;
+  head->next = head->prev = head;
+}
+
+#endif
-- 
2.39.2