universe@56: /* universe@103: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. universe@56: * universe@192: * Copyright 2015 Olaf Wintermann. All rights reserved. universe@103: * universe@103: * Redistribution and use in source and binary forms, with or without universe@103: * modification, are permitted provided that the following conditions are met: universe@103: * universe@103: * 1. Redistributions of source code must retain the above copyright universe@103: * notice, this list of conditions and the following disclaimer. universe@103: * universe@103: * 2. Redistributions in binary form must reproduce the above copyright universe@103: * notice, this list of conditions and the following disclaimer in the universe@103: * documentation and/or other materials provided with the distribution. universe@103: * universe@103: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" universe@103: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE universe@103: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE universe@103: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE universe@103: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR universe@103: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF universe@103: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS universe@103: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN universe@103: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) universe@103: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE universe@103: * POSSIBILITY OF SUCH DAMAGE. universe@56: */ universe@56: universe@192: #include "avl_tests.h" universe@56: olaf@198: #include "ucx/utils.h" olaf@198: olaf@198: static int node_height(UcxAVLNode *node) { olaf@198: if(!node) { olaf@198: return 0; olaf@198: } olaf@198: olaf@198: int left = 0; olaf@198: int right = 0; olaf@198: if(node->left) { olaf@198: left = node_height(node->left); olaf@198: } olaf@198: if(node->right) { olaf@198: right = node_height(node->right); olaf@198: } olaf@198: olaf@198: return left > right ? left+1 : right+1; olaf@198: } olaf@198: olaf@198: static int check_tree(UcxAVLNode *node) { olaf@198: if(!node) { olaf@198: return 1; olaf@198: } olaf@198: olaf@198: int left_height = node_height(node->left); olaf@198: int right_height = node_height(node->right); olaf@198: int bf = -left_height + right_height; olaf@198: if(bf < -1 || bf > 1) { olaf@198: return 0; olaf@198: } olaf@198: int height = left_height > right_height ? left_height : right_height; olaf@198: height++; olaf@198: if(height != node->height) { olaf@198: return 0; olaf@198: } olaf@198: olaf@198: if(!check_tree(node->left)) { olaf@198: return 0; olaf@198: } olaf@198: if(!check_tree(node->right)) { olaf@198: return 0; olaf@198: } olaf@198: olaf@198: return 1; olaf@198: } olaf@198: olaf@198: UCX_TEST(test_ucx_avl_put) { olaf@198: UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp); olaf@198: UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp); olaf@198: UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp); olaf@198: UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp); olaf@198: UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp); olaf@198: olaf@198: char *data1 = (char*)"data1"; olaf@198: char *data2 = (char*)"data2"; olaf@198: char *data3 = (char*)"data3"; olaf@198: olaf@198: UCX_TEST_BEGIN olaf@198: olaf@198: ucx_avl_put(tree1, 2, (char*)data2); olaf@198: ucx_avl_put(tree1, 1, (char*)data1); olaf@198: ucx_avl_put(tree1, 3, (char*)data3); olaf@198: olaf@198: UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)"); olaf@198: olaf@198: for(int i=0;i<100000;i++) { olaf@198: ucx_avl_put(tree2, i, data1); olaf@198: } olaf@198: UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); olaf@198: olaf@198: for(int i=100000;i>=0;i--) { olaf@198: ucx_avl_put(tree3, i, data1); olaf@198: } olaf@198: UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); olaf@198: olaf@198: for(int i=0;i<100;i++) { olaf@198: ucx_avl_put(tree4, i, data1); olaf@198: } olaf@198: for(int i=400;i<500;i++) { olaf@198: ucx_avl_put(tree4, i, data2); olaf@198: } olaf@198: for(int i=399;i>200;i--) { olaf@198: ucx_avl_put(tree4, i, data3); olaf@198: } olaf@198: for(int i=800;i<1000;i++) { olaf@198: ucx_avl_put(tree4, i, data1); olaf@198: } olaf@198: UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350"); olaf@198: UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900"); olaf@198: olaf@198: int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4}; olaf@198: int len = sizeof(values) / sizeof(int); olaf@198: for(int i=0;iroot), "check_tree failed (tree5)"); olaf@198: olaf@198: UCX_TEST_END olaf@198: olaf@198: ucx_avl_free(tree1); olaf@198: ucx_avl_free(tree2); olaf@198: ucx_avl_free(tree3); olaf@198: ucx_avl_free(tree4); olaf@198: ucx_avl_free(tree5); olaf@198: }