Merge the rest of the FullyBooted patch
[asterisk/asterisk.git] / tests / test_dlinklists.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2008, Steve Murphy
5  *
6  * Steve Murphy <murf@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Doubly-Linked List Tests
22  *
23  * \author\verbatim Steve Murphy <murf@digium.com> \endverbatim
24  * 
25  * This module will run some DLL tests at load time
26  * \ingroup tests
27  */
28
29 /*** MODULEINFO
30         <defaultenabled>no</defaultenabled>
31  ***/
32
33 #include "asterisk.h"
34
35 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
36
37 #include "asterisk/file.h"
38 #include "asterisk/channel.h"
39 #include "asterisk/pbx.h"
40 #include "asterisk/module.h"
41 #include "asterisk/lock.h"
42 #include "asterisk/app.h"
43
44
45 #include "asterisk/dlinkedlists.h"
46
47 /* Tests for DLLists! We really should, and here is a nice place to do it in asterisk */
48
49 struct test1
50 {
51         char name[10];
52         AST_DLLIST_ENTRY(test1) list;
53 };
54
55 struct test_container
56 {
57         AST_DLLIST_HEAD(entries, test1) entries;
58     int count;
59 };
60
61 static void print_list(struct test_container *x, char *expect)
62 {
63         struct test1 *t1;
64         char buff[1000];
65         buff[0] = 0;
66         AST_DLLIST_TRAVERSE(&x->entries, t1, list) {
67                 strcat(buff,t1->name);
68                 if (t1 != AST_DLLIST_LAST(&x->entries))
69                         strcat(buff," <=> ");
70         }
71         
72         ast_log(LOG_NOTICE,"Got: %s  [expect %s]\n", buff, expect);
73 }
74
75 static void print_list_backwards(struct test_container *x, char *expect)
76 {
77         struct test1 *t1;
78         char buff[1000];
79         buff[0] = 0;
80         AST_DLLIST_TRAVERSE_BACKWARDS(&x->entries, t1, list) {
81                 strcat(buff,t1->name);
82                 if (t1 != AST_DLLIST_FIRST(&x->entries))
83                         strcat(buff," <=> ");
84         }
85         
86         ast_log(LOG_NOTICE,"Got: %s  [expect %s]\n", buff, expect);
87 }
88
89 static struct test_container *make_cont(void)
90 {
91         struct test_container *t = ast_calloc(sizeof(struct test_container),1);
92         return t;
93 }
94
95 static struct test1 *make_test1(char *name)
96 {
97         struct test1 *t1 = ast_calloc(sizeof(struct test1),1);
98         strcpy(t1->name, name);
99         return t1;
100 }
101
102 static void destroy_test_container(struct test_container *x)
103 {
104         /* remove all the test1's */
105         struct test1 *t1;
106         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&x->entries, t1, list) {
107                 AST_DLLIST_REMOVE_CURRENT(list);
108                 free(t1);
109         }
110         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
111         free(x);
112 }
113
114 /* Macros to test:
115 AST_DLLIST_LOCK(head)
116 AST_RWDLLIST_WRLOCK(head)
117 AST_RWDLLIST_WRLOCK(head) 
118 AST_RWDLLIST_RDLOCK(head)
119 AST_DLLIST_TRYLOCK(head)
120 AST_RWDLLIST_TRYWRLOCK(head)
121 AST_RWDLLIST_TRYRDLOCK(head)
122 AST_DLLIST_UNLOCK(head)
123 AST_RWDLLIST_UNLOCK(head)
124
125 AST_DLLIST_HEAD(name, type)
126 AST_RWDLLIST_HEAD(name, type)
127 AST_DLLIST_HEAD_NOLOCK(name, type)
128 AST_DLLIST_HEAD_STATIC(name, type)
129 AST_RWDLLIST_HEAD_STATIC(name, type)
130 AST_DLLIST_HEAD_NOLOCK_STATIC(name, type)
131 AST_DLLIST_HEAD_SET(head, entry)
132 AST_RWDLLIST_HEAD_SET(head, entry)
133 AST_DLLIST_HEAD_SET_NOLOCK(head, entry)
134 AST_DLLIST_HEAD_INIT(head)
135 AST_RWDLLIST_HEAD_INIT(head)
136 AST_DLLIST_HEAD_INIT_NOLOCK(head)
137
138 AST_RWDLLIST_HEAD_DESTROY(head)
139
140 AST_DLLIST_ENTRY(type)
141
142 --- the above not going to be dealt with here ---
143
144 AST_DLLIST_INSERT_HEAD(head, elm, field)
145 AST_DLLIST_TRAVERSE(head,var,field)
146 AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field)
147 AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END
148 AST_DLLIST_FIRST(head)
149 AST_DLLIST_LAST(head)
150 AST_DLLIST_NEXT(elm, field)
151 AST_DLLIST_PREV(elm, field)
152 AST_DLLIST_EMPTY(head)
153 AST_DLLIST_TRAVERSE_BACKWARDS(head,var,field)
154 AST_DLLIST_INSERT_AFTER(head, listelm, elm, field)
155 AST_DLLIST_INSERT_TAIL(head, elm, field)
156 AST_DLLIST_REMOVE_HEAD(head, field)
157 AST_DLLIST_REMOVE(head, elm, field)
158 AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field)
159 AST_DLLIST_TRAVERSE_SAFE_END
160 AST_DLLIST_REMOVE_CURRENT(field)
161 AST_DLLIST_MOVE_CURRENT(newhead, field)
162 AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field) 
163
164
165 AST_DLLIST_MOVE_CURRENT_BACKWARDS(newhead, field)
166 AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field)
167 AST_DLLIST_HEAD_DESTROY(head)
168
169 AST_DLLIST_APPEND_DLLIST(head, list, field)
170
171 */
172
173 static void dll_tests(void)
174 {
175         struct test_container *tc;
176         struct test1 *a;
177         struct test1 *b;
178         struct test1 *c;
179         struct test1 *d;
180         struct test1 *e;
181         
182         ast_log(LOG_NOTICE,"Test AST_DLLIST_INSERT_HEAD, AST_DLLIST_TRAVERSE, AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN, AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END\n");
183         tc = make_cont();
184         a = make_test1("A");
185         b = make_test1("B");
186         c = make_test1("C");
187         d = make_test1("D");
188         AST_DLLIST_INSERT_HEAD(&tc->entries, d, list);
189         AST_DLLIST_INSERT_HEAD(&tc->entries, c, list);
190         AST_DLLIST_INSERT_HEAD(&tc->entries, b, list);
191         AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
192         print_list(tc, "A <=> B <=> C <=> D");
193
194         destroy_test_container(tc);
195         
196         tc = make_cont();
197
198         if (AST_DLLIST_EMPTY(&tc->entries))
199                 ast_log(LOG_NOTICE,"Test AST_DLLIST_EMPTY....OK\n");
200         else
201                 ast_log(LOG_NOTICE,"Test AST_DLLIST_EMPTY....PROBLEM!!\n");
202
203
204         a = make_test1("A");
205         b = make_test1("B");
206         c = make_test1("C");
207         d = make_test1("D");
208         
209         ast_log(LOG_NOTICE,"Test AST_DLLIST_INSERT_TAIL\n");
210         AST_DLLIST_INSERT_TAIL(&tc->entries, a, list);
211         AST_DLLIST_INSERT_TAIL(&tc->entries, b, list);
212         AST_DLLIST_INSERT_TAIL(&tc->entries, c, list);
213         AST_DLLIST_INSERT_TAIL(&tc->entries, d, list);
214         print_list(tc, "A <=> B <=> C <=> D");
215
216         if (AST_DLLIST_FIRST(&tc->entries) == a)
217                 ast_log(LOG_NOTICE,"Test AST_DLLIST_FIRST....OK\n");
218         else
219                 ast_log(LOG_NOTICE,"Test AST_DLLIST_FIRST....PROBLEM\n");
220
221         if (AST_DLLIST_LAST(&tc->entries) == d)
222                 ast_log(LOG_NOTICE,"Test AST_DLLIST_LAST....OK\n");
223         else
224                 ast_log(LOG_NOTICE,"Test AST_DLLIST_LAST....PROBLEM\n");
225
226         if (AST_DLLIST_NEXT(a,list) == b)
227                 ast_log(LOG_NOTICE,"Test AST_DLLIST_NEXT....OK\n");
228         else
229                 ast_log(LOG_NOTICE,"Test AST_DLLIST_NEXT....PROBLEM\n");
230
231         if (AST_DLLIST_PREV(d,list) == c)
232                 ast_log(LOG_NOTICE,"Test AST_DLLIST_PREV....OK\n");
233         else
234                 ast_log(LOG_NOTICE,"Test AST_DLLIST_PREV....PROBLEM\n");
235
236         destroy_test_container(tc);
237
238         tc = make_cont();
239
240         a = make_test1("A");
241         b = make_test1("B");
242         c = make_test1("C");
243         d = make_test1("D");
244
245         ast_log(LOG_NOTICE,"Test AST_DLLIST_INSERT_AFTER, AST_DLLIST_TRAVERSE_BACKWARDS\n");
246         AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
247         AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
248         AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
249         AST_DLLIST_INSERT_AFTER(&tc->entries, c, d, list);
250         print_list_backwards(tc, "D <=> C <=> B <=> A");
251
252         ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD\n");
253         AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
254         print_list_backwards(tc, "D <=> C <=> B");
255         ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD\n");
256         AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
257         print_list_backwards(tc, "D <=> C");
258         ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD\n");
259         AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
260         print_list_backwards(tc, "D");
261         AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
262
263         if (AST_DLLIST_EMPTY(&tc->entries))
264                 ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD....OK\n");
265         else
266                 ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD....PROBLEM!!\n");
267
268         AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
269         AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
270         AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
271         AST_DLLIST_INSERT_AFTER(&tc->entries, c, d, list);
272
273         ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE\n");
274         AST_DLLIST_REMOVE(&tc->entries, c, list);
275         print_list(tc, "A <=> B <=> D");
276         AST_DLLIST_REMOVE(&tc->entries, a, list);
277         print_list(tc, "B <=> D");
278         AST_DLLIST_REMOVE(&tc->entries, d, list);
279         print_list(tc, "B");
280         AST_DLLIST_REMOVE(&tc->entries, b, list);
281         
282         if (AST_DLLIST_EMPTY(&tc->entries))
283                 ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE....OK\n");
284         else
285                 ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE....PROBLEM!!\n");
286
287         AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
288         AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
289         AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
290         AST_DLLIST_INSERT_AFTER(&tc->entries, c, d, list);
291
292         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&tc->entries, e, list) {
293                 AST_DLLIST_REMOVE_CURRENT(list);
294         }
295         AST_DLLIST_TRAVERSE_SAFE_END;
296         if (AST_DLLIST_EMPTY(&tc->entries))
297                 ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_CURRENT... OK\n");
298         else
299                 ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_CURRENT... PROBLEM\n");
300         
301         ast_log(LOG_NOTICE,"Test AST_DLLIST_MOVE_CURRENT, AST_DLLIST_INSERT_BEFORE_CURRENT\n");
302         AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
303         AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
304         AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
305         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&tc->entries, e, list) {
306                 if (e == a) {
307                         AST_DLLIST_INSERT_BEFORE_CURRENT(d, list);  /* D A B C */
308                 }
309                 
310                 if (e == b) {
311                         AST_DLLIST_MOVE_CURRENT(&tc->entries, list); /* D A C B */
312                 }
313                 
314         }
315         AST_DLLIST_TRAVERSE_SAFE_END;
316         print_list(tc, "D <=> A <=> C <=> B");
317         
318         destroy_test_container(tc);
319
320         tc = make_cont();
321
322         a = make_test1("A");
323         b = make_test1("B");
324         c = make_test1("C");
325         d = make_test1("D");
326
327         ast_log(LOG_NOTICE,"Test: AST_DLLIST_MOVE_CURRENT_BACKWARDS and AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS\n");
328         AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
329         AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
330         AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
331         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&tc->entries, e, list) {
332                 if (e == c && AST_DLLIST_FIRST(&tc->entries) != c) {
333                         AST_DLLIST_MOVE_CURRENT_BACKWARDS(&tc->entries, list); /* C A B */
334                         print_list(tc, "C <=> A <=> B");
335                 }
336
337                 if (e == b) {
338                         AST_DLLIST_REMOVE_CURRENT(list);  /* C A */
339                         print_list(tc, "C <=> A");
340                 }
341                 if (e == a) {
342                         AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(d, list); /* C A D */
343                         print_list(tc, "C <=> A <=> D");
344                 }
345                 
346         }
347         AST_DLLIST_TRAVERSE_SAFE_END;
348         print_list(tc, "C <=> A <=> D");
349
350 }
351
352 static int unload_module(void)
353 {
354         return 0;
355 }
356
357 static int load_module(void)
358 {
359         dll_tests();
360         return AST_MODULE_LOAD_SUCCESS;
361 }
362
363 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Test Doubly-Linked Lists");