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