From 56b9180bd7f88eae968e9b1e485dc5cf85acadce Mon Sep 17 00:00:00 2001 From: Russell Bryant Date: Tue, 17 Feb 2009 20:56:26 +0000 Subject: Add a test module for the heap implementation. Review: http://reviewboard.digium.com/r/160/ git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@176635 65c4cc65-6c06-0410-ace0-fbb531ad65f3 --- tests/test_heap.c | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 219 insertions(+) create mode 100644 tests/test_heap.c (limited to 'tests') diff --git a/tests/test_heap.c b/tests/test_heap.c new file mode 100644 index 000000000..c5d3f5f2e --- /dev/null +++ b/tests/test_heap.c @@ -0,0 +1,219 @@ +/* + * Asterisk -- An open source telephony toolkit. + * + * Copyright (C) 2009, Digium, Inc. + * + * Russell Bryant + * + * See http://www.asterisk.org for more information about + * the Asterisk project. Please do not directly contact + * any of the maintainers of this project for assistance; + * the project provides a web site, mailing lists and IRC + * channels for your use. + * + * This program is free software, distributed under the terms of + * the GNU General Public License Version 2. See the LICENSE file + * at the top of the source tree. + */ + +/*! \file + * + * \brief Heap data structure test module + * + * \author Russell Bryant + */ + +#include "asterisk.h" + +ASTERISK_FILE_VERSION(__FILE__, "$Revision$") + +#include "asterisk/module.h" +#include "asterisk/cli.h" +#include "asterisk/utils.h" +#include "asterisk/heap.h" + +struct node { + long val; + size_t index; +}; + +static int node_cmp(void *_n1, void *_n2) +{ + 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; + } +} + +static int test1(int fd) +{ + struct ast_heap *h; + struct node *obj; + struct node nodes[3] = { + { 1, }, + { 2, }, + { 3, }, + }; + + if (!(h = ast_heap_create(8, node_cmp, offsetof(struct node, index)))) { + return -1; + } + + /* Pushing 1 2 3, and then popping 3 elements */ + + ast_cli(fd, "Test #1 - Push a few elements onto a heap and make sure that they " + "come back off in the right order.\n"); + + 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) { + return -2; + } + + obj = ast_heap_pop(h); + if (obj->val != 2) { + return -3; + } + + obj = ast_heap_pop(h); + if (obj->val != 1) { + return -4; + } + + obj = ast_heap_pop(h); + if (obj) { + return -5; + } + + h = ast_heap_destroy(h); + + ast_cli(fd, "Test #1 successful.\n"); + + return 0; +} + +static int test2(int fd) +{ + struct ast_heap *h = NULL; + static const unsigned int one_million = 1000000; + struct node *nodes = NULL; + struct node *node; + unsigned int i = one_million; + long last = LONG_MAX, cur; + int res = 0; + + ast_cli(fd, "Test #2 - 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\n"); + + if (!(nodes = ast_malloc(one_million * sizeof(*node)))) { + res = -1; + goto return_cleanup; + } + + if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) { + res = -2; + goto return_cleanup; + } + + while (i--) { + nodes[i].val = ast_random(); + ast_heap_push(h, &nodes[i]); + } + + if (ast_heap_verify(h)) { + res = -3; + goto return_cleanup; + } + + i = 0; + while ((node = ast_heap_pop(h))) { + cur = node->val; + if (cur > last) { + ast_cli(fd, "i: %u, cur: %ld, last: %ld\n", i, cur, last); + res = -4; + goto return_cleanup; + } + last = cur; + i++; + } + + if (i != one_million) { + ast_cli(fd, "Stopped popping off after only getting %u nodes\n", i); + res = -5; + goto return_cleanup; + } + + ast_cli(fd, "Test #2 successful.\n"); + +return_cleanup: + if (h) { + h = ast_heap_destroy(h); + } + if (nodes) { + ast_free(nodes); + } + + return res; +} + +static char *handle_cli_heap_test(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a) +{ + int res; + + switch (cmd) { + case CLI_INIT: + e->command = "heap test"; + e->usage = "" + "Usage: heap test\n" + ""; + return NULL; + case CLI_GENERATE: + return NULL; + } + + if (a->argc != e->args) { + return CLI_SHOWUSAGE; + } + + if ((res = test1(a->fd))) { + ast_cli(a->fd, "Test 1 failed! (%d)\n", res); + return CLI_FAILURE; + } + + if ((res = test2(a->fd))) { + ast_cli(a->fd, "Test 2 failed! (%d)\n", res); + return CLI_FAILURE; + } + + return CLI_SUCCESS; +} + +static struct ast_cli_entry cli_heap[] = { + AST_CLI_DEFINE(handle_cli_heap_test, "Test the heap implementation"), +}; + +static int unload_module(void) +{ + ast_cli_unregister_multiple(cli_heap, ARRAY_LEN(cli_heap)); + return 0; +} + +static int load_module(void) +{ + ast_cli_register_multiple(cli_heap, ARRAY_LEN(cli_heap)); + return AST_MODULE_LOAD_SUCCESS; +} + +AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Heap test module"); -- cgit v1.2.3