Pileus Git - ~andy/gtk/blob - gtk/tests/rbtree.c

   1 /* GtkRBTree 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 "../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\n");
 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
 510 int
 511 main (int argc, char *argv[])
 512 {
 513   g_test_init (&argc, &argv, NULL);
 514   setlocale (LC_ALL, "C");
 515   g_test_bug_base ("http://bugzilla.gnome.org/show_bug.cgi?id=%s");
 516
 517   g_test_add_func ("/rbtree/create", test_create);
 518   g_test_add_func ("/rbtree/insert_after", test_insert_after);
 519   g_test_add_func ("/rbtree/insert_before", test_insert_before);
 520   g_test_add_func ("/rbtree/remove_node", test_remove_node);
 521   g_test_add_func ("/rbtree/remove_root", test_remove_root);
 522   g_test_add_func ("/rbtree/reorder", test_reorder);
 523
 524   return g_test_run ();
 525 }