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