1/* GtkTreeRBTree tests.
2 *
3 * Copyright (C) 2011, Red Hat, Inc.
4 * Authors: Benjamin Otte <otte@gnome.org>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20#include <locale.h>
21
22#include "../../gtk/gtktreerbtreeprivate.h"
23
24/* gtk_tree_rbtree_test */
25
26static guint
27get_total_count (GtkTreeRBNode *node)
28{
29 guint child_total = 0;
30
31 child_total += (guint) node->left->total_count;
32 child_total += (guint) node->right->total_count;
33
34 if (node->children)
35 child_total += (guint) node->children->root->total_count;
36
37 return child_total + 1;
38}
39
40static guint
41count_total (GtkTreeRBTree *tree,
42 GtkTreeRBNode *node)
43{
44 guint res;
45
46 if (gtk_tree_rbtree_is_nil (node))
47 return 0;
48
49 res =
50 count_total (tree, node: node->left) +
51 count_total (tree, node: node->right) +
52 (guint) 1 +
53 (node->children ? count_total (tree: node->children, node: node->children->root) : 0);
54
55 if (res != node->total_count)
56 g_print (format: "total count incorrect for node\n");
57
58 if (get_total_count (node) != node->total_count)
59 g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
60
61 return res;
62}
63
64static int
65_count_nodes (GtkTreeRBTree *tree,
66 GtkTreeRBNode *node)
67{
68 int res;
69 if (gtk_tree_rbtree_is_nil (node))
70 return 0;
71
72 g_assert_true (node->left);
73 g_assert_true (node->right);
74
75 res = (_count_nodes (tree, node: node->left) +
76 _count_nodes (tree, node: node->right) + 1);
77
78 if (res != node->count)
79 g_print (format: "Tree failed\n");
80 return res;
81}
82
83static void
84gtk_tree_rbtree_test_height (GtkTreeRBTree *tree,
85 GtkTreeRBNode *node)
86{
87 int computed_offset = 0;
88
89 /* This whole test is sort of a useless truism. */
90
91 if (!gtk_tree_rbtree_is_nil (node: node->left))
92 computed_offset += node->left->offset;
93
94 if (!gtk_tree_rbtree_is_nil (node: node->right))
95 computed_offset += node->right->offset;
96
97 if (node->children && !gtk_tree_rbtree_is_nil (node: node->children->root))
98 computed_offset += node->children->root->offset;
99
100 if (GTK_TREE_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
101 g_error ("node has broken offset");
102
103 if (!gtk_tree_rbtree_is_nil (node: node->left))
104 gtk_tree_rbtree_test_height (tree, node: node->left);
105
106 if (!gtk_tree_rbtree_is_nil (node: node->right))
107 gtk_tree_rbtree_test_height (tree, node: node->right);
108
109 if (node->children && !gtk_tree_rbtree_is_nil (node: node->children->root))
110 gtk_tree_rbtree_test_height (tree: node->children, node: node->children->root);
111}
112
113static void
114gtk_tree_rbtree_test_dirty (GtkTreeRBTree *tree,
115 GtkTreeRBNode *node,
116 int expected_dirtyness)
117{
118 g_assert_nonnull (node);
119
120 if (expected_dirtyness)
121 {
122 g_assert_true (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) ||
123 GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
124 GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
125 GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
126 (node->children && GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID)));
127 }
128 else
129 {
130 g_assert_true (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) &&
131 !GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID));
132 if (!gtk_tree_rbtree_is_nil (node: node->left))
133 g_assert_true (!GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
134 if (!gtk_tree_rbtree_is_nil (node: node->right))
135 g_assert_true (!GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
136 if (node->children != NULL)
137 g_assert_true (!GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
138 }
139
140 if (!gtk_tree_rbtree_is_nil (node: node->left))
141 gtk_tree_rbtree_test_dirty (tree, node: node->left, GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
142 if (!gtk_tree_rbtree_is_nil (node: node->right))
143 gtk_tree_rbtree_test_dirty (tree, node: node->right, GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
144 if (node->children != NULL && !gtk_tree_rbtree_is_nil (node: node->children->root))
145 gtk_tree_rbtree_test_dirty (tree: node->children, node: node->children->root, GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
146}
147
148static void gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree);
149
150static guint
151gtk_tree_rbtree_test_structure_helper (GtkTreeRBTree *tree,
152 GtkTreeRBNode *node)
153{
154 guint left_blacks, right_blacks;
155
156 g_assert_false (gtk_tree_rbtree_is_nil (node));
157
158 g_assert_nonnull (node->left);
159 g_assert_nonnull (node->right);
160 g_assert_nonnull (node->parent);
161
162 if (!gtk_tree_rbtree_is_nil (node: node->left))
163 {
164 g_assert_true (node->left->parent == node);
165 left_blacks = gtk_tree_rbtree_test_structure_helper (tree, node: node->left);
166 }
167 else
168 left_blacks = 0;
169
170 if (!gtk_tree_rbtree_is_nil (node: node->right))
171 {
172 g_assert_true (node->right->parent == node);
173 right_blacks = gtk_tree_rbtree_test_structure_helper (tree, node: node->right);
174 }
175 else
176 right_blacks = 0;
177
178 if (node->children != NULL)
179 {
180 g_assert_true (node->children->parent_tree == tree);
181 g_assert_true (node->children->parent_node == node);
182
183 gtk_tree_rbtree_test_structure (tree: node->children);
184 }
185
186 g_assert_true (left_blacks == right_blacks);
187
188 return left_blacks + (GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK ? 1 : 0);
189}
190
191static void
192gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree)
193{
194 g_assert_nonnull (tree->root);
195 if (gtk_tree_rbtree_is_nil (node: tree->root))
196 return;
197
198 g_assert_true (gtk_tree_rbtree_is_nil (tree->root->parent));
199 gtk_tree_rbtree_test_structure_helper (tree, node: tree->root);
200}
201
202static void
203gtk_tree_rbtree_test (GtkTreeRBTree *tree)
204{
205 GtkTreeRBTree *tmp_tree;
206
207 if (tree == NULL)
208 return;
209
210 /* Test the entire tree */
211 tmp_tree = tree;
212 while (tmp_tree->parent_tree)
213 tmp_tree = tmp_tree->parent_tree;
214
215 if (gtk_tree_rbtree_is_nil (node: tmp_tree->root))
216 return;
217
218 gtk_tree_rbtree_test_structure (tree: tmp_tree);
219
220 g_assert_true ((_count_nodes (tmp_tree, tmp_tree->root->left) +
221 _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
222
223 gtk_tree_rbtree_test_height (tree: tmp_tree, node: tmp_tree->root);
224 gtk_tree_rbtree_test_dirty (tree: tmp_tree, node: tmp_tree->root, GTK_TREE_RBNODE_FLAG_SET (tmp_tree->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
225 g_assert_true (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
226}
227
228/* gtk_rbtree_print() - unused, for debugging only */
229
230static void
231gtk_rbtree_print_node (GtkTreeRBTree *tree,
232 GtkTreeRBNode *node,
233 int depth)
234{
235 int i;
236 for (i = 0; i < depth; i++)
237 g_print (format: "\t");
238
239 g_print (format: "(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
240 node,
241 (GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK) ? "BLACK" : " RED ",
242 node->offset,
243 node->total_count,
244 (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ? 1 : 0,
245 (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) ? 1 : 0,
246 (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)) ? 1 : 0);
247 if (node->children != NULL)
248 {
249 g_print (format: "Looking at child.\n");
250 gtk_rbtree_print_node (tree: node->children, node: node->children->root, depth: depth + 1);
251 g_print (format: "Done looking at child.\n");
252 }
253 if (!gtk_tree_rbtree_is_nil (node: node->left))
254 {
255 gtk_rbtree_print_node (tree, node: node->left, depth: depth + 1);
256 }
257 if (!gtk_tree_rbtree_is_nil (node: node->right))
258 {
259 gtk_rbtree_print_node (tree, node: node->right, depth: depth + 1);
260 }
261}
262
263/* not static so the debugger finds it. */
264void gtk_rbtree_print (GtkTreeRBTree *tree);
265
266void
267gtk_rbtree_print (GtkTreeRBTree *tree)
268{
269 g_return_if_fail (tree != NULL);
270
271 if (gtk_tree_rbtree_is_nil (node: tree->root))
272 g_print (format: "Empty tree...\n");
273 else
274 gtk_rbtree_print_node (tree, node: tree->root, depth: 0);
275}
276
277/* actual tests */
278
279static guint
280append_elements (GtkTreeRBTree *tree,
281 guint depth,
282 guint elements_per_depth,
283 gboolean check,
284 guint height)
285{
286 GtkTreeRBNode *node;
287 guint i;
288
289 g_assert_cmpint (depth, >, 0);
290
291 node = NULL;
292 depth--;
293
294 for (i = 0; i < elements_per_depth; i++)
295 {
296 node = gtk_tree_rbtree_insert_after (tree, node, height: ++height, TRUE);
297 if (depth)
298 {
299 node->children = gtk_tree_rbtree_new ();
300 node->children->parent_tree = tree;
301 node->children->parent_node = node;
302 height = append_elements (tree: node->children, depth, elements_per_depth, check, height);
303 }
304 if (check)
305 gtk_tree_rbtree_test (tree);
306 }
307
308 return height;
309}
310
311static GtkTreeRBTree *
312create_rbtree (guint depth,
313 guint elements_per_depth,
314 gboolean check)
315{
316 GtkTreeRBTree *tree;
317
318 tree = gtk_tree_rbtree_new ();
319
320 append_elements (tree, depth, elements_per_depth, check, height: 0);
321
322 gtk_tree_rbtree_test (tree);
323
324 return tree;
325}
326
327static void
328test_create (void)
329{
330 GtkTreeRBTree *tree;
331
332 tree = create_rbtree (depth: 5, elements_per_depth: 5, TRUE);
333
334 gtk_tree_rbtree_free (tree);
335}
336
337static void
338test_insert_after (void)
339{
340 guint i;
341 GtkTreeRBTree *tree;
342 GtkTreeRBNode *node;
343
344 tree = gtk_tree_rbtree_new ();
345 node = NULL;
346
347 for (i = 1; i <= 100; i++)
348 {
349 node = gtk_tree_rbtree_insert_after (tree, node, height: i, TRUE);
350 gtk_tree_rbtree_test (tree);
351 g_assert_cmpint (tree->root->count, ==, i);
352 g_assert_cmpint (tree->root->total_count, ==, i);
353 g_assert_cmpint (tree->root->offset, ==, i * (i + 1) / 2);
354 }
355
356 gtk_tree_rbtree_free (tree);
357}
358
359static void
360test_insert_before (void)
361{
362 guint i;
363 GtkTreeRBTree *tree;
364 GtkTreeRBNode *node;
365
366 tree = gtk_tree_rbtree_new ();
367 node = NULL;
368
369 for (i = 1; i <= 100; i++)
370 {
371 node = gtk_tree_rbtree_insert_before (tree, node, height: i, TRUE);
372 gtk_tree_rbtree_test (tree);
373 g_assert_cmpint (tree->root->count, ==, i);
374 g_assert_cmpint (tree->root->total_count, ==, i);
375 g_assert_cmpint (tree->root->offset, ==, i * (i + 1) / 2);
376 }
377
378 gtk_tree_rbtree_free (tree);
379}
380
381static void
382test_remove_node (void)
383{
384 GtkTreeRBTree *tree;
385
386 tree = create_rbtree (depth: 3, elements_per_depth: 16, g_test_thorough ());
387
388 while (tree->root->count > 1)
389 {
390 GtkTreeRBTree *find_tree;
391 GtkTreeRBNode *find_node;
392 guint i;
393
394 i = g_test_rand_int_range (begin: 0, end: tree->root->total_count);
395 if (!gtk_tree_rbtree_find_index (tree, index: i, new_tree: &find_tree, new_node: &find_node))
396 {
397 /* We search an available index, so we mustn't fail. */
398 g_assert_not_reached ();
399 }
400
401 gtk_tree_rbtree_test (tree: find_tree);
402
403 if (find_tree->root->count == 1)
404 {
405 gtk_tree_rbtree_remove (tree: find_tree);
406 }
407 else
408 gtk_tree_rbtree_remove_node (tree: find_tree, node: find_node);
409 gtk_tree_rbtree_test (tree);
410 }
411
412 gtk_tree_rbtree_free (tree);
413}
414
415static void
416test_remove_root (void)
417{
418 GtkTreeRBTree *tree;
419 GtkTreeRBNode *node;
420
421 tree = gtk_tree_rbtree_new ();
422
423 node = gtk_tree_rbtree_insert_after (tree, NULL, height: 1, TRUE);
424 gtk_tree_rbtree_insert_after (tree, node, height: 2, TRUE);
425 gtk_tree_rbtree_insert_before (tree, node, height: 3, TRUE);
426
427 gtk_tree_rbtree_remove_node (tree, node);
428
429 gtk_tree_rbtree_free (tree);
430}
431
432static int *
433fisher_yates_shuffle (guint n_items)
434{
435 int *list;
436 guint i, j;
437
438 list = g_new (int, n_items);
439
440 for (i = 0; i < n_items; i++)
441 {
442 j = g_random_int_range (begin: 0, end: i + 1);
443 list[i] = list[j];
444 list[j] = i;
445 }
446
447 return list;
448}
449
450static GtkTreeRBTree *
451create_unsorted_tree (int *order,
452 guint n)
453{
454 GtkTreeRBTree *tree;
455 GtkTreeRBNode *node;
456 guint i;
457
458 tree = gtk_tree_rbtree_new ();
459 node = NULL;
460
461 for (i = 0; i < n; i++)
462 {
463 node = gtk_tree_rbtree_insert_after (tree, node, height: 0, TRUE);
464 }
465
466 for (i = 0; i < n; i++)
467 {
468 node = gtk_tree_rbtree_find_count (tree, count: order[i] + 1);
469 gtk_tree_rbtree_node_set_height (tree, node, height: i);
470 }
471
472 gtk_tree_rbtree_test (tree);
473
474 return tree;
475}
476
477static void
478test_reorder (void)
479{
480 guint n = g_test_perf () ? 1000000 : 100;
481 GtkTreeRBTree *tree;
482 GtkTreeRBNode *node;
483 int *reorder;
484 guint i;
485 double elapsed;
486
487 reorder = fisher_yates_shuffle (n_items: n);
488 tree = create_unsorted_tree (order: reorder, n);
489
490 g_test_timer_start ();
491
492 gtk_tree_rbtree_reorder (tree, new_order: reorder, length: n);
493
494 elapsed = g_test_timer_elapsed ();
495 if (g_test_perf ())
496 g_test_minimized_result (minimized_quantity: elapsed, format: "reordering rbtree with %u items: %gsec", n, elapsed);
497
498 gtk_tree_rbtree_test (tree);
499
500 for (node = gtk_tree_rbtree_first (tree), i = 0;
501 node != NULL;
502 node = gtk_tree_rbtree_next (tree, node), i++)
503 {
504 g_assert_cmpint (GTK_TREE_RBNODE_GET_HEIGHT (node), ==, i);
505 }
506 g_assert_cmpint (i, ==, n);
507
508 gtk_tree_rbtree_free (tree);
509
510 g_free (mem: reorder);
511}
512
513int
514main (int argc,
515 char *argv[])
516{
517 (g_test_init) (argc: &argc, argv: &argv, NULL);
518 setlocale (LC_ALL, locale: "C");
519
520 g_test_add_func (testpath: "/rbtree/create", test_func: test_create);
521 g_test_add_func (testpath: "/rbtree/insert_after", test_func: test_insert_after);
522 g_test_add_func (testpath: "/rbtree/insert_before", test_func: test_insert_before);
523 g_test_add_func (testpath: "/rbtree/remove_node", test_func: test_remove_node);
524 g_test_add_func (testpath: "/rbtree/remove_root", test_func: test_remove_root);
525 g_test_add_func (testpath: "/rbtree/reorder", test_func: test_reorder);
526
527 return g_test_run ();
528}
529

source code of gtk/testsuite/gtk/rbtree.c