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_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 126                 (!_gtk_rbtree_is_nil (node->right) && 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                  guint      height)
 285 {
 286   GtkRBNode *node;
 287   guint i;
 288
 289   g_assert (depth > 0);
 290
 291   node = NULL;
 292   depth--;
 293
 294   for (i = 0; i < elements_per_depth; i++)
 295     {
 296       node = _gtk_rbtree_insert_after (tree, node, ++height, TRUE);
 297       if (depth)
 298         {
 299           node->children = _gtk_rbtree_new ();
 300           node->children->parent_tree = tree;
 301           node->children->parent_node = node;
 302           height = append_elements (node->children, depth, elements_per_depth, height);
 303         }
 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 {
 314   GtkRBTree *tree;
 315
 316   tree = _gtk_rbtree_new ();
 317
 318   append_elements (tree, depth, elements_per_depth, 0);
 319
 320   return tree;
 321 }
 322
 323 static void
 324 test_create (void)
 325 {
 326   GtkRBTree *tree;
 327
 328   tree = create_rbtree (5, 5);
 329
 330   _gtk_rbtree_free (tree);
 331 }
 332
 333 static void
 334 test_insert_after (void)
 335 {
 336   guint i;
 337   GtkRBTree *tree;
 338   GtkRBNode *node;
 339
 340   tree = _gtk_rbtree_new ();
 341   node = NULL;
 342
 343   for (i = 1; i <= 100; i++)
 344     {
 345       node = _gtk_rbtree_insert_after (tree, node, i, TRUE);
 346       _gtk_rbtree_test (tree);
 347       g_assert (tree->root->count == i);
 348       g_assert (tree->root->total_count == i);
 349       g_assert (tree->root->offset == i * (i + 1) / 2);
 350     }
 351
 352   _gtk_rbtree_free (tree);
 353 }
 354
 355 static void
 356 test_insert_before (void)
 357 {
 358   guint i;
 359   GtkRBTree *tree;
 360   GtkRBNode *node;
 361
 362   tree = _gtk_rbtree_new ();
 363   node = NULL;
 364
 365   for (i = 1; i <= 100; i++)
 366     {
 367       node = _gtk_rbtree_insert_before (tree, node, i, TRUE);
 368       _gtk_rbtree_test (tree);
 369       g_assert (tree->root->count == i);
 370       g_assert (tree->root->total_count == i);
 371       g_assert (tree->root->offset == i * (i + 1) / 2);
 372     }
 373
 374   _gtk_rbtree_free (tree);
 375 }
 376
 377 static void
 378 test_remove_node (void)
 379 {
 380   GtkRBTree *tree;
 381
 382   tree = create_rbtree (3, 16);
 383
 384   while (tree->root->count > 1)
 385     {
 386       GtkRBTree *find_tree;
 387       GtkRBNode *find_node;
 388       guint i;
 389
 390       i = g_test_rand_int_range (0, tree->root->total_count);
 391       if (!_gtk_rbtree_find_index (tree, i, &find_tree, &find_node))
 392         {
 393           /* We search an available index, so we mustn't fail. */
 394           g_assert_not_reached ();
 395         }
 396
 397       _gtk_rbtree_test (find_tree);
 398
 399       if (find_tree->root->count == 1)
 400         {
 401           _gtk_rbtree_remove (find_tree);
 402         }
 403       else
 404         _gtk_rbtree_remove_node (find_tree, find_node);
 405       _gtk_rbtree_test (tree);
 406     }
 407
 408   _gtk_rbtree_free (tree);
 409 }
 410
 411 static void
 412 test_remove_root (void)
 413 {
 414   GtkRBTree *tree;
 415   GtkRBNode *node;
 416
 417   tree = _gtk_rbtree_new ();
 418
 419   node = _gtk_rbtree_insert_after (tree, NULL, 1, TRUE);
 420   _gtk_rbtree_insert_after (tree, node, 2, TRUE);
 421   _gtk_rbtree_insert_before (tree, node, 3, TRUE);
 422
 423   _gtk_rbtree_remove_node (tree, node);
 424
 425   _gtk_rbtree_free (tree);
 426 }
 427
 428 int
 429 main (int argc, char *argv[])
 430 {
 431   g_test_init (&argc, &argv, NULL);
 432   setlocale (LC_ALL, "C");
 433   g_test_bug_base ("http://bugzilla.gnome.org/show_bug.cgi?id=%s");
 434
 435   g_test_add_func ("/rbtree/create", test_create);
 436   g_test_add_func ("/rbtree/insert_after", test_insert_after);
 437   g_test_add_func ("/rbtree/insert_before", test_insert_before);
 438   g_test_add_func ("/rbtree/remove_node", test_remove_node);
 439
 440   g_test_add_func ("/rbtree/remove_root", test_remove_root);
 441
 442   return g_test_run ();
 443 }