test/avl_tests.c

Sat, 15 Jul 2017 22:36:29 +0200

author
Mike Becker <universe@uap-core.de>
date
Sat, 15 Jul 2017 22:36:29 +0200
changeset 245
db732f8c083a
parent 244
98dc2d3a9b1d
child 250
b7d1317b138e
permissions
-rw-r--r--

adds AVL predecessor and successor functions

56
76caac0da4a0 added memstream to ucx - still little work to do
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
103
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
56
76caac0da4a0 added memstream to ucx - still little work to do
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
225
a1a068c2c4ef updates documenting comments
Mike Becker <universe@uap-core.de>
parents: 204
diff changeset
4 * Copyright 2016 Olaf Wintermann. All rights reserved.
103
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
5 *
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
6 * Redistribution and use in source and binary forms, with or without
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
7 * modification, are permitted provided that the following conditions are met:
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
8 *
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
10 * notice, this list of conditions and the following disclaimer.
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
11 *
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
14 * documentation and/or other materials provided with the distribution.
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
15 *
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
08018864fb91 added license and copyright notice to all files
Mike Becker <universe@uap-core.de>
parents: 95
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
56
76caac0da4a0 added memstream to ucx - still little work to do
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
76caac0da4a0 added memstream to ucx - still little work to do
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28
192
1e51558b9d09 updated copyright notice + added files for upcoming AVL tree implementation
Mike Becker <universe@uap-core.de>
parents: 177
diff changeset
29 #include "avl_tests.h"
56
76caac0da4a0 added memstream to ucx - still little work to do
Mike Becker <universe@uap-core.de>
parents:
diff changeset
30
198
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
31 #include "ucx/utils.h"
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
32
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
33 static int node_height(UcxAVLNode *node) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
34 if(!node) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
35 return 0;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
36 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
37
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
38 int left = 0;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
39 int right = 0;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
40 if(node->left) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
41 left = node_height(node->left);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
42 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
43 if(node->right) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
44 right = node_height(node->right);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
45 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
46
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
47 return left > right ? left+1 : right+1;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
48 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
49
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
50 static int check_tree(UcxAVLNode *node) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
51 if(!node) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
52 return 1;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
53 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
54
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
55 int left_height = node_height(node->left);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
56 int right_height = node_height(node->right);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
57 int bf = -left_height + right_height;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
58 if(bf < -1 || bf > 1) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
59 return 0;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
60 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
61 int height = left_height > right_height ? left_height : right_height;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
62 height++;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
63 if(height != node->height) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
64 return 0;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
65 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
66
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
67 if(!check_tree(node->left)) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
68 return 0;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
69 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
70 if(!check_tree(node->right)) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
71 return 0;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
72 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
73
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
74 return 1;
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
75 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
76
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
77 UCX_TEST(test_ucx_avl_put) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
78 UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
79 UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
80 UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
81 UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
82 UcxAVLTree *tree5 = ucx_avl_new(ucx_ptrcmp);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
83
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
84 char *data1 = (char*)"data1";
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
85 char *data2 = (char*)"data2";
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
86 char *data3 = (char*)"data3";
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
87
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
88 UCX_TEST_BEGIN
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
89
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
90 ucx_avl_put(tree1, 2, (char*)data2);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
91 ucx_avl_put(tree1, 1, (char*)data1);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
92 ucx_avl_put(tree1, 3, (char*)data3);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
93
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
94 UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
95 UCX_TEST_ASSERT(ucx_avl_get(tree1, 1) == data1, "wrong data (tree1)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
96 UCX_TEST_ASSERT(ucx_avl_get(tree1, 2) == data2, "wrong data (tree1)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
97 UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == data3, "wrong data (tree1)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
98
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
99 for(int i=0;i<100000;i++) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
100 ucx_avl_put(tree2, i, data1);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
101 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
102 UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
103
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
104 for(int i=100000;i>=0;i--) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
105 ucx_avl_put(tree3, i, data1);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
106 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
107 UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
108
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
109 for(int i=0;i<100;i++) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
110 ucx_avl_put(tree4, i, data1);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
111 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
112 for(int i=400;i<500;i++) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
113 ucx_avl_put(tree4, i, data2);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
114 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
115 for(int i=399;i>200;i--) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
116 ucx_avl_put(tree4, i, data3);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
117 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
118 for(int i=800;i<1000;i++) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
119 ucx_avl_put(tree4, i, data1);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
120 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
121 UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
122 UCX_TEST_ASSERT(ucx_avl_get(tree4, 0) == data1, "wrong data for key: 0");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
123 UCX_TEST_ASSERT(ucx_avl_get(tree4, 1) == data1, "wrong data for key: 1");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
124 UCX_TEST_ASSERT(ucx_avl_get(tree4, 99) == data1, "wrong data for key: 99");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
125 UCX_TEST_ASSERT(ucx_avl_get(tree4, 400)==data2, "wrong data for key: 400");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
126 UCX_TEST_ASSERT(ucx_avl_get(tree4, 410)==data2, "wrong data for key: 410");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
127 UCX_TEST_ASSERT(ucx_avl_get(tree4, 350)==data3, "wrong data for key: 350");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
128 UCX_TEST_ASSERT(ucx_avl_get(tree4, 900)==data1, "wrong data for key: 900");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
129
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
130 int values[] = { 3, 6, 12, 9, 23, 1, 0, 20, 34, 5, 8, 7, 6, 14, 15, 2, 4};
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
131 int len = sizeof(values) / sizeof(int);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
132 for(int i=0;i<len;i++) {
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
133 ucx_avl_put(tree5, values[i], NULL);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
134 }
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
135 UCX_TEST_ASSERT(check_tree(tree5->root), "check_tree failed (tree5)");
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
136
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
137 UCX_TEST_END
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
138
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
139 ucx_avl_free(tree1);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
140 ucx_avl_free(tree2);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
141 ucx_avl_free(tree3);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
142 ucx_avl_free(tree4);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
143 ucx_avl_free(tree5);
b0f4fb043b47 added test for ucx_avl_put
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 192
diff changeset
144 }
200
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
145
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
146 UCX_TEST(test_ucx_avl_remove) {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
147 UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
148 UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
149 UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
150 UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
151
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
152 char *data1 = (char*)"data1";
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
153 char *data2 = (char*)"data2";
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
154 char *data3 = (char*)"data3";
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
155
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
156 UCX_TEST_BEGIN
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
157 ucx_avl_put(tree1, 2, (char*)data2);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
158 ucx_avl_put(tree1, 1, (char*)data1);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
159 ucx_avl_put(tree1, 3, (char*)data3);
204
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
160 void *val;
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
161 ucx_avl_remove_s(tree1, 3, NULL, &val);
200
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
162
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
163 UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
204
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
164 UCX_TEST_ASSERT(val == data3,
201
45810f5b7b84 extended ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 200
diff changeset
165 "wrong return value for key: 1 (tree1)");
200
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
166 UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)");
204
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
167
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
168 ucx_avl_remove_s(tree1, 2, NULL, &val);
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
169 UCX_TEST_ASSERT(val == data2,
201
45810f5b7b84 extended ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 200
diff changeset
170 "wrong return value for key: 2 (tree1)");
45810f5b7b84 extended ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 200
diff changeset
171 UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
204
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
172
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
173 ucx_avl_remove_s(tree1, 1, NULL, &val);
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
174 UCX_TEST_ASSERT(val == data1,
201
45810f5b7b84 extended ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 200
diff changeset
175 "wrong return value for key: 1 (tree1)");
45810f5b7b84 extended ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 200
diff changeset
176 UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
45810f5b7b84 extended ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 200
diff changeset
177 UCX_TEST_ASSERT(tree1->root == NULL, "root not NULL (tree1)");
45810f5b7b84 extended ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 200
diff changeset
178
200
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
179
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
180 for(int i=0;i<20;i++) {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
181 if(i==10) {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
182 ucx_avl_put(tree2, i, data3);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
183 } else if(i==15) {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
184 ucx_avl_put(tree2, i, data2);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
185 } else {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
186 ucx_avl_put(tree2, i, data1);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
187 }
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
188 }
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
189
204
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
190 ucx_avl_remove_s(tree2, 10, NULL, &val);
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
191 UCX_TEST_ASSERT(val == data3,
200
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
192 "wrong return value for key: 10 (tree2)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
193 UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
194
204
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
195 ucx_avl_remove_s(tree2, 15, NULL, &val);
4477987d40cd better and better and better AVL API
Mike Becker <universe@uap-core.de>
parents: 203
diff changeset
196 UCX_TEST_ASSERT(val == data2,
200
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
197 "wrong return value for key: 15 (tree2)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
198 UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
199
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
200 for(int i=0;i<20;i++) {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
201 ucx_avl_remove(tree2, i);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
202 UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
203 }
203
3d999ea3f780 added 1 assert in ucx_avl_remove tests and fixed source code formatting
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 201
diff changeset
204 UCX_TEST_ASSERT(tree2->root == NULL, "root not NULL (tree2)");
200
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
205
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
206 for(int i=0;i<100000;i++) {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
207 ucx_avl_put(tree3, i, data1);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
208 }
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
209 for(int i=100000-1;i>=0;i--) {
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
210 ucx_avl_remove(tree3, i);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
211 }
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
212 UCX_TEST_ASSERT(tree3->root == NULL, "root not NULL (tree3)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
213 UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
214
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
215 ucx_avl_put(tree4, 1, data1);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
216 ucx_avl_remove(tree4, 1);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
217 UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
218 UCX_TEST_ASSERT(tree4->root == NULL, "root not NULL (tree4)");
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
219 UCX_TEST_END
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
220
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
221 ucx_avl_free(tree1);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
222 ucx_avl_free(tree2);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
223 ucx_avl_free(tree3);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
224 ucx_avl_free(tree4);
e3aad99d2d80 added ucx_avl_remove tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 198
diff changeset
225 }
243
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
226
244
98dc2d3a9b1d adds const qualifiers to compare, distance and copy function signatures
Mike Becker <universe@uap-core.de>
parents: 243
diff changeset
227 static intmax_t dist_int(const void* a, const void* b, void* n) {
243
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
228 return ((intmax_t)a)-((intmax_t)b);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
229 }
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
230
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
231 UCX_TEST(test_ucx_avl_find) {
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
232 UcxAVLTree *tree = ucx_avl_new(ucx_ptrcmp);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
233
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
234 size_t len = 12;
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
235 int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13};
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
236
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
237 for (size_t i = 0 ; i < len ; i++) {
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
238 ucx_avl_put(tree, val[i], &(val[i]));
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
239 }
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
240
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
241 UCX_TEST_BEGIN
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
242
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
243 void* ret;
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
244
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
245 /* test present values */
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
246 ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_CLOSEST);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
247 UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find closest failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
248 ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_EXACT);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
249 UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find exact failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
250 ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
251 UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
252 ret = ucx_avl_find(tree,(intptr_t)-5, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
253 UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find UB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
254 ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_CLOSEST);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
255 UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find closest failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
256 ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_EXACT);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
257 UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find exact failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
258 ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
259 UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find LB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
260 ret = ucx_avl_find(tree,(intptr_t)12, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
261 UCX_TEST_ASSERT(ret && *((int*)ret) == 12, "AVL find UB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
262
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
263 /* test missing values */
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
264 ret = ucx_avl_find(tree,(intptr_t)-10, dist_int, UCX_AVL_FIND_CLOSEST);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
265 UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find closest failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
266 ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_EXACT);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
267 UCX_TEST_ASSERT(!ret, "AVL find exact failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
268 ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
269 UCX_TEST_ASSERT(ret && *((int*)ret) == -5, "AVL find LB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
270 ret = ucx_avl_find(tree,(intptr_t)-8, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
271 UCX_TEST_ASSERT(ret && *((int*)ret) == -11, "AVL find UB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
272 ret = ucx_avl_find(tree,(intptr_t)18, dist_int, UCX_AVL_FIND_CLOSEST);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
273 UCX_TEST_ASSERT(ret && *((int*)ret) == 20, "AVL find closest failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
274 ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_EXACT);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
275 UCX_TEST_ASSERT(!ret, "AVL find exact failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
276 ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_LOWER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
277 UCX_TEST_ASSERT(ret && *((int*)ret) == 10, "AVL find LB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
278 ret = ucx_avl_find(tree,(intptr_t)7, dist_int, UCX_AVL_FIND_UPPER_BOUNDED);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
279 UCX_TEST_ASSERT(ret && *((int*)ret) == 4, "AVL find UB failed");
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
280
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
281 UCX_TEST_END
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
282
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
283 ucx_avl_free(tree);
2e74828c5e94 adds distance function and ucx_avl_find_node()
Mike Becker <universe@uap-core.de>
parents: 225
diff changeset
284 }
245
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
285
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
286 UCX_TEST(test_ucx_avl_traverse) {
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
287 UcxAVLTree *tree = ucx_avl_new(ucx_ptrcmp);
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
288
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
289 size_t len = 12;
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
290
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
291 int val[] = {10, 15, 3, 4, -30, 20, 14, -11, 12, -5, 1, 13};
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
292 int val_ordered[] = {-30, -11, -5, 1, 3, 4, 10, 12, 13, 14, 15, 20};
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
293
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
294 for (size_t i = 0 ; i < len ; i++) {
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
295 ucx_avl_put(tree, val[i], &(val[i]));
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
296 }
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
297
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
298 UCX_TEST_BEGIN
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
299
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
300 UcxAVLNode* node = ucx_avl_get_node(tree, (intptr_t) val_ordered[0]);
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
301 for (size_t i = 0 ; i < len ; i++) {
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
302 UCX_TEST_ASSERT(node->key == val_ordered[i], "AVL successor failed");
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
303 node = ucx_avl_succ(node);
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
304 }
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
305 UCX_TEST_ASSERT(!node, "AVL maximum incorrectly has a successor");
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
306
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
307 node = ucx_avl_get_node(tree, (intptr_t) val_ordered[len-1]);
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
308 for (size_t i = len ; i > 0 ; i--) {
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
309 UCX_TEST_ASSERT(node->key == val_ordered[i-1],"AVL predecessor failed");
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
310 node = ucx_avl_pred(node);
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
311 }
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
312 UCX_TEST_ASSERT(!node, "AVL minimum incorrectly has a predecessor");
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
313
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
314 UCX_TEST_END
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
315
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
316 ucx_avl_free(tree);
db732f8c083a adds AVL predecessor and successor functions
Mike Becker <universe@uap-core.de>
parents: 244
diff changeset
317 }

mercurial