Merge "Revert "app_voicemail: Remove need to subscribe to stasis""
[asterisk/asterisk.git] / tests / test_heap.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2009, Digium, Inc.
5  *
6  * Russell Bryant <russell@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 Heap data structure test module
22  *
23  * \author Russell Bryant <russell@digium.com>
24  */
25
26 /*** MODULEINFO
27         <depend>TEST_FRAMEWORK</depend>
28         <support_level>core</support_level>
29  ***/
30
31 #include "asterisk.h"
32
33 #include "asterisk/module.h"
34 #include "asterisk/utils.h"
35 #include "asterisk/heap.h"
36 #include "asterisk/test.h"
37
38 struct node {
39         long val;
40         size_t index;
41 };
42
43 static int node_cmp(void *_n1, void *_n2)
44 {
45         struct node *n1 = _n1;
46         struct node *n2 = _n2;
47
48         if (n1->val < n2->val) {
49                 return -1;
50         } else if (n1->val == n2->val) {
51                 return 0;
52         } else {
53                 return 1;
54         }
55 }
56
57 AST_TEST_DEFINE(heap_test_1)
58 {
59         struct ast_heap *h;
60         struct node *obj;
61         struct node nodes[3] = {
62                 { 1, } ,
63                 { 2, } ,
64                 { 3, } ,
65         };
66
67         switch (cmd) {
68         case TEST_INIT:
69                 info->name = "heap_test_1";
70                 info->category = "/main/heap/";
71                 info->summary = "push and pop elements";
72                 info->description = "Push a few elements onto a heap and make sure that they come back off in the right order.";
73                 return AST_TEST_NOT_RUN;
74         case TEST_EXECUTE:
75                 break;
76         }
77
78         if (!(h = ast_heap_create(8, node_cmp, offsetof(struct node, index)))) {
79                 return AST_TEST_FAIL;
80         }
81
82         ast_heap_push(h, &nodes[0]);
83
84         ast_heap_push(h, &nodes[1]);
85
86         ast_heap_push(h, &nodes[2]);
87
88         obj = ast_heap_pop(h);
89         if (obj->val != 3) {
90                 ast_test_status_update(test, "expected 3, got %ld\n", obj->val);
91                 return AST_TEST_FAIL;
92         }
93
94         obj = ast_heap_pop(h);
95         if (obj->val != 2) {
96                 ast_test_status_update(test, "expected 2, got %ld\n", obj->val);
97                 return AST_TEST_FAIL;
98         }
99
100         obj = ast_heap_pop(h);
101         if (obj->val != 1) {
102                 ast_test_status_update(test, "expected 1, got %ld\n", obj->val);
103                 return AST_TEST_FAIL;
104         }
105
106         obj = ast_heap_pop(h);
107         if (obj) {
108                 ast_test_status_update(test, "got unexpected object\n");
109                 return AST_TEST_FAIL;
110         }
111
112         h = ast_heap_destroy(h);
113
114         return AST_TEST_PASS;
115 }
116
117 AST_TEST_DEFINE(heap_test_2)
118 {
119         struct ast_heap *h = NULL;
120         static const unsigned int total = 100000;
121         struct node *nodes = NULL;
122         struct node *node;
123         unsigned int i = total;
124         long last = LONG_MAX;
125         long cur;
126         enum ast_test_result_state res = AST_TEST_PASS;
127
128         switch (cmd) {
129         case TEST_INIT:
130                 info->name = "heap_test_2";
131                 info->category = "/main/heap/";
132                 info->summary = "load test";
133                 info->description =
134                                 "Push one hundred thousand random elements on to a heap, "
135                                 "verify that the heap has been properly constructed, "
136                                 "and then ensure that the elements are come back off "
137                                 "in the proper order.";
138                 return AST_TEST_NOT_RUN;
139         case TEST_EXECUTE:
140                 break;
141         }
142
143         if (!(nodes = ast_malloc(total * sizeof(*node)))) {
144                 res = AST_TEST_FAIL;
145                 goto return_cleanup;
146         }
147
148         if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
149                 res = AST_TEST_FAIL;
150                 goto return_cleanup;
151         }
152
153         while (i--) {
154                 nodes[i].val = ast_random();
155                 ast_heap_push(h, &nodes[i]);
156         }
157
158         if (ast_heap_verify(h)) {
159                 res = AST_TEST_FAIL;
160                 goto return_cleanup;
161         }
162
163         i = 0;
164         while ((node = ast_heap_pop(h))) {
165                 cur = node->val;
166                 if (cur > last) {
167                         ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
168                         res = AST_TEST_FAIL;
169                         goto return_cleanup;
170                 }
171                 last = cur;
172                 i++;
173         }
174
175         if (i != total) {
176                 ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
177                 res = AST_TEST_FAIL;
178                 goto return_cleanup;
179         }
180
181 return_cleanup:
182         if (h) {
183                 h = ast_heap_destroy(h);
184         }
185         if (nodes) {
186                 ast_free(nodes);
187         }
188
189         return res;
190 }
191
192 AST_TEST_DEFINE(heap_test_3)
193 {
194         struct ast_heap *h = NULL;
195         struct node *nodes = NULL;
196         struct node *node;
197         static const unsigned int test_size = 100000;
198         unsigned int i = test_size;
199         long last = LONG_MAX, cur;
200         int random_index;
201         enum ast_test_result_state res = AST_TEST_PASS;
202
203         switch (cmd) {
204         case TEST_INIT:
205                 info->name = "heap_test_3";
206                 info->category = "/main/heap/";
207                 info->summary = "random element removal test";
208                 info->description =
209                         "Push a hundred thousand random elements on to a heap, "
210                         "verify that the heap has been properly constructed, "
211                         "randomly remove and re-add 10000 elements, and then "
212                         "ensure that the elements come back off in the proper order.";
213                 return AST_TEST_NOT_RUN;
214         case TEST_EXECUTE:
215                 break;
216         }
217
218         if (!(nodes = ast_malloc(test_size * sizeof(*node)))) {
219                 ast_test_status_update(test, "memory allocation failure\n");
220                 res = AST_TEST_FAIL;
221                 goto return_cleanup;
222         }
223
224         if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
225                 ast_test_status_update(test, "Failed to allocate heap\n");
226                 res = AST_TEST_FAIL;
227                 goto return_cleanup;
228         }
229
230         while (i--) {
231                 nodes[i].val = ast_random();
232                 ast_heap_push(h, &nodes[i]);
233         }
234
235         if (ast_heap_verify(h)) {
236                 ast_test_status_update(test, "Failed to verify heap after populating it\n");
237                 res = AST_TEST_FAIL;
238                 goto return_cleanup;
239         }
240
241         i = test_size / 10;
242         while (i--) {
243                 random_index = ast_random() % test_size;
244                 node = ast_heap_remove(h, &nodes[random_index]);
245                 if (nodes[random_index].val != node->val){
246                         ast_test_status_update(test, "Failed to remove what we expected to\n");
247                         res = AST_TEST_FAIL;
248                         goto return_cleanup;
249                 }
250                 ast_heap_push(h, &nodes[random_index]);
251         }
252
253         if (ast_heap_verify(h)) {
254                 ast_test_status_update(test, "Failed to verify after removals\n");
255                 res = AST_TEST_FAIL;
256                 goto return_cleanup;
257         }
258
259         i = 0;
260         while ((node = ast_heap_pop(h))) {
261                 cur = node->val;
262                 if (cur > last) {
263                         ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
264                         res = AST_TEST_FAIL;
265                         goto return_cleanup;
266                 }
267                 last = cur;
268                 i++;
269         }
270
271         if (i != test_size) {
272                 ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
273                 res = AST_TEST_FAIL;
274                 goto return_cleanup;
275         }
276
277 return_cleanup:
278         if (h) {
279                 h = ast_heap_destroy(h);
280         }
281         if (nodes) {
282                 ast_free(nodes);
283         }
284
285         return res;
286 }
287
288 static int unload_module(void)
289 {
290         AST_TEST_UNREGISTER(heap_test_1);
291         AST_TEST_UNREGISTER(heap_test_2);
292         AST_TEST_UNREGISTER(heap_test_3);
293
294         return 0;
295 }
296
297 static int load_module(void)
298 {
299         AST_TEST_REGISTER(heap_test_1);
300         AST_TEST_REGISTER(heap_test_2);
301         AST_TEST_REGISTER(heap_test_3);
302
303         return AST_MODULE_LOAD_SUCCESS;
304 }
305
306 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Heap test module");