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