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_module *	AST_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 = ASTERISK_GPL_KEY , .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_info *	ast_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.

{
    struct ast_heap *h;
    struct node *obj;
    struct node nodes[3] = {
        { 1, } ,
        { 2, } ,
        { 3, } ,
    };
 
    switch (cmd) {
    case TEST_INIT:
        info->name = "heap_test_1";
        info->category = "/main/heap/";
        info->summary = "push and pop elements";
        info->description = "Push a few elements onto a heap and make sure that they come back off in the right order.";
        return AST_TEST_NOT_RUN;
    case TEST_EXECUTE:
        break;
    }
 
    if (!(h = ast_heap_create(8, node_cmp, offsetof(struct node, index)))) {
        return AST_TEST_FAIL;
    }
 
    ast_heap_push(h, &nodes[0]);
 
    ast_heap_push(h, &nodes[1]);
 
    ast_heap_push(h, &nodes[2]);
 
    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;
    }
 
    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;
    }
 
    h = ast_heap_destroy(h);
 
    return AST_TEST_PASS;
}

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, 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.

{
    struct ast_heap *h = NULL;
    static const unsigned int total = 100000;
    struct node *nodes = NULL;
    struct node *node;
    unsigned int i = total;
    long last = LONG_MAX;
    long cur;
    enum ast_test_result_state res = AST_TEST_PASS;
 
    switch (cmd) {
    case TEST_INIT:
        info->name = "heap_test_2";
        info->category = "/main/heap/";
        info->summary = "load test";
        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;
}

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, 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.

{
    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(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;
    }
 
    while (i--) {
        nodes[i].val = ast_random();
        ast_heap_push(h, &nodes[i]);
    }
 
    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;
    }
 
    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 != test_size) {
        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;
}

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, 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.

{
    AST_TEST_REGISTER(heap_test_1);
    AST_TEST_REGISTER(heap_test_2);
    AST_TEST_REGISTER(heap_test_3);
 
    return AST_MODULE_LOAD_SUCCESS;
}

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.

{
    struct node *n1 = _n1;
    struct node *n2 = _n2;
 
    if (n1->val < n2->val) {
        return -1;
    } else if (n1->val == n2->val) {
        return 0;
    } else {
        return 1;
    }
}

References node::val.

Referenced by AST_TEST_DEFINE(), AST_TEST_DEFINE(), and AST_TEST_DEFINE().

unload_module()

static int unload_module ( void  )

static

Definition at line 288 of file test_heap.c.

{
    AST_TEST_UNREGISTER(heap_test_1);
    AST_TEST_UNREGISTER(heap_test_2);
    AST_TEST_UNREGISTER(heap_test_3);
 
    return 0;
}

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 = ASTERISK_GPL_KEY , .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.