librfn
An ad-hoc utility library
listtest.c
Go to the documentation of this file.
1 /*
2  * listtest.c
3  *
4  * Part of librfn (a general utility library from redfelineninja.org.uk)
5  *
6  * Copyright (C) 2013 Daniel Thompson <daniel@redfelineninja.org.uk>
7  *
8  * This program is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License as published
10  * by the Free Software Foundation; either version 3 of the License, or
11  * (at your option) any later version.
12  */
13 
14 #undef NDEBUG
15 
16 #include <assert.h>
17 #include <stdio.h>
18 #include <stdlib.h>
19 
20 #include <librfn.h>
21 
22 static int address_comparison(list_node_t *n1, list_node_t *n2)
23 {
24  return n1 - n2;
25 }
26 
27 static void test_list_insert()
28 {
29  list_t list = { 0 };
30  list_node_t n1 = { 0 };
31  list_node_t n2 = { 0 };
32  list_node_t n3 = { 0 };
33 
34  verify(NULL == list_extract(&list));
35  verify(NULL == list_extract(&list));
36 
37  list_insert(&list, &n1);
38  verify(&n1 == list_extract(&list));
39  verify(NULL == list_extract(&list));
40 
41  list_insert(&list, &n1);
42  verify(&n1 == list_extract(&list));
43  verify(NULL == list_extract(&list));
44 
45  list_insert(&list, &n1);
46  list_insert(&list, &n2);
47  verify(&n1 == list_extract(&list));
48  verify(&n2 == list_extract(&list));
49  verify(NULL == list_extract(&list));
50 
51  list_insert(&list, &n1);
52  list_insert(&list, &n2);
53  list_insert(&list, &n3);
54  verify(&n1 == list_extract(&list));
55  verify(&n2 == list_extract(&list));
56  verify(&n3 == list_extract(&list));
57  verify(NULL == list_extract(&list));
58 }
59 
60 static void test_list_push()
61 {
62  list_t list = { 0 };
63  list_node_t n1 = { 0 };
64  list_node_t n2 = { 0 };
65  list_node_t n3 = { 0 };
66 
67  verify(NULL == list_extract(&list));
68  verify(NULL == list_extract(&list));
69 
70  list_push(&list, &n1);
71  verify(&n1 == list_extract(&list));
72  verify(NULL == list_extract(&list));
73 
74  list_push(&list, &n1);
75  verify(&n1 == list_extract(&list));
76  verify(NULL == list_extract(&list));
77 
78  list_push(&list, &n1);
79  list_push(&list, &n2);
80  verify(&n2 == list_extract(&list));
81  verify(&n1 == list_extract(&list));
82  verify(NULL == list_extract(&list));
83 
84  list_push(&list, &n1);
85  list_push(&list, &n2);
86  list_push(&list, &n3);
87  verify(&n3 == list_extract(&list));
88  verify(&n2 == list_extract(&list));
89  verify(&n1 == list_extract(&list));
90  verify(NULL == list_extract(&list));
91 }
92 
93 static void test_list_insert_sorted()
94 {
95  list_t list = { 0 };
96  list_node_t n[3] = { { 0 } };
97 
98  verify(NULL == list_extract(&list));
99  verify(NULL == list_extract(&list));
100 
101  list_insert_sorted(&list, n+0, address_comparison);
102  verify(n+0 == list_extract(&list));
103  verify(NULL == list_extract(&list));
104 
105  list_insert_sorted(&list, n+0, address_comparison);
106  verify(n+0 == list_extract(&list));
107  verify(NULL == list_extract(&list));
108 
109  list_insert_sorted(&list, n+0, address_comparison);
110  list_insert_sorted(&list, n+1, address_comparison);
111  verify(n+0 == list_extract(&list));
112  verify(n+1 == list_extract(&list));
113  verify(NULL == list_extract(&list));
114 
115  list_insert_sorted(&list, n+1, address_comparison);
116  list_insert_sorted(&list, n+0, address_comparison);
117  verify(n+0 == list_extract(&list));
118  verify(n+1 == list_extract(&list));
119  verify(NULL == list_extract(&list));
120 
121  /* insert at end */
122  list_insert_sorted(&list, n+0, address_comparison);
123  list_insert_sorted(&list, n+1, address_comparison);
124  list_insert_sorted(&list, n+2, address_comparison);
125  verify(n+0 == list_extract(&list));
126  verify(n+1 == list_extract(&list));
127  verify(n+2 == list_extract(&list));
128  verify(NULL == list_extract(&list));
129 
130  /* insert at beginning */
131  list_insert_sorted(&list, n+2, address_comparison);
132  list_insert_sorted(&list, n+1, address_comparison);
133  list_insert_sorted(&list, n+0, address_comparison);
134  verify(n+0 == list_extract(&list));
135  verify(n+1 == list_extract(&list));
136  verify(n+2 == list_extract(&list));
137  verify(NULL == list_extract(&list));
138 
139  /* insert into middle */
140  list_insert_sorted(&list, n+2, address_comparison);
141  list_insert_sorted(&list, n+0, address_comparison);
142  list_insert_sorted(&list, n+1, address_comparison);
143  verify(n+0 == list_extract(&list));
144  verify(n+1 == list_extract(&list));
145  verify(n+2 == list_extract(&list));
146  verify(NULL == list_extract(&list));
147 }
148 
149 static void test_list_iterate()
150 {
151  list_t list = { 0 };
152  list_node_t n1 = { 0 };
153  list_node_t n2 = { 0 };
154  list_node_t n3 = { 0 };
155 
156  list_insert(&list, &n1);
157  list_insert(&list, &n2);
158  list_insert(&list, &n3);
159 
160  list_iterator_t iter;
161  verify(&n1 == list_iterate(&list, &iter));
162  verify(&n2 == list_iterator_next(&iter));
163  verify(&n3 == list_iterator_next(&iter));
164  verify(NULL == list_iterator_next(&iter));
165  verify(NULL == list_iterator_next(&iter));
166 
167  // no dynamic allocation so no need to clean up
168 }
169 
170 static void test_list_iterator_insert_remove()
171 {
172  list_t list = { 0 };
173  list_node_t n1 = { 0 };
174  list_node_t n2 = { 0 };
175  list_node_t n3 = { 0 };
176  list_node_t n4 = { 0 };
177  list_iterator_t iter;
178 
179  /* insert into empty list */
180  verify(NULL == list_iterate(&list, &iter));
181  list_iterator_insert(&iter, &n4);
182  verify(NULL == list_iterator_next(&iter));
183 
184  verify(&n4 == list_iterate(&list, &iter));
185  verify(NULL == list_iterator_next(&iter));
186 
187  /* remove from singleton list */
188  verify(&n4 == list_iterate(&list, &iter));
189  verify(NULL == list_iterator_remove(&iter));
190  verify(NULL == list_iterator_next(&iter));
191 
192  verify(NULL == list_iterate(&list, &iter));
193 
194  /* prepare list from remaining tests (testing interoperation with
195  * list_insert() in the process) */
196  verify(NULL == list_iterate(&list, &iter));
197  list_iterator_insert(&iter, &n2);
198  list_iterator_insert(&iter, &n1);
199  list_insert(&list, &n3);
200  verify(&n1 == list_iterate(&list, &iter));
201  verify(&n2 == list_iterator_next(&iter));
202  verify(&n3 == list_iterator_next(&iter));
203  verify(NULL == list_iterator_next(&iter));
204 
205  /* insert at beginning */
206  verify(&n1 == list_iterate(&list, &iter));
207  list_iterator_insert(&iter, &n4);
208  verify(&n1 == list_iterator_next(&iter));
209 
210  verify(&n4 == list_iterate(&list, &iter));
211  verify(&n1 == list_iterator_next(&iter));
212  verify(&n2 == list_iterator_next(&iter));
213  verify(&n3 == list_iterator_next(&iter));
214  verify(NULL == list_iterator_next(&iter));
215 
216  /* remove from beginning */
217  verify(&n4 == list_iterate(&list, &iter));
218  verify(&n1 == list_iterator_remove(&iter));
219  verify(&n2 == list_iterator_next(&iter));
220 
221  verify(&n1 == list_iterate(&list, &iter));
222  verify(&n2 == list_iterator_next(&iter));
223  verify(&n3 == list_iterator_next(&iter));
224  verify(NULL == list_iterator_next(&iter));
225 
226  /* insert at end */
227  verify(&n1 == list_iterate(&list, &iter));
228  verify(&n2 == list_iterator_next(&iter));
229  verify(&n3 == list_iterator_next(&iter));
230  verify(NULL == list_iterator_next(&iter));
231  list_iterator_insert(&iter, &n4);
232  verify(NULL == list_iterator_next(&iter));
233 
234  verify(&n1 == list_iterate(&list, &iter));
235  verify(&n2 == list_iterator_next(&iter));
236  verify(&n3 == list_iterator_next(&iter));
237  verify(&n4 == list_iterator_next(&iter));
238  verify(NULL == list_iterator_next(&iter));
239 
240  /* remove from end */
241  verify(&n1 == list_iterate(&list, &iter));
242  verify(&n2 == list_iterator_next(&iter));
243  verify(&n3 == list_iterator_next(&iter));
244  verify(&n4 == list_iterator_next(&iter));
245  verify(NULL == list_iterator_remove(&iter));
246 
247  verify(&n1 == list_iterate(&list, &iter));
248  verify(&n2 == list_iterator_next(&iter));
249  verify(&n3 == list_iterator_next(&iter));
250  verify(NULL == list_iterator_next(&iter));
251 
252  /* insert in middle */
253  verify(&n1 == list_iterate(&list, &iter));
254  verify(&n2 == list_iterator_next(&iter));
255  list_iterator_insert(&iter, &n4);
256  verify(&n2 == list_iterator_next(&iter));
257 
258  verify(&n1 == list_iterate(&list, &iter));
259  verify(&n4 == list_iterator_next(&iter));
260  verify(&n2 == list_iterator_next(&iter));
261  verify(&n3 == list_iterator_next(&iter));
262  verify(NULL == list_iterator_next(&iter));
263 
264  /* remove from middle */
265  verify(&n1 == list_iterate(&list, &iter));
266  verify(&n4 == list_iterator_next(&iter));
267  verify(&n2 == list_iterator_remove(&iter));
268 
269  verify(&n1 == list_iterate(&list, &iter));
270  verify(&n2 == list_iterator_next(&iter));
271  verify(&n3 == list_iterator_next(&iter));
272  verify(NULL == list_iterator_next(&iter));
273 
274  /* test interoperation between remove and list_insert */
275  /* (this test is a regression test introduced after code review) */
276  verify(&n1 == list_iterate(&list, &iter));
277  verify(&n2 == list_iterator_next(&iter));
278  verify(&n3 == list_iterator_next(&iter));
279  verify(NULL == list_iterator_remove(&iter));
280  list_insert(&list, &n4);
281  verify(&n1 == list_iterate(&list, &iter));
282  verify(&n2 == list_iterator_next(&iter));
283  verify(&n4 == list_iterator_next(&iter));
284  verify(NULL == list_iterator_remove(&iter));
285  list_iterator_insert(&iter, &n3);
286  list_insert(&list, &n4);
287  verify(&n1 == list_iterate(&list, &iter));
288  verify(&n2 == list_iterator_next(&iter));
289  verify(&n3 == list_iterator_next(&iter));
290  verify(&n4 == list_iterator_next(&iter));
291  list_iterator_remove(&iter);
292 
293  verify(&n1 == list_iterate(&list, &iter));
294  verify(&n2 == list_iterator_next(&iter));
295  verify(&n3 == list_iterator_next(&iter));
296  verify(NULL == list_iterator_next(&iter));
297 
298  // no dynamic allocation so no need to clean up
299 }
300 
301 static void test_list_contains()
302 {
303  list_t list = { 0 };
304  list_node_t n1 = { 0 };
305  list_node_t n2 = { 0 };
306  list_node_t n3 = { 0 };
307  list_node_t n4 = { 0 };
308  list_iterator_t iter;
309 
310  list_insert(&list, &n1);
311  verify(true == list_contains(&list, &n1, NULL));
312  verify(true == list_contains(&list, &n1, &iter));
313  verify(NULL == list_iterator_next(&iter));
314  verify(false == list_contains(&list, &n2, NULL));
315  verify(false == list_contains(&list, &n2, &iter));
316 
317  list_insert(&list, &n2);
318  verify(true == list_contains(&list, &n1, &iter));
319  verify(&n2 == list_iterator_next(&iter));
320  verify(true == list_contains(&list, &n2, &iter));
321  verify(NULL == list_iterator_next(&iter));
322  verify(false == list_contains(&list, &n3, &iter));
323 
324  list_insert(&list, &n3);
325  verify(true == list_contains(&list, &n3, &iter));
326  verify(NULL == list_iterator_next(&iter));
327  verify(true == list_contains(&list, &n2, &iter));
328  verify(&n3 == list_iterator_next(&iter));
329  verify(true == list_contains(&list, &n1, &iter));
330  verify(&n2 == list_iterator_next(&iter));
331  verify(false == list_contains(&list, &n4, &iter));
332 }
333 
334 static void test_list_remove()
335 {
336  list_t list = { 0 };
337  list_node_t n1 = { 0 };
338  list_node_t n2 = { 0 };
339  list_node_t n3 = { 0 };
340  list_iterator_t iter;
341 
342  verify(false == list_remove(&list, &n1));
343 
344  list_insert(&list, &n1);
345  verify(true == list_remove(&list, &n1));
346  verify(false == list_remove(&list, &n1));
347  verify(NULL == list_iterate(&list, &iter));
348 
349  list_insert(&list, &n1);
350  list_insert(&list, &n2);
351  list_insert(&list, &n3);
352 
353  /* remove from the beginning */
354  verify(true == list_remove(&list, &n1));
355  verify(false == list_remove(&list, &n1));
356  verify(&n2 == list_iterate(&list, &iter));
357  verify(&n3 == list_iterator_next(&iter));
358  verify(NULL == list_iterator_next(&iter));
359  list_push(&list, &n1);
360 
361  verify(&n1 == list_iterate(&list, &iter));
362  verify(&n2 == list_iterator_next(&iter));
363  verify(&n3 == list_iterator_next(&iter));
364  verify(NULL == list_iterator_next(&iter));
365 
366  /* remove from the middle */
367  verify(true == list_remove(&list, &n2));
368  verify(false == list_remove(&list, &n2));
369  verify(&n1 == list_iterate(&list, &iter));
370  verify(&n3 == list_iterator_next(&iter));
371  list_iterator_insert(&iter, &n2);
372  verify(&n3 == list_iterator_next(&iter));
373  verify(NULL == list_iterator_next(&iter));
374 
375  verify(&n1 == list_iterate(&list, &iter));
376  verify(&n2 == list_iterator_next(&iter));
377  verify(&n3 == list_iterator_next(&iter));
378  verify(NULL == list_iterator_next(&iter));
379 
380  /* remove from the end */
381  verify(true == list_remove(&list, &n3));
382  verify(false == list_remove(&list, &n3));
383  verify(&n1 == list_iterate(&list, &iter));
384  verify(&n2 == list_iterator_next(&iter));
385  verify(NULL == list_iterator_next(&iter));
386  list_insert(&list, &n3);
387 
388  verify(&n1 == list_iterate(&list, &iter));
389  verify(&n2 == list_iterator_next(&iter));
390  verify(&n3 == list_iterator_next(&iter));
391  verify(NULL == list_iterator_next(&iter));
392 
393  // no dynamic allocation so no need to clean up
394 }
395 
396 int main()
397 {
398  test_list_insert();
399  test_list_push();
400  test_list_insert_sorted();
401  test_list_iterate();
402  test_list_iterator_insert_remove();
403  test_list_contains();
404  test_list_remove();
405 
406  return 0;
407 }
list_iterate
list_node_t * list_iterate(list_t *list, list_iterator_t *iter)
Definition: list.c:91
list_t
Definition: list.h:39
list_contains
bool list_contains(list_t *list, list_node_t *node, list_iterator_t *iter)
Definition: list.c:155
list_iterator_next
list_node_t * list_iterator_next(list_iterator_t *iter)
Definition: list.c:99
list_iterator_t
Definition: list.h:45
list_iterator_insert
void list_iterator_insert(list_iterator_t *iter, list_node_t *node)
Definition: list.c:113
list_iterator_remove
list_node_t * list_iterator_remove(list_iterator_t *iter)
Definition: list.c:124
main
int main()
Definition: listtest.c:396
verify
#define verify(x)
Definition: util.h:55
list_insert
void list_insert(list_t *list, list_node_t *node)
Definition: list.c:21
list_node
Definition: list.h:34
list_insert_sorted
void list_insert_sorted(list_t *list, list_node_t *node, list_node_compare_t *nodecmp)
Definition: list.c:34
list_extract
list_node_t * list_extract(list_t *list)
Definition: list.c:77
list_push
void list_push(list_t *list, list_node_t *node)
Definition: list.c:65
list_remove
bool list_remove(list_t *list, list_node_t *node)
Definition: list.c:171
Generated on Sat Feb 6 2016 21:25:32 for librfn by   doxygen 1.8.10