stasis cache: Enhance to keep track of an item from different entities.
[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                 return AST_TEST_FAIL; \
109         }
110
111 #define MATCH_OR_FAIL_DBL(list, val, retbuf) \
112         if (dbl_list_expect_forward(list, val, &retbuf)) { \
113                 ast_test_status_update(test, "Expected: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \
114                 return AST_TEST_FAIL; \
115         } \
116         if (dbl_list_expect_reverse(list, val, &retbuf)) { \
117                 ast_test_status_update(test, "Expected reverse of: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \
118                 return AST_TEST_FAIL; \
119         }
120
121 #define ELEM_OR_FAIL(x,y) \
122         if ((x) != (y)) { \
123                 ast_test_status_update(test, "Expected: %s, Got: %s\n", (x)->name, (y)->name); \
124                 return AST_TEST_FAIL; \
125         }
126
127 AST_TEST_DEFINE(single_ll_tests)
128 {
129         RAII_VAR(struct ast_str *, buf, NULL, ast_free);
130         struct test_llist test_list = { 0, };
131         struct test_llist other_list = { 0, };
132         struct test_val *bogus;
133
134         switch (cmd) {
135         case TEST_INIT:
136                 info->name = "ll_tests";
137                 info->category = "/main/linkedlists/";
138                 info->summary = "single linked list unit test";
139                 info->description =
140                         "Test the single linked list API";
141                 return AST_TEST_NOT_RUN;
142         case TEST_EXECUTE:
143                 break;
144         }
145
146         if (!(buf = ast_str_create(16))) {
147                 return AST_TEST_FAIL;
148         }
149
150         if (!(bogus = ast_alloca(sizeof(*bogus)))) {
151                 return AST_TEST_FAIL;
152         }
153
154         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
155                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL for missing element from empty list\n");
156                 return AST_TEST_FAIL;
157         }
158
159         /* INSERT_HEAD and REMOVE_HEAD tests */
160         AST_LIST_INSERT_HEAD(&test_list, &a, list);
161         MATCH_OR_FAIL(&test_list, "A", buf);
162         AST_LIST_INSERT_HEAD(&test_list, &b, list);
163         MATCH_OR_FAIL(&test_list, "BA", buf);
164         AST_LIST_REMOVE_HEAD(&test_list, list);
165         MATCH_OR_FAIL(&test_list, "A", buf);
166         AST_LIST_REMOVE_HEAD(&test_list, list);
167         MATCH_OR_FAIL(&test_list, "", buf);
168         if (AST_LIST_REMOVE_HEAD(&test_list, list)) {
169                 ast_test_status_update(test, "Somehow removed an item from the head of a list that didn't exist\n");
170                 return AST_TEST_FAIL;
171         }
172         MATCH_OR_FAIL(&test_list, "", buf);
173
174         /* Check empty list test */
175
176         if (!AST_LIST_EMPTY(&test_list)) {
177                 ast_test_status_update(test, "List should be empty\n");
178                 return AST_TEST_FAIL;
179         }
180
181         /* Insert tail and remove specific item tests. */
182
183         AST_LIST_INSERT_TAIL(&test_list, &a, list);
184         MATCH_OR_FAIL(&test_list, "A", buf);
185         AST_LIST_INSERT_TAIL(&test_list, &b, list);
186         MATCH_OR_FAIL(&test_list, "AB", buf);
187         AST_LIST_INSERT_TAIL(&test_list, &c, list);
188         MATCH_OR_FAIL(&test_list, "ABC", buf);
189         AST_LIST_INSERT_TAIL(&test_list, &d, list);
190         MATCH_OR_FAIL(&test_list, "ABCD", buf);
191         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
192                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL for missing element\n");
193                 return AST_TEST_FAIL;
194         }
195         bogus = NULL;
196         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
197                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL for element set to NULL\n");
198                 return AST_TEST_FAIL;
199         }
200         AST_LIST_REMOVE(&test_list, &b, list);
201         MATCH_OR_FAIL(&test_list, "ACD", buf);
202         AST_LIST_REMOVE(&test_list, &d, list);
203         MATCH_OR_FAIL(&test_list, "AC", buf);
204         AST_LIST_REMOVE(&test_list, &a, list);
205         MATCH_OR_FAIL(&test_list, "C", buf);
206         AST_LIST_REMOVE(&test_list, &c, list);
207         MATCH_OR_FAIL(&test_list, "", buf);
208         if (!AST_LIST_EMPTY(&test_list)) {
209                 ast_test_status_update(test, "List should be empty\n");
210                 return AST_TEST_FAIL;
211         }
212         if (AST_LIST_REMOVE(&test_list, bogus, list)) {
213                 ast_test_status_update(test, "AST_LIST_REMOVE should safely return NULL asked to remove a NULL pointer from an empty list\n");
214                 return AST_TEST_FAIL;
215         }
216
217         /* Insert item after specific item tests */
218
219         AST_LIST_INSERT_HEAD(&test_list, &a, list);
220         MATCH_OR_FAIL(&test_list, "A", buf);
221         AST_LIST_INSERT_TAIL(&test_list, &c, list);
222         MATCH_OR_FAIL(&test_list, "AC", buf);
223         AST_LIST_INSERT_AFTER(&test_list, &a, &b, list);
224         MATCH_OR_FAIL(&test_list, "ABC", buf);
225         AST_LIST_INSERT_AFTER(&test_list, &c, &d, list);
226         MATCH_OR_FAIL(&test_list, "ABCD", buf);
227
228         ELEM_OR_FAIL(AST_LIST_FIRST(&test_list), &a);
229         ELEM_OR_FAIL(AST_LIST_LAST(&test_list), &d);
230         ELEM_OR_FAIL(AST_LIST_NEXT(&a, list), &b);
231
232         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
233                 AST_LIST_REMOVE_CURRENT(list);
234         }
235         AST_LIST_TRAVERSE_SAFE_END;
236
237         if (!AST_LIST_EMPTY(&test_list)) {
238                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
239                 return AST_TEST_FAIL;
240         }
241
242         /* Append list test */
243
244         AST_LIST_INSERT_HEAD(&test_list, &a, list);
245         MATCH_OR_FAIL(&test_list, "A", buf);
246         AST_LIST_INSERT_TAIL(&test_list, &b, list);
247         MATCH_OR_FAIL(&test_list, "AB", buf);
248         AST_LIST_INSERT_HEAD(&other_list, &c, list);
249         MATCH_OR_FAIL(&other_list, "C", buf);
250         AST_LIST_INSERT_TAIL(&other_list, &d, list);
251         MATCH_OR_FAIL(&other_list, "CD", buf);
252         AST_LIST_APPEND_LIST(&test_list, &other_list, list);
253         MATCH_OR_FAIL(&test_list, "ABCD", buf);
254         MATCH_OR_FAIL(&other_list, "", buf);
255         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
256                 AST_LIST_REMOVE_CURRENT(list);
257         }
258         AST_LIST_TRAVERSE_SAFE_END;
259         if (!AST_LIST_EMPTY(&test_list)) {
260                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
261                 return AST_TEST_FAIL;
262         }
263
264         /* Insert list after specific item in middle test */
265
266         AST_LIST_INSERT_HEAD(&test_list, &a, list);
267         MATCH_OR_FAIL(&test_list, "A", buf);
268         AST_LIST_INSERT_TAIL(&test_list, &d, list);
269         MATCH_OR_FAIL(&test_list, "AD", buf);
270         AST_LIST_INSERT_HEAD(&other_list, &b, list);
271         MATCH_OR_FAIL(&other_list, "B", buf);
272         AST_LIST_INSERT_TAIL(&other_list, &c, list);
273         MATCH_OR_FAIL(&other_list, "BC", buf);
274         AST_LIST_INSERT_LIST_AFTER(&test_list, &other_list, &a, list);
275         MATCH_OR_FAIL(&test_list, "ABCD", buf);
276         MATCH_OR_FAIL(&other_list, "", buf);
277         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
278                 AST_LIST_REMOVE_CURRENT(list);
279         }
280         AST_LIST_TRAVERSE_SAFE_END;
281         if (!AST_LIST_EMPTY(&test_list)) {
282                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
283                 return AST_TEST_FAIL;
284         }
285
286         /* Insert list after specific item on end test */
287
288         AST_LIST_INSERT_HEAD(&test_list, &a, list);
289         MATCH_OR_FAIL(&test_list, "A", buf);
290         AST_LIST_INSERT_TAIL(&test_list, &b, list);
291         MATCH_OR_FAIL(&test_list, "AB", buf);
292         AST_LIST_INSERT_HEAD(&other_list, &c, list);
293         MATCH_OR_FAIL(&other_list, "C", buf);
294         AST_LIST_INSERT_TAIL(&other_list, &d, list);
295         MATCH_OR_FAIL(&other_list, "CD", buf);
296         AST_LIST_INSERT_LIST_AFTER(&test_list, &other_list, &b, list);
297         MATCH_OR_FAIL(&test_list, "ABCD", buf);
298         MATCH_OR_FAIL(&other_list, "", buf);
299         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
300                 AST_LIST_REMOVE_CURRENT(list);
301         }
302         AST_LIST_TRAVERSE_SAFE_END;
303         if (!AST_LIST_EMPTY(&test_list)) {
304                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
305                 return AST_TEST_FAIL;
306         }
307
308         /* Safe traversal list modification tests */
309
310         AST_LIST_INSERT_HEAD(&test_list, &a, list);
311         MATCH_OR_FAIL(&test_list, "A", buf);
312         AST_LIST_INSERT_TAIL(&test_list, &d, list);
313         MATCH_OR_FAIL(&test_list, "AD", buf);
314         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
315                 if (bogus == &d) {
316                         AST_LIST_INSERT_BEFORE_CURRENT(&b, list);
317                         MATCH_OR_FAIL(&test_list, "ABD", buf);
318                         AST_LIST_INSERT_BEFORE_CURRENT(&c, list);
319                         MATCH_OR_FAIL(&test_list, "ABCD", buf);
320                         AST_LIST_REMOVE_CURRENT(list);
321                         MATCH_OR_FAIL(&test_list, "ABC", buf);
322                 }
323         }
324         AST_LIST_TRAVERSE_SAFE_END;
325         MATCH_OR_FAIL(&test_list, "ABC", buf);
326         AST_LIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, list) {
327                 AST_LIST_REMOVE_CURRENT(list);
328         }
329         AST_LIST_TRAVERSE_SAFE_END;
330         if (!AST_LIST_EMPTY(&test_list)) {
331                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
332                 return AST_TEST_FAIL;
333         }
334
335         return AST_TEST_PASS;
336 }
337
338 AST_TEST_DEFINE(double_ll_tests)
339 {
340         RAII_VAR(struct ast_str *, buf, NULL, ast_free);
341         struct test_dbl_llist test_list = { 0, };
342         struct test_dbl_llist other_list = { 0, };
343         struct test_val *bogus;
344
345         switch (cmd) {
346         case TEST_INIT:
347                 info->name = "double_ll_tests";
348                 info->category = "/main/linkedlists/";
349                 info->summary = "double linked list unit test";
350                 info->description =
351                         "Test the double linked list API";
352                 return AST_TEST_NOT_RUN;
353         case TEST_EXECUTE:
354                 break;
355         }
356
357         if (!(buf = ast_str_create(16))) {
358                 return AST_TEST_FAIL;
359         }
360
361         bogus = ast_alloca(sizeof(*bogus));
362
363         if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) {
364                 ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for missing element from empty list\n");
365                 return AST_TEST_FAIL;
366         }
367
368         /* INSERT_HEAD and REMOVE_HEAD tests */
369         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
370         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
371         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
372         MATCH_OR_FAIL_DBL(&test_list, "BA", buf);
373         AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list);
374         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
375         AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list);
376         MATCH_OR_FAIL_DBL(&test_list, "", buf);
377         if (AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list)) {
378                 ast_test_status_update(test, "Somehow removed an item from the head of a list that didn't exist\n");
379                 return AST_TEST_FAIL;
380         }
381         MATCH_OR_FAIL_DBL(&test_list, "", buf);
382
383         /* Check empty list test */
384
385         if (!AST_DLLIST_EMPTY(&test_list)) {
386                 ast_test_status_update(test, "List should be empty\n");
387                 return AST_TEST_FAIL;
388         }
389
390         /* Insert tail and remove specific item tests. */
391
392         AST_DLLIST_INSERT_TAIL(&test_list, &a, dbl_list);
393         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
394         AST_DLLIST_INSERT_TAIL(&test_list, &b, dbl_list);
395         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
396         AST_DLLIST_INSERT_TAIL(&test_list, &c, dbl_list);
397         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
398         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
399         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
400         if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) {
401                 ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for missing element\n");
402                 return AST_TEST_FAIL;
403         }
404         bogus = NULL;
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 element set to NULL\n");
407                 return AST_TEST_FAIL;
408         }
409         AST_DLLIST_REMOVE(&test_list, &b, dbl_list);
410         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
411         AST_DLLIST_REMOVE(&test_list, &d, dbl_list);
412         MATCH_OR_FAIL_DBL(&test_list, "AC", buf);
413         AST_DLLIST_REMOVE(&test_list, &a, dbl_list);
414         MATCH_OR_FAIL_DBL(&test_list, "C", buf);
415         AST_DLLIST_REMOVE(&test_list, &c, dbl_list);
416         MATCH_OR_FAIL_DBL(&test_list, "", buf);
417         if (!AST_DLLIST_EMPTY(&test_list)) {
418                 ast_test_status_update(test, "List should be empty\n");
419                 return AST_TEST_FAIL;
420         }
421         if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) {
422                 ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL asked to remove a NULL pointer from an empty list\n");
423                 return AST_TEST_FAIL;
424         }
425
426         /* Insert item after and before specific item tests */
427
428         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
429         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
430         AST_DLLIST_INSERT_TAIL(&test_list, &c, dbl_list);
431         MATCH_OR_FAIL_DBL(&test_list, "AC", buf);
432         AST_DLLIST_INSERT_AFTER(&test_list, &a, &b, dbl_list);
433         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
434         AST_DLLIST_INSERT_AFTER(&test_list, &c, &d, dbl_list);
435         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
436         AST_DLLIST_REMOVE_TAIL(&test_list, dbl_list);
437         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
438         AST_DLLIST_REMOVE_TAIL(&test_list, dbl_list);
439         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
440         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
441         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
442         AST_DLLIST_INSERT_BEFORE(&test_list, &d, &c, dbl_list);
443         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
444         AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list);
445         MATCH_OR_FAIL_DBL(&test_list, "BCD", buf);
446         AST_DLLIST_INSERT_BEFORE(&test_list, &b, &a, dbl_list);
447         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
448
449         ELEM_OR_FAIL(AST_DLLIST_FIRST(&test_list), &a);
450         ELEM_OR_FAIL(AST_DLLIST_LAST(&test_list), &d);
451         ELEM_OR_FAIL(AST_DLLIST_NEXT(&a, dbl_list), &b);
452         ELEM_OR_FAIL(AST_DLLIST_PREV(&b, dbl_list), &a);
453
454         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
455                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
456         }
457         AST_DLLIST_TRAVERSE_SAFE_END;
458
459         if (!AST_DLLIST_EMPTY(&test_list)) {
460                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
461                 return AST_TEST_FAIL;
462         }
463
464         /* Append list test */
465
466         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
467         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
468         AST_DLLIST_INSERT_TAIL(&test_list, &b, dbl_list);
469         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
470         AST_DLLIST_INSERT_HEAD(&other_list, &c, dbl_list);
471         MATCH_OR_FAIL_DBL(&other_list, "C", buf);
472         AST_DLLIST_INSERT_TAIL(&other_list, &d, dbl_list);
473         MATCH_OR_FAIL_DBL(&other_list, "CD", buf);
474         AST_DLLIST_APPEND_DLLIST(&test_list, &other_list, dbl_list);
475         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
476         MATCH_OR_FAIL_DBL(&other_list, "", buf);
477         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
478                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
479         }
480         AST_DLLIST_TRAVERSE_SAFE_END;
481         if (!AST_DLLIST_EMPTY(&test_list)) {
482                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
483                 return AST_TEST_FAIL;
484         }
485
486         /*
487          * Safe traversal list modification tests
488          * Traverse starting from first element
489          */
490
491         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
492         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
493         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
494         MATCH_OR_FAIL_DBL(&test_list, "AD", buf);
495         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
496                 if (bogus == &d) {
497                         AST_DLLIST_INSERT_BEFORE_CURRENT(&b, dbl_list);
498                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
499                         AST_DLLIST_INSERT_BEFORE_CURRENT(&c, dbl_list);
500                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
501                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
502                         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
503                 }
504         }
505         AST_DLLIST_TRAVERSE_SAFE_END;
506         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
507         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
508                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
509         }
510         AST_DLLIST_TRAVERSE_SAFE_END;
511         if (!AST_DLLIST_EMPTY(&test_list)) {
512                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
513                 return AST_TEST_FAIL;
514         }
515
516         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
517         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
518         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
519         MATCH_OR_FAIL_DBL(&test_list, "BD", buf);
520         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
521                 if (bogus == &b) {
522                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
523                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
524                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
525                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
526                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
527                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
528                 }
529         }
530         AST_DLLIST_TRAVERSE_SAFE_END;
531         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
532         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
533                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
534         }
535         AST_DLLIST_TRAVERSE_SAFE_END;
536         if (!AST_DLLIST_EMPTY(&test_list)) {
537                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
538                 return AST_TEST_FAIL;
539         }
540
541         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
542         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
543         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
544                 if (bogus == &b) {
545                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
546                         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
547                         AST_DLLIST_INSERT_AFTER_CURRENT(&d, dbl_list);
548                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
549                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
550                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
551                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
552                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
553                 }
554         }
555         AST_DLLIST_TRAVERSE_SAFE_END;
556         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
557         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
558                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
559         }
560         AST_DLLIST_TRAVERSE_SAFE_END;
561         if (!AST_DLLIST_EMPTY(&test_list)) {
562                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
563                 return AST_TEST_FAIL;
564         }
565
566         /*
567          * Safe traversal list modification tests
568          * Traverse starting from last element
569          */
570
571         AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list);
572         MATCH_OR_FAIL_DBL(&test_list, "A", buf);
573         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
574         MATCH_OR_FAIL_DBL(&test_list, "AD", buf);
575         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
576                 if (bogus == &d) {
577                         AST_DLLIST_INSERT_BEFORE_CURRENT(&b, dbl_list);
578                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
579                         AST_DLLIST_INSERT_BEFORE_CURRENT(&c, dbl_list);
580                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
581                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
582                         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
583                 }
584         }
585         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
586         MATCH_OR_FAIL_DBL(&test_list, "ABC", buf);
587         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
588                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
589         }
590         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
591         if (!AST_DLLIST_EMPTY(&test_list)) {
592                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
593                 return AST_TEST_FAIL;
594         }
595
596         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
597         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
598         AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list);
599         MATCH_OR_FAIL_DBL(&test_list, "BD", buf);
600         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
601                 if (bogus == &b) {
602                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
603                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
604                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
605                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
606                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
607                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
608                 }
609         }
610         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
611         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
612         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
613                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
614         }
615         AST_DLLIST_TRAVERSE_SAFE_END;
616         if (!AST_DLLIST_EMPTY(&test_list)) {
617                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
618                 return AST_TEST_FAIL;
619         }
620
621         AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list);
622         MATCH_OR_FAIL_DBL(&test_list, "B", buf);
623         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) {
624                 if (bogus == &b) {
625                         AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list);
626                         MATCH_OR_FAIL_DBL(&test_list, "AB", buf);
627                         AST_DLLIST_INSERT_AFTER_CURRENT(&d, dbl_list);
628                         MATCH_OR_FAIL_DBL(&test_list, "ABD", buf);
629                         AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list);
630                         MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf);
631                         AST_DLLIST_REMOVE_CURRENT(dbl_list);
632                         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
633                 }
634         }
635         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
636         MATCH_OR_FAIL_DBL(&test_list, "ACD", buf);
637         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) {
638                 AST_DLLIST_REMOVE_CURRENT(dbl_list);
639         }
640         AST_DLLIST_TRAVERSE_SAFE_END;
641         if (!AST_DLLIST_EMPTY(&test_list)) {
642                 ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n");
643                 return AST_TEST_FAIL;
644         }
645
646         return AST_TEST_PASS;
647 }
648
649 static int unload_module(void)
650 {
651         AST_TEST_UNREGISTER(single_ll_tests);
652         AST_TEST_UNREGISTER(double_ll_tests);
653         return 0;
654 }
655
656 static int load_module(void)
657 {
658         AST_TEST_REGISTER(single_ll_tests);
659         AST_TEST_REGISTER(double_ll_tests);
660         return AST_MODULE_LOAD_SUCCESS;
661 }
662
663 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Test Linked Lists");