aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/tests/eina_test_rbtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/tests/eina_test_rbtree.c')
-rw-r--r--libraries/eina/src/tests/eina_test_rbtree.c452
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
30static inline Eina_Bool
31_eina_rbtree_is_red(Eina_Rbtree *tree)
32{
33 return tree != NULL && tree->color == EINA_RBTREE_RED;
34}
35
36static 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
80typedef struct _Eina_Rbtree_Int Eina_Rbtree_Int;
81struct _Eina_Rbtree_Int
82{
83 Eina_Rbtree node;
84 int value;
85};
86
87static Eina_Rbtree_Direction
88eina_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
101static int
102eina_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
111static 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
124START_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}
147END_TEST
148
149START_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}
185END_TEST
186
187START_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}
233END_TEST
234
235START_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}
282END_TEST
283
284START_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}
346END_TEST
347
348START_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}
440END_TEST
441
442void
443eina_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
generated by cgit v1.1 at 2024-10-30 02:36:18 +0000