diff options
Diffstat (limited to 'libraries/eina/src/tests/eina_test_rbtree.c')
-rw-r--r-- | libraries/eina/src/tests/eina_test_rbtree.c | 452 |
1 files changed, 452 insertions, 0 deletions
diff --git a/libraries/eina/src/tests/eina_test_rbtree.c b/libraries/eina/src/tests/eina_test_rbtree.c new file mode 100644 index 0000000..fabe2bf --- /dev/null +++ b/libraries/eina/src/tests/eina_test_rbtree.c | |||
@@ -0,0 +1,452 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2008 Cedric Bail | ||
3 | * | ||
4 | * This library is free software; you can redistribute it and/or | ||
5 | * modify it under the terms of the GNU Lesser General Public | ||
6 | * License as published by the Free Software Foundation; either | ||
7 | * version 2.1 of the License, or (at your option) any later version. | ||
8 | * | ||
9 | * This library is distributed in the hope that it will be useful, | ||
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
12 | * Lesser General Public License for more details. | ||
13 | * | ||
14 | * You should have received a copy of the GNU Lesser General Public | ||
15 | * License along with this library; | ||
16 | * if not, see <http://www.gnu.org/licenses/>. | ||
17 | */ | ||
18 | |||
19 | #ifdef HAVE_CONFIG_H | ||
20 | # include "config.h" | ||
21 | #endif | ||
22 | |||
23 | #include <stdlib.h> | ||
24 | #include <stdio.h> | ||
25 | #include <time.h> | ||
26 | |||
27 | #include "eina_suite.h" | ||
28 | #include "Eina.h" | ||
29 | |||
30 | static inline Eina_Bool | ||
31 | _eina_rbtree_is_red(Eina_Rbtree *tree) | ||
32 | { | ||
33 | return tree != NULL && tree->color == EINA_RBTREE_RED; | ||
34 | } | ||
35 | |||
36 | static int | ||
37 | _eina_rbtree_black_height(Eina_Rbtree *tree, Eina_Rbtree_Cmp_Node_Cb cmp) | ||
38 | { | ||
39 | Eina_Rbtree *left; | ||
40 | Eina_Rbtree *right; | ||
41 | Eina_Rbtree_Direction dir; | ||
42 | int left_height; | ||
43 | int right_height; | ||
44 | |||
45 | if (!tree) | ||
46 | return 1; | ||
47 | |||
48 | left = tree->son[EINA_RBTREE_LEFT]; | ||
49 | right = tree->son[EINA_RBTREE_RIGHT]; | ||
50 | |||
51 | /* Consecutive red links. */ | ||
52 | fail_if(_eina_rbtree_is_red(tree) && | ||
53 | (_eina_rbtree_is_red(left) || _eina_rbtree_is_red(right))); | ||
54 | |||
55 | left_height = _eina_rbtree_black_height(left, cmp); | ||
56 | right_height = _eina_rbtree_black_height(right, cmp); | ||
57 | |||
58 | /* Check binary search tree. */ | ||
59 | if (left) | ||
60 | { | ||
61 | dir = cmp(tree, left, NULL); | ||
62 | fail_if(dir != EINA_RBTREE_LEFT); | ||
63 | } | ||
64 | |||
65 | if (right) | ||
66 | { | ||
67 | dir = cmp(tree, right, NULL); | ||
68 | fail_if(dir != EINA_RBTREE_RIGHT); | ||
69 | } | ||
70 | |||
71 | /* Check black height */ | ||
72 | if (left_height != right_height) | ||
73 | fprintf(stderr, "%i != %i\n", left_height, right_height); | ||
74 | |||
75 | fail_if(left_height != right_height); | ||
76 | |||
77 | return _eina_rbtree_is_red(tree) ? left_height : left_height + 1; | ||
78 | } | ||
79 | |||
80 | typedef struct _Eina_Rbtree_Int Eina_Rbtree_Int; | ||
81 | struct _Eina_Rbtree_Int | ||
82 | { | ||
83 | Eina_Rbtree node; | ||
84 | int value; | ||
85 | }; | ||
86 | |||
87 | static Eina_Rbtree_Direction | ||
88 | eina_rbtree_int_cmp(const Eina_Rbtree_Int *left, | ||
89 | const Eina_Rbtree_Int *right, | ||
90 | __UNUSED__ void *data) | ||
91 | { | ||
92 | fail_if(!left); | ||
93 | fail_if(!right); | ||
94 | |||
95 | if (left->value < right->value) | ||
96 | return EINA_RBTREE_LEFT; | ||
97 | |||
98 | return EINA_RBTREE_RIGHT; | ||
99 | } | ||
100 | |||
101 | static int | ||
102 | eina_rbtree_int_key(const Eina_Rbtree_Int *node, | ||
103 | const int *key, | ||
104 | __UNUSED__ int length, | ||
105 | __UNUSED__ void *data) | ||
106 | { | ||
107 | fail_if(!node); | ||
108 | return node->value - *key; | ||
109 | } | ||
110 | |||
111 | static Eina_Rbtree_Int * | ||
112 | _eina_rbtree_int_new(int value) | ||
113 | { | ||
114 | Eina_Rbtree_Int *it; | ||
115 | |||
116 | it = malloc(sizeof (Eina_Rbtree_Int)); | ||
117 | fail_if(!it); | ||
118 | |||
119 | it->value = value; | ||
120 | |||
121 | return it; | ||
122 | } | ||
123 | |||
124 | START_TEST(eina_rbtree_insertion) | ||
125 | { | ||
126 | Eina_Rbtree_Int *root = NULL; | ||
127 | Eina_Rbtree_Int *item; | ||
128 | int i; | ||
129 | |||
130 | srand(time(NULL)); | ||
131 | |||
132 | for (i = 0; i < 500; ++i) | ||
133 | { | ||
134 | item = _eina_rbtree_int_new(rand()); | ||
135 | root = (Eina_Rbtree_Int *)eina_rbtree_inline_insert( | ||
136 | &root->node, | ||
137 | &item->node, | ||
138 | EINA_RBTREE_CMP_NODE_CB( | ||
139 | eina_rbtree_int_cmp), | ||
140 | NULL); | ||
141 | } | ||
142 | |||
143 | _eina_rbtree_black_height(&root->node, | ||
144 | EINA_RBTREE_CMP_NODE_CB( | ||
145 | eina_rbtree_int_cmp)); | ||
146 | } | ||
147 | END_TEST | ||
148 | |||
149 | START_TEST(eina_rbtree_lookup) | ||
150 | { | ||
151 | Eina_Rbtree_Int *root = NULL; | ||
152 | Eina_Rbtree_Int *item; | ||
153 | int list[] = { 50, 100, 10, 43, 23 }; | ||
154 | unsigned int i; | ||
155 | |||
156 | for (i = 0; i < sizeof (list) / sizeof (int); ++i) | ||
157 | { | ||
158 | item = _eina_rbtree_int_new(list[i]); | ||
159 | root = (Eina_Rbtree_Int *)eina_rbtree_inline_insert( | ||
160 | &root->node, | ||
161 | &item->node, | ||
162 | EINA_RBTREE_CMP_NODE_CB( | ||
163 | eina_rbtree_int_cmp), | ||
164 | NULL); | ||
165 | } | ||
166 | |||
167 | item = (Eina_Rbtree_Int *)eina_rbtree_inline_lookup(&root->node, | ||
168 | &list[0], | ||
169 | sizeof(int), | ||
170 | EINA_RBTREE_CMP_KEY_CB( | ||
171 | eina_rbtree_int_key), | ||
172 | NULL); | ||
173 | fail_if(!item); | ||
174 | |||
175 | i = 42; | ||
176 | item = | ||
177 | (Eina_Rbtree_Int *)eina_rbtree_inline_lookup(&root->node, | ||
178 | &i, | ||
179 | sizeof(int), | ||
180 | EINA_RBTREE_CMP_KEY_CB( | ||
181 | eina_rbtree_int_key), | ||
182 | NULL); | ||
183 | fail_if(item); | ||
184 | } | ||
185 | END_TEST | ||
186 | |||
187 | START_TEST(eina_rbtree_remove) | ||
188 | { | ||
189 | Eina_Rbtree_Int *root = NULL; | ||
190 | Eina_Rbtree_Int *item; | ||
191 | Eina_Array *ea; | ||
192 | Eina_Array_Iterator it; | ||
193 | unsigned int i; | ||
194 | |||
195 | eina_init(); | ||
196 | |||
197 | ea = eina_array_new(11); | ||
198 | fail_if(!ea); | ||
199 | |||
200 | srand(time(NULL)); | ||
201 | |||
202 | for (i = 0; i < 500; ++i) | ||
203 | { | ||
204 | item = _eina_rbtree_int_new(rand()); | ||
205 | eina_array_push(ea, item); | ||
206 | root = (Eina_Rbtree_Int *)eina_rbtree_inline_insert( | ||
207 | &root->node, | ||
208 | &item->node, | ||
209 | EINA_RBTREE_CMP_NODE_CB( | ||
210 | eina_rbtree_int_cmp), | ||
211 | NULL); | ||
212 | } | ||
213 | |||
214 | _eina_rbtree_black_height(&root->node, | ||
215 | EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
216 | |||
217 | EINA_ARRAY_ITER_NEXT(ea, i, item, it) | ||
218 | { | ||
219 | root = (Eina_Rbtree_Int *)eina_rbtree_inline_remove( | ||
220 | &root->node, | ||
221 | &item->node, | ||
222 | EINA_RBTREE_CMP_NODE_CB( | ||
223 | eina_rbtree_int_cmp), | ||
224 | NULL); | ||
225 | _eina_rbtree_black_height(&root->node, | ||
226 | EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
227 | } | ||
228 | |||
229 | fail_if(root != NULL); | ||
230 | |||
231 | eina_shutdown(); | ||
232 | } | ||
233 | END_TEST | ||
234 | |||
235 | START_TEST(eina_rbtree_simple_remove) | ||
236 | { | ||
237 | Eina_Rbtree *root = NULL; | ||
238 | Eina_Rbtree *lookup; | ||
239 | int i; | ||
240 | |||
241 | root = | ||
242 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
243 | 10), | ||
244 | EINA_RBTREE_CMP_NODE_CB( | ||
245 | eina_rbtree_int_cmp), NULL); | ||
246 | root = | ||
247 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
248 | 42), | ||
249 | EINA_RBTREE_CMP_NODE_CB( | ||
250 | eina_rbtree_int_cmp), NULL); | ||
251 | root = | ||
252 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
253 | 69), | ||
254 | EINA_RBTREE_CMP_NODE_CB( | ||
255 | eina_rbtree_int_cmp), NULL); | ||
256 | root = | ||
257 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
258 | 1337), | ||
259 | EINA_RBTREE_CMP_NODE_CB( | ||
260 | eina_rbtree_int_cmp), NULL); | ||
261 | _eina_rbtree_black_height(root, | ||
262 | EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
263 | |||
264 | fail_if(root == NULL); | ||
265 | |||
266 | i = 69; | ||
267 | lookup = eina_rbtree_inline_lookup(root, | ||
268 | &i, | ||
269 | sizeof (int), | ||
270 | EINA_RBTREE_CMP_KEY_CB( | ||
271 | eina_rbtree_int_key), | ||
272 | NULL); | ||
273 | _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
274 | fail_if(lookup == NULL); | ||
275 | |||
276 | root = | ||
277 | eina_rbtree_inline_remove(root, lookup, EINA_RBTREE_CMP_NODE_CB( | ||
278 | eina_rbtree_int_cmp), NULL); | ||
279 | |||
280 | _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
281 | } | ||
282 | END_TEST | ||
283 | |||
284 | START_TEST(eina_rbtree_simple_remove2) | ||
285 | { | ||
286 | Eina_Rbtree *root = NULL; | ||
287 | Eina_Rbtree *lookup; | ||
288 | int i; | ||
289 | |||
290 | root = | ||
291 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
292 | 10), | ||
293 | EINA_RBTREE_CMP_NODE_CB( | ||
294 | eina_rbtree_int_cmp), NULL); | ||
295 | root = | ||
296 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
297 | 42), | ||
298 | EINA_RBTREE_CMP_NODE_CB( | ||
299 | eina_rbtree_int_cmp), NULL); | ||
300 | root = | ||
301 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
302 | 69), | ||
303 | EINA_RBTREE_CMP_NODE_CB( | ||
304 | eina_rbtree_int_cmp), NULL); | ||
305 | root = | ||
306 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
307 | 1337), | ||
308 | EINA_RBTREE_CMP_NODE_CB( | ||
309 | eina_rbtree_int_cmp), NULL); | ||
310 | root = | ||
311 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
312 | 77), | ||
313 | EINA_RBTREE_CMP_NODE_CB( | ||
314 | eina_rbtree_int_cmp), NULL); | ||
315 | root = | ||
316 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
317 | 75), | ||
318 | EINA_RBTREE_CMP_NODE_CB( | ||
319 | eina_rbtree_int_cmp), NULL); | ||
320 | root = | ||
321 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
322 | 81), | ||
323 | EINA_RBTREE_CMP_NODE_CB( | ||
324 | eina_rbtree_int_cmp), NULL); | ||
325 | _eina_rbtree_black_height(root, | ||
326 | EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
327 | |||
328 | fail_if(root == NULL); | ||
329 | |||
330 | i = 69; | ||
331 | lookup = eina_rbtree_inline_lookup(root, | ||
332 | &i, | ||
333 | sizeof (int), | ||
334 | EINA_RBTREE_CMP_KEY_CB( | ||
335 | eina_rbtree_int_key), | ||
336 | NULL); | ||
337 | _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
338 | fail_if(lookup == NULL); | ||
339 | |||
340 | root = | ||
341 | eina_rbtree_inline_remove(root, lookup, EINA_RBTREE_CMP_NODE_CB( | ||
342 | eina_rbtree_int_cmp), NULL); | ||
343 | |||
344 | _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
345 | } | ||
346 | END_TEST | ||
347 | |||
348 | START_TEST(eina_rbtree_simple_remove3) | ||
349 | { | ||
350 | Eina_Rbtree *root = NULL; | ||
351 | Eina_Rbtree *lookup; | ||
352 | int i; | ||
353 | |||
354 | root = | ||
355 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
356 | 1113497590), | ||
357 | EINA_RBTREE_CMP_NODE_CB( | ||
358 | eina_rbtree_int_cmp), NULL); | ||
359 | root = | ||
360 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
361 | 499187507), | ||
362 | EINA_RBTREE_CMP_NODE_CB( | ||
363 | eina_rbtree_int_cmp), NULL); | ||
364 | root = | ||
365 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
366 | 1693860487), | ||
367 | EINA_RBTREE_CMP_NODE_CB( | ||
368 | eina_rbtree_int_cmp), NULL); | ||
369 | root = | ||
370 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
371 | 26211080), | ||
372 | EINA_RBTREE_CMP_NODE_CB( | ||
373 | eina_rbtree_int_cmp), NULL); | ||
374 | root = | ||
375 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
376 | 797272577), | ||
377 | EINA_RBTREE_CMP_NODE_CB( | ||
378 | eina_rbtree_int_cmp), NULL); | ||
379 | root = | ||
380 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
381 | 1252184882), | ||
382 | EINA_RBTREE_CMP_NODE_CB( | ||
383 | eina_rbtree_int_cmp), NULL); | ||
384 | root = | ||
385 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
386 | 1448158229), | ||
387 | EINA_RBTREE_CMP_NODE_CB( | ||
388 | eina_rbtree_int_cmp), NULL); | ||
389 | root = | ||
390 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
391 | 1821884856), | ||
392 | EINA_RBTREE_CMP_NODE_CB( | ||
393 | eina_rbtree_int_cmp), NULL); | ||
394 | root = | ||
395 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
396 | 346086006), | ||
397 | EINA_RBTREE_CMP_NODE_CB( | ||
398 | eina_rbtree_int_cmp), NULL); | ||
399 | root = | ||
400 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
401 | 936357333), | ||
402 | EINA_RBTREE_CMP_NODE_CB( | ||
403 | eina_rbtree_int_cmp), NULL); | ||
404 | root = | ||
405 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
406 | 1462073936), | ||
407 | EINA_RBTREE_CMP_NODE_CB( | ||
408 | eina_rbtree_int_cmp), NULL); | ||
409 | root = | ||
410 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
411 | 1717320055), | ||
412 | EINA_RBTREE_CMP_NODE_CB( | ||
413 | eina_rbtree_int_cmp), NULL); | ||
414 | root = | ||
415 | eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new( | ||
416 | 1845524606), | ||
417 | EINA_RBTREE_CMP_NODE_CB( | ||
418 | eina_rbtree_int_cmp), NULL); | ||
419 | _eina_rbtree_black_height(root, | ||
420 | EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
421 | |||
422 | fail_if(root == NULL); | ||
423 | |||
424 | i = 1113497590; | ||
425 | lookup = eina_rbtree_inline_lookup(root, | ||
426 | &i, | ||
427 | sizeof (int), | ||
428 | EINA_RBTREE_CMP_KEY_CB( | ||
429 | eina_rbtree_int_key), | ||
430 | NULL); | ||
431 | _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
432 | fail_if(lookup == NULL); | ||
433 | |||
434 | root = | ||
435 | eina_rbtree_inline_remove(root, lookup, EINA_RBTREE_CMP_NODE_CB( | ||
436 | eina_rbtree_int_cmp), NULL); | ||
437 | |||
438 | _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp)); | ||
439 | } | ||
440 | END_TEST | ||
441 | |||
442 | void | ||
443 | eina_test_rbtree(TCase *tc) | ||
444 | { | ||
445 | tcase_add_test(tc, eina_rbtree_insertion); | ||
446 | tcase_add_test(tc, eina_rbtree_lookup); | ||
447 | tcase_add_test(tc, eina_rbtree_remove); | ||
448 | tcase_add_test(tc, eina_rbtree_simple_remove); | ||
449 | tcase_add_test(tc, eina_rbtree_simple_remove2); | ||
450 | tcase_add_test(tc, eina_rbtree_simple_remove3); | ||
451 | } | ||
452 | |||