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 | |
26 | static guint |
27 | get_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 | |
40 | static guint |
41 | count_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 | |
64 | static 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 | |
83 | static void |
84 | gtk_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 | |
113 | static void |
114 | gtk_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 | |
148 | static void gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree); |
149 | |
150 | static guint |
151 | gtk_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 | |
191 | static void |
192 | gtk_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 | |
202 | static void |
203 | gtk_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 | |
230 | static void |
231 | gtk_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. */ |
264 | void gtk_rbtree_print (GtkTreeRBTree *tree); |
265 | |
266 | void |
267 | gtk_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 | |
279 | static guint |
280 | append_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 | |
311 | static GtkTreeRBTree * |
312 | create_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 | |
327 | static void |
328 | test_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 | |
337 | static void |
338 | test_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 | |
359 | static void |
360 | test_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 | |
381 | static void |
382 | test_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 | |
415 | static void |
416 | test_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 | |
432 | static int * |
433 | fisher_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 | |
450 | static GtkTreeRBTree * |
451 | create_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 | |
477 | static void |
478 | test_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 | |
513 | int |
514 | main (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 | |