1 /* Copyright (c) 2009-2018 Dovecot authors, see the included COPYING file */
2
3 #include "test-lib.h"
4 #include "llist.h"
5
6
7 struct dllist {
8 struct dllist *prev, *next;
9 };
10
test_dllist(void)11 static void test_dllist(void)
12 {
13 struct dllist *head = NULL, *l4, *l3, *l2, *l1;
14 struct dllist empty = { NULL, NULL };
15
16 l4 = t_new(struct dllist, 1);
17 l3 = t_new(struct dllist, 1);
18 l2 = t_new(struct dllist, 1);
19 l1 = t_new(struct dllist, 1);
20
21 test_begin("dllist");
22 DLLIST_PREPEND(&head, l4);
23 test_assert(head == l4);
24 test_assert(l4->prev == NULL && l4->next == NULL);
25 DLLIST_PREPEND(&head, l3);
26 test_assert(head == l3);
27 test_assert(l3->prev == NULL && l3->next == l4);
28 test_assert(l4->prev == l3 && l4->next == NULL);
29 DLLIST_PREPEND(&head, l2);
30 DLLIST_PREPEND(&head, l1);
31 /* remove from middle */
32 DLLIST_REMOVE(&head, l2);
33 test_assert(l2->prev == NULL && l2->next == NULL);
34 test_assert(head == l1);
35 test_assert(l1->prev == NULL && l1->next == l3);
36 test_assert(l3->prev == l1 && l3->next == l4);
37 test_assert(l4->prev == l3 && l4->next == NULL);
38 /* remove from head */
39 DLLIST_REMOVE(&head, l1);
40 test_assert(l1->prev == NULL && l1->next == NULL);
41 test_assert(head == l3);
42 test_assert(l3->prev == NULL && l3->next == l4);
43 test_assert(l4->prev == l3 && l4->next == NULL);
44 /* remove from tail */
45 DLLIST_PREPEND(&head, l1);
46 DLLIST_REMOVE(&head, l4);
47 test_assert(l4->prev == NULL && l4->next == NULL);
48 test_assert(head == l1);
49 test_assert(l1->prev == NULL && l1->next == l3);
50 test_assert(l3->prev == l1 && l3->next == NULL);
51 /* removal of an entry not in the list shouldn't cause the list to break */
52 DLLIST_REMOVE(&head, &empty);
53 test_assert(head == l1);
54 test_assert(l1->prev == NULL && l1->next == l3);
55 test_assert(l3->prev == l1 && l3->next == NULL);
56 /* remove last two */
57 DLLIST_REMOVE(&head, l1);
58 DLLIST_REMOVE(&head, l3);
59 test_assert(l3->prev == NULL && l3->next == NULL);
60 test_assert(head == NULL);
61 test_end();
62 }
63
test_dllist2(void)64 static void test_dllist2(void)
65 {
66 struct dllist *head = NULL, *tail = NULL, *l4, *l3, *l2, *l1;
67 struct dllist empty = { NULL, NULL };
68
69 l4 = t_new(struct dllist, 1);
70 l3 = t_new(struct dllist, 1);
71 l2 = t_new(struct dllist, 1);
72 l1 = t_new(struct dllist, 1);
73
74 test_begin("dllist");
75 /* prepend to empty */
76 DLLIST2_PREPEND(&head, &tail, l3);
77 test_assert(head == l3 && tail == l3);
78 test_assert(l3->next == NULL && l3->prev == NULL);
79 /* remove last */
80 DLLIST2_REMOVE(&head, &tail, l3);
81 test_assert(head == NULL && tail == NULL);
82 test_assert(l3->next == NULL && l3->prev == NULL);
83 /* append to empty */
84 DLLIST2_APPEND(&head, &tail, l3);
85 test_assert(head == l3 && tail == l3);
86 test_assert(l3->next == NULL && l3->prev == NULL);
87 /* prepend */
88 DLLIST2_PREPEND(&head, &tail, l2);
89 test_assert(head == l2 && tail == l3);
90 test_assert(l2->prev == NULL && l2->next == l3);
91 test_assert(l3->prev == l2 && l3->next == NULL);
92 /* append */
93 DLLIST2_APPEND(&head, &tail, l4);
94 test_assert(head == l2 && tail == l4);
95 test_assert(l2->prev == NULL && l2->next == l3);
96 test_assert(l3->prev == l2 && l3->next == l4);
97 test_assert(l4->prev == l3 && l4->next == NULL);
98 DLLIST2_PREPEND(&head, &tail, l1);
99
100 /* remove from middle */
101 DLLIST2_REMOVE(&head, &tail, l2);
102 test_assert(l2->prev == NULL && l2->next == NULL);
103 test_assert(head == l1 && tail == l4);
104 test_assert(l1->prev == NULL && l1->next == l3);
105 test_assert(l3->prev == l1 && l3->next == l4);
106 test_assert(l4->prev == l3 && l4->next == NULL);
107 /* remove from head */
108 DLLIST2_REMOVE(&head, &tail, l1);
109 test_assert(l1->prev == NULL && l1->next == NULL);
110 test_assert(head == l3 && tail == l4);
111 test_assert(l3->prev == NULL && l3->next == l4);
112 test_assert(l4->prev == l3 && l4->next == NULL);
113 /* remove from tail */
114 DLLIST2_PREPEND(&head, &tail, l1);
115 DLLIST2_REMOVE(&head, &tail, l4);
116 test_assert(l4->prev == NULL && l4->next == NULL);
117 test_assert(head == l1 && tail == l3);
118 test_assert(l1->prev == NULL && l1->next == l3);
119 test_assert(l3->prev == l1 && l3->next == NULL);
120 /* removal of an entry not in the list shouldn't cause the list to break */
121 DLLIST2_REMOVE(&head, &tail, &empty);
122 test_assert(head == l1);
123 test_assert(head == l1 && tail == l3);
124 test_assert(l1->prev == NULL && l1->next == l3);
125 test_assert(l3->prev == l1 && l3->next == NULL);
126 /* remove last two */
127 DLLIST2_REMOVE(&head, &tail, l1);
128 DLLIST2_REMOVE(&head, &tail, l3);
129 test_assert(l3->prev == NULL && l3->next == NULL);
130 test_assert(head == NULL && tail == NULL);
131 test_end();
132 }
133
test_llist(void)134 void test_llist(void)
135 {
136 test_dllist();
137 test_dllist2();
138 }
139