Mercurial > hg > ucx / file comparison

comparison: test/avl_tests.c

test/avl_tests.c

changeset 390
d345541018fa
parent 351
87c22ec6a0fd
equal deleted inserted replaced
389:92e482410453 390:d345541018fa
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 }

Mercurial Repository: ucx

mercurial