Unit Test Framework API
[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/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_test_status_update(&args->status_update, "pushing nodes\n");
84
85         ast_heap_push(h, &nodes[0]);
86
87         ast_heap_push(h, &nodes[1]);
88
89         ast_heap_push(h, &nodes[2]);
90
91         obj = ast_heap_pop(h);
92         if (obj->val != 3) {
93                 return AST_TEST_FAIL;
94         }
95
96         ast_test_status_update(&args->status_update, "popping nodes\n");
97         obj = ast_heap_pop(h);
98         if (obj->val != 2) {
99                 return AST_TEST_FAIL;
100         }
101
102         obj = ast_heap_pop(h);
103         if (obj->val != 1) {
104                 return AST_TEST_FAIL;
105         }
106
107         obj = ast_heap_pop(h);
108         if (obj) {
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 one_million = 1000000;
121         struct node *nodes = NULL;
122         struct node *node;
123         unsigned int i = one_million;
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 = "Push a million random elements on to a heap,verify that the heap has been properly constructed, and then ensure that the elements are come back off in the proper order";
134                 return AST_TEST_NOT_RUN;
135         case TEST_EXECUTE:
136                 break;
137         }
138
139         if (!(nodes = ast_malloc(one_million * sizeof(*node)))) {
140                 res = AST_TEST_FAIL;
141                 goto return_cleanup;
142         }
143
144         if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
145                 res = AST_TEST_FAIL;
146                 goto return_cleanup;
147         }
148
149         while (i--) {
150                 nodes[i].val = ast_random();
151                 ast_heap_push(h, &nodes[i]);
152         }
153
154         if (ast_heap_verify(h)) {
155                 res = AST_TEST_FAIL;
156                 goto return_cleanup;
157         }
158
159         i = 0;
160         while ((node = ast_heap_pop(h))) {
161                 cur = node->val;
162                 if (cur > last) {
163                         ast_str_set(&args->ast_test_error_str, 0, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
164                         res = AST_TEST_FAIL;
165                         goto return_cleanup;
166                 }
167                 last = cur;
168                 i++;
169         }
170
171         if (i != one_million) {
172                 ast_str_set(&args->ast_test_error_str, 0, "Stopped popping off after only getting %u nodes\n", i);
173                 res = AST_TEST_FAIL;
174                 goto return_cleanup;
175         }
176
177 return_cleanup:
178         if (h) {
179                 h = ast_heap_destroy(h);
180         }
181         if (nodes) {
182                 ast_free(nodes);
183         }
184
185         return res;
186 }
187
188 static int unload_module(void)
189 {
190         AST_TEST_UNREGISTER(heap_test_1);
191         AST_TEST_UNREGISTER(heap_test_2);
192         return 0;
193 }
194
195 static int load_module(void)
196 {
197
198         AST_TEST_REGISTER(heap_test_1);
199
200         AST_TEST_REGISTER(heap_test_2);
201
202         return AST_MODULE_LOAD_SUCCESS;
203 }
204
205 AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Heap test module");