diff -r a82f3456b76d -r b0f4fb043b47 test/avl_tests.c --- a/test/avl_tests.c Mon May 18 18:42:45 2015 +0200 +++ b/test/avl_tests.c Mon May 18 19:12:32 2015 +0200 @@ -28,3 +28,117 @@ #include "avl_tests.h" +#include "ucx/utils.h" + +static int node_height(UcxAVLNode *node) { + if(!node) { + return 0; + } + + int left = 0; + int right = 0; + if(node->left) { + left = node_height(node->left); + } + if(node->right) { + right = node_height(node->right); + } + + return left > right ? left+1 : right+1; +} + +static int check_tree(UcxAVLNode *node) { + if(!node) { + return 1; + } + + int left_height = node_height(node->left); + int right_height = node_height(node->right); + int bf = -left_height + right_height; + if(bf < -1 || bf > 1) { + return 0; + } + int height = left_height > right_height ? left_height : right_height; + height++; + if(height != node->height) { + return 0; + } + + if(!check_tree(node->left)) { + return 0; + } + if(!check_tree(node->right)) { + return 0; + } + + return 1; +} + +UCX_TEST(test_ucx_avl_put) { + UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp); + UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp); + UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp); + UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp); + UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp); + + char *data1 = (char*)"data1"; + char *data2 = (char*)"data2"; + char *data3 = (char*)"data3"; + + UCX_TEST_BEGIN + + ucx_avl_put(tree1, 2, (char*)data2); + ucx_avl_put(tree1, 1, (char*)data1); + ucx_avl_put(tree1, 3, (char*)data3); + + UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); + UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)"); + UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)"); + UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)"); + + for(int i=0;i<100000;i++) { + ucx_avl_put(tree2, i, data1); + } + UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); + + for(int i=100000;i>=0;i--) { + ucx_avl_put(tree3, i, data1); + } + UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); + + for(int i=0;i<100;i++) { + ucx_avl_put(tree4, i, data1); + } + for(int i=400;i<500;i++) { + ucx_avl_put(tree4, i, data2); + } + for(int i=399;i>200;i--) { + ucx_avl_put(tree4, i, data3); + } + for(int i=800;i<1000;i++) { + ucx_avl_put(tree4, i, data1); + } + UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); + UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0"); + UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1"); + UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99"); + UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400"); + UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410"); + UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350"); + UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900"); + + int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4}; + int len = sizeof(values) / sizeof(int); + for(int i=0;iroot), "check_tree failed (tree5)"); + + UCX_TEST_END + + ucx_avl_free(tree1); + ucx_avl_free(tree2); + ucx_avl_free(tree3); + ucx_avl_free(tree4); + ucx_avl_free(tree5); +}