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