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