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_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 662           (!_gtk_rbtree_is_nil (node->right) && 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 typedef struct _GtkRBReorder
 771 {
 772   GtkRBTree *children;
 773   gint height;
 774   gint flags;
 775   gint order;
 776   gint invert_order;
 777   guint total_count;
 778 } GtkRBReorder;
 779
 780 static int
 781 gtk_rbtree_reorder_sort_func (gconstpointer a,
 782                               gconstpointer b)
 783 {
 784   return ((GtkRBReorder *) a)->order - ((GtkRBReorder *) b)->order;
 785 }
 786
 787 static int
 788 gtk_rbtree_reorder_invert_func (gconstpointer a,
 789                                 gconstpointer b)
 790 {
 791   return ((GtkRBReorder *) a)->invert_order - ((GtkRBReorder *) b)->invert_order;
 792 }
 793
 794 static void
 795 gtk_rbtree_reorder_fixup (GtkRBTree *tree,
 796                           GtkRBNode *node)
 797 {
 798   if (_gtk_rbtree_is_nil (node))
 799     return;
 800
 801   node->total_count = 1;
 802
 803   if (!_gtk_rbtree_is_nil (node->left))
 804     {
 805       gtk_rbtree_reorder_fixup (tree, node->left);
 806       node->offset += node->left->offset;
 807       node->total_count += node->left->total_count;
 808     }
 809   if (!_gtk_rbtree_is_nil (node->right))
 810     {
 811       gtk_rbtree_reorder_fixup (tree, node->right);
 812       node->offset += node->right->offset;
 813       node->total_count += node->right->total_count;
 814     }
 815
 816   if (node->children)
 817     {
 818       node->offset += node->children->root->offset;
 819       node->total_count += node->children->root->total_count;
 820     }
 821
 822   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
 823       (!_gtk_rbtree_is_nil (node->right) && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 824       (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 825       (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 826     GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 827   else
 828     GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 829 }
 830
 831 /* It basically pulls everything out of the tree, rearranges it, and puts it
 832  * back together.  Our strategy is to keep the old RBTree intact, and just
 833  * rearrange the contents.  When that is done, we go through and update the
 834  * heights.  There is probably a more elegant way to write this function.  If
 835  * anyone wants to spend the time writing it, patches will be accepted.
 836  */
 837 void
 838 _gtk_rbtree_reorder (GtkRBTree *tree,
 839                      gint      *new_order,
 840                      gint       length)
 841 {
 842   GtkRBReorder reorder = { NULL };
 843   GArray *array;
 844   GtkRBNode *node;
 845   gint i;
 846
 847   g_return_if_fail (tree != NULL);
 848   g_return_if_fail (length > 0);
 849   g_return_if_fail (tree->root->count == length);
 850
 851   /* Sort the trees values in the new tree. */
 852   array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
 853   for (i = 0; i < length; i++)
 854     {
 855       reorder.order = new_order[i];
 856       reorder.invert_order = i;
 857       g_array_append_val (array, reorder);
 858     }
 859
 860   g_array_sort(array, gtk_rbtree_reorder_sort_func);
 861
 862   /* rewind node*/
 863   node = _gtk_rbtree_first (tree);
 864
 865   for (i = 0; i < length; i++)
 866     {
 867       g_assert (!_gtk_rbtree_is_nil (node));
 868       g_array_index (array, GtkRBReorder, i).children = node->children;
 869       g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
 870       g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
 871
 872       node = _gtk_rbtree_next (tree, node);
 873     }
 874
 875   g_array_sort (array, gtk_rbtree_reorder_invert_func);
 876
 877   /* rewind node*/
 878   node = _gtk_rbtree_first (tree);
 879
 880   /* Go through the tree and change the values to the new ones. */
 881   for (i = 0; i < length; i++)
 882     {
 883       reorder = g_array_index (array, GtkRBReorder, i);
 884       node->children = reorder.children;
 885       if (node->children)
 886         node->children->parent_node = node;
 887       node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
 888       /* We temporarily set the height to this. */
 889       node->offset = reorder.height;
 890       node = _gtk_rbtree_next (tree, node);
 891     }
 892   gtk_rbtree_reorder_fixup (tree, tree->root);
 893
 894   g_array_free (array, TRUE);
 895 }
 896
 897
 898 gint
 899 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 900                               GtkRBNode *node)
 901 {
 902   GtkRBNode *last;
 903   gint retval;
 904
 905   g_assert (node);
 906   g_assert (node->left);
 907
 908   retval = node->left->offset;
 909
 910   while (tree && node && !_gtk_rbtree_is_nil (node))
 911     {
 912       last = node;
 913       node = node->parent;
 914
 915       /* Add left branch, plus children, iff we came from the right */
 916       if (node->right == last)
 917         retval += node->offset - node->right->offset;
 918
 919       if (_gtk_rbtree_is_nil (node))
 920         {
 921           node = tree->parent_node;
 922           tree = tree->parent_tree;
 923
 924           /* Add the parent node, plus the left branch. */
 925           if (node)
 926             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 927         }
 928     }
 929   return retval;
 930 }
 931
 932 guint
 933 _gtk_rbtree_node_get_index (GtkRBTree *tree,
 934                             GtkRBNode *node)
 935 {
 936   GtkRBNode *last;
 937   guint retval;
 938
 939   g_assert (node);
 940   g_assert (node->left);
 941
 942   retval = node->left->total_count;
 943
 944   while (tree && node && !_gtk_rbtree_is_nil (node))
 945     {
 946       last = node;
 947       node = node->parent;
 948
 949       /* Add left branch, plus children, iff we came from the right */
 950       if (node->right == last)
 951         retval += node->total_count - node->right->total_count;
 952
 953       if (_gtk_rbtree_is_nil (node))
 954         {
 955           node = tree->parent_node;
 956           tree = tree->parent_tree;
 957
 958           /* Add the parent node, plus the left branch. */
 959           if (node)
 960             retval += node->left->total_count + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
 961         }
 962     }
 963
 964   return retval;
 965 }
 966
 967 gint
 968 _gtk_rbtree_real_find_offset (GtkRBTree  *tree,
 969                               gint        height,
 970                               GtkRBTree **new_tree,
 971                               GtkRBNode **new_node)
 972 {
 973   GtkRBNode *tmp_node;
 974
 975   g_assert (tree);
 976
 977   if (height < 0)
 978     {
 979       *new_tree = NULL;
 980       *new_node = NULL;
 981
 982       return 0;
 983     }
 984
 985
 986   tmp_node = tree->root;
 987   while (!_gtk_rbtree_is_nil (tmp_node) &&
 988          (tmp_node->left->offset > height ||
 989           (tmp_node->offset - tmp_node->right->offset) < height))
 990     {
 991       if (tmp_node->left->offset > height)
 992         tmp_node = tmp_node->left;
 993       else
 994         {
 995           height -= (tmp_node->offset - tmp_node->right->offset);
 996           tmp_node = tmp_node->right;
 997         }
 998     }
 999   if (_gtk_rbtree_is_nil (tmp_node))
1000     {
1001       *new_tree = NULL;
1002       *new_node = NULL;
1003       return 0;
1004     }
1005   if (tmp_node->children)
1006     {
1007       if ((tmp_node->offset -
1008            tmp_node->right->offset -
1009            tmp_node->children->root->offset) > height)
1010         {
1011           *new_tree = tree;
1012           *new_node = tmp_node;
1013           return (height - tmp_node->left->offset);
1014         }
1015       return _gtk_rbtree_real_find_offset (tmp_node->children,
1016                                            height - tmp_node->left->offset -
1017                                            (tmp_node->offset -
1018                                             tmp_node->left->offset -
1019                                             tmp_node->right->offset -
1020                                             tmp_node->children->root->offset),
1021                                            new_tree,
1022                                            new_node);
1023     }
1024   *new_tree = tree;
1025   *new_node = tmp_node;
1026   return (height - tmp_node->left->offset);
1027 }
1028
1029 gint
1030 _gtk_rbtree_find_offset (GtkRBTree  *tree,
1031                               gint        height,
1032                               GtkRBTree **new_tree,
1033                               GtkRBNode **new_node)
1034 {
1035   g_assert (tree);
1036
1037   if ((height < 0) ||
1038       (height >= tree->root->offset))
1039     {
1040       *new_tree = NULL;
1041       *new_node = NULL;
1042
1043       return 0;
1044     }
1045   return _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1046 }
1047
1048 gboolean
1049 _gtk_rbtree_find_index (GtkRBTree  *tree,
1050                         guint       index,
1051                         GtkRBTree **new_tree,
1052                         GtkRBNode **new_node)
1053 {
1054   GtkRBNode *tmp_node;
1055
1056   g_assert (tree);
1057
1058   tmp_node = tree->root;
1059   while (!_gtk_rbtree_is_nil (tmp_node))
1060     {
1061       if (tmp_node->left->total_count > index)
1062         {
1063           tmp_node = tmp_node->left;
1064         }
1065       else if (tmp_node->total_count - tmp_node->right->total_count <= index)
1066         {
1067           index -= tmp_node->total_count - tmp_node->right->total_count;
1068           tmp_node = tmp_node->right;
1069         }
1070       else
1071         {
1072           index -= tmp_node->left->total_count;
1073           break;
1074         }
1075     }
1076   if (_gtk_rbtree_is_nil (tmp_node))
1077     {
1078       *new_tree = NULL;
1079       *new_node = NULL;
1080       return FALSE;
1081     }
1082
1083   if (index > 0)
1084     {
1085       g_assert (tmp_node->children);
1086
1087       return _gtk_rbtree_find_index (tmp_node->children,
1088                                      index - 1,
1089                                      new_tree,
1090                                      new_node);
1091     }
1092
1093   *new_tree = tree;
1094   *new_node = tmp_node;
1095   return TRUE;
1096 }
1097
1098 void
1099 _gtk_rbtree_remove_node (GtkRBTree *tree,
1100                          GtkRBNode *node)
1101 {
1102   GtkRBNode *x, *y;
1103   gint y_height;
1104   guint y_total_count;
1105
1106   g_return_if_fail (tree != NULL);
1107   g_return_if_fail (node != NULL);
1108
1109
1110 #ifdef G_ENABLE_DEBUG
1111   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1112     {
1113       g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1114       _gtk_rbtree_debug_spew (tree);
1115       _gtk_rbtree_test (G_STRLOC, tree);
1116     }
1117 #endif /* G_ENABLE_DEBUG */
1118
1119   /* make sure we're deleting a node that's actually in the tree */
1120   for (x = node; !_gtk_rbtree_is_nil (x->parent); x = x->parent)
1121     ;
1122   g_return_if_fail (x == tree->root);
1123
1124 #ifdef G_ENABLE_DEBUG
1125   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1126     _gtk_rbtree_test (G_STRLOC, tree);
1127 #endif
1128
1129   if (_gtk_rbtree_is_nil (node->left) ||
1130       _gtk_rbtree_is_nil (node->right))
1131     {
1132       y = node;
1133     }
1134   else
1135     {
1136       y = node->right;
1137
1138       while (!_gtk_rbtree_is_nil (y->left))
1139         y = y->left;
1140     }
1141
1142   y_height = GTK_RBNODE_GET_HEIGHT (y)
1143              + (y->children ? y->children->root->offset : 0);
1144   y_total_count = 1 + (y->children ? y->children->root->total_count : 0);
1145
1146   /* x is y's only child, or nil */
1147   if (!_gtk_rbtree_is_nil (y->left))
1148     x = y->left;
1149   else
1150     x = y->right;
1151
1152   /* remove y from the parent chain */
1153   if (!_gtk_rbtree_is_nil (x))
1154     x->parent = y->parent;
1155   if (!_gtk_rbtree_is_nil (y->parent))
1156     {
1157       if (y == y->parent->left)
1158         y->parent->left = x;
1159       else
1160         y->parent->right = x;
1161     }
1162   else
1163     {
1164       tree->root = x;
1165     }
1166
1167   /* We need to clean up the validity of the tree.
1168    */
1169   gtk_rbnode_adjust (tree, y, -1, - y_total_count, - y_height);
1170
1171   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1172     _gtk_rbtree_remove_node_fixup (tree, x, y->parent);
1173
1174   if (y != node)
1175     {
1176       gint node_height, node_total_count;
1177
1178       /* We want to see how much we remove from the aggregate values.
1179        * This is all the children we remove plus the node's values.
1180        */
1181       node_height = GTK_RBNODE_GET_HEIGHT (node)
1182                     + (node->children ? node->children->root->offset : 0);
1183       node_total_count = 1
1184                          + (node->children ? node->children->root->total_count : 0);
1185
1186       /* Move the node over */
1187       if (GTK_RBNODE_GET_COLOR (node) != GTK_RBNODE_GET_COLOR (y))
1188         y->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
1189
1190       y->left = node->left;
1191       if (!_gtk_rbtree_is_nil (y->left))
1192         y->left->parent = y;
1193       y->right = node->right;
1194       if (!_gtk_rbtree_is_nil (y->right))
1195         y->right->parent = y;
1196       y->parent = node->parent;
1197       if (!_gtk_rbtree_is_nil (y->parent))
1198         {
1199           if (y->parent->left == node)
1200             y->parent->left = y;
1201           else
1202             y->parent->right = y;
1203         }
1204       else
1205         {
1206           tree->root = y;
1207         }
1208       y->count = node->count;
1209       y->total_count = node->total_count;
1210       y->offset = node->offset;
1211
1212       gtk_rbnode_adjust (tree, y,
1213                          0,
1214                          y_total_count - node_total_count,
1215                          y_height - node_height);
1216     }
1217
1218   _gtk_rbnode_free (node);
1219
1220 #ifdef G_ENABLE_DEBUG
1221   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1222     {
1223       g_print ("_gtk_rbtree_remove_node finished...\n");
1224       _gtk_rbtree_debug_spew (tree);
1225       g_print ("\n\n");
1226       _gtk_rbtree_test (G_STRLOC, tree);
1227     }
1228 #endif /* G_ENABLE_DEBUG */
1229 }
1230
1231 GtkRBNode *
1232 _gtk_rbtree_first (GtkRBTree *tree)
1233 {
1234   GtkRBNode *node;
1235
1236   node = tree->root;
1237
1238   if (_gtk_rbtree_is_nil (node))
1239     return NULL;
1240
1241   while (!_gtk_rbtree_is_nil (node->left))
1242     node = node->left;
1243
1244   return node;
1245 }
1246
1247 GtkRBNode *
1248 _gtk_rbtree_next (GtkRBTree *tree,
1249                   GtkRBNode *node)
1250 {
1251   g_return_val_if_fail (tree != NULL, NULL);
1252   g_return_val_if_fail (node != NULL, NULL);
1253
1254   /* Case 1: the node's below us. */
1255   if (!_gtk_rbtree_is_nil (node->right))
1256     {
1257       node = node->right;
1258       while (!_gtk_rbtree_is_nil (node->left))
1259         node = node->left;
1260       return node;
1261     }
1262
1263   /* Case 2: it's an ancestor */
1264   while (!_gtk_rbtree_is_nil (node->parent))
1265     {
1266       if (node->parent->right == node)
1267         node = node->parent;
1268       else
1269         return (node->parent);
1270     }
1271
1272   /* Case 3: There is no next node */
1273   return NULL;
1274 }
1275
1276 GtkRBNode *
1277 _gtk_rbtree_prev (GtkRBTree *tree,
1278                   GtkRBNode *node)
1279 {
1280   g_return_val_if_fail (tree != NULL, NULL);
1281   g_return_val_if_fail (node != NULL, NULL);
1282
1283   /* Case 1: the node's below us. */
1284   if (!_gtk_rbtree_is_nil (node->left))
1285     {
1286       node = node->left;
1287       while (!_gtk_rbtree_is_nil (node->right))
1288         node = node->right;
1289       return node;
1290     }
1291
1292   /* Case 2: it's an ancestor */
1293   while (!_gtk_rbtree_is_nil (node->parent))
1294     {
1295       if (node->parent->left == node)
1296         node = node->parent;
1297       else
1298         return (node->parent);
1299     }
1300
1301   /* Case 3: There is no next node */
1302   return NULL;
1303 }
1304
1305 void
1306 _gtk_rbtree_next_full (GtkRBTree  *tree,
1307                        GtkRBNode  *node,
1308                        GtkRBTree **new_tree,
1309                        GtkRBNode **new_node)
1310 {
1311   g_return_if_fail (tree != NULL);
1312   g_return_if_fail (node != NULL);
1313   g_return_if_fail (new_tree != NULL);
1314   g_return_if_fail (new_node != NULL);
1315
1316   if (node->children)
1317     {
1318       *new_tree = node->children;
1319       *new_node = (*new_tree)->root;
1320       while (!_gtk_rbtree_is_nil ((*new_node)->left))
1321         *new_node = (*new_node)->left;
1322       return;
1323     }
1324
1325   *new_tree = tree;
1326   *new_node = _gtk_rbtree_next (tree, node);
1327
1328   while ((*new_node == NULL) &&
1329          (*new_tree != NULL))
1330     {
1331       *new_node = (*new_tree)->parent_node;
1332       *new_tree = (*new_tree)->parent_tree;
1333       if (*new_tree)
1334         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1335     }
1336 }
1337
1338 void
1339 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1340                        GtkRBNode  *node,
1341                        GtkRBTree **new_tree,
1342                        GtkRBNode **new_node)
1343 {
1344   g_return_if_fail (tree != NULL);
1345   g_return_if_fail (node != NULL);
1346   g_return_if_fail (new_tree != NULL);
1347   g_return_if_fail (new_node != NULL);
1348
1349   *new_tree = tree;
1350   *new_node = _gtk_rbtree_prev (tree, node);
1351
1352   if (*new_node == NULL)
1353     {
1354       *new_node = (*new_tree)->parent_node;
1355       *new_tree = (*new_tree)->parent_tree;
1356     }
1357   else
1358     {
1359       while ((*new_node)->children)
1360         {
1361           *new_tree = (*new_node)->children;
1362           *new_node = (*new_tree)->root;
1363           while (!_gtk_rbtree_is_nil ((*new_node)->right))
1364             *new_node = (*new_node)->right;
1365         }
1366     }
1367 }
1368
1369 gint
1370 _gtk_rbtree_get_depth (GtkRBTree *tree)
1371 {
1372   GtkRBTree *tmp_tree;
1373   gint depth = 0;
1374
1375   tmp_tree = tree->parent_tree;
1376   while (tmp_tree)
1377     {
1378       ++depth;
1379       tmp_tree = tmp_tree->parent_tree;
1380     }
1381
1382   return depth;
1383 }
1384
1385 static void
1386 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1387                                 GtkRBNode             *node,
1388                                 GtkRBTreeTraverseFunc  func,
1389                                 gpointer               data)
1390 {
1391   if (_gtk_rbtree_is_nil (node))
1392     return;
1393
1394   (* func) (tree, node, data);
1395   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1396   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1397 }
1398
1399 static void
1400 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1401                                  GtkRBNode             *node,
1402                                  GtkRBTreeTraverseFunc  func,
1403                                  gpointer               data)
1404 {
1405   if (_gtk_rbtree_is_nil (node))
1406     return;
1407
1408   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1409   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1410   (* func) (tree, node, data);
1411 }
1412
1413 void
1414 _gtk_rbtree_traverse (GtkRBTree             *tree,
1415                       GtkRBNode             *node,
1416                       GTraverseType          order,
1417                       GtkRBTreeTraverseFunc  func,
1418                       gpointer               data)
1419 {
1420   g_return_if_fail (tree != NULL);
1421   g_return_if_fail (node != NULL);
1422   g_return_if_fail (func != NULL);
1423   g_return_if_fail (order <= G_LEVEL_ORDER);
1424
1425   switch (order)
1426     {
1427     case G_PRE_ORDER:
1428       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1429       break;
1430     case G_POST_ORDER:
1431       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1432       break;
1433     case G_IN_ORDER:
1434     case G_LEVEL_ORDER:
1435     default:
1436       g_warning ("unsupported traversal order.");
1437       break;
1438     }
1439 }
1440
1441 static inline
1442 void _fixup_validation (GtkRBTree *tree,
1443                         GtkRBNode *node)
1444 {
1445   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1446       GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1447       (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1448       (!_gtk_rbtree_is_nil (node->right) && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1449       (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1450     {
1451       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1452     }
1453   else
1454     {
1455       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1456     }
1457 }
1458
1459 static inline
1460 void _fixup_total_count (GtkRBTree *tree,
1461                     GtkRBNode *node)
1462 {
1463   node->total_count = 1 +
1464     (node->children != NULL ? node->children->root->total_count : 0) +
1465     node->left->total_count + node->right->total_count;
1466 }
1467
1468 #ifdef G_ENABLE_DEBUG
1469 static guint
1470 get_total_count (GtkRBNode *node)
1471 {
1472   guint child_total = 0;
1473
1474   child_total += (guint) node->left->total_count;
1475   child_total += (guint) node->right->total_count;
1476
1477   if (node->children)
1478     child_total += (guint) node->children->root->total_count;
1479
1480   return child_total + 1;
1481 }
1482
1483 static guint
1484 count_total (GtkRBTree *tree,
1485              GtkRBNode *node)
1486 {
1487   guint res;
1488
1489   if (_gtk_rbtree_is_nil (node))
1490     return 0;
1491
1492   res =
1493     count_total (tree, node->left) +
1494     count_total (tree, node->right) +
1495     (guint)1 +
1496     (node->children ? count_total (node->children, node->children->root) : 0);
1497
1498   if (res != node->total_count)
1499     g_print ("total count incorrect for node\n");
1500
1501   if (get_total_count (node) != node->total_count)
1502     g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1503
1504   return res;
1505 }
1506
1507 static gint
1508 _count_nodes (GtkRBTree *tree,
1509               GtkRBNode *node)
1510 {
1511   gint res;
1512   if (_gtk_rbtree_is_nil (node))
1513     return 0;
1514
1515   g_assert (node->left);
1516   g_assert (node->right);
1517
1518   res = (_count_nodes (tree, node->left) +
1519          _count_nodes (tree, node->right) + 1);
1520
1521   if (res != node->count)
1522     g_print ("Tree failed\n");
1523   return res;
1524 }
1525
1526 static void
1527 _gtk_rbtree_test_height (GtkRBTree *tree,
1528                          GtkRBNode *node)
1529 {
1530   gint computed_offset = 0;
1531
1532   /* This whole test is sort of a useless truism. */
1533
1534   if (!_gtk_rbtree_is_nil (node->left))
1535     computed_offset += node->left->offset;
1536
1537   if (!_gtk_rbtree_is_nil (node->right))
1538     computed_offset += node->right->offset;
1539
1540   if (node->children && !_gtk_rbtree_is_nil (node->children->root))
1541     computed_offset += node->children->root->offset;
1542
1543   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1544     g_error ("node has broken offset\n");
1545
1546   if (!_gtk_rbtree_is_nil (node->left))
1547     _gtk_rbtree_test_height (tree, node->left);
1548
1549   if (!_gtk_rbtree_is_nil (node->right))
1550     _gtk_rbtree_test_height (tree, node->right);
1551
1552   if (node->children && !_gtk_rbtree_is_nil (node->children->root))
1553     _gtk_rbtree_test_height (node->children, node->children->root);
1554 }
1555
1556 static void
1557 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1558                         GtkRBNode *node,
1559                          gint      expected_dirtyness)
1560 {
1561
1562   if (expected_dirtyness)
1563     {
1564       g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1565                 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1566                 (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1567                 (!_gtk_rbtree_is_nil (node->right) && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1568                 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1569     }
1570   else
1571     {
1572       g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1573                 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1574       if (!_gtk_rbtree_is_nil (node->left))
1575         g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1576       if (!_gtk_rbtree_is_nil (node->right))
1577         g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1578       if (node->children != NULL)
1579         g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1580     }
1581
1582   if (!_gtk_rbtree_is_nil (node->left))
1583     _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1584   if (!_gtk_rbtree_is_nil (node->right))
1585     _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1586   if (node->children != NULL && !_gtk_rbtree_is_nil (node->children->root))
1587     _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1588 }
1589
1590 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1591
1592 static void
1593 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1594                                    GtkRBNode *node)
1595 {
1596   g_assert (!_gtk_rbtree_is_nil (node));
1597
1598   g_assert (node->left != NULL);
1599   g_assert (node->right != NULL);
1600   g_assert (node->parent != NULL);
1601
1602   if (!_gtk_rbtree_is_nil (node->left))
1603     {
1604       g_assert (node->left->parent == node);
1605       _gtk_rbtree_test_structure_helper (tree, node->left);
1606     }
1607   if (!_gtk_rbtree_is_nil (node->right))
1608     {
1609       g_assert (node->right->parent == node);
1610       _gtk_rbtree_test_structure_helper (tree, node->right);
1611     }
1612
1613   if (node->children != NULL)
1614     {
1615       g_assert (node->children->parent_tree == tree);
1616       g_assert (node->children->parent_node == node);
1617
1618       _gtk_rbtree_test_structure (node->children);
1619     }
1620 }
1621 static void
1622 _gtk_rbtree_test_structure (GtkRBTree *tree)
1623 {
1624   g_assert (tree->root);
1625   if (_gtk_rbtree_is_nil (tree->root))
1626     return;
1627
1628   g_assert (_gtk_rbtree_is_nil (tree->root->parent));
1629   _gtk_rbtree_test_structure_helper (tree, tree->root);
1630 }
1631
1632 static void
1633 _gtk_rbtree_test (const gchar *where,
1634                   GtkRBTree   *tree)
1635 {
1636   GtkRBTree *tmp_tree;
1637
1638   if (tree == NULL)
1639     return;
1640
1641   /* Test the entire tree */
1642   tmp_tree = tree;
1643   while (tmp_tree->parent_tree)
1644     tmp_tree = tmp_tree->parent_tree;
1645
1646   if (_gtk_rbtree_is_nil (tmp_tree->root))
1647     return;
1648
1649   _gtk_rbtree_test_structure (tmp_tree);
1650
1651   g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1652              _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1653
1654
1655   _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1656   _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1657   g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
1658 }
1659
1660 static void
1661 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1662                                GtkRBNode *node,
1663                                gint       depth)
1664 {
1665   gint i;
1666   for (i = 0; i < depth; i++)
1667     g_print ("\t");
1668
1669   g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1670            node,
1671            (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1672            node->offset,
1673            node->total_count,
1674            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1675            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1676            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1677   if (node->children != NULL)
1678     {
1679       g_print ("Looking at child.\n");
1680       _gtk_rbtree_debug_spew (node->children);
1681       g_print ("Done looking at child.\n");
1682     }
1683   if (!_gtk_rbtree_is_nil (node->left))
1684     {
1685       _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1686     }
1687   if (!_gtk_rbtree_is_nil (node->right))
1688     {
1689       _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1690     }
1691 }
1692
1693 static void
1694 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1695 {
1696   g_return_if_fail (tree != NULL);
1697
1698   if (_gtk_rbtree_is_nil (tree->root))
1699     g_print ("Empty tree...\n");
1700   else
1701     _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1702 }
1703 #endif /* G_ENABLE_DEBUG */