Mercurial > dovecot > core-2.2
changeset 10262:07e0e2b4abe1 HEAD
Added DLLIST2_*() functions for doubly linked list with head and tail.
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Thu, 05 Nov 2009 19:47:44 -0500 |
parents | 16d40abb75b8 |
children | 18f5fdeed659 |
files | src/lib/Makefile.am src/lib/llist.h src/lib/test-lib.c src/lib/test-lib.h src/lib/test-llist.c |
diffstat | 5 files changed, 158 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- 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-istream-crlf.c \ test-istream-seekable.c \ test-istream-tee.c \ + test-llist.c \ test-mempool-alloconly.c \ test-network.c \ test-primes.c \
--- 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
--- 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 @@ test_istream_crlf, test_istream_seekable, test_istream_tee, + test_llist, test_mempool_alloconly, test_network, test_primes,
--- 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_seekable(void); void test_istream_tee(void); +void test_llist(void); void test_mempool_alloconly(void); void test_network(void); void test_primes(void);
--- /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(); +}