43 static int node_cmp(
void *_n1,
void *_n2)
45 struct node *n1 = _n1;
46 struct node *n2 = _n2;
48 if (n1->val < n2->val) {
50 }
else if (n1->val == n2->val) {
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;
90 ast_test_status_update(
test,
"expected 3, got %ld\n", obj->val);
96 ast_test_status_update(
test,
"expected 2, got %ld\n", obj->val);
102 ast_test_status_update(
test,
"expected 1, got %ld\n", obj->val);
103 return AST_TEST_FAIL;
108 ast_test_status_update(
test,
"got unexpected object\n");
109 return AST_TEST_FAIL;
114 return AST_TEST_PASS;
120 static const unsigned int total = 100000;
121 struct node *nodes = NULL;
123 unsigned int i = total;
124 long last = LONG_MAX;
126 enum ast_test_result_state res = AST_TEST_PASS;
130 info->name =
"heap_test_2";
131 info->category =
"/main/heap/";
132 info->summary =
"load test";
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;
143 if (!(nodes =
ast_malloc(total *
sizeof(*node)))) {
148 if (!(h =
ast_heap_create(20, node_cmp, offsetof(
struct node, index)))) {
154 nodes[i].val = ast_random();
167 ast_test_status_update(
test,
"i: %u, cur: %ld, last: %ld\n", i, cur, last);
176 ast_test_status_update(
test,
"Stopped popping off after only getting %u nodes\n", i);
195 struct node *nodes = NULL;
197 static const unsigned int test_size = 100000;
198 unsigned int i = test_size;
199 long last = LONG_MAX, cur;
201 enum ast_test_result_state res = AST_TEST_PASS;
205 info->name =
"heap_test_3";
206 info->category =
"/main/heap/";
207 info->summary =
"random element removal test";
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;
218 if (!(nodes =
ast_malloc(test_size *
sizeof(*node)))) {
219 ast_test_status_update(
test,
"memory allocation failure\n");
224 if (!(h =
ast_heap_create(20, node_cmp, offsetof(
struct node, index)))) {
225 ast_test_status_update(
test,
"Failed to allocate heap\n");
231 nodes[i].val = ast_random();
236 ast_test_status_update(
test,
"Failed to verify heap after populating it\n");
243 random_index = ast_random() % test_size;
245 if (nodes[random_index].
val != node->val){
246 ast_test_status_update(
test,
"Failed to remove what we expected to\n");
254 ast_test_status_update(
test,
"Failed to verify after removals\n");
263 ast_test_status_update(
test,
"i: %u, cur: %ld, last: %ld\n", i, cur, last);
271 if (i != test_size) {
272 ast_test_status_update(
test,
"Stopped popping off after only getting %u nodes\n", i);
288 static int unload_module(
void)
290 AST_TEST_UNREGISTER(heap_test_1);
291 AST_TEST_UNREGISTER(heap_test_2);
292 AST_TEST_UNREGISTER(heap_test_3);
297 static int load_module(
void)
299 AST_TEST_REGISTER(heap_test_1);
300 AST_TEST_REGISTER(heap_test_2);
301 AST_TEST_REGISTER(heap_test_3);
Asterisk main include file. File version handling, generic pbx functions.
struct ast_heap * ast_heap_destroy(struct ast_heap *h)
Destroy a max heap.
void * ast_heap_pop(struct ast_heap *h)
Pop the max element off of the heap.
#define ast_heap_push(h, elm)
Push an element on to a heap.
#define ast_malloc(len)
A wrapper for malloc()
#define ast_heap_create(init_height, cmp_fn, index_offset)
Create a max heap.
void * ast_heap_remove(struct ast_heap *h, void *elm)
Remove a specific element from a heap.
#define AST_TEST_DEFINE(hdr)
int ast_heap_verify(struct ast_heap *h)
Verify that a heap has been properly constructed.
#define ASTERISK_GPL_KEY
The text the key() function should return.
Asterisk module definitions.
static struct ao2_container * nodes
All the nodes that we're aware of.