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