Asterisk - The Open Source Telephony Project GIT-master-0bf3178
Data Structures | Functions | Variables
test_heap.c File Reference

Heap data structure test module. More...

#include "asterisk.h"
#include "asterisk/module.h"
#include "asterisk/utils.h"
#include "asterisk/heap.h"
#include "asterisk/test.h"
Include dependency graph for test_heap.c:

Go to the source code of this file.

Data Structures

struct  node
 

Functions

static void __reg_module (void)
 
static void __unreg_module (void)
 
struct ast_moduleAST_MODULE_SELF_SYM (void)
 
 AST_TEST_DEFINE (heap_test_1)
 
 AST_TEST_DEFINE (heap_test_2)
 
 AST_TEST_DEFINE (heap_test_3)
 
static int load_module (void)
 
static int node_cmp (void *_n1, void *_n2)
 
static int unload_module (void)
 

Variables

static struct ast_module_info __mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Heap test module" , .key = "This paragraph is copyright (c) 2006 by Digium, Inc. \In order for your module to load, it must return this \key via a function called \"key\". Any code which \includes this paragraph must be licensed under the GNU \General Public License version 2 or later (at your \option). In addition to Digium's general reservations \of rights, Digium expressly reserves the right to \allow other parties to license this paragraph under \different terms. Any use of Digium, Inc. trademarks or \logos (including \"Asterisk\" or \"Digium\") without \express written permission of Digium, Inc. is prohibited.\n" , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }
 
static const struct ast_module_infoast_module_info = &__mod_info
 

Detailed Description

Heap data structure test module.

Author
Russell Bryant russe.nosp@m.ll@d.nosp@m.igium.nosp@m..com

Definition in file test_heap.c.

Function Documentation

◆ __reg_module()

static void __reg_module ( void  )
static

Definition at line 306 of file test_heap.c.

◆ __unreg_module()

static void __unreg_module ( void  )
static

Definition at line 306 of file test_heap.c.

◆ AST_MODULE_SELF_SYM()

struct ast_module * AST_MODULE_SELF_SYM ( void  )

Definition at line 306 of file test_heap.c.

◆ AST_TEST_DEFINE() [1/3]

AST_TEST_DEFINE ( heap_test_1  )

Definition at line 57 of file test_heap.c.

58{
59 struct ast_heap *h;
60 struct node *obj;
61 struct node nodes[3] = {
62 { 1, } ,
63 { 2, } ,
64 { 3, } ,
65 };
66
67 switch (cmd) {
68 case TEST_INIT:
69 info->name = "heap_test_1";
70 info->category = "/main/heap/";
71 info->summary = "push and pop elements";
72 info->description = "Push a few elements onto a heap and make sure that they come back off in the right order.";
73 return AST_TEST_NOT_RUN;
74 case TEST_EXECUTE:
75 break;
76 }
77
78 if (!(h = ast_heap_create(8, node_cmp, offsetof(struct node, index)))) {
79 return AST_TEST_FAIL;
80 }
81
82 ast_heap_push(h, &nodes[0]);
83
84 ast_heap_push(h, &nodes[1]);
85
86 ast_heap_push(h, &nodes[2]);
87
88 obj = ast_heap_pop(h);
89 if (obj->val != 3) {
90 ast_test_status_update(test, "expected 3, got %ld\n", obj->val);
91 return AST_TEST_FAIL;
92 }
93
94 obj = ast_heap_pop(h);
95 if (obj->val != 2) {
96 ast_test_status_update(test, "expected 2, got %ld\n", obj->val);
97 return AST_TEST_FAIL;
98 }
99
100 obj = ast_heap_pop(h);
101 if (obj->val != 1) {
102 ast_test_status_update(test, "expected 1, got %ld\n", obj->val);
103 return AST_TEST_FAIL;
104 }
105
106 obj = ast_heap_pop(h);
107 if (obj) {
108 ast_test_status_update(test, "got unexpected object\n");
109 return AST_TEST_FAIL;
110 }
111
112 h = ast_heap_destroy(h);
113
114 return AST_TEST_PASS;
115}
struct ast_heap * ast_heap_destroy(struct ast_heap *h)
Destroy a max heap.
Definition: heap.c:146
#define ast_heap_create(init_height, cmp_fn, index_offset)
Create a max heap.
Definition: heap.h:100
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
Definition: heap.c:262
#define ast_heap_push(h, elm)
Push an element on to a heap.
Definition: heap.h:125
def info(msg)
static struct ao2_container * nodes
All the nodes that we're aware of.
Definition: res_corosync.c:65
Definition: heap.c:36
Definition: test_heap.c:38
size_t index
Definition: test_heap.c:40
long val
Definition: test_heap.c:39
@ TEST_INIT
Definition: test.h:200
@ TEST_EXECUTE
Definition: test.h:201
#define ast_test_status_update(a, b, c...)
Definition: test.h:129
@ AST_TEST_PASS
Definition: test.h:195
@ AST_TEST_FAIL
Definition: test.h:196
@ AST_TEST_NOT_RUN
Definition: test.h:194
static int node_cmp(void *_n1, void *_n2)
Definition: test_heap.c:43

References ast_heap_create, ast_heap_destroy(), ast_heap_pop(), ast_heap_push, AST_TEST_FAIL, AST_TEST_NOT_RUN, AST_TEST_PASS, ast_test_status_update, node::index, sip_to_pjsip::info(), node_cmp(), nodes, TEST_EXECUTE, TEST_INIT, and node::val.

◆ AST_TEST_DEFINE() [2/3]

AST_TEST_DEFINE ( heap_test_2  )

Definition at line 117 of file test_heap.c.

118{
119 struct ast_heap *h = NULL;
120 static const unsigned int total = 100000;
121 struct node *nodes = NULL;
122 struct node *node;
123 unsigned int i = total;
124 long last = LONG_MAX;
125 long cur;
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 =
134 "Push one hundred thousand random elements on to a heap, "
135 "verify that the heap has been properly constructed, "
136 "and then ensure that the elements are come back off "
137 "in the proper order.";
138 return AST_TEST_NOT_RUN;
139 case TEST_EXECUTE:
140 break;
141 }
142
143 if (!(nodes = ast_malloc(total * sizeof(*node)))) {
144 res = AST_TEST_FAIL;
145 goto return_cleanup;
146 }
147
148 if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
149 res = AST_TEST_FAIL;
150 goto return_cleanup;
151 }
152
153 while (i--) {
154 nodes[i].val = ast_random();
155 ast_heap_push(h, &nodes[i]);
156 }
157
158 if (ast_heap_verify(h)) {
159 res = AST_TEST_FAIL;
160 goto return_cleanup;
161 }
162
163 i = 0;
164 while ((node = ast_heap_pop(h))) {
165 cur = node->val;
166 if (cur > last) {
167 ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
168 res = AST_TEST_FAIL;
169 goto return_cleanup;
170 }
171 last = cur;
172 i++;
173 }
174
175 if (i != total) {
176 ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
177 res = AST_TEST_FAIL;
178 goto return_cleanup;
179 }
180
181return_cleanup:
182 if (h) {
183 h = ast_heap_destroy(h);
184 }
185 if (nodes) {
187 }
188
189 return res;
190}
struct sla_ringing_trunk * last
Definition: app_sla.c:332
#define ast_free(a)
Definition: astmm.h:180
#define ast_malloc(len)
A wrapper for malloc()
Definition: astmm.h:191
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
Definition: heap.c:88
static int total
Definition: res_adsi.c:970
#define NULL
Definition: resample.c:96
ast_test_result_state
Definition: test.h:193
long int ast_random(void)
Definition: utils.c:2312

References ast_free, ast_heap_create, ast_heap_destroy(), ast_heap_pop(), ast_heap_push, ast_heap_verify(), ast_malloc, ast_random(), AST_TEST_FAIL, AST_TEST_NOT_RUN, AST_TEST_PASS, ast_test_status_update, node::index, sip_to_pjsip::info(), last, node_cmp(), nodes, NULL, TEST_EXECUTE, TEST_INIT, total, and node::val.

◆ AST_TEST_DEFINE() [3/3]

AST_TEST_DEFINE ( heap_test_3  )

Definition at line 192 of file test_heap.c.

193{
194 struct ast_heap *h = NULL;
195 struct node *nodes = NULL;
196 struct node *node;
197 static const unsigned int test_size = 100000;
198 unsigned int i = test_size;
199 long last = LONG_MAX, cur;
200 int random_index;
202
203 switch (cmd) {
204 case TEST_INIT:
205 info->name = "heap_test_3";
206 info->category = "/main/heap/";
207 info->summary = "random element removal test";
208 info->description =
209 "Push a hundred thousand random elements on to a heap, "
210 "verify that the heap has been properly constructed, "
211 "randomly remove and re-add 10000 elements, and then "
212 "ensure that the elements come back off in the proper order.";
213 return AST_TEST_NOT_RUN;
214 case TEST_EXECUTE:
215 break;
216 }
217
218 if (!(nodes = ast_malloc(test_size * sizeof(*node)))) {
219 ast_test_status_update(test, "memory allocation failure\n");
220 res = AST_TEST_FAIL;
221 goto return_cleanup;
222 }
223
224 if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
225 ast_test_status_update(test, "Failed to allocate heap\n");
226 res = AST_TEST_FAIL;
227 goto return_cleanup;
228 }
229
230 while (i--) {
231 nodes[i].val = ast_random();
232 ast_heap_push(h, &nodes[i]);
233 }
234
235 if (ast_heap_verify(h)) {
236 ast_test_status_update(test, "Failed to verify heap after populating it\n");
237 res = AST_TEST_FAIL;
238 goto return_cleanup;
239 }
240
241 i = test_size / 10;
242 while (i--) {
243 random_index = ast_random() % test_size;
244 node = ast_heap_remove(h, &nodes[random_index]);
245 if (nodes[random_index].val != node->val){
246 ast_test_status_update(test, "Failed to remove what we expected to\n");
247 res = AST_TEST_FAIL;
248 goto return_cleanup;
249 }
250 ast_heap_push(h, &nodes[random_index]);
251 }
252
253 if (ast_heap_verify(h)) {
254 ast_test_status_update(test, "Failed to verify after removals\n");
255 res = AST_TEST_FAIL;
256 goto return_cleanup;
257 }
258
259 i = 0;
260 while ((node = ast_heap_pop(h))) {
261 cur = node->val;
262 if (cur > last) {
263 ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
264 res = AST_TEST_FAIL;
265 goto return_cleanup;
266 }
267 last = cur;
268 i++;
269 }
270
271 if (i != test_size) {
272 ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
273 res = AST_TEST_FAIL;
274 goto return_cleanup;
275 }
276
277return_cleanup:
278 if (h) {
279 h = ast_heap_destroy(h);
280 }
281 if (nodes) {
283 }
284
285 return res;
286}
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
Definition: heap.c:251
Definition: ast_expr2.c:325

References ast_free, ast_heap_create, ast_heap_destroy(), ast_heap_pop(), ast_heap_push, ast_heap_remove(), ast_heap_verify(), ast_malloc, ast_random(), AST_TEST_FAIL, AST_TEST_NOT_RUN, AST_TEST_PASS, ast_test_status_update, node::index, sip_to_pjsip::info(), last, node_cmp(), nodes, NULL, TEST_EXECUTE, TEST_INIT, and node::val.

◆ load_module()

static int load_module ( void  )
static

Definition at line 297 of file test_heap.c.

298{
299 AST_TEST_REGISTER(heap_test_1);
300 AST_TEST_REGISTER(heap_test_2);
301 AST_TEST_REGISTER(heap_test_3);
302
304}
@ AST_MODULE_LOAD_SUCCESS
Definition: module.h:70
#define AST_TEST_REGISTER(cb)
Definition: test.h:127

References AST_MODULE_LOAD_SUCCESS, and AST_TEST_REGISTER.

◆ node_cmp()

static int node_cmp ( void *  _n1,
void *  _n2 
)
static

Definition at line 43 of file test_heap.c.

44{
45 struct node *n1 = _n1;
46 struct node *n2 = _n2;
47
48 if (n1->val < n2->val) {
49 return -1;
50 } else if (n1->val == n2->val) {
51 return 0;
52 } else {
53 return 1;
54 }
55}

References node::val.

Referenced by AST_TEST_DEFINE().

◆ unload_module()

static int unload_module ( void  )
static

Definition at line 288 of file test_heap.c.

289{
290 AST_TEST_UNREGISTER(heap_test_1);
291 AST_TEST_UNREGISTER(heap_test_2);
292 AST_TEST_UNREGISTER(heap_test_3);
293
294 return 0;
295}
#define AST_TEST_UNREGISTER(cb)
Definition: test.h:128

References AST_TEST_UNREGISTER.

Variable Documentation

◆ __mod_info

struct ast_module_info __mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Heap test module" , .key = "This paragraph is copyright (c) 2006 by Digium, Inc. \In order for your module to load, it must return this \key via a function called \"key\". Any code which \includes this paragraph must be licensed under the GNU \General Public License version 2 or later (at your \option). In addition to Digium's general reservations \of rights, Digium expressly reserves the right to \allow other parties to license this paragraph under \different terms. Any use of Digium, Inc. trademarks or \logos (including \"Asterisk\" or \"Digium\") without \express written permission of Digium, Inc. is prohibited.\n" , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }
static

Definition at line 306 of file test_heap.c.

◆ ast_module_info

const struct ast_module_info* ast_module_info = &__mod_info
static

Definition at line 306 of file test_heap.c.