And the automerge property.
[asterisk/asterisk.git] / tests / test_heap.c
index 0757f29..de48f0a 100644 (file)
@@ -24,7 +24,7 @@
  */
 
 /*** MODULEINFO
-       <defaultenabled>no</defaultenabled>
+       <depend>TEST_FRAMEWORK</depend>
  ***/
 
 #include "asterisk.h"
@@ -80,8 +80,6 @@ AST_TEST_DEFINE(heap_test_1)
                return AST_TEST_FAIL;
        }
 
-       ast_test_status_update(&args->status_update, "pushing nodes\n");
-
        ast_heap_push(h, &nodes[0]);
 
        ast_heap_push(h, &nodes[1]);
@@ -90,22 +88,25 @@ AST_TEST_DEFINE(heap_test_1)
 
        obj = ast_heap_pop(h);
        if (obj->val != 3) {
+               ast_test_status_update(test, "expected 3, got %ld\n", obj->val);
                return AST_TEST_FAIL;
        }
 
-       ast_test_status_update(&args->status_update, "popping nodes\n");
        obj = ast_heap_pop(h);
        if (obj->val != 2) {
+               ast_test_status_update(test, "expected 2, got %ld\n", obj->val);
                return AST_TEST_FAIL;
        }
 
        obj = ast_heap_pop(h);
        if (obj->val != 1) {
+               ast_test_status_update(test, "expected 1, got %ld\n", obj->val);
                return AST_TEST_FAIL;
        }
 
        obj = ast_heap_pop(h);
        if (obj) {
+               ast_test_status_update(test, "got unexpected object\n");
                return AST_TEST_FAIL;
        }
 
@@ -117,10 +118,10 @@ AST_TEST_DEFINE(heap_test_1)
 AST_TEST_DEFINE(heap_test_2)
 {
        struct ast_heap *h = NULL;
-       static const unsigned int one_million = 1000000;
+       static const unsigned int total = 100000;
        struct node *nodes = NULL;
        struct node *node;
-       unsigned int i = one_million;
+       unsigned int i = total;
        long last = LONG_MAX;
        long cur;
        enum ast_test_result_state res = AST_TEST_PASS;
@@ -130,18 +131,99 @@ AST_TEST_DEFINE(heap_test_2)
                info->name = "heap_test_2";
                info->category = "main/heap/";
                info->summary = "load test";
-               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";
+               info->description =
+                               "Push one hundred thousand 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.";
+               return AST_TEST_NOT_RUN;
+       case TEST_EXECUTE:
+               break;
+       }
+
+       if (!(nodes = ast_malloc(total * sizeof(*node)))) {
+               res = AST_TEST_FAIL;
+               goto return_cleanup;
+       }
+
+       if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
+               res = AST_TEST_FAIL;
+               goto return_cleanup;
+       }
+
+       while (i--) {
+               nodes[i].val = ast_random();
+               ast_heap_push(h, &nodes[i]);
+       }
+
+       if (ast_heap_verify(h)) {
+               res = AST_TEST_FAIL;
+               goto return_cleanup;
+       }
+
+       i = 0;
+       while ((node = ast_heap_pop(h))) {
+               cur = node->val;
+               if (cur > last) {
+                       ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
+                       res = AST_TEST_FAIL;
+                       goto return_cleanup;
+               }
+               last = cur;
+               i++;
+       }
+
+       if (i != total) {
+               ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
+               res = AST_TEST_FAIL;
+               goto return_cleanup;
+       }
+
+return_cleanup:
+       if (h) {
+               h = ast_heap_destroy(h);
+       }
+       if (nodes) {
+               ast_free(nodes);
+       }
+
+       return res;
+}
+
+AST_TEST_DEFINE(heap_test_3)
+{
+       struct ast_heap *h = NULL;
+       struct node *nodes = NULL;
+       struct node *node;
+       static const unsigned int test_size = 100000;
+       unsigned int i = test_size;
+       long last = LONG_MAX, cur;
+       int random_index;
+       enum ast_test_result_state res = AST_TEST_PASS;
+
+       switch (cmd) {
+       case TEST_INIT:
+               info->name = "heap_test_3";
+               info->category = "main/heap/";
+               info->summary = "random element removal test";
+               info->description =
+                       "Push a hundred thousand random elements on to a heap, "
+                       "verify that the heap has been properly constructed, "
+                       "randomly remove and re-add 10000 elements, and then "
+                       "ensure that the elements come back off in the proper order.";
                return AST_TEST_NOT_RUN;
        case TEST_EXECUTE:
                break;
        }
 
-       if (!(nodes = ast_malloc(one_million * sizeof(*node)))) {
+       if (!(nodes = ast_malloc(test_size * sizeof(*node)))) {
+               ast_test_status_update(test, "memory allocation failure\n");
                res = AST_TEST_FAIL;
                goto return_cleanup;
        }
 
        if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
+               ast_test_status_update(test, "Failed to allocate heap\n");
                res = AST_TEST_FAIL;
                goto return_cleanup;
        }
@@ -152,6 +234,25 @@ AST_TEST_DEFINE(heap_test_2)
        }
 
        if (ast_heap_verify(h)) {
+               ast_test_status_update(test, "Failed to verify heap after populating it\n");
+               res = AST_TEST_FAIL;
+               goto return_cleanup;
+       }
+
+       i = test_size / 10;
+       while (i--) {
+               random_index = ast_random() % test_size;
+               node = ast_heap_remove(h, &nodes[random_index]);
+               if (nodes[random_index].val != node->val){
+                       ast_test_status_update(test, "Failed to remove what we expected to\n");
+                       res = AST_TEST_FAIL;
+                       goto return_cleanup;
+               }
+               ast_heap_push(h, &nodes[random_index]);
+       }
+
+       if (ast_heap_verify(h)) {
+               ast_test_status_update(test, "Failed to verify after removals\n");
                res = AST_TEST_FAIL;
                goto return_cleanup;
        }
@@ -160,7 +261,7 @@ AST_TEST_DEFINE(heap_test_2)
        while ((node = ast_heap_pop(h))) {
                cur = node->val;
                if (cur > last) {
-                       ast_str_set(&args->ast_test_error_str, 0, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
+                       ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
                        res = AST_TEST_FAIL;
                        goto return_cleanup;
                }
@@ -168,8 +269,8 @@ AST_TEST_DEFINE(heap_test_2)
                i++;
        }
 
-       if (i != one_million) {
-               ast_str_set(&args->ast_test_error_str, 0, "Stopped popping off after only getting %u nodes\n", i);
+       if (i != test_size) {
+               ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
                res = AST_TEST_FAIL;
                goto return_cleanup;
        }
@@ -189,15 +290,16 @@ static int unload_module(void)
 {
        AST_TEST_UNREGISTER(heap_test_1);
        AST_TEST_UNREGISTER(heap_test_2);
+       AST_TEST_UNREGISTER(heap_test_3);
+
        return 0;
 }
 
 static int load_module(void)
 {
-
        AST_TEST_REGISTER(heap_test_1);
-
        AST_TEST_REGISTER(heap_test_2);
+       AST_TEST_REGISTER(heap_test_3);
 
        return AST_MODULE_LOAD_SUCCESS;
 }