diff -r 92e482410453 -r d345541018fa test/avl_tests.c --- a/test/avl_tests.c Mon Dec 30 09:54:10 2019 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,335 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -#include "avl_tests.h" - -#include - -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_cmp_ptr); - UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree4 = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree5 = ucx_avl_new(ucx_cmp_ptr); - - 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); -} - -UCX_TEST(test_ucx_avl_remove) { - UcxAVLTree *tree1 = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree4 = ucx_avl_new(ucx_cmp_ptr); - - 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); - void *val; - ucx_avl_remove_s(tree1, 3, NULL, &val); - - UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); - UCX_TEST_ASSERT(val == data3, - "wrong return value for key: 1 (tree1)"); - UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)"); - - ucx_avl_remove_s(tree1, 2, NULL, &val); - UCX_TEST_ASSERT(val == data2, - "wrong return value for key: 2 (tree1)"); - UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); - - ucx_avl_remove_s(tree1, 1, NULL, &val); - UCX_TEST_ASSERT(val == data1, - "wrong return value for key: 1 (tree1)"); - UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); - UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)"); - - - for(int i=0;i<20;i++) { - if(i==10) { - ucx_avl_put(tree2, i, data3); - } else if(i==15) { - ucx_avl_put(tree2, i, data2); - } else { - ucx_avl_put(tree2, i, data1); - } - } - - ucx_avl_remove_s(tree2, 10, NULL, &val); - UCX_TEST_ASSERT(val == data3, - "wrong return value for key: 10 (tree2)"); - UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); - - ucx_avl_remove_s(tree2, 15, NULL, &val); - UCX_TEST_ASSERT(val == data2, - "wrong return value for key: 15 (tree2)"); - UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); - - for(int i=0;i<20;i++) { - ucx_avl_remove(tree2, i); - UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); - } - UCX_TEST_ASSERT(tree2->root == NULL, "root not NULL (tree2)"); - - for(int i=0;i<100000;i++) { - ucx_avl_put(tree3, i, data1); - } - for(int i=100000-1;i>=0;i--) { - ucx_avl_remove(tree3, i); - } - UCX_TEST_ASSERT(tree3->root == NULL, "root not NULL (tree3)"); - UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); - - ucx_avl_put(tree4, 1, data1); - ucx_avl_remove(tree4, 1); - UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); - UCX_TEST_ASSERT(tree4->root == NULL, "root not NULL (tree4)"); - UCX_TEST_END - - ucx_avl_free(tree1); - ucx_avl_free(tree2); - ucx_avl_free(tree3); - ucx_avl_free(tree4); -} - -static intmax_t dist_int(const void* a, const void* b, void* n) { - return ((intptr_t)a)-((intptr_t)b); -} - -UCX_TEST(test_ucx_avl_find) { - UcxAVLTree *tree = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr); - UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr); - - size_t len = 12; - int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13}; - - for (size_t i = 0 ; i < len ; i++) { - ucx_avl_put(tree, val[i], &(val[i])); - } - - UCX_TEST_BEGIN - - void* ret; - - /* test present values */ - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_CLOSEST); - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find closest failed"); - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_EXACT); - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find exact failed"); - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed"); - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find UB failed"); - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_CLOSEST); - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find closest failed"); - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_EXACT); - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find exact failed"); - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find LB failed"); - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find UB failed"); - - /* test missing values */ - ret = ucx_avl_find(tree,(intptr_t)-10, dist_int, UCX_AVL_FIND_CLOSEST); - UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find closest failed"); - ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_EXACT); - UCX_TEST_ASSERT(!ret, "AVL find exact failed"); - ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed"); - ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find UB failed"); - ret = ucx_avl_find(tree,(intptr_t)18, dist_int, UCX_AVL_FIND_CLOSEST); - UCX_TEST_ASSERT(ret && *((int*)ret) == 20, "AVL find closest failed"); - ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_EXACT); - UCX_TEST_ASSERT(!ret, "AVL find exact failed"); - ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed"); - ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == 4, "AVL find UB failed"); - - int val2[] = { 10, 15 }; - ucx_avl_put(tree2, val2[0], &(val2[0])); - ucx_avl_put(tree2, val2[1], &(val2[1])); - ret = ucx_avl_find(tree2,(intptr_t)11, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); - UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed"); - - int val3[] = { 15, 16, 1 }; - ucx_avl_put(tree3, val3[0], &(val3[0])); - ucx_avl_put(tree3, val3[1], &(val3[1])); - ucx_avl_put(tree3, val3[2], &(val3[2])); - - ret = ucx_avl_find(tree3, (intptr_t)13, dist_int, UCX_AVL_FIND_CLOSEST); - UCX_TEST_ASSERT(ret && *((int*)ret) == 15, "AVL find closest failed"); - - UCX_TEST_END - - ucx_avl_free(tree); - ucx_avl_free(tree2); - ucx_avl_free(tree3); -} - -UCX_TEST(test_ucx_avl_traverse) { - UcxAVLTree *tree = ucx_avl_new(ucx_cmp_ptr); - - size_t len = 12; - - int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13}; - int val_ordered[] = {-30, -11, -5, 1, 3, 4, 10, 12, 13, 14, 15, 20}; - - for (size_t i = 0 ; i < len ; i++) { - ucx_avl_put(tree, val[i], &(val[i])); - } - - UCX_TEST_BEGIN - - UcxAVLNode* node = ucx_avl_get_node(tree, (intptr_t) val_ordered[0]); - for (size_t i = 0 ; i < len ; i++) { - UCX_TEST_ASSERT(node->key == val_ordered[i], "AVL successor failed"); - node = ucx_avl_succ(node); - } - UCX_TEST_ASSERT(!node, "AVL maximum incorrectly has a successor"); - - node = ucx_avl_get_node(tree, (intptr_t) val_ordered[len-1]); - for (size_t i = len ; i > 0 ; i--) { - UCX_TEST_ASSERT(node->key == val_ordered[i-1],"AVL predecessor failed"); - node = ucx_avl_pred(node); - } - UCX_TEST_ASSERT(!node, "AVL minimum incorrectly has a predecessor"); - - UCX_TEST_END - - ucx_avl_free(tree); -}