test-llist.c revision 1139a1f61032e3b81bd1c7f526b9e9553f51a5a8
02c335c23bf5fa225a467c19f2c063fb0dc7b8c3Timo Sirainen/* Copyright (c) 2009-2014 Dovecot authors, see the included COPYING file */
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen
08d6658a4e2ec8104cd1307f6baa75fdb07a24f8Mark Washenberger#include "test-lib.h"
7a60e1dc9e93ef3f7c7fe1af6385a0bfa1e31bc3Timo Sirainen#include "llist.h"
31a12066e4cd9310d64091c81b59fb8eb1986023Timo Sirainen
44cf91b7a701a9b4d9f59a990552eab4f7f64fbcTimo Sirainen#include <stdlib.h>
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainenstruct dllist {
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen struct dllist *prev, *next;
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen};
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainenstatic void test_dllist(void)
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen{
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen struct dllist *head = NULL, *l4, *l3, *l2, *l1;
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen struct dllist empty = { NULL, NULL };
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen l4 = t_new(struct dllist, 1);
9ed2951bd0bb1878a27437d7c00611b2baadd614Timo Sirainen l3 = t_new(struct dllist, 1);
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen l2 = t_new(struct dllist, 1);
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen l1 = t_new(struct dllist, 1);
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen
6cbe2facd40ea3461620571a1c168ce9884be3b3Timo Sirainen test_begin("dllist");
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen DLLIST_PREPEND(&head, l4);
6135260095e1704ed6edff9d00bdfc043c11429cTimo Sirainen test_assert(head == l4);
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen test_assert(l4->prev == NULL && l4->next == NULL);
7ace5117d5f2395bd66f20b09e77dac05492f7ceTimo Sirainen DLLIST_PREPEND(&head, l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(head == l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l3->prev == NULL && l3->next == l4);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen DLLIST_PREPEND(&head, l2);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen DLLIST_PREPEND(&head, l1);
44cf91b7a701a9b4d9f59a990552eab4f7f64fbcTimo Sirainen /* remove from middle */
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen DLLIST_REMOVE(&head, l2);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l2->prev == NULL && l2->next == NULL);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(head == l1);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l3->prev == l1 && l3->next == l4);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen /* remove from head */
44cf91b7a701a9b4d9f59a990552eab4f7f64fbcTimo Sirainen DLLIST_REMOVE(&head, l1);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l1->prev == NULL && l1->next == NULL);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(head == l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l3->prev == NULL && l3->next == l4);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen /* remove from tail */
44cf91b7a701a9b4d9f59a990552eab4f7f64fbcTimo Sirainen DLLIST_PREPEND(&head, l1);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen DLLIST_REMOVE(&head, l4);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l4->prev == NULL && l4->next == NULL);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(head == l1);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen /* removal of an entry not in the list shouldn't cause the list to break */
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen DLLIST_REMOVE(&head, &empty);
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen test_assert(head == l1);
5bb7c9863cbb62c41b13e7f42e04f1d57b4634f8Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen /* remove last two */
8759adc67109b5a12a7af3ed717c7040622a0a04Timo Sirainen DLLIST_REMOVE(&head, l1);
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen DLLIST_REMOVE(&head, l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l3->prev == NULL && l3->next == NULL);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(head == NULL);
d31c77e63713a6cf3687a4b38ff8daf6d6c7a3ddTimo Sirainen test_end();
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen}
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainenstatic void test_dllist2(void)
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen{
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen struct dllist *head = NULL, *tail = NULL, *l4, *l3, *l2, *l1;
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen struct dllist empty = { NULL, NULL };
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen l4 = t_new(struct dllist, 1);
6135260095e1704ed6edff9d00bdfc043c11429cTimo Sirainen l3 = t_new(struct dllist, 1);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen l2 = t_new(struct dllist, 1);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen l1 = t_new(struct dllist, 1);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_begin("dllist");
7a60e1dc9e93ef3f7c7fe1af6385a0bfa1e31bc3Timo Sirainen /* prepend to empty */
3ab7783791bd46cdd46e9b9de3e98e8efcb6c6bfTimo Sirainen DLLIST2_PREPEND(&head, &tail, l3);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(head == l3 && tail == l3);
3ab7783791bd46cdd46e9b9de3e98e8efcb6c6bfTimo Sirainen test_assert(l3->next == NULL && l3->prev == NULL);
3ab7783791bd46cdd46e9b9de3e98e8efcb6c6bfTimo Sirainen /* remove last */
6135260095e1704ed6edff9d00bdfc043c11429cTimo Sirainen DLLIST2_REMOVE(&head, &tail, l3);
6135260095e1704ed6edff9d00bdfc043c11429cTimo Sirainen test_assert(head == NULL && tail == NULL);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(l3->next == NULL && l3->prev == NULL);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen /* append to empty */
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen DLLIST2_APPEND(&head, &tail, l3);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(head == l3 && tail == l3);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(l3->next == NULL && l3->prev == NULL);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen /* prepend */
6135260095e1704ed6edff9d00bdfc043c11429cTimo Sirainen DLLIST2_PREPEND(&head, &tail, l2);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(head == l2 && tail == l3);
145d2eef238ed8bbff635e3b06951a83f0ee5a03Timo Sirainen test_assert(l2->prev == NULL && l2->next == l3);
145d2eef238ed8bbff635e3b06951a83f0ee5a03Timo Sirainen test_assert(l3->prev == l2 && l3->next == NULL);
145d2eef238ed8bbff635e3b06951a83f0ee5a03Timo Sirainen /* append */
145d2eef238ed8bbff635e3b06951a83f0ee5a03Timo Sirainen DLLIST2_APPEND(&head, &tail, l4);
145d2eef238ed8bbff635e3b06951a83f0ee5a03Timo Sirainen test_assert(head == l2 && tail == l4);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(l2->prev == NULL && l2->next == l3);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(l3->prev == l2 && l3->next == l4);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
8759adc67109b5a12a7af3ed717c7040622a0a04Timo Sirainen DLLIST2_PREPEND(&head, &tail, l1);
8759adc67109b5a12a7af3ed717c7040622a0a04Timo Sirainen
8759adc67109b5a12a7af3ed717c7040622a0a04Timo Sirainen /* remove from middle */
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen DLLIST2_REMOVE(&head, &tail, l2);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(l2->prev == NULL && l2->next == NULL);
553308791c097219e8eb31cbd03a29e9e1333848Timo Sirainen test_assert(head == l1 && tail == l4);
24d7c5fc9fa1cb1f49402ec796654113199ba4e6Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(l3->prev == l1 && l3->next == l4);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen /* remove from head */
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen DLLIST2_REMOVE(&head, &tail, l1);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(l1->prev == NULL && l1->next == NULL);
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen test_assert(head == l3 && tail == l4);
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen test_assert(l3->prev == NULL && l3->next == l4);
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen test_assert(l4->prev == l3 && l4->next == NULL);
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen /* remove from tail */
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen DLLIST2_PREPEND(&head, &tail, l1);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen DLLIST2_REMOVE(&head, &tail, l4);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(l4->prev == NULL && l4->next == NULL);
8759adc67109b5a12a7af3ed717c7040622a0a04Timo Sirainen test_assert(head == l1 && tail == l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
d31c77e63713a6cf3687a4b38ff8daf6d6c7a3ddTimo Sirainen /* removal of an entry not in the list shouldn't cause the list to break */
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen DLLIST2_REMOVE(&head, &tail, &empty);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(head == l1);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(head == l1 && tail == l3);
90cf976e328e093da91a8332d96182201f4ef6c1Timo Sirainen test_assert(l1->prev == NULL && l1->next == l3);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_assert(l3->prev == l1 && l3->next == NULL);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen /* remove last two */
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen DLLIST2_REMOVE(&head, &tail, l1);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen DLLIST2_REMOVE(&head, &tail, l3);
a3dd97fb6d92a89c3de0597fed2d4b044c7aeb84Timo Sirainen test_assert(l3->prev == NULL && l3->next == NULL);
a3dd97fb6d92a89c3de0597fed2d4b044c7aeb84Timo Sirainen test_assert(head == NULL && tail == NULL);
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_end();
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen}
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainenvoid test_llist(void)
7a60e1dc9e93ef3f7c7fe1af6385a0bfa1e31bc3Timo Sirainen{
553308791c097219e8eb31cbd03a29e9e1333848Timo Sirainen test_dllist();
dc9bfb7dc057964238e181d3d8b08751527bb08aTimo Sirainen test_dllist2();
a3dd97fb6d92a89c3de0597fed2d4b044c7aeb84Timo Sirainen}
7dcb5545370faa9d4ff83b3ede65a69fc3dd4b65Timo Sirainen