Sat, 15 Jul 2017 22:36:29 +0200
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 | } |