Add a test module for the heap implementation.
[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 #include "asterisk.h"
27
28 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
29
30 #include "asterisk/module.h"
31 #include "asterisk/cli.h"
32 #include "asterisk/utils.h"
33 #include "asterisk/heap.h"
34
35 struct node {
36         long val;
37         size_t index;
38 };
39
40 static int node_cmp(void *_n1, void *_n2)
41 {
42         struct node *n1 = _n1;
43         struct node *n2 = _n2;
44
45         if (n1->val < n2->val) {
46                 return -1;
47         } else if (n1->val == n2->val) {
48                 return 0;
49         } else {
50                 return 1;
51         }
52 }
53
54 static int test1(int fd)
55 {
56         struct ast_heap *h;
57         struct node *obj;
58         struct node nodes[3] = {
59                 { 1, },
60                 { 2, },
61                 { 3, },
62         };
63
64         if (!(h = ast_heap_create(8, node_cmp, offsetof(struct node, index)))) {
65                 return -1;
66         }
67
68         /* Pushing 1 2 3, and then popping 3 elements */
69
70         ast_cli(fd, "Test #1 - Push a few elements onto a heap and make sure that they "
71                         "come back off in the right order.\n");
72
73         ast_heap_push(h, &nodes[0]);
74
75         ast_heap_push(h, &nodes[1]);
76
77         ast_heap_push(h, &nodes[2]);
78
79         obj = ast_heap_pop(h);
80         if (obj->val != 3) {
81                 return -2;
82         }
83
84         obj = ast_heap_pop(h);
85         if (obj->val != 2) {
86                 return -3;
87         }
88
89         obj = ast_heap_pop(h);
90         if (obj->val != 1) {
91                 return -4;
92         }
93
94         obj = ast_heap_pop(h);
95         if (obj) {
96                 return -5;
97         }
98
99         h = ast_heap_destroy(h);
100
101         ast_cli(fd, "Test #1 successful.\n");
102
103         return 0;
104 }
105
106 static int test2(int fd)
107 {
108         struct ast_heap *h = NULL;
109         static const unsigned int one_million = 1000000;
110         struct node *nodes = NULL;
111         struct node *node;
112         unsigned int i = one_million;
113         long last = LONG_MAX, cur;
114         int res = 0;
115
116         ast_cli(fd, "Test #2 - Push a million random elements on to a heap, "
117                         "verify that the heap has been properly constructed, "
118                         "and then ensure that the elements are come back off in the proper order\n");
119
120         if (!(nodes = ast_malloc(one_million * sizeof(*node)))) {
121                 res = -1;
122                 goto return_cleanup;
123         }
124
125         if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
126                 res = -2;
127                 goto return_cleanup;
128         }
129
130         while (i--) {
131                 nodes[i].val = ast_random();
132                 ast_heap_push(h, &nodes[i]);
133         }
134
135         if (ast_heap_verify(h)) {
136                 res = -3;
137                 goto return_cleanup;
138         }
139
140         i = 0;
141         while ((node = ast_heap_pop(h))) {
142                 cur = node->val;
143                 if (cur > last) {
144                         ast_cli(fd, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
145                         res = -4;
146                         goto return_cleanup;
147                 }
148                 last = cur;
149                 i++;
150         }
151
152         if (i != one_million) {
153                 ast_cli(fd, "Stopped popping off after only getting %u nodes\n", i);
154                 res = -5;
155                 goto return_cleanup;
156         }
157
158         ast_cli(fd, "Test #2 successful.\n");
159
160 return_cleanup:
161         if (h) {
162                 h = ast_heap_destroy(h);
163         }
164         if (nodes) {
165                 ast_free(nodes);
166         }
167
168         return res;
169 }
170
171 static char *handle_cli_heap_test(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
172 {
173         int res;
174
175         switch (cmd) {
176         case CLI_INIT:
177                 e->command = "heap test";
178                 e->usage = ""
179                         "Usage: heap test\n"
180                         "";
181                 return NULL;
182         case CLI_GENERATE:
183                 return NULL;
184         }
185
186         if (a->argc != e->args) {
187                 return CLI_SHOWUSAGE;
188         }
189
190         if ((res = test1(a->fd))) {
191                 ast_cli(a->fd, "Test 1 failed! (%d)\n", res);
192                 return CLI_FAILURE;
193         }
194
195         if ((res = test2(a->fd))) {
196                 ast_cli(a->fd, "Test 2 failed! (%d)\n", res);
197                 return CLI_FAILURE;
198         }
199
200         return CLI_SUCCESS;
201 }
202
203 static struct ast_cli_entry cli_heap[] = {
204         AST_CLI_DEFINE(handle_cli_heap_test, "Test the heap implementation"),
205 };
206
207 static int unload_module(void)
208 {
209         ast_cli_unregister_multiple(cli_heap, ARRAY_LEN(cli_heap));
210         return 0;
211 }
212
213 static int load_module(void)
214 {
215         ast_cli_register_multiple(cli_heap, ARRAY_LEN(cli_heap));
216         return AST_MODULE_LOAD_SUCCESS;
217 }
218
219 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Heap test module");