bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2009-2018 Dovecot authors, see the included COPYING file */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen#include "test-lib.h"
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen#include "llist.h"
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainenstruct dllist {
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen struct dllist *prev, *next;
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen};
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainenstatic void test_dllist(void)
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen{
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen struct dllist *head = NULL, *l4, *l3, *l2, *l1;
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen struct dllist empty = { NULL, NULL };
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l4 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l3 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l2 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l1 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_begin("dllist");
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_PREPEND(&head, l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == NULL && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_PREPEND(&head, l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == NULL && l3->next == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_PREPEND(&head, l2);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_PREPEND(&head, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove from middle */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_REMOVE(&head, l2);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l2->prev == NULL && l2->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == l1 && l3->next == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove from head */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_REMOVE(&head, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l1->prev == NULL && l1->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == NULL && l3->next == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove from tail */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_PREPEND(&head, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_REMOVE(&head, l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == NULL && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen /* removal of an entry not in the list shouldn't cause the list to break */
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen DLLIST_REMOVE(&head, &empty);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen test_assert(head == l1);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove last two */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_REMOVE(&head, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST_REMOVE(&head, l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == NULL && l3->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_end();
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen}
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainenstatic void test_dllist2(void)
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen{
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen struct dllist *head = NULL, *tail = NULL, *l4, *l3, *l2, *l1;
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen struct dllist empty = { NULL, NULL };
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l4 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l3 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l2 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen l1 = t_new(struct dllist, 1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_begin("dllist");
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* prepend to empty */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_PREPEND(&head, &tail, l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l3 && tail == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->next == NULL && l3->prev == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove last */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_REMOVE(&head, &tail, l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == NULL && tail == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->next == NULL && l3->prev == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* append to empty */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_APPEND(&head, &tail, l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l3 && tail == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->next == NULL && l3->prev == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* prepend */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_PREPEND(&head, &tail, l2);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l2 && tail == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l2->prev == NULL && l2->next == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == l2 && l3->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* append */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_APPEND(&head, &tail, l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l2 && tail == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l2->prev == NULL && l2->next == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == l2 && l3->next == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_PREPEND(&head, &tail, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove from middle */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_REMOVE(&head, &tail, l2);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l2->prev == NULL && l2->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l1 && tail == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == l1 && l3->next == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove from head */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_REMOVE(&head, &tail, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l1->prev == NULL && l1->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l3 && tail == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == NULL && l3->next == l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove from tail */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_PREPEND(&head, &tail, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_REMOVE(&head, &tail, l4);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l4->prev == NULL && l4->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == l1 && tail == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen /* removal of an entry not in the list shouldn't cause the list to break */
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen DLLIST2_REMOVE(&head, &tail, &empty);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen test_assert(head == l1);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen test_assert(head == l1 && tail == l3);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
1139a1f61032e3b81bd1c7f526b9e9553f51a5a8Timo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen /* remove last two */
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_REMOVE(&head, &tail, l1);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen DLLIST2_REMOVE(&head, &tail, l3);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(l3->prev == NULL && l3->next == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_assert(head == NULL && tail == NULL);
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_end();
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen}
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainenvoid test_llist(void)
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen{
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_dllist();
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen test_dllist2();
9761e0036c87f459abe040632e1252f794ffe5f7Timo Sirainen}