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