Pileus Git - ~andy/gtk/blob - gtk/gtkrbtree.c

   1 /* gtkrbtree.c
   2  * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library. If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include "config.h"
  19 #include "gtkrbtree.h"
  20 #include "gtkdebug.h"
  21
  22 static GtkRBNode * _gtk_rbnode_new                (GtkRBTree  *tree,
  23                                                    gint        height);
  24 static void        _gtk_rbnode_free               (GtkRBNode  *node);
  25 static void        _gtk_rbnode_rotate_left        (GtkRBTree  *tree,
  26                                                    GtkRBNode  *node);
  27 static void        _gtk_rbnode_rotate_right       (GtkRBTree  *tree,
  28                                                    GtkRBNode  *node);
  29 static void        _gtk_rbtree_insert_fixup       (GtkRBTree  *tree,
  30                                                    GtkRBNode  *node);
  31 static void        _gtk_rbtree_remove_node_fixup  (GtkRBTree  *tree,
  32                                                    GtkRBNode  *node,
  33                                                    GtkRBNode  *parent);
  34 static inline void _fixup_validation              (GtkRBTree  *tree,
  35                                                    GtkRBNode  *node);
  36 static inline void _fixup_total_count             (GtkRBTree  *tree,
  37                                                    GtkRBNode  *node);
  38 #ifdef G_ENABLE_DEBUG
  39 static void        _gtk_rbtree_test               (const gchar *where,
  40                                                    GtkRBTree  *tree);
  41 static void        _gtk_rbtree_debug_spew         (GtkRBTree  *tree);
  42 #endif
  43
  44 static const GtkRBNode nil = {
  45   /* .flags = */ GTK_RBNODE_BLACK,
  46
  47   /* rest is NULL */
  48 };
  49
  50 gboolean
  51 _gtk_rbtree_is_nil (GtkRBNode *node)
  52 {
  53   return node == &nil;
  54 }
  55
  56 static GtkRBNode *
  57 _gtk_rbnode_new (GtkRBTree *tree,
  58                  gint       height)
  59 {
  60   GtkRBNode *node = g_slice_new (GtkRBNode);
  61
  62   node->left = (GtkRBNode *) &nil;
  63   node->right = (GtkRBNode *) &nil;
  64   node->parent = (GtkRBNode *) &nil;
  65   node->flags = GTK_RBNODE_RED;
  66   node->total_count = 1;
  67   node->count = 1;
  68   node->children = NULL;
  69   node->offset = height;
  70   return node;
  71 }
  72
  73 static void
  74 _gtk_rbnode_free (GtkRBNode *node)
  75 {
  76 #ifdef G_ENABLE_DEBUG
  77   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
  78     {
  79       node->left = (gpointer) 0xdeadbeef;
  80       node->right = (gpointer) 0xdeadbeef;
  81       node->parent = (gpointer) 0xdeadbeef;
  82       node->total_count = 56789;
  83       node->offset = 56789;
  84       node->count = 56789;
  85       node->flags = 0;
  86     }
  87 #endif
  88   g_slice_free (GtkRBNode, node);
  89 }
  90
  91 static void
  92 _gtk_rbnode_rotate_left (GtkRBTree *tree,
  93                          GtkRBNode *node)
  94 {
  95   gint node_height, right_height;
  96   GtkRBNode *right;
  97
  98   g_return_if_fail (!_gtk_rbtree_is_nil (node));
  99   g_return_if_fail (!_gtk_rbtree_is_nil (node->right));
 100
 101   right = node->right;
 102
 103   node_height = GTK_RBNODE_GET_HEIGHT (node);
 104   right_height = GTK_RBNODE_GET_HEIGHT (right);
 105   node->right = right->left;
 106   if (!_gtk_rbtree_is_nil (right->left))
 107     right->left->parent = node;
 108
 109   right->parent = node->parent;
 110   if (!_gtk_rbtree_is_nil (node->parent))
 111     {
 112       if (node == node->parent->left)
 113         node->parent->left = right;
 114       else
 115         node->parent->right = right;
 116     } else {
 117       tree->root = right;
 118     }
 119
 120   right->left = node;
 121   node->parent = right;
 122
 123   node->count = 1 + node->left->count + node->right->count;
 124   right->count = 1 + right->left->count + right->right->count;
 125
 126   node->offset = node_height + node->left->offset + node->right->offset +
 127                  (node->children ? node->children->root->offset : 0);
 128   right->offset = right_height + right->left->offset + right->right->offset +
 129                   (right->children ? right->children->root->offset : 0);
 130
 131   _fixup_validation (tree, node);
 132   _fixup_validation (tree, right);
 133   _fixup_total_count (tree, node);
 134   _fixup_total_count (tree, right);
 135 }
 136
 137 static void
 138 _gtk_rbnode_rotate_right (GtkRBTree *tree,
 139                           GtkRBNode *node)
 140 {
 141   gint node_height, left_height;
 142   GtkRBNode *left;
 143
 144   g_return_if_fail (!_gtk_rbtree_is_nil (node));
 145   g_return_if_fail (!_gtk_rbtree_is_nil (node->left));
 146
 147   left = node->left;
 148
 149   node_height = GTK_RBNODE_GET_HEIGHT (node);
 150   left_height = GTK_RBNODE_GET_HEIGHT (left);
 151
 152   node->left = left->right;
 153   if (!_gtk_rbtree_is_nil (left->right))
 154     left->right->parent = node;
 155
 156   left->parent = node->parent;
 157   if (!_gtk_rbtree_is_nil (node->parent))
 158     {
 159       if (node == node->parent->right)
 160         node->parent->right = left;
 161       else
 162         node->parent->left = left;
 163     }
 164   else
 165     {
 166       tree->root = left;
 167     }
 168
 169   /* link node and left */
 170   left->right = node;
 171   node->parent = left;
 172
 173   node->count = 1 + node->left->count + node->right->count;
 174   left->count = 1 + left->left->count + left->right->count;
 175
 176   node->offset = node_height + node->left->offset + node->right->offset +
 177                  (node->children ? node->children->root->offset : 0);
 178   left->offset = left_height + left->left->offset + left->right->offset +
 179                  (left->children?left->children->root->offset:0);
 180
 181   _fixup_validation (tree, node);
 182   _fixup_validation (tree, left);
 183   _fixup_total_count (tree, node);
 184   _fixup_total_count (tree, left);
 185 }
 186
 187 static void
 188 _gtk_rbtree_insert_fixup (GtkRBTree *tree,
 189                           GtkRBNode *node)
 190 {
 191
 192   /* check Red-Black properties */
 193   while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)
 194     {
 195       /* we have a violation */
 196       if (node->parent == node->parent->parent->left)
 197         {
 198           GtkRBNode *y = node->parent->parent->right;
 199           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 200             {
 201                                 /* uncle is GTK_RBNODE_RED */
 202               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 203               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 204               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 205               node = node->parent->parent;
 206             }
 207           else
 208             {
 209                                 /* uncle is GTK_RBNODE_BLACK */
 210               if (node == node->parent->right)
 211                 {
 212                   /* make node a left child */
 213                   node = node->parent;
 214                   _gtk_rbnode_rotate_left (tree, node);
 215                 }
 216
 217                                 /* recolor and rotate */
 218               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 219               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 220               _gtk_rbnode_rotate_right(tree, node->parent->parent);
 221             }
 222         }
 223       else
 224         {
 225           /* mirror image of above code */
 226           GtkRBNode *y = node->parent->parent->left;
 227           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 228             {
 229                                 /* uncle is GTK_RBNODE_RED */
 230               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 231               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 232               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 233               node = node->parent->parent;
 234             }
 235           else
 236             {
 237                                 /* uncle is GTK_RBNODE_BLACK */
 238               if (node == node->parent->left)
 239                 {
 240                   node = node->parent;
 241                   _gtk_rbnode_rotate_right (tree, node);
 242                 }
 243               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 244               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 245               _gtk_rbnode_rotate_left (tree, node->parent->parent);
 246             }
 247         }
 248     }
 249   GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);
 250 }
 251
 252 static void
 253 _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
 254                                GtkRBNode *node,
 255                                GtkRBNode *parent)
 256 {
 257   while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
 258     {
 259       if (node == parent->left)
 260         {
 261           GtkRBNode *w = parent->right;
 262           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 263             {
 264               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 265               GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED);
 266               _gtk_rbnode_rotate_left (tree, parent);
 267               w = parent->right;
 268             }
 269           if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 270             {
 271               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 272               node = parent;
 273             }
 274           else
 275             {
 276               if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 277                 {
 278                   GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 279                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 280                   _gtk_rbnode_rotate_right (tree, w);
 281                   w = parent->right;
 282                 }
 283               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent));
 284               GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK);
 285               GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 286               _gtk_rbnode_rotate_left (tree, parent);
 287               node = tree->root;
 288             }
 289         }
 290       else
 291         {
 292           GtkRBNode *w = parent->left;
 293           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 294             {
 295               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 296               GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED);
 297               _gtk_rbnode_rotate_right (tree, parent);
 298               w = parent->left;
 299             }
 300           if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 301             {
 302               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 303               node = parent;
 304             }
 305           else
 306             {
 307               if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 308                 {
 309                   GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 310                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 311                   _gtk_rbnode_rotate_left (tree, w);
 312                   w = parent->left;
 313                 }
 314               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent));
 315               GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK);
 316               GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 317               _gtk_rbnode_rotate_right (tree, parent);
 318               node = tree->root;
 319             }
 320         }
 321
 322       parent = node->parent;
 323     }
 324   GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
 325 }
 326
 327 GtkRBTree *
 328 _gtk_rbtree_new (void)
 329 {
 330   GtkRBTree *retval;
 331
 332   retval = g_new (GtkRBTree, 1);
 333   retval->parent_tree = NULL;
 334   retval->parent_node = NULL;
 335
 336   retval->root = (GtkRBNode *) &nil;
 337
 338   return retval;
 339 }
 340
 341 static void
 342 _gtk_rbtree_free_helper (GtkRBTree  *tree,
 343                          GtkRBNode  *node,
 344                          gpointer    data)
 345 {
 346   if (node->children)
 347     _gtk_rbtree_free (node->children);
 348
 349   _gtk_rbnode_free (node);
 350 }
 351
 352 void
 353 _gtk_rbtree_free (GtkRBTree *tree)
 354 {
 355   _gtk_rbtree_traverse (tree,
 356                         tree->root,
 357                         G_POST_ORDER,
 358                         _gtk_rbtree_free_helper,
 359                         NULL);
 360
 361   if (tree->parent_node &&
 362       tree->parent_node->children == tree)
 363     tree->parent_node->children = NULL;
 364   g_free (tree);
 365 }
 366
 367 static void
 368 gtk_rbnode_adjust (GtkRBTree *tree,
 369                    GtkRBNode *node,
 370                    int        count_diff,
 371                    int        total_count_diff,
 372                    int        offset_diff)
 373 {
 374   while (tree && node && !_gtk_rbtree_is_nil (node))
 375     {
 376       _fixup_validation (tree, node);
 377       node->offset += offset_diff;
 378       node->count += count_diff;
 379       node->total_count += total_count_diff;
 380
 381       node = node->parent;
 382       if (_gtk_rbtree_is_nil (node))
 383         {
 384           node = tree->parent_node;
 385           tree = tree->parent_tree;
 386           count_diff = 0;
 387         }
 388     }
 389 }
 390
 391 void
 392 _gtk_rbtree_remove (GtkRBTree *tree)
 393 {
 394 #ifdef G_ENABLE_DEBUG
 395   GtkRBTree *tmp_tree;
 396
 397   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 398     _gtk_rbtree_test (G_STRLOC, tree);
 399 #endif
 400
 401   /* ugly hack to make _fixup_validation work in the first iteration of the
 402    * loop below */
 403   GTK_RBNODE_UNSET_FLAG (tree->root, GTK_RBNODE_DESCENDANTS_INVALID);
 404
 405   gtk_rbnode_adjust (tree->parent_tree,
 406                      tree->parent_node,
 407                      0,
 408                      - (int) tree->root->total_count,
 409                      - tree->root->offset);
 410
 411 #ifdef G_ENABLE_DEBUG
 412   tmp_tree = tree->parent_tree;
 413 #endif
 414
 415   _gtk_rbtree_free (tree);
 416
 417 #ifdef G_ENABLE_DEBUG
 418   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 419     _gtk_rbtree_test (G_STRLOC, tmp_tree);
 420 #endif
 421 }
 422
 423
 424 GtkRBNode *
 425 _gtk_rbtree_insert_after (GtkRBTree *tree,
 426                           GtkRBNode *current,
 427                           gint       height,
 428                           gboolean   valid)
 429 {
 430   GtkRBNode *node;
 431   gboolean right = TRUE;
 432
 433 #ifdef G_ENABLE_DEBUG
 434   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 435     {
 436       g_print ("\n\n_gtk_rbtree_insert_after: %p\n", current);
 437       _gtk_rbtree_debug_spew (tree);
 438       _gtk_rbtree_test (G_STRLOC, tree);
 439     }
 440 #endif /* G_ENABLE_DEBUG */
 441
 442   if (current != NULL && !_gtk_rbtree_is_nil (current->right))
 443     {
 444       current = current->right;
 445       while (!_gtk_rbtree_is_nil (current->left))
 446         current = current->left;
 447       right = FALSE;
 448     }
 449   /* setup new node */
 450   node = _gtk_rbnode_new (tree, height);
 451
 452   /* insert node in tree */
 453   if (current)
 454     {
 455       node->parent = current;
 456       if (right)
 457         current->right = node;
 458       else
 459         current->left = node;
 460       gtk_rbnode_adjust (tree, node->parent,
 461                          1, 1, height);
 462     }
 463   else
 464     {
 465       g_assert (_gtk_rbtree_is_nil (tree->root));
 466       tree->root = node;
 467       gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
 468                          0, 1, height);
 469     }
 470
 471   if (valid)
 472     _gtk_rbtree_node_mark_valid (tree, node);
 473   else
 474     _gtk_rbtree_node_mark_invalid (tree, node);
 475
 476   _gtk_rbtree_insert_fixup (tree, node);
 477
 478 #ifdef G_ENABLE_DEBUG
 479   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 480     {
 481       g_print ("_gtk_rbtree_insert_after finished...\n");
 482       _gtk_rbtree_debug_spew (tree);
 483       g_print ("\n\n");
 484       _gtk_rbtree_test (G_STRLOC, tree);
 485     }
 486 #endif /* G_ENABLE_DEBUG */
 487
 488   return node;
 489 }
 490
 491 GtkRBNode *
 492 _gtk_rbtree_insert_before (GtkRBTree *tree,
 493                            GtkRBNode *current,
 494                            gint       height,
 495                            gboolean   valid)
 496 {
 497   GtkRBNode *node;
 498   gboolean left = TRUE;
 499
 500 #ifdef G_ENABLE_DEBUG
 501   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 502     {
 503       g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current);
 504       _gtk_rbtree_debug_spew (tree);
 505       _gtk_rbtree_test (G_STRLOC, tree);
 506     }
 507 #endif /* G_ENABLE_DEBUG */
 508
 509   if (current != NULL && !_gtk_rbtree_is_nil (current->left))
 510     {
 511       current = current->left;
 512       while (!_gtk_rbtree_is_nil (current->right))
 513         current = current->right;
 514       left = FALSE;
 515     }
 516
 517   /* setup new node */
 518   node = _gtk_rbnode_new (tree, height);
 519
 520   /* insert node in tree */
 521   if (current)
 522     {
 523       node->parent = current;
 524       if (left)
 525         current->left = node;
 526       else
 527         current->right = node;
 528       gtk_rbnode_adjust (tree, node->parent,
 529                          1, 1, height);
 530     }
 531   else
 532     {
 533       g_assert (_gtk_rbtree_is_nil (tree->root));
 534       tree->root = node;
 535       gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
 536                          0, 1, height);
 537     }
 538
 539   if (valid)
 540     _gtk_rbtree_node_mark_valid (tree, node);
 541   else
 542     _gtk_rbtree_node_mark_invalid (tree, node);
 543
 544   _gtk_rbtree_insert_fixup (tree, node);
 545
 546 #ifdef G_ENABLE_DEBUG
 547   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 548     {
 549       g_print ("_gtk_rbtree_insert_before finished...\n");
 550       _gtk_rbtree_debug_spew (tree);
 551       g_print ("\n\n");
 552       _gtk_rbtree_test (G_STRLOC, tree);
 553     }
 554 #endif /* G_ENABLE_DEBUG */
 555
 556   return node;
 557 }
 558
 559 GtkRBNode *
 560 _gtk_rbtree_find_count (GtkRBTree *tree,
 561                         gint       count)
 562 {
 563   GtkRBNode *node;
 564
 565   node = tree->root;
 566   while (!_gtk_rbtree_is_nil (node) && (node->left->count + 1 != count))
 567     {
 568       if (node->left->count >= count)
 569         node = node->left;
 570       else
 571         {
 572           count -= (node->left->count + 1);
 573           node = node->right;
 574         }
 575     }
 576   if (_gtk_rbtree_is_nil (node))
 577     return NULL;
 578   return node;
 579 }
 580
 581 void
 582 _gtk_rbtree_node_set_height (GtkRBTree *tree,
 583                              GtkRBNode *node,
 584                              gint       height)
 585 {
 586   gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
 587
 588   if (diff == 0)
 589     return;
 590
 591   gtk_rbnode_adjust (tree, node, 0, 0, diff);
 592
 593 #ifdef G_ENABLE_DEBUG
 594   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 595     _gtk_rbtree_test (G_STRLOC, tree);
 596 #endif
 597 }
 598
 599 void
 600 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
 601                                GtkRBNode *node)
 602 {
 603   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 604     return;
 605
 606   GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 607   do
 608     {
 609       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
 610         return;
 611       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 612       node = node->parent;
 613       if (_gtk_rbtree_is_nil (node))
 614         {
 615           node = tree->parent_node;
 616           tree = tree->parent_tree;
 617         }
 618     }
 619   while (node);
 620 }
 621
 622 #if 0
 623 /* Draconian version. */
 624 void
 625 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
 626                                GtkRBNode *node)
 627 {
 628   GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 629   do
 630     {
 631       _fixup_validation (tree, node);
 632       node = node->parent;
 633       if (_gtk_rbtree_is_nil (node))
 634         {
 635           node = tree->parent_node;
 636           tree = tree->parent_tree;
 637         }
 638     }
 639   while (node);
 640 }
 641 #endif
 642
 643 void
 644 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 645                              GtkRBNode *node)
 646 {
 647   if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
 648       (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))
 649     return;
 650
 651   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
 652   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 653
 654   do
 655     {
 656       if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||
 657           (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||
 658           (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 659           (GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 660           (GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
 661         return;
 662
 663       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 664       node = node->parent;
 665       if (_gtk_rbtree_is_nil (node))
 666         {
 667           node = tree->parent_node;
 668           tree = tree->parent_tree;
 669         }
 670     }
 671   while (node);
 672 }
 673
 674 #if 0
 675 /* Draconian version */
 676 void
 677 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 678                              GtkRBNode *node)
 679 {
 680   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
 681   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 682
 683   do
 684     {
 685       _fixup_validation (tree, node);
 686       node = node->parent;
 687       if (_gtk_rbtree_is_nil (node))
 688         {
 689           node = tree->parent_node;
 690           tree = tree->parent_tree;
 691         }
 692     }
 693   while (node);
 694 }
 695 #endif
 696 /* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
 697  */
 698 void
 699 _gtk_rbtree_column_invalid (GtkRBTree *tree)
 700 {
 701   GtkRBNode *node;
 702
 703   if (tree == NULL)
 704     return;
 705
 706   node = _gtk_rbtree_first (tree);
 707
 708   do
 709     {
 710       if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))
 711         GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 712       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 713
 714       if (node->children)
 715         _gtk_rbtree_column_invalid (node->children);
 716     }
 717   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 718 }
 719
 720 void
 721 _gtk_rbtree_mark_invalid (GtkRBTree *tree)
 722 {
 723   GtkRBNode *node;
 724
 725   if (tree == NULL)
 726     return;
 727
 728   node = _gtk_rbtree_first (tree);
 729
 730   do
 731     {
 732       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 733       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 734
 735       if (node->children)
 736         _gtk_rbtree_mark_invalid (node->children);
 737     }
 738   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 739 }
 740
 741 void
 742 _gtk_rbtree_set_fixed_height (GtkRBTree *tree,
 743                               gint       height,
 744                               gboolean   mark_valid)
 745 {
 746   GtkRBNode *node;
 747
 748   if (tree == NULL)
 749     return;
 750
 751   node = _gtk_rbtree_first (tree);
 752
 753   do
 754     {
 755       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 756         {
 757           _gtk_rbtree_node_set_height (tree, node, height);
 758           if (mark_valid)
 759             _gtk_rbtree_node_mark_valid (tree, node);
 760         }
 761
 762       if (node->children)
 763         _gtk_rbtree_set_fixed_height (node->children, height, mark_valid);
 764     }
 765   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 766 }
 767
 768 static void
 769 reorder_prepare (GtkRBTree *tree,
 770                  GtkRBNode *node,
 771                  gpointer   data)
 772 {
 773   node->offset -= node->left->offset + node->right->offset;
 774   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 775 }
 776
 777 static void
 778 reorder_fixup (GtkRBTree *tree,
 779                GtkRBNode *node,
 780                gpointer   data)
 781 {
 782   node->offset += node->left->offset + node->right->offset;
 783   node->count = 1 + node->left->count + node->right->count;
 784   _fixup_validation (tree, node);
 785   _fixup_total_count (tree, node);
 786 }
 787
 788 static void
 789 reorder_copy_node (GtkRBTree *tree,
 790                    GtkRBNode *to,
 791                    GtkRBNode *from)
 792 {
 793   to->flags = (to->flags & GTK_RBNODE_NON_COLORS) | GTK_RBNODE_GET_COLOR (from);
 794
 795   to->left = from->left;
 796   if (!_gtk_rbtree_is_nil (to->left))
 797     to->left->parent = to;
 798
 799   to->right = from->right;
 800   if (!_gtk_rbtree_is_nil (to->right))
 801     to->right->parent = to;
 802
 803   to->parent = from->parent;
 804   if (_gtk_rbtree_is_nil (to->parent))
 805     tree->root = to;
 806   else if (to->parent->left == from)
 807     to->parent->left = to;
 808   else if (to->parent->right == from)
 809     to->parent->right = to;
 810 }
 811
 812 /* It basically pulls everything out of the tree, rearranges it, and puts it
 813  * back together.  Our strategy is to keep the old RBTree intact, and just
 814  * rearrange the contents.  When that is done, we go through and update the
 815  * heights.  There is probably a more elegant way to write this function.  If
 816  * anyone wants to spend the time writing it, patches will be accepted.
 817  */
 818 void
 819 _gtk_rbtree_reorder (GtkRBTree *tree,
 820                      gint      *new_order,
 821                      gint       length)
 822 {
 823   GtkRBNode **nodes;
 824   GtkRBNode *node;
 825   gint i, j;
 826
 827   g_return_if_fail (tree != NULL);
 828   g_return_if_fail (length > 0);
 829   g_return_if_fail (tree->root->count == length);
 830
 831   nodes = g_new (GtkRBNode *, length);
 832
 833   _gtk_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL);
 834
 835   for (node = _gtk_rbtree_first (tree), i = 0;
 836        node;
 837        node = _gtk_rbtree_next (tree, node), i++)
 838     {
 839       nodes[i] = node;
 840     }
 841
 842   for (i = 0; i < length; i++)
 843     {
 844       GtkRBNode tmp = { 0, };
 845       GSList *l, *cycle = NULL;
 846
 847       tmp.offset = -1;
 848
 849       /* already swapped */
 850       if (nodes[i] == NULL)
 851         continue;
 852       /* no need to swap */
 853       if (new_order[i] == i)
 854         continue;
 855
 856       /* make a list out of the pending nodes */
 857       for (j = i; new_order[j] != i; j = new_order[j])
 858         {
 859           cycle = g_slist_prepend (cycle, nodes[j]);
 860           nodes[j] = NULL;
 861         }
 862
 863       node = nodes[j];
 864       reorder_copy_node (tree, &tmp, node);
 865       for (l = cycle; l; l = l->next)
 866         {
 867           reorder_copy_node (tree, node, l->data);
 868           node = l->data;
 869         }
 870
 871       reorder_copy_node (tree, node, &tmp);
 872       nodes[j] = NULL;
 873       g_slist_free (cycle);
 874     }
 875
 876   _gtk_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL);
 877
 878   g_free (nodes);
 879 }
 880
 881 /**
 882  * _gtk_rbtree_contains:
 883  * @tree: a tree
 884  * @potential_child: a potential child of @tree
 885  *
 886  * Checks if @potential_child is a child (direct or via intermediate
 887  * trees) of @tree.
 888  *
 889  * Returns: %TRUE if @potentitial_child is a child of @tree.
 890  **/
 891 gboolean
 892 _gtk_rbtree_contains (GtkRBTree *tree,
 893                       GtkRBTree *potential_child)
 894 {
 895   g_return_val_if_fail (tree != NULL, FALSE);
 896   g_return_val_if_fail (potential_child != NULL, FALSE);
 897
 898   do {
 899     potential_child = potential_child->parent_tree;
 900     if (potential_child == tree)
 901       return TRUE;
 902   } while (potential_child != NULL);
 903
 904   return FALSE;
 905 }
 906
 907 gint
 908 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 909                               GtkRBNode *node)
 910 {
 911   GtkRBNode *last;
 912   gint retval;
 913
 914   g_assert (node);
 915   g_assert (node->left);
 916
 917   retval = node->left->offset;
 918
 919   while (tree && node && !_gtk_rbtree_is_nil (node))
 920     {
 921       last = node;
 922       node = node->parent;
 923
 924       /* Add left branch, plus children, iff we came from the right */
 925       if (node->right == last)
 926         retval += node->offset - node->right->offset;
 927
 928       if (_gtk_rbtree_is_nil (node))
 929         {
 930           node = tree->parent_node;
 931           tree = tree->parent_tree;
 932
 933           /* Add the parent node, plus the left branch. */
 934           if (node)
 935             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 936         }
 937     }
 938   return retval;
 939 }
 940
 941 guint
 942 _gtk_rbtree_node_get_index (GtkRBTree *tree,
 943                             GtkRBNode *node)
 944 {
 945   GtkRBNode *last;
 946   guint retval;
 947
 948   g_assert (node);
 949   g_assert (node->left);
 950
 951   retval = node->left->total_count;
 952
 953   while (tree && node && !_gtk_rbtree_is_nil (node))
 954     {
 955       last = node;
 956       node = node->parent;
 957
 958       /* Add left branch, plus children, iff we came from the right */
 959       if (node->right == last)
 960         retval += node->total_count - node->right->total_count;
 961
 962       if (_gtk_rbtree_is_nil (node))
 963         {
 964           node = tree->parent_node;
 965           tree = tree->parent_tree;
 966
 967           /* Add the parent node, plus the left branch. */
 968           if (node)
 969             retval += node->left->total_count + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
 970         }
 971     }
 972
 973   return retval;
 974 }
 975
 976 static gint
 977 gtk_rbtree_real_find_offset (GtkRBTree  *tree,
 978                              gint        height,
 979                              GtkRBTree **new_tree,
 980                              GtkRBNode **new_node)
 981 {
 982   GtkRBNode *tmp_node;
 983
 984   g_assert (tree);
 985
 986   if (height < 0)
 987     {
 988       *new_tree = NULL;
 989       *new_node = NULL;
 990
 991       return 0;
 992     }
 993
 994
 995   tmp_node = tree->root;
 996   while (!_gtk_rbtree_is_nil (tmp_node) &&
 997          (tmp_node->left->offset > height ||
 998           (tmp_node->offset - tmp_node->right->offset) < height))
 999     {
1000       if (tmp_node->left->offset > height)
1001         tmp_node = tmp_node->left;
1002       else
1003         {
1004           height -= (tmp_node->offset - tmp_node->right->offset);
1005           tmp_node = tmp_node->right;
1006         }
1007     }
1008   if (_gtk_rbtree_is_nil (tmp_node))
1009     {
1010       *new_tree = NULL;
1011       *new_node = NULL;
1012       return 0;
1013     }
1014   if (tmp_node->children)
1015     {
1016       if ((tmp_node->offset -
1017            tmp_node->right->offset -
1018            tmp_node->children->root->offset) > height)
1019         {
1020           *new_tree = tree;
1021           *new_node = tmp_node;
1022           return (height - tmp_node->left->offset);
1023         }
1024       return gtk_rbtree_real_find_offset (tmp_node->children,
1025                                           height - tmp_node->left->offset -
1026                                           (tmp_node->offset -
1027                                            tmp_node->left->offset -
1028                                            tmp_node->right->offset -
1029                                            tmp_node->children->root->offset),
1030                                           new_tree,
1031                                           new_node);
1032     }
1033   *new_tree = tree;
1034   *new_node = tmp_node;
1035   return (height - tmp_node->left->offset);
1036 }
1037
1038 gint
1039 _gtk_rbtree_find_offset (GtkRBTree  *tree,
1040                          gint        height,
1041                          GtkRBTree **new_tree,
1042                          GtkRBNode **new_node)
1043 {
1044   g_assert (tree);
1045
1046   if ((height < 0) ||
1047       (height >= tree->root->offset))
1048     {
1049       *new_tree = NULL;
1050       *new_node = NULL;
1051
1052       return 0;
1053     }
1054   return gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1055 }
1056
1057 gboolean
1058 _gtk_rbtree_find_index (GtkRBTree  *tree,
1059                         guint       index,
1060                         GtkRBTree **new_tree,
1061                         GtkRBNode **new_node)
1062 {
1063   GtkRBNode *tmp_node;
1064
1065   g_assert (tree);
1066
1067   tmp_node = tree->root;
1068   while (!_gtk_rbtree_is_nil (tmp_node))
1069     {
1070       if (tmp_node->left->total_count > index)
1071         {
1072           tmp_node = tmp_node->left;
1073         }
1074       else if (tmp_node->total_count - tmp_node->right->total_count <= index)
1075         {
1076           index -= tmp_node->total_count - tmp_node->right->total_count;
1077           tmp_node = tmp_node->right;
1078         }
1079       else
1080         {
1081           index -= tmp_node->left->total_count;
1082           break;
1083         }
1084     }
1085   if (_gtk_rbtree_is_nil (tmp_node))
1086     {
1087       *new_tree = NULL;
1088       *new_node = NULL;
1089       return FALSE;
1090     }
1091
1092   if (index > 0)
1093     {
1094       g_assert (tmp_node->children);
1095
1096       return _gtk_rbtree_find_index (tmp_node->children,
1097                                      index - 1,
1098                                      new_tree,
1099                                      new_node);
1100     }
1101
1102   *new_tree = tree;
1103   *new_node = tmp_node;
1104   return TRUE;
1105 }
1106
1107 void
1108 _gtk_rbtree_remove_node (GtkRBTree *tree,
1109                          GtkRBNode *node)
1110 {
1111   GtkRBNode *x, *y;
1112   gint y_height;
1113   guint y_total_count;
1114
1115   g_return_if_fail (tree != NULL);
1116   g_return_if_fail (node != NULL);
1117
1118
1119 #ifdef G_ENABLE_DEBUG
1120   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1121     {
1122       g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1123       _gtk_rbtree_debug_spew (tree);
1124       _gtk_rbtree_test (G_STRLOC, tree);
1125     }
1126 #endif /* G_ENABLE_DEBUG */
1127
1128   /* make sure we're deleting a node that's actually in the tree */
1129   for (x = node; !_gtk_rbtree_is_nil (x->parent); x = x->parent)
1130     ;
1131   g_return_if_fail (x == tree->root);
1132
1133 #ifdef G_ENABLE_DEBUG
1134   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1135     _gtk_rbtree_test (G_STRLOC, tree);
1136 #endif
1137
1138   if (_gtk_rbtree_is_nil (node->left) ||
1139       _gtk_rbtree_is_nil (node->right))
1140     {
1141       y = node;
1142     }
1143   else
1144     {
1145       y = node->right;
1146
1147       while (!_gtk_rbtree_is_nil (y->left))
1148         y = y->left;
1149     }
1150
1151   y_height = GTK_RBNODE_GET_HEIGHT (y)
1152              + (y->children ? y->children->root->offset : 0);
1153   y_total_count = 1 + (y->children ? y->children->root->total_count : 0);
1154
1155   /* x is y's only child, or nil */
1156   if (!_gtk_rbtree_is_nil (y->left))
1157     x = y->left;
1158   else
1159     x = y->right;
1160
1161   /* remove y from the parent chain */
1162   if (!_gtk_rbtree_is_nil (x))
1163     x->parent = y->parent;
1164   if (!_gtk_rbtree_is_nil (y->parent))
1165     {
1166       if (y == y->parent->left)
1167         y->parent->left = x;
1168       else
1169         y->parent->right = x;
1170     }
1171   else
1172     {
1173       tree->root = x;
1174     }
1175
1176   /* We need to clean up the validity of the tree.
1177    */
1178   gtk_rbnode_adjust (tree, y, -1, - y_total_count, - y_height);
1179
1180   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1181     _gtk_rbtree_remove_node_fixup (tree, x, y->parent);
1182
1183   if (y != node)
1184     {
1185       gint node_height, node_total_count;
1186
1187       /* We want to see how much we remove from the aggregate values.
1188        * This is all the children we remove plus the node's values.
1189        */
1190       node_height = GTK_RBNODE_GET_HEIGHT (node)
1191                     + (node->children ? node->children->root->offset : 0);
1192       node_total_count = 1
1193                          + (node->children ? node->children->root->total_count : 0);
1194
1195       /* Move the node over */
1196       if (GTK_RBNODE_GET_COLOR (node) != GTK_RBNODE_GET_COLOR (y))
1197         y->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
1198
1199       y->left = node->left;
1200       if (!_gtk_rbtree_is_nil (y->left))
1201         y->left->parent = y;
1202       y->right = node->right;
1203       if (!_gtk_rbtree_is_nil (y->right))
1204         y->right->parent = y;
1205       y->parent = node->parent;
1206       if (!_gtk_rbtree_is_nil (y->parent))
1207         {
1208           if (y->parent->left == node)
1209             y->parent->left = y;
1210           else
1211             y->parent->right = y;
1212         }
1213       else
1214         {
1215           tree->root = y;
1216         }
1217       y->count = node->count;
1218       y->total_count = node->total_count;
1219       y->offset = node->offset;
1220
1221       gtk_rbnode_adjust (tree, y,
1222                          0,
1223                          y_total_count - node_total_count,
1224                          y_height - node_height);
1225     }
1226
1227   _gtk_rbnode_free (node);
1228
1229 #ifdef G_ENABLE_DEBUG
1230   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1231     {
1232       g_print ("_gtk_rbtree_remove_node finished...\n");
1233       _gtk_rbtree_debug_spew (tree);
1234       g_print ("\n\n");
1235       _gtk_rbtree_test (G_STRLOC, tree);
1236     }
1237 #endif /* G_ENABLE_DEBUG */
1238 }
1239
1240 GtkRBNode *
1241 _gtk_rbtree_first (GtkRBTree *tree)
1242 {
1243   GtkRBNode *node;
1244
1245   node = tree->root;
1246
1247   if (_gtk_rbtree_is_nil (node))
1248     return NULL;
1249
1250   while (!_gtk_rbtree_is_nil (node->left))
1251     node = node->left;
1252
1253   return node;
1254 }
1255
1256 GtkRBNode *
1257 _gtk_rbtree_next (GtkRBTree *tree,
1258                   GtkRBNode *node)
1259 {
1260   g_return_val_if_fail (tree != NULL, NULL);
1261   g_return_val_if_fail (node != NULL, NULL);
1262
1263   /* Case 1: the node's below us. */
1264   if (!_gtk_rbtree_is_nil (node->right))
1265     {
1266       node = node->right;
1267       while (!_gtk_rbtree_is_nil (node->left))
1268         node = node->left;
1269       return node;
1270     }
1271
1272   /* Case 2: it's an ancestor */
1273   while (!_gtk_rbtree_is_nil (node->parent))
1274     {
1275       if (node->parent->right == node)
1276         node = node->parent;
1277       else
1278         return (node->parent);
1279     }
1280
1281   /* Case 3: There is no next node */
1282   return NULL;
1283 }
1284
1285 GtkRBNode *
1286 _gtk_rbtree_prev (GtkRBTree *tree,
1287                   GtkRBNode *node)
1288 {
1289   g_return_val_if_fail (tree != NULL, NULL);
1290   g_return_val_if_fail (node != NULL, NULL);
1291
1292   /* Case 1: the node's below us. */
1293   if (!_gtk_rbtree_is_nil (node->left))
1294     {
1295       node = node->left;
1296       while (!_gtk_rbtree_is_nil (node->right))
1297         node = node->right;
1298       return node;
1299     }
1300
1301   /* Case 2: it's an ancestor */
1302   while (!_gtk_rbtree_is_nil (node->parent))
1303     {
1304       if (node->parent->left == node)
1305         node = node->parent;
1306       else
1307         return (node->parent);
1308     }
1309
1310   /* Case 3: There is no next node */
1311   return NULL;
1312 }
1313
1314 void
1315 _gtk_rbtree_next_full (GtkRBTree  *tree,
1316                        GtkRBNode  *node,
1317                        GtkRBTree **new_tree,
1318                        GtkRBNode **new_node)
1319 {
1320   g_return_if_fail (tree != NULL);
1321   g_return_if_fail (node != NULL);
1322   g_return_if_fail (new_tree != NULL);
1323   g_return_if_fail (new_node != NULL);
1324
1325   if (node->children)
1326     {
1327       *new_tree = node->children;
1328       *new_node = (*new_tree)->root;
1329       while (!_gtk_rbtree_is_nil ((*new_node)->left))
1330         *new_node = (*new_node)->left;
1331       return;
1332     }
1333
1334   *new_tree = tree;
1335   *new_node = _gtk_rbtree_next (tree, node);
1336
1337   while ((*new_node == NULL) &&
1338          (*new_tree != NULL))
1339     {
1340       *new_node = (*new_tree)->parent_node;
1341       *new_tree = (*new_tree)->parent_tree;
1342       if (*new_tree)
1343         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1344     }
1345 }
1346
1347 void
1348 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1349                        GtkRBNode  *node,
1350                        GtkRBTree **new_tree,
1351                        GtkRBNode **new_node)
1352 {
1353   g_return_if_fail (tree != NULL);
1354   g_return_if_fail (node != NULL);
1355   g_return_if_fail (new_tree != NULL);
1356   g_return_if_fail (new_node != NULL);
1357
1358   *new_tree = tree;
1359   *new_node = _gtk_rbtree_prev (tree, node);
1360
1361   if (*new_node == NULL)
1362     {
1363       *new_node = (*new_tree)->parent_node;
1364       *new_tree = (*new_tree)->parent_tree;
1365     }
1366   else
1367     {
1368       while ((*new_node)->children)
1369         {
1370           *new_tree = (*new_node)->children;
1371           *new_node = (*new_tree)->root;
1372           while (!_gtk_rbtree_is_nil ((*new_node)->right))
1373             *new_node = (*new_node)->right;
1374         }
1375     }
1376 }
1377
1378 gint
1379 _gtk_rbtree_get_depth (GtkRBTree *tree)
1380 {
1381   GtkRBTree *tmp_tree;
1382   gint depth = 0;
1383
1384   tmp_tree = tree->parent_tree;
1385   while (tmp_tree)
1386     {
1387       ++depth;
1388       tmp_tree = tmp_tree->parent_tree;
1389     }
1390
1391   return depth;
1392 }
1393
1394 static void
1395 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1396                                 GtkRBNode             *node,
1397                                 GtkRBTreeTraverseFunc  func,
1398                                 gpointer               data)
1399 {
1400   if (_gtk_rbtree_is_nil (node))
1401     return;
1402
1403   (* func) (tree, node, data);
1404   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1405   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1406 }
1407
1408 static void
1409 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1410                                  GtkRBNode             *node,
1411                                  GtkRBTreeTraverseFunc  func,
1412                                  gpointer               data)
1413 {
1414   if (_gtk_rbtree_is_nil (node))
1415     return;
1416
1417   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1418   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1419   (* func) (tree, node, data);
1420 }
1421
1422 void
1423 _gtk_rbtree_traverse (GtkRBTree             *tree,
1424                       GtkRBNode             *node,
1425                       GTraverseType          order,
1426                       GtkRBTreeTraverseFunc  func,
1427                       gpointer               data)
1428 {
1429   g_return_if_fail (tree != NULL);
1430   g_return_if_fail (node != NULL);
1431   g_return_if_fail (func != NULL);
1432   g_return_if_fail (order <= G_LEVEL_ORDER);
1433
1434   switch (order)
1435     {
1436     case G_PRE_ORDER:
1437       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1438       break;
1439     case G_POST_ORDER:
1440       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1441       break;
1442     case G_IN_ORDER:
1443     case G_LEVEL_ORDER:
1444     default:
1445       g_warning ("unsupported traversal order.");
1446       break;
1447     }
1448 }
1449
1450 static inline
1451 void _fixup_validation (GtkRBTree *tree,
1452                         GtkRBNode *node)
1453 {
1454   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1455       GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1456       GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
1457       GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
1458       (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1459     {
1460       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1461     }
1462   else
1463     {
1464       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1465     }
1466 }
1467
1468 static inline
1469 void _fixup_total_count (GtkRBTree *tree,
1470                     GtkRBNode *node)
1471 {
1472   node->total_count = 1 +
1473     (node->children != NULL ? node->children->root->total_count : 0) +
1474     node->left->total_count + node->right->total_count;
1475 }
1476
1477 #ifdef G_ENABLE_DEBUG
1478 static guint
1479 get_total_count (GtkRBNode *node)
1480 {
1481   guint child_total = 0;
1482
1483   child_total += (guint) node->left->total_count;
1484   child_total += (guint) node->right->total_count;
1485
1486   if (node->children)
1487     child_total += (guint) node->children->root->total_count;
1488
1489   return child_total + 1;
1490 }
1491
1492 static guint
1493 count_total (GtkRBTree *tree,
1494              GtkRBNode *node)
1495 {
1496   guint res;
1497
1498   if (_gtk_rbtree_is_nil (node))
1499     return 0;
1500
1501   res =
1502     count_total (tree, node->left) +
1503     count_total (tree, node->right) +
1504     (guint)1 +
1505     (node->children ? count_total (node->children, node->children->root) : 0);
1506
1507   if (res != node->total_count)
1508     g_print ("total count incorrect for node\n");
1509
1510   if (get_total_count (node) != node->total_count)
1511     g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1512
1513   return res;
1514 }
1515
1516 static gint
1517 _count_nodes (GtkRBTree *tree,
1518               GtkRBNode *node)
1519 {
1520   gint res;
1521   if (_gtk_rbtree_is_nil (node))
1522     return 0;
1523
1524   g_assert (node->left);
1525   g_assert (node->right);
1526
1527   res = (_count_nodes (tree, node->left) +
1528          _count_nodes (tree, node->right) + 1);
1529
1530   if (res != node->count)
1531     g_print ("Tree failed\n");
1532   return res;
1533 }
1534
1535 static void
1536 _gtk_rbtree_test_height (GtkRBTree *tree,
1537                          GtkRBNode *node)
1538 {
1539   gint computed_offset = 0;
1540
1541   /* This whole test is sort of a useless truism. */
1542
1543   if (!_gtk_rbtree_is_nil (node->left))
1544     computed_offset += node->left->offset;
1545
1546   if (!_gtk_rbtree_is_nil (node->right))
1547     computed_offset += node->right->offset;
1548
1549   if (node->children && !_gtk_rbtree_is_nil (node->children->root))
1550     computed_offset += node->children->root->offset;
1551
1552   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1553     g_error ("node has broken offset\n");
1554
1555   if (!_gtk_rbtree_is_nil (node->left))
1556     _gtk_rbtree_test_height (tree, node->left);
1557
1558   if (!_gtk_rbtree_is_nil (node->right))
1559     _gtk_rbtree_test_height (tree, node->right);
1560
1561   if (node->children && !_gtk_rbtree_is_nil (node->children->root))
1562     _gtk_rbtree_test_height (node->children, node->children->root);
1563 }
1564
1565 static void
1566 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1567                         GtkRBNode *node,
1568                          gint      expected_dirtyness)
1569 {
1570
1571   if (expected_dirtyness)
1572     {
1573       g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1574                 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1575                 GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
1576                 GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
1577                 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1578     }
1579   else
1580     {
1581       g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1582                 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1583       if (!_gtk_rbtree_is_nil (node->left))
1584         g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1585       if (!_gtk_rbtree_is_nil (node->right))
1586         g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1587       if (node->children != NULL)
1588         g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1589     }
1590
1591   if (!_gtk_rbtree_is_nil (node->left))
1592     _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1593   if (!_gtk_rbtree_is_nil (node->right))
1594     _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1595   if (node->children != NULL && !_gtk_rbtree_is_nil (node->children->root))
1596     _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1597 }
1598
1599 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1600
1601 static void
1602 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1603                                    GtkRBNode *node)
1604 {
1605   g_assert (!_gtk_rbtree_is_nil (node));
1606
1607   g_assert (node->left != NULL);
1608   g_assert (node->right != NULL);
1609   g_assert (node->parent != NULL);
1610
1611   if (!_gtk_rbtree_is_nil (node->left))
1612     {
1613       g_assert (node->left->parent == node);
1614       _gtk_rbtree_test_structure_helper (tree, node->left);
1615     }
1616   if (!_gtk_rbtree_is_nil (node->right))
1617     {
1618       g_assert (node->right->parent == node);
1619       _gtk_rbtree_test_structure_helper (tree, node->right);
1620     }
1621
1622   if (node->children != NULL)
1623     {
1624       g_assert (node->children->parent_tree == tree);
1625       g_assert (node->children->parent_node == node);
1626
1627       _gtk_rbtree_test_structure (node->children);
1628     }
1629 }
1630 static void
1631 _gtk_rbtree_test_structure (GtkRBTree *tree)
1632 {
1633   g_assert (tree->root);
1634   if (_gtk_rbtree_is_nil (tree->root))
1635     return;
1636
1637   g_assert (_gtk_rbtree_is_nil (tree->root->parent));
1638   _gtk_rbtree_test_structure_helper (tree, tree->root);
1639 }
1640
1641 static void
1642 _gtk_rbtree_test (const gchar *where,
1643                   GtkRBTree   *tree)
1644 {
1645   GtkRBTree *tmp_tree;
1646
1647   if (tree == NULL)
1648     return;
1649
1650   /* Test the entire tree */
1651   tmp_tree = tree;
1652   while (tmp_tree->parent_tree)
1653     tmp_tree = tmp_tree->parent_tree;
1654
1655   if (_gtk_rbtree_is_nil (tmp_tree->root))
1656     return;
1657
1658   _gtk_rbtree_test_structure (tmp_tree);
1659
1660   g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1661              _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1662
1663
1664   _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1665   _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1666   g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
1667 }
1668
1669 static void
1670 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1671                                GtkRBNode *node,
1672                                gint       depth)
1673 {
1674   gint i;
1675   for (i = 0; i < depth; i++)
1676     g_print ("\t");
1677
1678   g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1679            node,
1680            (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1681            node->offset,
1682            node->total_count,
1683            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1684            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1685            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1686   if (node->children != NULL)
1687     {
1688       g_print ("Looking at child.\n");
1689       _gtk_rbtree_debug_spew (node->children);
1690       g_print ("Done looking at child.\n");
1691     }
1692   if (!_gtk_rbtree_is_nil (node->left))
1693     {
1694       _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1695     }
1696   if (!_gtk_rbtree_is_nil (node->right))
1697     {
1698       _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1699     }
1700 }
1701
1702 static void
1703 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1704 {
1705   g_return_if_fail (tree != NULL);
1706
1707   if (_gtk_rbtree_is_nil (tree->root))
1708     g_print ("Empty tree...\n");
1709   else
1710     _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1711 }
1712 #endif /* G_ENABLE_DEBUG */