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