]>
Commit | Line | Data |
---|---|---|
9b0a0ba9 OZ |
1 | /* |
2 | * BIRD Library -- Linked Lists Tests | |
3 | * | |
4 | * (c) 2015 CZ.NIC z.s.p.o. | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
9 | #include "test/birdtest.h" | |
10 | #include "lib/lists.h" | |
11 | ||
12 | #define MAX_NUM 1000 | |
13 | ||
14 | static node nodes[MAX_NUM]; | |
15 | static list l; | |
16 | ||
17 | static void | |
18 | show_list(void) | |
19 | { | |
20 | bt_debug("\n"); | |
21 | bt_debug("list.null is at %p and point to %p\n", &l.null, l.null); | |
22 | bt_debug("list.head is at %p and point to %p\n", &l.head, l.head); | |
23 | bt_debug("list.tail is at %p and point to %p\n", &l.tail, l.tail); | |
24 | ||
25 | int i; | |
26 | for (i = 0; i < MAX_NUM; i++) | |
27 | { | |
28 | bt_debug("n[%3i] is at %p\n", i, &nodes[i]); | |
29 | bt_debug(" prev is at %p and point to %p\n", &(nodes[i].prev), nodes[i].prev); | |
30 | bt_debug(" next is at %p and point to %p\n", &(nodes[i].next), nodes[i].next); | |
31 | } | |
32 | } | |
33 | ||
34 | static int | |
35 | is_filled_list_well_linked(void) | |
36 | { | |
37 | int i; | |
38 | bt_assert(l.head == &nodes[0]); | |
39 | bt_assert(l.tail == &nodes[MAX_NUM-1]); | |
40 | bt_assert((void *) nodes[0].prev == (void *) &l.head); | |
41 | bt_assert((void *) nodes[MAX_NUM-1].next == (void *) &l.null); | |
42 | ||
43 | for (i = 0; i < MAX_NUM; i++) | |
44 | { | |
45 | if (i < (MAX_NUM-1)) | |
46 | bt_assert(nodes[i].next == &nodes[i+1]); | |
47 | ||
48 | if (i > 0) | |
49 | bt_assert(nodes[i].prev == &nodes[i-1]); | |
50 | } | |
51 | ||
52 | return 1; | |
53 | } | |
54 | ||
55 | static int | |
56 | is_empty_list_well_unlinked(void) | |
57 | { | |
58 | int i; | |
59 | ||
60 | bt_assert(l.head == NODE &l.null); | |
61 | bt_assert(l.tail == NODE &l.head); | |
62 | bt_assert(EMPTY_LIST(l)); | |
63 | ||
64 | for (i = 0; i < MAX_NUM; i++) | |
65 | { | |
66 | bt_assert(nodes[i].next == NULL); | |
67 | bt_assert(nodes[i].prev == NULL); | |
68 | } | |
69 | ||
70 | return 1; | |
71 | } | |
72 | ||
73 | static void | |
74 | init_list__(list *l, struct node nodes[]) | |
75 | { | |
76 | init_list(l); | |
77 | ||
78 | int i; | |
79 | for (i = 0; i < MAX_NUM; i++) | |
80 | { | |
81 | nodes[i].next = NULL; | |
82 | nodes[i].prev = NULL; | |
83 | } | |
84 | } | |
85 | ||
86 | static void | |
87 | init_list_(void) | |
88 | { | |
89 | init_list__(&l, (node *) nodes); | |
90 | } | |
91 | ||
92 | static int | |
93 | t_add_tail(void) | |
94 | { | |
95 | int i; | |
96 | ||
97 | init_list_(); | |
98 | for (i = 0; i < MAX_NUM; i++) | |
99 | { | |
100 | add_tail(&l, &nodes[i]); | |
101 | bt_debug("."); | |
102 | bt_assert(l.tail == &nodes[i]); | |
103 | bt_assert(l.head == &nodes[0]); | |
104 | bt_assert((void *) nodes[i].next == (void *) &l.null); | |
105 | if (i > 0) | |
106 | { | |
107 | bt_assert(nodes[i-1].next == &nodes[i]); | |
108 | bt_assert(nodes[i].prev == &nodes[i-1]); | |
109 | } | |
110 | } | |
111 | show_list(); | |
112 | bt_assert(is_filled_list_well_linked()); | |
113 | ||
5e3cd0e5 | 114 | return 1; |
9b0a0ba9 OZ |
115 | } |
116 | ||
117 | static int | |
118 | t_add_head(void) | |
119 | { | |
120 | int i; | |
121 | ||
122 | init_list_(); | |
123 | for (i = MAX_NUM-1; i >= 0; i--) | |
124 | { | |
125 | add_head(&l, &nodes[i]); | |
126 | bt_debug("."); | |
127 | bt_assert(l.head == &nodes[i]); | |
128 | bt_assert(l.tail == &nodes[MAX_NUM-1]); | |
129 | if (i < MAX_NUM-1) | |
130 | { | |
131 | bt_assert(nodes[i+1].prev == &nodes[i]); | |
132 | bt_assert(nodes[i].next == &nodes[i+1]); | |
133 | } | |
134 | } | |
135 | show_list(); | |
136 | bt_assert(is_filled_list_well_linked()); | |
137 | ||
5e3cd0e5 | 138 | return 1; |
9b0a0ba9 OZ |
139 | } |
140 | ||
141 | static void | |
142 | insert_node_(node *n, node *after) | |
143 | { | |
144 | insert_node(n, after); | |
145 | bt_debug("."); | |
146 | } | |
147 | ||
148 | static int | |
149 | t_insert_node(void) | |
150 | { | |
151 | int i; | |
152 | ||
153 | init_list_(); | |
154 | ||
155 | // add first node | |
156 | insert_node_(&nodes[0], NODE &l.head); | |
157 | ||
158 | // add odd nodes | |
159 | for (i = 2; i < MAX_NUM; i+=2) | |
160 | insert_node_(&nodes[i], &nodes[i-2]); | |
161 | ||
162 | // add even nodes | |
163 | for (i = 1; i < MAX_NUM; i+=2) | |
164 | insert_node_(&nodes[i], &nodes[i-1]); | |
165 | ||
166 | bt_debug("\n"); | |
167 | bt_assert(is_filled_list_well_linked()); | |
168 | ||
5e3cd0e5 | 169 | return 1; |
9b0a0ba9 OZ |
170 | } |
171 | ||
172 | static void | |
173 | fill_list2(list *l, node nodes[]) | |
174 | { | |
175 | int i; | |
176 | for (i = 0; i < MAX_NUM; i++) | |
177 | add_tail(l, &nodes[i]); | |
178 | } | |
179 | ||
180 | static void | |
181 | fill_list(void) | |
182 | { | |
183 | fill_list2(&l, (node *) nodes); | |
184 | } | |
185 | ||
186 | static int | |
187 | t_remove_node(void) | |
188 | { | |
189 | int i; | |
190 | ||
191 | init_list_(); | |
192 | ||
193 | /* Fill & Remove & Check */ | |
194 | fill_list(); | |
195 | for (i = 0; i < MAX_NUM; i++) | |
196 | rem_node(&nodes[i]); | |
197 | bt_assert(is_empty_list_well_unlinked()); | |
198 | ||
199 | /* Fill & Remove the half of nodes & Check & Remove the rest nodes & Check */ | |
200 | fill_list(); | |
201 | for (i = 0; i < MAX_NUM; i+=2) | |
202 | rem_node(&nodes[i]); | |
203 | ||
204 | int tail_node_index = (MAX_NUM % 2) ? MAX_NUM - 2 : MAX_NUM - 1; | |
205 | bt_assert(l.head == &nodes[1]); | |
206 | bt_assert(l.tail == &nodes[tail_node_index]); | |
207 | bt_assert(nodes[tail_node_index].next == NODE &l.null); | |
208 | ||
209 | for (i = 1; i < MAX_NUM; i+=2) | |
210 | { | |
211 | if (i > 1) | |
212 | bt_assert(nodes[i].prev == &nodes[i-2]); | |
213 | if (i < tail_node_index) | |
214 | bt_assert(nodes[i].next == &nodes[i+2]); | |
215 | } | |
216 | ||
217 | for (i = 1; i < MAX_NUM; i+=2) | |
218 | rem_node(&nodes[i]); | |
219 | bt_assert(is_empty_list_well_unlinked()); | |
220 | ||
5e3cd0e5 | 221 | return 1; |
9b0a0ba9 OZ |
222 | } |
223 | ||
224 | static int | |
9ac13d7a | 225 | t_update_node(void) |
9b0a0ba9 OZ |
226 | { |
227 | node head, inside, tail; | |
228 | ||
229 | init_list_(); | |
230 | fill_list(); | |
231 | ||
9ac13d7a MM |
232 | head = nodes[0]; |
233 | update_node(&head); | |
9b0a0ba9 OZ |
234 | bt_assert(l.head == &head); |
235 | bt_assert(head.prev == NODE &l.head); | |
236 | bt_assert(head.next == &nodes[1]); | |
237 | bt_assert(nodes[1].prev == &head); | |
238 | ||
9ac13d7a MM |
239 | inside = nodes[MAX_NUM/2]; |
240 | update_node(&inside); | |
9b0a0ba9 OZ |
241 | bt_assert(nodes[MAX_NUM/2-1].next == &inside); |
242 | bt_assert(nodes[MAX_NUM/2+1].prev == &inside); | |
243 | bt_assert(inside.prev == &nodes[MAX_NUM/2-1]); | |
244 | bt_assert(inside.next == &nodes[MAX_NUM/2+1]); | |
245 | ||
9ac13d7a MM |
246 | tail = nodes[MAX_NUM-1]; |
247 | update_node(&tail); | |
9b0a0ba9 OZ |
248 | bt_assert(l.tail == &tail); |
249 | bt_assert(tail.prev == &nodes[MAX_NUM-2]); | |
250 | bt_assert(tail.next == NODE &l.null); | |
251 | bt_assert(nodes[MAX_NUM-2].next == &tail); | |
252 | ||
5e3cd0e5 | 253 | return 1; |
9b0a0ba9 OZ |
254 | } |
255 | ||
256 | static int | |
257 | t_add_tail_list(void) | |
258 | { | |
259 | node nodes2[MAX_NUM]; | |
260 | list l2; | |
261 | ||
262 | init_list__(&l, (node *) nodes); | |
263 | fill_list2(&l, (node *) nodes); | |
264 | ||
265 | init_list__(&l2, (node *) nodes2); | |
266 | fill_list2(&l2, (node *) nodes2); | |
267 | ||
268 | add_tail_list(&l, &l2); | |
269 | ||
270 | bt_assert(nodes[MAX_NUM-1].next == &nodes2[0]); | |
271 | bt_assert(nodes2[0].prev == &nodes[MAX_NUM-1]); | |
272 | bt_assert(l.tail == &nodes2[MAX_NUM-1]); | |
273 | ||
5e3cd0e5 | 274 | return 1; |
9b0a0ba9 OZ |
275 | } |
276 | ||
277 | int | |
278 | main(int argc, char *argv[]) | |
279 | { | |
280 | bt_init(argc, argv); | |
281 | ||
282 | bt_test_suite(t_add_tail, "Adding nodes to tail of list"); | |
283 | bt_test_suite(t_add_head, "Adding nodes to head of list"); | |
284 | bt_test_suite(t_insert_node, "Inserting nodes to list"); | |
285 | bt_test_suite(t_remove_node, "Removing nodes from list"); | |
9ac13d7a | 286 | bt_test_suite(t_update_node, "Updating nodes in list"); |
9b0a0ba9 OZ |
287 | bt_test_suite(t_add_tail_list, "At the tail of a list adding the another list"); |
288 | ||
289 | return bt_exit_value(); | |
290 | } |