1.1 --- a/test/avl_tests.c Mon Dec 30 09:54:10 2019 +0100 1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 1.3 @@ -1,335 +0,0 @@ 1.4 -/* 1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 - * 1.7 - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. 1.8 - * 1.9 - * Redistribution and use in source and binary forms, with or without 1.10 - * modification, are permitted provided that the following conditions are met: 1.11 - * 1.12 - * 1. Redistributions of source code must retain the above copyright 1.13 - * notice, this list of conditions and the following disclaimer. 1.14 - * 1.15 - * 2. Redistributions in binary form must reproduce the above copyright 1.16 - * notice, this list of conditions and the following disclaimer in the 1.17 - * documentation and/or other materials provided with the distribution. 1.18 - * 1.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.29 - * POSSIBILITY OF SUCH DAMAGE. 1.30 - */ 1.31 - 1.32 -#include "avl_tests.h" 1.33 - 1.34 -#include <ucx/utils.h> 1.35 - 1.36 -static int node_height(UcxAVLNode *node) { 1.37 - if(!node) { 1.38 - return 0; 1.39 - } 1.40 - 1.41 - int left = 0; 1.42 - int right = 0; 1.43 - if(node->left) { 1.44 - left = node_height(node->left); 1.45 - } 1.46 - if(node->right) { 1.47 - right = node_height(node->right); 1.48 - } 1.49 - 1.50 - return left > right ? left+1 : right+1; 1.51 -} 1.52 - 1.53 -static int check_tree(UcxAVLNode *node) { 1.54 - if(!node) { 1.55 - return 1; 1.56 - } 1.57 - 1.58 - int left_height = node_height(node->left); 1.59 - int right_height = node_height(node->right); 1.60 - int bf = -left_height + right_height; 1.61 - if(bf < -1 || bf > 1) { 1.62 - return 0; 1.63 - } 1.64 - int height = left_height > right_height ? left_height : right_height; 1.65 - height++; 1.66 - if(height != node->height) { 1.67 - return 0; 1.68 - } 1.69 - 1.70 - if(!check_tree(node->left)) { 1.71 - return 0; 1.72 - } 1.73 - if(!check_tree(node->right)) { 1.74 - return 0; 1.75 - } 1.76 - 1.77 - return 1; 1.78 -} 1.79 - 1.80 -UCX_TEST(test_ucx_avl_put) { 1.81 - UcxAVLTree *tree1 = ucx_avl_new(ucx_cmp_ptr); 1.82 - UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr); 1.83 - UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr); 1.84 - UcxAVLTree *tree4 = ucx_avl_new(ucx_cmp_ptr); 1.85 - UcxAVLTree *tree5 = ucx_avl_new(ucx_cmp_ptr); 1.86 - 1.87 - char *data1 = (char*)"data1"; 1.88 - char *data2 = (char*)"data2"; 1.89 - char *data3 = (char*)"data3"; 1.90 - 1.91 - UCX_TEST_BEGIN 1.92 - 1.93 - ucx_avl_put(tree1, 2, (char*)data2); 1.94 - ucx_avl_put(tree1, 1, (char*)data1); 1.95 - ucx_avl_put(tree1, 3, (char*)data3); 1.96 - 1.97 - UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); 1.98 - UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)"); 1.99 - UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)"); 1.100 - UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)"); 1.101 - 1.102 - for(int i=0;i<100000;i++) { 1.103 - ucx_avl_put(tree2, i, data1); 1.104 - } 1.105 - UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); 1.106 - 1.107 - for(int i=100000;i>=0;i--) { 1.108 - ucx_avl_put(tree3, i, data1); 1.109 - } 1.110 - UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); 1.111 - 1.112 - for(int i=0;i<100;i++) { 1.113 - ucx_avl_put(tree4, i, data1); 1.114 - } 1.115 - for(int i=400;i<500;i++) { 1.116 - ucx_avl_put(tree4, i, data2); 1.117 - } 1.118 - for(int i=399;i>200;i--) { 1.119 - ucx_avl_put(tree4, i, data3); 1.120 - } 1.121 - for(int i=800;i<1000;i++) { 1.122 - ucx_avl_put(tree4, i, data1); 1.123 - } 1.124 - UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); 1.125 - UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0"); 1.126 - UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1"); 1.127 - UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99"); 1.128 - UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400"); 1.129 - UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410"); 1.130 - UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350"); 1.131 - UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900"); 1.132 - 1.133 - int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4}; 1.134 - int len = sizeof(values) / sizeof(int); 1.135 - for(int i=0;i<len;i++) { 1.136 - ucx_avl_put(tree5, values[i], NULL); 1.137 - } 1.138 - UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)"); 1.139 - 1.140 - UCX_TEST_END 1.141 - 1.142 - ucx_avl_free(tree1); 1.143 - ucx_avl_free(tree2); 1.144 - ucx_avl_free(tree3); 1.145 - ucx_avl_free(tree4); 1.146 - ucx_avl_free(tree5); 1.147 -} 1.148 - 1.149 -UCX_TEST(test_ucx_avl_remove) { 1.150 - UcxAVLTree *tree1 = ucx_avl_new(ucx_cmp_ptr); 1.151 - UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr); 1.152 - UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr); 1.153 - UcxAVLTree *tree4 = ucx_avl_new(ucx_cmp_ptr); 1.154 - 1.155 - char *data1 = (char*)"data1"; 1.156 - char *data2 = (char*)"data2"; 1.157 - char *data3 = (char*)"data3"; 1.158 - 1.159 - UCX_TEST_BEGIN 1.160 - ucx_avl_put(tree1, 2, (char*)data2); 1.161 - ucx_avl_put(tree1, 1, (char*)data1); 1.162 - ucx_avl_put(tree1, 3, (char*)data3); 1.163 - void *val; 1.164 - ucx_avl_remove_s(tree1, 3, NULL, &val); 1.165 - 1.166 - UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); 1.167 - UCX_TEST_ASSERT(val == data3, 1.168 - "wrong return value for key: 1 (tree1)"); 1.169 - UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)"); 1.170 - 1.171 - ucx_avl_remove_s(tree1, 2, NULL, &val); 1.172 - UCX_TEST_ASSERT(val == data2, 1.173 - "wrong return value for key: 2 (tree1)"); 1.174 - UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); 1.175 - 1.176 - ucx_avl_remove_s(tree1, 1, NULL, &val); 1.177 - UCX_TEST_ASSERT(val == data1, 1.178 - "wrong return value for key: 1 (tree1)"); 1.179 - UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)"); 1.180 - UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)"); 1.181 - 1.182 - 1.183 - for(int i=0;i<20;i++) { 1.184 - if(i==10) { 1.185 - ucx_avl_put(tree2, i, data3); 1.186 - } else if(i==15) { 1.187 - ucx_avl_put(tree2, i, data2); 1.188 - } else { 1.189 - ucx_avl_put(tree2, i, data1); 1.190 - } 1.191 - } 1.192 - 1.193 - ucx_avl_remove_s(tree2, 10, NULL, &val); 1.194 - UCX_TEST_ASSERT(val == data3, 1.195 - "wrong return value for key: 10 (tree2)"); 1.196 - UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); 1.197 - 1.198 - ucx_avl_remove_s(tree2, 15, NULL, &val); 1.199 - UCX_TEST_ASSERT(val == data2, 1.200 - "wrong return value for key: 15 (tree2)"); 1.201 - UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); 1.202 - 1.203 - for(int i=0;i<20;i++) { 1.204 - ucx_avl_remove(tree2, i); 1.205 - UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)"); 1.206 - } 1.207 - UCX_TEST_ASSERT(tree2->root == NULL, "root not NULL (tree2)"); 1.208 - 1.209 - for(int i=0;i<100000;i++) { 1.210 - ucx_avl_put(tree3, i, data1); 1.211 - } 1.212 - for(int i=100000-1;i>=0;i--) { 1.213 - ucx_avl_remove(tree3, i); 1.214 - } 1.215 - UCX_TEST_ASSERT(tree3->root == NULL, "root not NULL (tree3)"); 1.216 - UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)"); 1.217 - 1.218 - ucx_avl_put(tree4, 1, data1); 1.219 - ucx_avl_remove(tree4, 1); 1.220 - UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)"); 1.221 - UCX_TEST_ASSERT(tree4->root == NULL, "root not NULL (tree4)"); 1.222 - UCX_TEST_END 1.223 - 1.224 - ucx_avl_free(tree1); 1.225 - ucx_avl_free(tree2); 1.226 - ucx_avl_free(tree3); 1.227 - ucx_avl_free(tree4); 1.228 -} 1.229 - 1.230 -static intmax_t dist_int(const void* a, const void* b, void* n) { 1.231 - return ((intptr_t)a)-((intptr_t)b); 1.232 -} 1.233 - 1.234 -UCX_TEST(test_ucx_avl_find) { 1.235 - UcxAVLTree *tree = ucx_avl_new(ucx_cmp_ptr); 1.236 - UcxAVLTree *tree2 = ucx_avl_new(ucx_cmp_ptr); 1.237 - UcxAVLTree *tree3 = ucx_avl_new(ucx_cmp_ptr); 1.238 - 1.239 - size_t len = 12; 1.240 - int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13}; 1.241 - 1.242 - for (size_t i = 0 ; i < len ; i++) { 1.243 - ucx_avl_put(tree, val[i], &(val[i])); 1.244 - } 1.245 - 1.246 - UCX_TEST_BEGIN 1.247 - 1.248 - void* ret; 1.249 - 1.250 - /* test present values */ 1.251 - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_CLOSEST); 1.252 - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find closest failed"); 1.253 - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_EXACT); 1.254 - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find exact failed"); 1.255 - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); 1.256 - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed"); 1.257 - ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); 1.258 - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find UB failed"); 1.259 - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_CLOSEST); 1.260 - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find closest failed"); 1.261 - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_EXACT); 1.262 - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find exact failed"); 1.263 - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); 1.264 - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find LB failed"); 1.265 - ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); 1.266 - UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find UB failed"); 1.267 - 1.268 - /* test missing values */ 1.269 - ret = ucx_avl_find(tree,(intptr_t)-10, dist_int, UCX_AVL_FIND_CLOSEST); 1.270 - UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find closest failed"); 1.271 - ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_EXACT); 1.272 - UCX_TEST_ASSERT(!ret, "AVL find exact failed"); 1.273 - ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); 1.274 - UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed"); 1.275 - ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); 1.276 - UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find UB failed"); 1.277 - ret = ucx_avl_find(tree,(intptr_t)18, dist_int, UCX_AVL_FIND_CLOSEST); 1.278 - UCX_TEST_ASSERT(ret && *((int*)ret) == 20, "AVL find closest failed"); 1.279 - ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_EXACT); 1.280 - UCX_TEST_ASSERT(!ret, "AVL find exact failed"); 1.281 - ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_LOWER_BOUNDED); 1.282 - UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed"); 1.283 - ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); 1.284 - UCX_TEST_ASSERT(ret && *((int*)ret) == 4, "AVL find UB failed"); 1.285 - 1.286 - int val2[] = { 10, 15 }; 1.287 - ucx_avl_put(tree2, val2[0], &(val2[0])); 1.288 - ucx_avl_put(tree2, val2[1], &(val2[1])); 1.289 - ret = ucx_avl_find(tree2,(intptr_t)11, dist_int, UCX_AVL_FIND_UPPER_BOUNDED); 1.290 - UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed"); 1.291 - 1.292 - int val3[] = { 15, 16, 1 }; 1.293 - ucx_avl_put(tree3, val3[0], &(val3[0])); 1.294 - ucx_avl_put(tree3, val3[1], &(val3[1])); 1.295 - ucx_avl_put(tree3, val3[2], &(val3[2])); 1.296 - 1.297 - ret = ucx_avl_find(tree3, (intptr_t)13, dist_int, UCX_AVL_FIND_CLOSEST); 1.298 - UCX_TEST_ASSERT(ret && *((int*)ret) == 15, "AVL find closest failed"); 1.299 - 1.300 - UCX_TEST_END 1.301 - 1.302 - ucx_avl_free(tree); 1.303 - ucx_avl_free(tree2); 1.304 - ucx_avl_free(tree3); 1.305 -} 1.306 - 1.307 -UCX_TEST(test_ucx_avl_traverse) { 1.308 - UcxAVLTree *tree = ucx_avl_new(ucx_cmp_ptr); 1.309 - 1.310 - size_t len = 12; 1.311 - 1.312 - int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13}; 1.313 - int val_ordered[] = {-30, -11, -5, 1, 3, 4, 10, 12, 13, 14, 15, 20}; 1.314 - 1.315 - for (size_t i = 0 ; i < len ; i++) { 1.316 - ucx_avl_put(tree, val[i], &(val[i])); 1.317 - } 1.318 - 1.319 - UCX_TEST_BEGIN 1.320 - 1.321 - UcxAVLNode* node = ucx_avl_get_node(tree, (intptr_t) val_ordered[0]); 1.322 - for (size_t i = 0 ; i < len ; i++) { 1.323 - UCX_TEST_ASSERT(node->key == val_ordered[i], "AVL successor failed"); 1.324 - node = ucx_avl_succ(node); 1.325 - } 1.326 - UCX_TEST_ASSERT(!node, "AVL maximum incorrectly has a successor"); 1.327 - 1.328 - node = ucx_avl_get_node(tree, (intptr_t) val_ordered[len-1]); 1.329 - for (size_t i = len ; i > 0 ; i--) { 1.330 - UCX_TEST_ASSERT(node->key == val_ordered[i-1],"AVL predecessor failed"); 1.331 - node = ucx_avl_pred(node); 1.332 - } 1.333 - UCX_TEST_ASSERT(!node, "AVL minimum incorrectly has a predecessor"); 1.334 - 1.335 - UCX_TEST_END 1.336 - 1.337 - ucx_avl_free(tree); 1.338 -}