Debian Codegraph @

testsuite/gtk/rbtree.c

raw
1 /* GtkRBTree tests.
2 *
3 * Copyright (C) 2011, Red Hat, Inc.
4 * Authors: Benjamin Otte <[email protected]>
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/gtkrbtree.h"
23
24 /* _gtk_rbtree_test */
25
26 static guint
27 get_total_count (GtkRBNode *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 (GtkRBTree *tree,
42 GtkRBNode *node)
43 {
44 guint res;
45
46 if (_gtk_rbtree_is_nil (node))
47 return 0;
48
49 res =
50 count_total (tree, node->left) +
51 count_total (tree, node->right) +
52 (guint)1 +
53 (node->children ? count_total (node->children, node->children->root) : 0);
54
55 if (res != node->total_count)
56 g_print ("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 gint
65 _count_nodes (GtkRBTree *tree,
66 GtkRBNode *node)
67 {
68 gint res;
69 if (_gtk_rbtree_is_nil (node))
70 return 0;
71
72 g_assert (node->left);
73 g_assert (node->right);
74
75 res = (_count_nodes (tree, node->left) +
76 _count_nodes (tree, node->right) + 1);
77
78 if (res != node->count)
79 g_print ("Tree failed\n");
80 return res;
81 }
82
83 static void
84 _gtk_rbtree_test_height (GtkRBTree *tree,
85 GtkRBNode *node)
86 {
87 gint computed_offset = 0;
88
89 /* This whole test is sort of a useless truism. */
90
91 if (!_gtk_rbtree_is_nil (node->left))
92 computed_offset += node->left->offset;
93
94 if (!_gtk_rbtree_is_nil (node->right))
95 computed_offset += node->right->offset;
96
97 if (node->children && !_gtk_rbtree_is_nil (node->children->root))
98 computed_offset += node->children->root->offset;
99
100 if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
101 g_error ("node has broken offset");
102
103 if (!_gtk_rbtree_is_nil (node->left))
104 _gtk_rbtree_test_height (tree, node->left);
105
106 if (!_gtk_rbtree_is_nil (node->right))
107 _gtk_rbtree_test_height (tree, node->right);
108
109 if (node->children && !_gtk_rbtree_is_nil (node->children->root))
110 _gtk_rbtree_test_height (node->children, node->children->root);
111 }
112
113 static void
114 _gtk_rbtree_test_dirty (GtkRBTree *tree,
115 GtkRBNode *node,
116 gint expected_dirtyness)
117 {
118
119 if (expected_dirtyness)
120 {
121 g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
122 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
123 GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
124 GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
125 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
126 }
127 else
128 {
129 g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
130 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
131 if (!_gtk_rbtree_is_nil (node->left))
132 g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
133 if (!_gtk_rbtree_is_nil (node->right))
134 g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
135 if (node->children != NULL)
136 g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
137 }
138
139 if (!_gtk_rbtree_is_nil (node->left))
140 _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
141 if (!_gtk_rbtree_is_nil (node->right))
142 _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
143 if (node->children != NULL && !_gtk_rbtree_is_nil (node->children->root))
144 _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
145 }
146
147 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
148
149 static guint
150 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
151 GtkRBNode *node)
152 {
153 guint left_blacks, right_blacks;
154
155 g_assert (!_gtk_rbtree_is_nil (node));
156
157 g_assert (node->left != NULL);
158 g_assert (node->right != NULL);
159 g_assert (node->parent != NULL);
160
161 if (!_gtk_rbtree_is_nil (node->left))
162 {
163 g_assert (node->left->parent == node);
164 left_blacks = _gtk_rbtree_test_structure_helper (tree, node->left);
165 }
166 else
167 left_blacks = 0;
168
169 if (!_gtk_rbtree_is_nil (node->right))
170 {
171 g_assert (node->right->parent == node);
172 right_blacks = _gtk_rbtree_test_structure_helper (tree, node->right);
173 }
174 else
175 right_blacks = 0;
176
177 if (node->children != NULL)
178 {
179 g_assert (node->children->parent_tree == tree);
180 g_assert (node->children->parent_node == node);
181
182 _gtk_rbtree_test_structure (node->children);
183 }
184
185 g_assert (left_blacks == right_blacks);
186
187 return left_blacks + (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK ? 1 : 0);
188 }
189
190 static void
191 _gtk_rbtree_test_structure (GtkRBTree *tree)
192 {
193 g_assert (tree->root);
194 if (_gtk_rbtree_is_nil (tree->root))
195 return;
196
197 g_assert (_gtk_rbtree_is_nil (tree->root->parent));
198 _gtk_rbtree_test_structure_helper (tree, tree->root);
199 }
200
201 static void
202 _gtk_rbtree_test (GtkRBTree *tree)
203 {
204 GtkRBTree *tmp_tree;
205
206 if (tree == NULL)
207 return;
208
209 /* Test the entire tree */
210 tmp_tree = tree;
211 while (tmp_tree->parent_tree)
212 tmp_tree = tmp_tree->parent_tree;
213
214 if (_gtk_rbtree_is_nil (tmp_tree->root))
215 return;
216
217 _gtk_rbtree_test_structure (tmp_tree);
218
219 g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
220 _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
221
222 _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
223 _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
224 g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
225 }
226
227 /* gtk_rbtree_print() - unused, for debugging only */
228
229 static void
230 gtk_rbtree_print_node (GtkRBTree *tree,
231 GtkRBNode *node,
232 gint depth)
233 {
234 gint i;
235 for (i = 0; i < depth; i++)
236 g_print ("\t");
237
238 g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
239 node,
240 (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
241 node->offset,
242 node->total_count,
243 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
244 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
245 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
246 if (node->children != NULL)
247 {
248 g_print ("Looking at child.\n");
249 gtk_rbtree_print_node (node->children, node->children->root, depth + 1);
250 g_print ("Done looking at child.\n");
251 }
252 if (!_gtk_rbtree_is_nil (node->left))
253 {
254 gtk_rbtree_print_node (tree, node->left, depth+1);
255 }
256 if (!_gtk_rbtree_is_nil (node->right))
257 {
258 gtk_rbtree_print_node (tree, node->right, depth+1);
259 }
260 }
261
262 /* not static so the debugger finds it. */
263 void gtk_rbtree_print (GtkRBTree *tree);
264
265 void
266 gtk_rbtree_print (GtkRBTree *tree)
267 {
268 g_return_if_fail (tree != NULL);
269
270 if (_gtk_rbtree_is_nil (tree->root))
271 g_print ("Empty tree...\n");
272 else
273 gtk_rbtree_print_node (tree, tree->root, 0);
274 }
275
276 /* actual tests */
277
278 static guint
279 append_elements (GtkRBTree *tree,
280 guint depth,
281 guint elements_per_depth,
282 gboolean check,
283 guint height)
284 {
285 GtkRBNode *node;
286 guint i;
287
288 g_assert (depth > 0);
289
290 node = NULL;
291 depth--;
292
293 for (i = 0; i < elements_per_depth; i++)
294 {
295 node = _gtk_rbtree_insert_after (tree, node, ++height, TRUE);
296 if (depth)
297 {
298 node->children = _gtk_rbtree_new ();
299 node->children->parent_tree = tree;
300 node->children->parent_node = node;
301 height = append_elements (node->children, depth, elements_per_depth, check, height);
302 }
303 if (check)
304 _gtk_rbtree_test (tree);
305 }
306
307 return height;
308 }
309
310 static GtkRBTree *
311 create_rbtree (guint depth,
312 guint elements_per_depth,
313 gboolean check)
314 {
315 GtkRBTree *tree;
316
317 tree = _gtk_rbtree_new ();
318
319 append_elements (tree, depth, elements_per_depth, check, 0);
320
321 _gtk_rbtree_test (tree);
322
323 return tree;
324 }
325
326 static void
327 test_create (void)
328 {
329 GtkRBTree *tree;
330
331 tree = create_rbtree (5, 5, TRUE);
332
333 _gtk_rbtree_free (tree);
334 }
335
336 static void
337 test_insert_after (void)
338 {
339 guint i;
340 GtkRBTree *tree;
341 GtkRBNode *node;
342
343 tree = _gtk_rbtree_new ();
344 node = NULL;
345
346 for (i = 1; i <= 100; i++)
347 {
348 node = _gtk_rbtree_insert_after (tree, node, i, TRUE);
349 _gtk_rbtree_test (tree);
350 g_assert (tree->root->count == i);
351 g_assert (tree->root->total_count == i);
352 g_assert (tree->root->offset == i * (i + 1) / 2);
353 }
354
355 _gtk_rbtree_free (tree);
356 }
357
358 static void
359 test_insert_before (void)
360 {
361 guint i;
362 GtkRBTree *tree;
363 GtkRBNode *node;
364
365 tree = _gtk_rbtree_new ();
366 node = NULL;
367
368 for (i = 1; i <= 100; i++)
369 {
370 node = _gtk_rbtree_insert_before (tree, node, i, TRUE);
371 _gtk_rbtree_test (tree);
372 g_assert (tree->root->count == i);
373 g_assert (tree->root->total_count == i);
374 g_assert (tree->root->offset == i * (i + 1) / 2);
375 }
376
377 _gtk_rbtree_free (tree);
378 }
379
380 static void
381 test_remove_node (void)
382 {
383 GtkRBTree *tree;
384
385 tree = create_rbtree (3, 16, g_test_thorough ());
386
387 while (tree->root->count > 1)
388 {
389 GtkRBTree *find_tree;
390 GtkRBNode *find_node;
391 guint i;
392
393 i = g_test_rand_int_range (0, tree->root->total_count);
394 if (!_gtk_rbtree_find_index (tree, i, &find_tree, &find_node))
395 {
396 /* We search an available index, so we mustn't fail. */
397 g_assert_not_reached ();
398 }
399
400 _gtk_rbtree_test (find_tree);
401
402 if (find_tree->root->count == 1)
403 {
404 _gtk_rbtree_remove (find_tree);
405 }
406 else
407 _gtk_rbtree_remove_node (find_tree, find_node);
408 _gtk_rbtree_test (tree);
409 }
410
411 _gtk_rbtree_free (tree);
412 }
413
414 static void
415 test_remove_root (void)
416 {
417 GtkRBTree *tree;
418 GtkRBNode *node;
419
420 tree = _gtk_rbtree_new ();
421
422 node = _gtk_rbtree_insert_after (tree, NULL, 1, TRUE);
423 _gtk_rbtree_insert_after (tree, node, 2, TRUE);
424 _gtk_rbtree_insert_before (tree, node, 3, TRUE);
425
426 _gtk_rbtree_remove_node (tree, node);
427
428 _gtk_rbtree_free (tree);
429 }
430
431 static gint *
432 fisher_yates_shuffle (guint n_items)
433 {
434 gint *list;
435 guint i, j;
436
437 list = g_new (gint, n_items);
438
439 for (i = 0; i < n_items; i++)
440 {
441 j = g_random_int_range (0, i + 1);
442 list[i] = list[j];
443 list[j] = i;
444 }
445
446 return list;
447 }
448
449 static GtkRBTree *
450 create_unsorted_tree (gint *order,
451 guint n)
452 {
453 GtkRBTree *tree;
454 GtkRBNode *node;
455 guint i;
456
457 tree = _gtk_rbtree_new ();
458 node = NULL;
459
460 for (i = 0; i < n; i++)
461 {
462 node = _gtk_rbtree_insert_after (tree, node, 0, TRUE);
463 }
464
465 for (i = 0; i < n; i++)
466 {
467 node = _gtk_rbtree_find_count (tree, order[i] + 1);
468 _gtk_rbtree_node_set_height (tree, node, i);
469 }
470
471 _gtk_rbtree_test (tree);
472
473 return tree;
474 }
475
476 static void
477 test_reorder (void)
478 {
479 guint n = g_test_perf () ? 1000000 : 100;
480 GtkRBTree *tree;
481 GtkRBNode *node;
482 gint *reorder;
483 guint i;
484 double elapsed;
485
486 reorder = fisher_yates_shuffle (n);
487 tree = create_unsorted_tree (reorder, n);
488
489 g_test_timer_start ();
490
491 _gtk_rbtree_reorder (tree, reorder, n);
492
493 elapsed = g_test_timer_elapsed ();
494 if (g_test_perf ())
495 g_test_minimized_result (elapsed, "reordering rbtree with %u items: %gsec", n, elapsed);
496
497 _gtk_rbtree_test (tree);
498
499 for (node = _gtk_rbtree_first (tree), i = 0;
500 node != NULL;
501 node = _gtk_rbtree_next (tree, node), i++)
502 {
503 g_assert (GTK_RBNODE_GET_HEIGHT (node) == i);
504 }
505 g_assert (i == n);
506
507 _gtk_rbtree_free (tree);
508
509 g_free (reorder);
510 }
511
512 int
513 main (int argc, char *argv[])
514 {
515 g_test_init (&argc, &argv, NULL);
516 setlocale (LC_ALL, "C");
517 g_test_bug_base ("http://bugzilla.gnome.org/show_bug.cgi?id=%s");
518
519 g_test_add_func ("/rbtree/create", test_create);
520 g_test_add_func ("/rbtree/insert_after", test_insert_after);
521 g_test_add_func ("/rbtree/insert_before", test_insert_before);
522 g_test_add_func ("/rbtree/remove_node", test_remove_node);
523 g_test_add_func ("/rbtree/remove_root", test_remove_root);
524 g_test_add_func ("/rbtree/reorder", test_reorder);
525
526 return g_test_run ();
527 }