dovecot-2.0-sslstream: Added DLLIST2_*() functions for doubly li...
dovecot at dovecot.org
dovecot at dovecot.org
Sat Feb 13 02:56:04 EET 2010
details: http://hg.dovecot.org/dovecot-2.0-sslstream/rev/07e0e2b4abe1
changeset: 10263:07e0e2b4abe1
user: Timo Sirainen <tss at iki.fi>
date: Thu Nov 05 19:47:44 2009 -0500
description:
Added DLLIST2_*() functions for doubly linked list with head and tail.
diffstat:
5 files changed, 158 insertions(+)
src/lib/Makefile.am | 1
src/lib/llist.h | 29 +++++++++++
src/lib/test-lib.c | 1
src/lib/test-lib.h | 1
src/lib/test-llist.c | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++
diffs (200 lines):
diff -r 16d40abb75b8 -r 07e0e2b4abe1 src/lib/Makefile.am
--- a/src/lib/Makefile.am Thu Nov 05 19:47:18 2009 -0500
+++ b/src/lib/Makefile.am Thu Nov 05 19:47:44 2009 -0500
@@ -225,6 +225,7 @@ test_lib_SOURCES = \
test-istream-crlf.c \
test-istream-seekable.c \
test-istream-tee.c \
+ test-llist.c \
test-mempool-alloconly.c \
test-network.c \
test-primes.c \
diff -r 16d40abb75b8 -r 07e0e2b4abe1 src/lib/llist.h
--- a/src/lib/llist.h Thu Nov 05 19:47:18 2009 -0500
+++ b/src/lib/llist.h Thu Nov 05 19:47:44 2009 -0500
@@ -21,4 +21,33 @@
(item)->prev = NULL; \
} STMT_END
+/* Doubly linked list with head and tail */
+#define DLLIST2_PREPEND(head, tail, item) STMT_START { \
+ (item)->prev = NULL; \
+ (item)->next = *(head); \
+ if (*(head) != NULL) (*(head))->prev = (item); else (*tail) = (item); \
+ *(head) = (item); \
+ } STMT_END
+
+#define DLLIST2_APPEND(head, tail, item) STMT_START { \
+ (item)->prev = *(tail); \
+ (item)->next = NULL; \
+ if (*(tail) != NULL) (*(tail))->next = (item); else (*head) = (item); \
+ *(tail) = (item); \
+ } STMT_END
+
+#define DLLIST2_REMOVE(head, tail, item) STMT_START { \
+ if ((item)->prev == NULL) \
+ *(head) = (item)->next; \
+ else \
+ (item)->prev->next = (item)->next; \
+ if ((item)->next == NULL) \
+ *(tail) = (item)->prev; \
+ else { \
+ (item)->next->prev = (item)->prev; \
+ (item)->next = NULL; \
+ } \
+ (item)->prev = NULL; \
+ } STMT_END
+
#endif
diff -r 16d40abb75b8 -r 07e0e2b4abe1 src/lib/test-lib.c
--- a/src/lib/test-lib.c Thu Nov 05 19:47:18 2009 -0500
+++ b/src/lib/test-lib.c Thu Nov 05 19:47:44 2009 -0500
@@ -15,6 +15,7 @@ int main(void)
test_istream_crlf,
test_istream_seekable,
test_istream_tee,
+ test_llist,
test_mempool_alloconly,
test_network,
test_primes,
diff -r 16d40abb75b8 -r 07e0e2b4abe1 src/lib/test-lib.h
--- a/src/lib/test-lib.h Thu Nov 05 19:47:18 2009 -0500
+++ b/src/lib/test-lib.h Thu Nov 05 19:47:44 2009 -0500
@@ -14,6 +14,7 @@ void test_istream_crlf(void);
void test_istream_crlf(void);
void test_istream_seekable(void);
void test_istream_tee(void);
+void test_llist(void);
void test_mempool_alloconly(void);
void test_network(void);
void test_primes(void);
diff -r 16d40abb75b8 -r 07e0e2b4abe1 src/lib/test-llist.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/test-llist.c Thu Nov 05 19:47:44 2009 -0500
@@ -0,0 +1,126 @@
+/* Copyright (c) 2009 Dovecot authors, see the included COPYING file */
+
+#include "test-lib.h"
+#include "llist.h"
+
+#include <stdlib.h>
+
+struct dllist {
+ struct dllist *prev, *next;
+};
+
+static void test_dllist(void)
+{
+ struct dllist *head = NULL, *l4, *l3, *l2, *l1;
+
+ l4 = t_new(struct dllist, 1);
+ l3 = t_new(struct dllist, 1);
+ l2 = t_new(struct dllist, 1);
+ l1 = t_new(struct dllist, 1);
+
+ test_begin("dllist");
+ DLLIST_PREPEND(&head, l4);
+ test_assert(head == l4);
+ test_assert(l4->prev == NULL && l4->next == NULL);
+ DLLIST_PREPEND(&head, l3);
+ test_assert(head == l3);
+ test_assert(l3->prev == NULL && l3->next == l4);
+ test_assert(l4->prev == l3 && l4->next == NULL);
+ DLLIST_PREPEND(&head, l2);
+ DLLIST_PREPEND(&head, l1);
+ /* remove from middle */
+ DLLIST_REMOVE(&head, l2);
+ test_assert(l2->prev == NULL && l2->next == NULL);
+ test_assert(head == l1);
+ test_assert(l1->prev == NULL && l1->next == l3);
+ test_assert(l3->prev == l1 && l3->next == l4);
+ test_assert(l4->prev == l3 && l4->next == NULL);
+ /* remove from head */
+ DLLIST_REMOVE(&head, l1);
+ test_assert(l1->prev == NULL && l1->next == NULL);
+ test_assert(head == l3);
+ test_assert(l3->prev == NULL && l3->next == l4);
+ test_assert(l4->prev == l3 && l4->next == NULL);
+ /* remove from tail */
+ DLLIST_PREPEND(&head, l1);
+ DLLIST_REMOVE(&head, l4);
+ test_assert(l4->prev == NULL && l4->next == NULL);
+ test_assert(head == l1);
+ test_assert(l1->prev == NULL && l1->next == l3);
+ test_assert(l3->prev == l1 && l3->next == NULL);
+ /* remove last two */
+ DLLIST_REMOVE(&head, l1);
+ DLLIST_REMOVE(&head, l3);
+ test_assert(l3->prev == NULL && l3->next == NULL);
+ test_assert(head == NULL);
+ test_end();
+}
+
+static void test_dllist2(void)
+{
+ struct dllist *head = NULL, *tail = NULL, *l4, *l3, *l2, *l1;
+
+ l4 = t_new(struct dllist, 1);
+ l3 = t_new(struct dllist, 1);
+ l2 = t_new(struct dllist, 1);
+ l1 = t_new(struct dllist, 1);
+
+ test_begin("dllist");
+ /* prepend to empty */
+ DLLIST2_PREPEND(&head, &tail, l3);
+ test_assert(head == l3 && tail == l3);
+ test_assert(l3->next == NULL && l3->prev == NULL);
+ /* remove last */
+ DLLIST2_REMOVE(&head, &tail, l3);
+ test_assert(head == NULL && tail == NULL);
+ test_assert(l3->next == NULL && l3->prev == NULL);
+ /* append to empty */
+ DLLIST2_APPEND(&head, &tail, l3);
+ test_assert(head == l3 && tail == l3);
+ test_assert(l3->next == NULL && l3->prev == NULL);
+ /* prepend */
+ DLLIST2_PREPEND(&head, &tail, l2);
+ test_assert(head == l2 && tail == l3);
+ test_assert(l2->prev == NULL && l2->next == l3);
+ test_assert(l3->prev == l2 && l3->next == NULL);
+ /* append */
+ DLLIST2_APPEND(&head, &tail, l4);
+ test_assert(head == l2 && tail == l4);
+ test_assert(l2->prev == NULL && l2->next == l3);
+ test_assert(l3->prev == l2 && l3->next == l4);
+ test_assert(l4->prev == l3 && l4->next == NULL);
+ DLLIST2_PREPEND(&head, &tail, l1);
+
+ /* remove from middle */
+ DLLIST2_REMOVE(&head, &tail, l2);
+ test_assert(l2->prev == NULL && l2->next == NULL);
+ test_assert(head == l1 && tail == l4);
+ test_assert(l1->prev == NULL && l1->next == l3);
+ test_assert(l3->prev == l1 && l3->next == l4);
+ test_assert(l4->prev == l3 && l4->next == NULL);
+ /* remove from head */
+ DLLIST2_REMOVE(&head, &tail, l1);
+ test_assert(l1->prev == NULL && l1->next == NULL);
+ test_assert(head == l3 && tail == l4);
+ test_assert(l3->prev == NULL && l3->next == l4);
+ test_assert(l4->prev == l3 && l4->next == NULL);
+ /* remove from tail */
+ DLLIST2_PREPEND(&head, &tail, l1);
+ DLLIST2_REMOVE(&head, &tail, l4);
+ test_assert(l4->prev == NULL && l4->next == NULL);
+ test_assert(head == l1 && tail == l3);
+ test_assert(l1->prev == NULL && l1->next == l3);
+ test_assert(l3->prev == l1 && l3->next == NULL);
+ /* remove last two */
+ DLLIST2_REMOVE(&head, &tail, l1);
+ DLLIST2_REMOVE(&head, &tail, l3);
+ test_assert(l3->prev == NULL && l3->next == NULL);
+ test_assert(head == NULL && tail == NULL);
+ test_end();
+}
+
+void test_llist(void)
+{
+ test_dllist();
+ test_dllist2();
+}
More information about the dovecot-cvs
mailing list