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