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