Doubly linked lists unit test and update to implementation.
[asterisk/asterisk.git] / tests / test_linkedlists.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2011, Terry Wilson
5  *
6  * See http://www.asterisk.org for more information about
7  * the Asterisk project. Please do not directly contact
8  * any of the maintainers of this project for assistance;
9  * the project provides a web site, mailing lists and IRC
10  * channels for your use.
11  *
12  * This program is free software, distributed under the terms of
13  * the GNU General Public License Version 2. See the LICENSE file
14  * at the top of the source tree.
15  */
16
17 /*! \file
18  *
19  * \brief Linked List Tests
20  *
21  * \author Terry Wilson <twilson@digium.com>
22  *
23  * \ingroup tests
24  */
25
26 /*** MODULEINFO
27         <depend>TEST_FRAMEWORK</depend>
28         <support_level>core</support_level>
29  ***/
30
31 #include "asterisk.h"
32
33 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
34
35 #include "asterisk/module.h"
36 #include "asterisk/test.h"
37 #include "asterisk/strings.h"
38 #include "asterisk/logger.h"
39 #include "asterisk/linkedlists.h"
40 #include "asterisk/dlinkedlists.h"
41
42 struct test_val {
43         const char *name;
44         AST_LIST_ENTRY(test_val) list;
45         AST_DLLIST_ENTRY(test_val) dbl_list;
46 };
47
48 static struct test_val a = { "A" };
49 static struct test_val b = { "B" };
50 static struct test_val c = { "C" };
51 static struct test_val d = { "D" };
52
53 AST_LIST_HEAD_NOLOCK(test_llist, test_val);
54 AST_DLLIST_HEAD_NOLOCK(test_dbl_llist, test_val);
55
56 static int list_expect(struct test_llist *test_list, const char *expect, struct ast_str **buf)
57 {
58         struct test_val *i;
59
60         ast_str_reset(*buf);
61         AST_LIST_TRAVERSE(test_list, i, list) {
62                 ast_str_append(buf, 0, "%s", i->name);
63         }
64
65         return strcmp(expect, ast_str_buffer(*buf));
66 }
67
68 static int dbl_list_expect_forward(struct test_dbl_llist *test_list, const char *expect, struct ast_str **buf)
69 {
70         struct test_val *i;
71
72         ast_str_reset(*buf);
73         AST_DLLIST_TRAVERSE(test_list, i, dbl_list) {
74                 ast_str_append(buf, 0, "%s", i->name);
75         }
76
77         return strcmp(expect, ast_str_buffer(*buf));
78 }
79
80 static int dbl_list_expect_reverse(struct test_dbl_llist *test_list, const char *expect, struct ast_str **buf)
81 {
82         struct test_val *i;
83         char *str;
84         int len = strlen(expect);
85         int idx;
86
87         ast_str_reset(*buf);
88         AST_DLLIST_TRAVERSE_BACKWARDS(test_list, i, dbl_list) {
89                 ast_str_append(buf, 0, "%s", i->name);
90         }
91
92         /* Check reverse string. */
93         str = ast_str_buffer(*buf);
94         if (len != strlen(str)) {
95                 return 1;
96         }
97         for (idx = 0; idx < len; ++idx) {
98                 if (expect[idx] != str[len - idx - 1]) {
99                         return 1;
100                 }
101         }
102         return 0;
103 }
104
105 #define MATCH_OR_FAIL(list, val, retbuf) \
106         if (list_expect(list, val, &retbuf)) { \
107                 ast_test_status_update(test, "Expected: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \
108                 ast_free(retbuf); \
109                 return AST_TEST_FAIL; \
110         }
111
112 #define MATCH_OR_FAIL_DBL(list, val, retbuf) \
113         if (dbl_list_expect_forward(list, val, &retbuf)) { \
114                 ast_test_status_update(test, "Expected: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \
115                 ast_free(retbuf); \
116                 return AST_TEST_FAIL; \
117         } \
118         if (dbl_list_expect_reverse(list, val, &retbuf)) { \
119                 ast_test_status_update(test, "Expected reverse of: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \
120                 ast_free(retbuf); \
121                 return AST_TEST_FAIL; \
122         }
123
124 #define ELEM_OR_FAIL(x,y) \
125         if ((x) != (y)) { \
126                 ast_test_status_update(test, "Expected: %s, Got: %s\n", (x)->name, (y)->name); \
127                 return AST_TEST_FAIL; \
128         }
129
130 AST_TEST_DEFINE(single_ll_tests)
131 {
132         struct ast_str *buf;
133         struct test_llist test_list = { 0, };
134         struct test_llist other_list = { 0, };
135         struct test_val *bogus;
136
137         switch (cmd) {
138         case TEST_INIT:
139                 info->name = "ll_tests";
140                 info->category = "/main/linkedlists";
141                 info->summary = "single linked list unit test";
142                 info->description =
143                         "Test the single linked list API";
144                 return AST_TEST_NOT_RUN;
145         case TEST_EXECUTE:
146                 break;
147         }
148
149         if (!(buf = ast_str_create(16))) {
150                 return AST_TEST_FAIL;
151         }
152
153         if (!(bogus = alloca(sizeof(*bogus)))) {
154                 return AST_TEST_FAIL;
155         }
156
157         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
158                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL for missing element from empty list\n");
159                 return AST_TEST_FAIL;
160         }
161
162         /* INSERT_HEAD and REMOVE_HEAD tests */
163         AST_LIST_INSERT_HEAD(&test_list, &a, list);
164         MATCH_OR_FAIL(&test_list, "A", buf);
165         AST_LIST_INSERT_HEAD(&test_list, &b, list);
166         MATCH_OR_FAIL(&test_list, "BA", buf);
167         AST_LIST_REMOVE_HEAD(&test_list, list);
168         MATCH_OR_FAIL(&test_list, "A", buf);
169         AST_LIST_REMOVE_HEAD(&test_list, list);
170         MATCH_OR_FAIL(&test_list, "", buf);
171         if (AST_LIST_REMOVE_HEAD(&test_list, list)) {
172                 ast_test_status_update(test, "Somehow removed an item from the head of a list that didn't exist\n");
173                 return AST_TEST_FAIL;
174         }
175         MATCH_OR_FAIL(&test_list, "", buf);
176
177         /* Check empty list test */
178
179         if (!AST_LIST_EMPTY(&test_list)) {
180                 ast_test_status_update(test, "List should be empty\n");
181                 return AST_TEST_FAIL;
182         }
183
184         /* Insert tail and remove specific item tests. */
185
186         AST_LIST_INSERT_TAIL(&test_list, &a, list);
187         MATCH_OR_FAIL(&test_list, "A", buf);
188         AST_LIST_INSERT_TAIL(&test_list, &b, list);
189         MATCH_OR_FAIL(&test_list, "AB", buf);
190         AST_LIST_INSERT_TAIL(&test_list, &c, list);
191         MATCH_OR_FAIL(&test_list, "ABC", buf);
192         AST_LIST_INSERT_TAIL(&test_list, &d, list);
193         MATCH_OR_FAIL(&test_list, "ABCD", buf);
194         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
195                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL for missing element\n");
196                 return AST_TEST_FAIL;
197         }
198         bogus = NULL;
199         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
200                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL for element set to NULL\n");
201                 return AST_TEST_FAIL;
202         }
203         AST_LIST_REMOVE(&test_list, &b, list);
204         MATCH_OR_FAIL(&test_list, "ACD", buf);
205         AST_LIST_REMOVE(&test_list, &d, list);
206         MATCH_OR_FAIL(&test_list, "AC", buf);
207         AST_LIST_REMOVE(&test_list, &a, list);
208         MATCH_OR_FAIL(&test_list, "C", buf);
209         AST_LIST_REMOVE(&test_list, &c, list);
210         MATCH_OR_FAIL(&test_list, "", buf);
211         if (!AST_LIST_EMPTY(&test_list)) {
212                 ast_test_status_update(test, "List should be empty\n");
213                 return AST_TEST_FAIL;
214         }
215         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
216                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL asked to remove a NULL pointer from an empty list\n");
217                 return AST_TEST_FAIL;
218         }
219
220         /* Insert item after specific item tests */
221
222         AST_LIST_INSERT_HEAD(&test_list, &a, list);
223         MATCH_OR_FAIL(&test_list, "A", buf);
224         AST_LIST_INSERT_TAIL(&test_list, &c, list);
225         MATCH_OR_FAIL(&test_list, "AC", buf);
226         AST_LIST_INSERT_AFTER(&test_list, &a, &b, list);
227         MATCH_OR_FAIL(&test_list, "ABC", buf);
228         AST_LIST_INSERT_AFTER(&test_list, &c, &d, list);
229         MATCH_OR_FAIL(&test_list, "ABCD", buf);
230
231         ELEM_OR_FAIL(AST_LIST_FIRST(&test_list), &a);
232         ELEM_OR_FAIL(AST_LIST_LAST(&test_list), &d);
233         ELEM_OR_FAIL(AST_LIST_NEXT(&a, list), &b);
234
235         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
236                 AST_LIST_REMOVE_CURRENT(list);
237         }
238         AST_LIST_TRAVERSE_SAFE_END;
239
240         if (!AST_LIST_EMPTY(&test_list)) {
241                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
242                 return AST_TEST_FAIL;
243         }
244
245         /* Append list test */
246
247         AST_LIST_INSERT_HEAD(&test_list, &a, list);
248         MATCH_OR_FAIL(&test_list, "A", buf);
249         AST_LIST_INSERT_TAIL(&test_list, &b, list);
250         MATCH_OR_FAIL(&test_list, "AB", buf);
251         AST_LIST_INSERT_HEAD(&other_list, &c, list);
252         MATCH_OR_FAIL(&other_list, "C", buf);
253         AST_LIST_INSERT_TAIL(&other_list, &d, list);
254         MATCH_OR_FAIL(&other_list, "CD", buf);
255         AST_LIST_APPEND_LIST(&test_list, &other_list, list);
256         MATCH_OR_FAIL(&test_list, "ABCD", buf);
257         MATCH_OR_FAIL(&other_list, "", buf);
258         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
259                 AST_LIST_REMOVE_CURRENT(list);
260         }
261         AST_LIST_TRAVERSE_SAFE_END;
262         if (!AST_LIST_EMPTY(&test_list)) {
263                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
264                 return AST_TEST_FAIL;
265         }
266
267         /* Insert list after specific item in middle test */
268
269         AST_LIST_INSERT_HEAD(&test_list, &a, list);
270         MATCH_OR_FAIL(&test_list, "A", buf);
271         AST_LIST_INSERT_TAIL(&test_list, &d, list);
272         MATCH_OR_FAIL(&test_list, "AD", buf);
273         AST_LIST_INSERT_HEAD(&other_list, &b, list);
274         MATCH_OR_FAIL(&other_list, "B", buf);
275         AST_LIST_INSERT_TAIL(&other_list, &c, list);
276         MATCH_OR_FAIL(&other_list, "BC", buf);
277         AST_LIST_INSERT_LIST_AFTER(&test_list, &other_list, &a, list);
278         MATCH_OR_FAIL(&test_list, "ABCD", buf);
279         MATCH_OR_FAIL(&other_list, "", buf);
280         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
281                 AST_LIST_REMOVE_CURRENT(list);
282         }
283         AST_LIST_TRAVERSE_SAFE_END;
284         if (!AST_LIST_EMPTY(&test_list)) {
285                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
286                 return AST_TEST_FAIL;
287         }
288
289         /* Insert list after specific item on end test */
290
291         AST_LIST_INSERT_HEAD(&test_list, &a, list);
292         MATCH_OR_FAIL(&test_list, "A", buf);
293         AST_LIST_INSERT_TAIL(&test_list, &b, list);
294         MATCH_OR_FAIL(&test_list, "AB", buf);
295         AST_LIST_INSERT_HEAD(&other_list, &c, list);
296         MATCH_OR_FAIL(&other_list, "C", buf);
297         AST_LIST_INSERT_TAIL(&other_list, &d, list);
298         MATCH_OR_FAIL(&other_list, "CD", buf);
299         AST_LIST_INSERT_LIST_AFTER(&test_list, &other_list, &b, list);
300         MATCH_OR_FAIL(&test_list, "ABCD", buf);
301         MATCH_OR_FAIL(&other_list, "", buf);
302         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
303                 AST_LIST_REMOVE_CURRENT(list);
304         }
305         AST_LIST_TRAVERSE_SAFE_END;
306         if (!AST_LIST_EMPTY(&test_list)) {
307                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
308                 return AST_TEST_FAIL;
309         }
310
311         /* Safe traversal list modification tests */
312
313         AST_LIST_INSERT_HEAD(&test_list, &a, list);
314         MATCH_OR_FAIL(&test_list, "A", buf);
315         AST_LIST_INSERT_TAIL(&test_list, &d, list);
316         MATCH_OR_FAIL(&test_list, "AD", buf);
317         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
318                 if (bogus == &d) {
319                         AST_LIST_INSERT_BEFORE_CURRENT(&b, list);
320                         MATCH_OR_FAIL(&test_list, "ABD", buf);
321                         AST_LIST_INSERT_BEFORE_CURRENT(&c, list);
322                         MATCH_OR_FAIL(&test_list, "ABCD", buf);
323                         AST_LIST_REMOVE_CURRENT(list);
324                         MATCH_OR_FAIL(&test_list, "ABC", buf);
325                 }
326         }
327         AST_LIST_TRAVERSE_SAFE_END;
328         MATCH_OR_FAIL(&test_list, "ABC", buf);
329         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
330                 AST_LIST_REMOVE_CURRENT(list);
331         }
332         AST_LIST_TRAVERSE_SAFE_END;
333         if (!AST_LIST_EMPTY(&test_list)) {
334                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
335                 return AST_TEST_FAIL;
336         }
337
338         return AST_TEST_PASS;
339 }
340
341 AST_TEST_DEFINE(double_ll_tests)
342 {
343         struct ast_str *buf;
344         struct test_dbl_llist test_list = { 0, };
345         struct test_dbl_llist other_list = { 0, };
346         struct test_val *bogus;
347
348         switch (cmd) {
349         case TEST_INIT:
350                 info->name = "double_ll_tests";
351                 info->category = "/main/linkedlists";
352                 info->summary = "double linked list unit test";
353                 info->description =
354                         "Test the double linked list API";
355                 return AST_TEST_NOT_RUN;
356         case TEST_EXECUTE:
357                 break;
358         }
359
360         if (!(buf = ast_str_create(16))) {
361                 return AST_TEST_FAIL;
362         }
363
364         if (!(bogus = alloca(sizeof(*bogus)))) {
365                 return AST_TEST_FAIL;
366         }
367
368         if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) {
369                 ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for missing element from empty list\n");
370                 return AST_TEST_FAIL;
371         }
372
373         /* INSERT_HEAD and REMOVE_HEAD tests */
374         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
375         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
376         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
377         MATCH_OR_FAIL_DBL(&test_list, "BA", buf);
378         AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list);
379         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
380         AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list);
381         MATCH_OR_FAIL_DBL(&test_list, "", buf);
382         if (AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list)) {
383                 ast_test_status_update(test, "Somehow removed an item from the head of a list that didn't exist\n");
384                 return AST_TEST_FAIL;
385         }
386         MATCH_OR_FAIL_DBL(&test_list, "", buf);
387
388         /* Check empty list test */
389
390         if (!AST_DLLIST_EMPTY(&test_list)) {
391                 ast_test_status_update(test, "List should be empty\n");
392                 return AST_TEST_FAIL;
393         }
394
395         /* Insert tail and remove specific item tests. */
396
397         AST_DLLIST_INSERT_TAIL(&test_list, &a, dbl_list);
398         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
399         AST_DLLIST_INSERT_TAIL(&test_list, &b, dbl_list);
400         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
401         AST_DLLIST_INSERT_TAIL(&test_list, &c, dbl_list);
402         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
403         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
404         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
405         if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) {
406                 ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for missing element\n");
407                 return AST_TEST_FAIL;
408         }
409         bogus = NULL;
410         if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) {
411                 ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for element set to NULL\n");
412                 return AST_TEST_FAIL;
413         }
414         AST_DLLIST_REMOVE(&test_list, &b, dbl_list);
415         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
416         AST_DLLIST_REMOVE(&test_list, &d, dbl_list);
417         MATCH_OR_FAIL_DBL(&test_list, "AC", buf);
418         AST_DLLIST_REMOVE(&test_list, &a, dbl_list);
419         MATCH_OR_FAIL_DBL(&test_list, "C", buf);
420         AST_DLLIST_REMOVE(&test_list, &c, dbl_list);
421         MATCH_OR_FAIL_DBL(&test_list, "", buf);
422         if (!AST_DLLIST_EMPTY(&test_list)) {
423                 ast_test_status_update(test, "List should be empty\n");
424                 return AST_TEST_FAIL;
425         }
426         if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) {
427                 ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL asked to remove a NULL pointer from an empty list\n");
428                 return AST_TEST_FAIL;
429         }
430
431         /* Insert item after and before specific item tests */
432
433         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
434         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
435         AST_DLLIST_INSERT_TAIL(&test_list, &c, dbl_list);
436         MATCH_OR_FAIL_DBL(&test_list, "AC", buf);
437         AST_DLLIST_INSERT_AFTER(&test_list, &a, &b, dbl_list);
438         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
439         AST_DLLIST_INSERT_AFTER(&test_list, &c, &d, dbl_list);
440         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
441         AST_DLLIST_REMOVE_TAIL(&test_list, dbl_list);
442         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
443         AST_DLLIST_REMOVE_TAIL(&test_list, dbl_list);
444         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
445         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
446         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
447         AST_DLLIST_INSERT_BEFORE(&test_list, &d, &c, dbl_list);
448         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
449         AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list);
450         MATCH_OR_FAIL_DBL(&test_list, "BCD", buf);
451         AST_DLLIST_INSERT_BEFORE(&test_list, &b, &a, dbl_list);
452         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
453
454         ELEM_OR_FAIL(AST_DLLIST_FIRST(&test_list), &a);
455         ELEM_OR_FAIL(AST_DLLIST_LAST(&test_list), &d);
456         ELEM_OR_FAIL(AST_DLLIST_NEXT(&a, dbl_list), &b);
457         ELEM_OR_FAIL(AST_DLLIST_PREV(&b, dbl_list), &a);
458
459         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
460                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
461         }
462         AST_DLLIST_TRAVERSE_SAFE_END;
463
464         if (!AST_DLLIST_EMPTY(&test_list)) {
465                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
466                 return AST_TEST_FAIL;
467         }
468
469         /* Append list test */
470
471         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
472         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
473         AST_DLLIST_INSERT_TAIL(&test_list, &b, dbl_list);
474         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
475         AST_DLLIST_INSERT_HEAD(&other_list, &c, dbl_list);
476         MATCH_OR_FAIL_DBL(&other_list, "C", buf);
477         AST_DLLIST_INSERT_TAIL(&other_list, &d, dbl_list);
478         MATCH_OR_FAIL_DBL(&other_list, "CD", buf);
479         AST_DLLIST_APPEND_DLLIST(&test_list, &other_list, dbl_list);
480         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
481         MATCH_OR_FAIL_DBL(&other_list, "", buf);
482         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
483                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
484         }
485         AST_DLLIST_TRAVERSE_SAFE_END;
486         if (!AST_DLLIST_EMPTY(&test_list)) {
487                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
488                 return AST_TEST_FAIL;
489         }
490
491         /*
492          * Safe traversal list modification tests
493          * Traverse starting from first element
494          */
495
496         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
497         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
498         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
499         MATCH_OR_FAIL_DBL(&test_list, "AD", buf);
500         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
501                 if (bogus == &d) {
502                         AST_DLLIST_INSERT_BEFORE_CURRENT(&b, dbl_list);
503                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
504                         AST_DLLIST_INSERT_BEFORE_CURRENT(&c, dbl_list);
505                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
506                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
507                         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
508                 }
509         }
510         AST_DLLIST_TRAVERSE_SAFE_END;
511         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
512         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
513                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
514         }
515         AST_DLLIST_TRAVERSE_SAFE_END;
516         if (!AST_DLLIST_EMPTY(&test_list)) {
517                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
518                 return AST_TEST_FAIL;
519         }
520
521         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
522         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
523         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
524         MATCH_OR_FAIL_DBL(&test_list, "BD", buf);
525         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
526                 if (bogus == &b) {
527                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
528                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
529                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
530                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
531                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
532                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
533                 }
534         }
535         AST_DLLIST_TRAVERSE_SAFE_END;
536         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
537         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
538                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
539         }
540         AST_DLLIST_TRAVERSE_SAFE_END;
541         if (!AST_DLLIST_EMPTY(&test_list)) {
542                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
543                 return AST_TEST_FAIL;
544         }
545
546         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
547         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
548         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
549                 if (bogus == &b) {
550                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
551                         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
552                         AST_DLLIST_INSERT_AFTER_CURRENT(&d, dbl_list);
553                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
554                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
555                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
556                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
557                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
558                 }
559         }
560         AST_DLLIST_TRAVERSE_SAFE_END;
561         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
562         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
563                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
564         }
565         AST_DLLIST_TRAVERSE_SAFE_END;
566         if (!AST_DLLIST_EMPTY(&test_list)) {
567                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
568                 return AST_TEST_FAIL;
569         }
570
571         /*
572          * Safe traversal list modification tests
573          * Traverse starting from last element
574          */
575
576         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
577         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
578         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
579         MATCH_OR_FAIL_DBL(&test_list, "AD", buf);
580         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
581                 if (bogus == &d) {
582                         AST_DLLIST_INSERT_BEFORE_CURRENT(&b, dbl_list);
583                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
584                         AST_DLLIST_INSERT_BEFORE_CURRENT(&c, dbl_list);
585                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
586                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
587                         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
588                 }
589         }
590         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
591         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
592         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
593                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
594         }
595         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
596         if (!AST_DLLIST_EMPTY(&test_list)) {
597                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
598                 return AST_TEST_FAIL;
599         }
600
601         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
602         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
603         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
604         MATCH_OR_FAIL_DBL(&test_list, "BD", buf);
605         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
606                 if (bogus == &b) {
607                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
608                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
609                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
610                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
611                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
612                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
613                 }
614         }
615         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
616         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
617         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
618                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
619         }
620         AST_DLLIST_TRAVERSE_SAFE_END;
621         if (!AST_DLLIST_EMPTY(&test_list)) {
622                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
623                 return AST_TEST_FAIL;
624         }
625
626         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
627         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
628         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
629                 if (bogus == &b) {
630                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
631                         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
632                         AST_DLLIST_INSERT_AFTER_CURRENT(&d, dbl_list);
633                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
634                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
635                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
636                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
637                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
638                 }
639         }
640         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
641         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
642         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
643                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
644         }
645         AST_DLLIST_TRAVERSE_SAFE_END;
646         if (!AST_DLLIST_EMPTY(&test_list)) {
647                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
648                 return AST_TEST_FAIL;
649         }
650
651         return AST_TEST_PASS;
652 }
653
654 static int unload_module(void)
655 {
656         AST_TEST_UNREGISTER(single_ll_tests);
657         AST_TEST_UNREGISTER(double_ll_tests);
658         return 0;
659 }
660
661 static int load_module(void)
662 {
663         AST_TEST_REGISTER(single_ll_tests);
664         AST_TEST_REGISTER(double_ll_tests);
665         return AST_MODULE_LOAD_SUCCESS;
666 }
667
668 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Test Linked Lists");