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       g_assert (tree->root == tree->nil);
 476       tree->root = node;
 477       tmp_node = tree->parent_node;
 478       tmp_tree = tree->parent_tree;
 479     }
 480
 481   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 482     {
 483       /* We only want to propagate the count if we are in the tree we
 484        * started in. */
 485       if (tmp_tree == tree)
 486         tmp_node->count++;
 487
 488       tmp_node->total_count += 1;
 489       tmp_node->offset += height;
 490       tmp_node = tmp_node->parent;
 491       if (tmp_node == tmp_tree->nil)
 492         {
 493           tmp_node = tmp_tree->parent_node;
 494           tmp_tree = tmp_tree->parent_tree;
 495         }
 496     }
 497
 498   if (valid)
 499     _gtk_rbtree_node_mark_valid (tree, node);
 500   else
 501     _gtk_rbtree_node_mark_invalid (tree, node);
 502
 503   _gtk_rbtree_insert_fixup (tree, node);
 504
 505 #ifdef G_ENABLE_DEBUG
 506   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 507     {
 508       g_print ("_gtk_rbtree_insert_after finished...\n");
 509       _gtk_rbtree_debug_spew (tree);
 510       g_print ("\n\n");
 511       _gtk_rbtree_test (G_STRLOC, tree);
 512     }
 513 #endif /* G_ENABLE_DEBUG */
 514
 515   return node;
 516 }
 517
 518 GtkRBNode *
 519 _gtk_rbtree_insert_before (GtkRBTree *tree,
 520                            GtkRBNode *current,
 521                            gint       height,
 522                            gboolean   valid)
 523 {
 524   GtkRBNode *node;
 525   gboolean left = TRUE;
 526   GtkRBNode *tmp_node;
 527   GtkRBTree *tmp_tree;
 528
 529 #ifdef G_ENABLE_DEBUG
 530   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 531     {
 532       g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current);
 533       _gtk_rbtree_debug_spew (tree);
 534       _gtk_rbtree_test (G_STRLOC, tree);
 535     }
 536 #endif /* G_ENABLE_DEBUG */
 537
 538   if (current != NULL && current->left != tree->nil)
 539     {
 540       current = current->left;
 541       while (current->right != tree->nil)
 542         current = current->right;
 543       left = FALSE;
 544     }
 545
 546   /* setup new node */
 547   node = _gtk_rbnode_new (tree, height);
 548   node->parent = (current?current:tree->nil);
 549
 550   /* insert node in tree */
 551   if (current)
 552     {
 553       if (left)
 554         current->left = node;
 555       else
 556         current->right = node;
 557       tmp_node = node->parent;
 558       tmp_tree = tree;
 559     }
 560   else
 561     {
 562       g_assert (tree->root == tree->nil);
 563       tree->root = node;
 564       tmp_node = tree->parent_node;
 565       tmp_tree = tree->parent_tree;
 566     }
 567
 568   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 569     {
 570       /* We only want to propagate the count if we are in the tree we
 571        * started in. */
 572       if (tmp_tree == tree)
 573         tmp_node->count++;
 574
 575       tmp_node->total_count += 1;
 576       tmp_node->offset += height;
 577       tmp_node = tmp_node->parent;
 578       if (tmp_node == tmp_tree->nil)
 579         {
 580           tmp_node = tmp_tree->parent_node;
 581           tmp_tree = tmp_tree->parent_tree;
 582         }
 583     }
 584
 585   if (valid)
 586     _gtk_rbtree_node_mark_valid (tree, node);
 587   else
 588     _gtk_rbtree_node_mark_invalid (tree, node);
 589
 590   _gtk_rbtree_insert_fixup (tree, node);
 591
 592 #ifdef G_ENABLE_DEBUG
 593   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 594     {
 595       g_print ("_gtk_rbtree_insert_before finished...\n");
 596       _gtk_rbtree_debug_spew (tree);
 597       g_print ("\n\n");
 598       _gtk_rbtree_test (G_STRLOC, tree);
 599     }
 600 #endif /* G_ENABLE_DEBUG */
 601
 602   return node;
 603 }
 604
 605 GtkRBNode *
 606 _gtk_rbtree_find_count (GtkRBTree *tree,
 607                         gint       count)
 608 {
 609   GtkRBNode *node;
 610
 611   node = tree->root;
 612   while (node != tree->nil && (node->left->count + 1 != count))
 613     {
 614       if (node->left->count >= count)
 615         node = node->left;
 616       else
 617         {
 618           count -= (node->left->count + 1);
 619           node = node->right;
 620         }
 621     }
 622   if (node == tree->nil)
 623     return NULL;
 624   return node;
 625 }
 626
 627 void
 628 _gtk_rbtree_node_set_height (GtkRBTree *tree,
 629                              GtkRBNode *node,
 630                              gint       height)
 631 {
 632   gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
 633   GtkRBNode *tmp_node = node;
 634   GtkRBTree *tmp_tree = tree;
 635
 636   if (diff == 0)
 637     return;
 638
 639   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 640     {
 641       tmp_node->offset += diff;
 642       tmp_node = tmp_node->parent;
 643       if (tmp_node == tmp_tree->nil)
 644         {
 645           tmp_node = tmp_tree->parent_node;
 646           tmp_tree = tmp_tree->parent_tree;
 647         }
 648     }
 649 #ifdef G_ENABLE_DEBUG
 650   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
 651     _gtk_rbtree_test (G_STRLOC, tree);
 652 #endif
 653 }
 654
 655 void
 656 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
 657                                GtkRBNode *node)
 658 {
 659   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 660     return;
 661
 662   GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 663   do
 664     {
 665       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
 666         return;
 667       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 668       node = node->parent;
 669       if (node == tree->nil)
 670         {
 671           node = tree->parent_node;
 672           tree = tree->parent_tree;
 673         }
 674     }
 675   while (node);
 676 }
 677
 678 #if 0
 679 /* Draconian version. */
 680 void
 681 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
 682                                GtkRBNode *node)
 683 {
 684   GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 685   do
 686     {
 687       _fixup_validation (tree, node);
 688       node = node->parent;
 689       if (node == tree->nil)
 690         {
 691           node = tree->parent_node;
 692           tree = tree->parent_tree;
 693         }
 694     }
 695   while (node);
 696 }
 697 #endif
 698
 699 void
 700 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 701                              GtkRBNode *node)
 702 {
 703   if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
 704       (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))
 705     return;
 706
 707   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
 708   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 709
 710   do
 711     {
 712       if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||
 713           (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||
 714           (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 715           (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 716           (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
 717         return;
 718
 719       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 720       node = node->parent;
 721       if (node == tree->nil)
 722         {
 723           node = tree->parent_node;
 724           tree = tree->parent_tree;
 725         }
 726     }
 727   while (node);
 728 }
 729
 730 #if 0
 731 /* Draconian version */
 732 void
 733 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 734                              GtkRBNode *node)
 735 {
 736   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
 737   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 738
 739   do
 740     {
 741       _fixup_validation (tree, node);
 742       node = node->parent;
 743       if (node == tree->nil)
 744         {
 745           node = tree->parent_node;
 746           tree = tree->parent_tree;
 747         }
 748     }
 749   while (node);
 750 }
 751 #endif
 752 /* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
 753  */
 754 void
 755 _gtk_rbtree_column_invalid (GtkRBTree *tree)
 756 {
 757   GtkRBNode *node;
 758
 759   if (tree == NULL)
 760     return;
 761   node = tree->root;
 762   g_assert (node);
 763
 764   while (node->left != tree->nil)
 765     node = node->left;
 766
 767   do
 768     {
 769       if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))
 770         GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 771       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 772
 773       if (node->children)
 774         _gtk_rbtree_column_invalid (node->children);
 775     }
 776   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 777 }
 778
 779 void
 780 _gtk_rbtree_mark_invalid (GtkRBTree *tree)
 781 {
 782   GtkRBNode *node;
 783
 784   if (tree == NULL)
 785     return;
 786   node = tree->root;
 787   g_assert (node);
 788
 789   while (node->left != tree->nil)
 790     node = node->left;
 791
 792   do
 793     {
 794       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 795       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 796
 797       if (node->children)
 798         _gtk_rbtree_mark_invalid (node->children);
 799     }
 800   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 801 }
 802
 803 void
 804 _gtk_rbtree_set_fixed_height (GtkRBTree *tree,
 805                               gint       height,
 806                               gboolean   mark_valid)
 807 {
 808   GtkRBNode *node;
 809
 810   if (tree == NULL)
 811     return;
 812
 813   node = tree->root;
 814   g_assert (node);
 815
 816   while (node->left != tree->nil)
 817     node = node->left;
 818
 819   do
 820     {
 821       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 822         {
 823           _gtk_rbtree_node_set_height (tree, node, height);
 824           if (mark_valid)
 825             _gtk_rbtree_node_mark_valid (tree, node);
 826         }
 827
 828       if (node->children)
 829         _gtk_rbtree_set_fixed_height (node->children, height, mark_valid);
 830     }
 831   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 832 }
 833
 834 typedef struct _GtkRBReorder
 835 {
 836   GtkRBTree *children;
 837   gint height;
 838   gint flags;
 839   gint order;
 840   gint invert_order;
 841   guint total_count;
 842 } GtkRBReorder;
 843
 844 static int
 845 gtk_rbtree_reorder_sort_func (gconstpointer a,
 846                               gconstpointer b)
 847 {
 848   return ((GtkRBReorder *) a)->order - ((GtkRBReorder *) b)->order;
 849 }
 850
 851 static int
 852 gtk_rbtree_reorder_invert_func (gconstpointer a,
 853                                 gconstpointer b)
 854 {
 855   return ((GtkRBReorder *) a)->invert_order - ((GtkRBReorder *) b)->invert_order;
 856 }
 857
 858 static void
 859 gtk_rbtree_reorder_fixup (GtkRBTree *tree,
 860                           GtkRBNode *node)
 861 {
 862   if (node == tree->nil)
 863     return;
 864
 865   node->total_count = 1;
 866
 867   if (node->left != tree->nil)
 868     {
 869       gtk_rbtree_reorder_fixup (tree, node->left);
 870       node->offset += node->left->offset;
 871       node->total_count += node->left->total_count;
 872     }
 873   if (node->right != tree->nil)
 874     {
 875       gtk_rbtree_reorder_fixup (tree, node->right);
 876       node->offset += node->right->offset;
 877       node->total_count += node->right->total_count;
 878     }
 879
 880   if (node->children)
 881     {
 882       node->offset += node->children->root->offset;
 883       node->total_count += node->children->root->total_count;
 884     }
 885
 886   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
 887       (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 888       (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 889       (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 890     GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 891   else
 892     GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 893 }
 894
 895 /* It basically pulls everything out of the tree, rearranges it, and puts it
 896  * back together.  Our strategy is to keep the old RBTree intact, and just
 897  * rearrange the contents.  When that is done, we go through and update the
 898  * heights.  There is probably a more elegant way to write this function.  If
 899  * anyone wants to spend the time writing it, patches will be accepted.
 900  */
 901 void
 902 _gtk_rbtree_reorder (GtkRBTree *tree,
 903                      gint      *new_order,
 904                      gint       length)
 905 {
 906   GtkRBReorder reorder = { NULL };
 907   GArray *array;
 908   GtkRBNode *node;
 909   gint i;
 910
 911   g_return_if_fail (tree != NULL);
 912   g_return_if_fail (length > 0);
 913   g_return_if_fail (tree->root->count == length);
 914
 915   /* Sort the trees values in the new tree. */
 916   array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
 917   for (i = 0; i < length; i++)
 918     {
 919       reorder.order = new_order[i];
 920       reorder.invert_order = i;
 921       g_array_append_val (array, reorder);
 922     }
 923
 924   g_array_sort(array, gtk_rbtree_reorder_sort_func);
 925
 926   /* rewind node*/
 927   node = tree->root;
 928   while (node && node->left != tree->nil)
 929     node = node->left;
 930
 931   for (i = 0; i < length; i++)
 932     {
 933       g_assert (node != tree->nil);
 934       g_array_index (array, GtkRBReorder, i).children = node->children;
 935       g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
 936       g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
 937
 938       node = _gtk_rbtree_next (tree, node);
 939     }
 940
 941   g_array_sort (array, gtk_rbtree_reorder_invert_func);
 942
 943   /* rewind node*/
 944   node = tree->root;
 945   while (node && node->left != tree->nil)
 946     node = node->left;
 947
 948   /* Go through the tree and change the values to the new ones. */
 949   for (i = 0; i < length; i++)
 950     {
 951       reorder = g_array_index (array, GtkRBReorder, i);
 952       node->children = reorder.children;
 953       if (node->children)
 954         node->children->parent_node = node;
 955       node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
 956       /* We temporarily set the height to this. */
 957       node->offset = reorder.height;
 958       node = _gtk_rbtree_next (tree, node);
 959     }
 960   gtk_rbtree_reorder_fixup (tree, tree->root);
 961
 962   g_array_free (array, TRUE);
 963 }
 964
 965
 966 gint
 967 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 968                               GtkRBNode *node)
 969 {
 970   GtkRBNode *last;
 971   gint retval;
 972
 973   g_assert (node);
 974   g_assert (node->left);
 975
 976   retval = node->left->offset;
 977
 978   while (tree && node && node != tree->nil)
 979     {
 980       last = node;
 981       node = node->parent;
 982
 983       /* Add left branch, plus children, iff we came from the right */
 984       if (node->right == last)
 985         retval += node->offset - node->right->offset;
 986
 987       if (node == tree->nil)
 988         {
 989           node = tree->parent_node;
 990           tree = tree->parent_tree;
 991
 992           /* Add the parent node, plus the left branch. */
 993           if (node)
 994             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 995         }
 996     }
 997   return retval;
 998 }
 999
1000 guint
1001 _gtk_rbtree_node_get_index (GtkRBTree *tree,
1002                             GtkRBNode *node)
1003 {
1004   GtkRBNode *last;
1005   guint retval;
1006
1007   g_assert (node);
1008   g_assert (node->left);
1009
1010   retval = node->left->total_count;
1011
1012   while (tree && node && node != tree->nil)
1013     {
1014       last = node;
1015       node = node->parent;
1016
1017       /* Add left branch, plus children, iff we came from the right */
1018       if (node->right == last)
1019         retval += node->total_count - node->right->total_count;
1020
1021       if (node == tree->nil)
1022         {
1023           node = tree->parent_node;
1024           tree = tree->parent_tree;
1025
1026           /* Add the parent node, plus the left branch. */
1027           if (node)
1028             retval += node->left->total_count + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
1029         }
1030     }
1031
1032   return retval;
1033 }
1034
1035 gint
1036 _gtk_rbtree_real_find_offset (GtkRBTree  *tree,
1037                               gint        height,
1038                               GtkRBTree **new_tree,
1039                               GtkRBNode **new_node)
1040 {
1041   GtkRBNode *tmp_node;
1042
1043   g_assert (tree);
1044
1045   if (height < 0)
1046     {
1047       *new_tree = NULL;
1048       *new_node = NULL;
1049
1050       return 0;
1051     }
1052
1053
1054   tmp_node = tree->root;
1055   while (tmp_node != tree->nil &&
1056          (tmp_node->left->offset > height ||
1057           (tmp_node->offset - tmp_node->right->offset) < height))
1058     {
1059       if (tmp_node->left->offset > height)
1060         tmp_node = tmp_node->left;
1061       else
1062         {
1063           height -= (tmp_node->offset - tmp_node->right->offset);
1064           tmp_node = tmp_node->right;
1065         }
1066     }
1067   if (tmp_node == tree->nil)
1068     {
1069       *new_tree = NULL;
1070       *new_node = NULL;
1071       return 0;
1072     }
1073   if (tmp_node->children)
1074     {
1075       if ((tmp_node->offset -
1076            tmp_node->right->offset -
1077            tmp_node->children->root->offset) > height)
1078         {
1079           *new_tree = tree;
1080           *new_node = tmp_node;
1081           return (height - tmp_node->left->offset);
1082         }
1083       return _gtk_rbtree_real_find_offset (tmp_node->children,
1084                                            height - tmp_node->left->offset -
1085                                            (tmp_node->offset -
1086                                             tmp_node->left->offset -
1087                                             tmp_node->right->offset -
1088                                             tmp_node->children->root->offset),
1089                                            new_tree,
1090                                            new_node);
1091     }
1092   *new_tree = tree;
1093   *new_node = tmp_node;
1094   return (height - tmp_node->left->offset);
1095 }
1096
1097 gint
1098 _gtk_rbtree_find_offset (GtkRBTree  *tree,
1099                               gint        height,
1100                               GtkRBTree **new_tree,
1101                               GtkRBNode **new_node)
1102 {
1103   g_assert (tree);
1104
1105   if ((height < 0) ||
1106       (height >= tree->root->offset))
1107     {
1108       *new_tree = NULL;
1109       *new_node = NULL;
1110
1111       return 0;
1112     }
1113   return _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1114 }
1115
1116 gboolean
1117 _gtk_rbtree_find_index (GtkRBTree  *tree,
1118                         guint       index,
1119                         GtkRBTree **new_tree,
1120                         GtkRBNode **new_node)
1121 {
1122   GtkRBNode *tmp_node;
1123
1124   g_assert (tree);
1125
1126   tmp_node = tree->root;
1127   while (tmp_node != tree->nil)
1128     {
1129       if (tmp_node->left->total_count > index)
1130         {
1131           tmp_node = tmp_node->left;
1132         }
1133       else if (tmp_node->total_count - tmp_node->right->total_count <= index)
1134         {
1135           index -= tmp_node->total_count - tmp_node->right->total_count;
1136           tmp_node = tmp_node->right;
1137         }
1138       else
1139         {
1140           index -= tmp_node->left->total_count;
1141           break;
1142         }
1143     }
1144   if (tmp_node == tree->nil)
1145     {
1146       *new_tree = NULL;
1147       *new_node = NULL;
1148       return FALSE;
1149     }
1150
1151   if (index > 0)
1152     {
1153       g_assert (tmp_node->children);
1154
1155       return _gtk_rbtree_find_index (tmp_node->children,
1156                                      index - 1,
1157                                      new_tree,
1158                                      new_node);
1159     }
1160
1161   *new_tree = tree;
1162   *new_node = tmp_node;
1163   return TRUE;
1164 }
1165
1166 void
1167 _gtk_rbtree_remove_node (GtkRBTree *tree,
1168                          GtkRBNode *node)
1169 {
1170   GtkRBNode *x, *y;
1171   GtkRBTree *tmp_tree;
1172   GtkRBNode *tmp_node;
1173   gint y_height;
1174
1175   g_return_if_fail (tree != NULL);
1176   g_return_if_fail (node != NULL);
1177
1178
1179 #ifdef G_ENABLE_DEBUG
1180   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1181     {
1182       g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1183       _gtk_rbtree_debug_spew (tree);
1184       _gtk_rbtree_test (G_STRLOC, tree);
1185     }
1186 #endif /* G_ENABLE_DEBUG */
1187
1188   /* make sure we're deleting a node that's actually in the tree */
1189   for (x = node; x->parent != tree->nil; x = x->parent)
1190     ;
1191   g_return_if_fail (x == tree->root);
1192
1193 #ifdef G_ENABLE_DEBUG
1194   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1195     _gtk_rbtree_test (G_STRLOC, tree);
1196 #endif
1197
1198   if (node->left == tree->nil || node->right == tree->nil)
1199     {
1200       y = node;
1201     }
1202   else
1203     {
1204       y = node->right;
1205
1206       while (y->left != tree->nil)
1207         y = y->left;
1208     }
1209
1210   /* adjust count only beneath tree */
1211   for (x = y; x != tree->nil; x = x->parent)
1212     {
1213       x->count--;
1214     }
1215
1216   /* offsets and total count adjust all the way up through parent trees */
1217   y_height = GTK_RBNODE_GET_HEIGHT (y);
1218
1219   tmp_tree = tree;
1220   tmp_node = y;
1221   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1222     {
1223       tmp_node->offset -= (y_height + (y->children?y->children->root->offset:0));
1224       _fixup_validation (tmp_tree, tmp_node);
1225       _fixup_total_count (tmp_tree, tmp_node);
1226       tmp_node = tmp_node->parent;
1227       if (tmp_node == tmp_tree->nil)
1228         {
1229           tmp_node = tmp_tree->parent_node;
1230           tmp_tree = tmp_tree->parent_tree;
1231         }
1232     }
1233
1234   /* x is y's only child, or nil */
1235   if (y->left != tree->nil)
1236     x = y->left;
1237   else
1238     x = y->right;
1239
1240   /* remove y from the parent chain */
1241   x->parent = y->parent;
1242   if (y->parent != tree->nil)
1243     {
1244       if (y == y->parent->left)
1245         y->parent->left = x;
1246       else
1247         y->parent->right = x;
1248     }
1249   else
1250     {
1251       tree->root = x;
1252     }
1253
1254   /* We need to clean up the validity of the tree.
1255    */
1256
1257   tmp_tree = tree;
1258   tmp_node = x;
1259   do
1260     {
1261       /* We skip the first time, iff x is nil */
1262       if (tmp_node != tmp_tree->nil)
1263         {
1264           _fixup_validation (tmp_tree, tmp_node);
1265           _fixup_total_count (tmp_tree, tmp_node);
1266         }
1267       tmp_node = tmp_node->parent;
1268       if (tmp_node == tmp_tree->nil)
1269         {
1270           tmp_node = tmp_tree->parent_node;
1271           tmp_tree = tmp_tree->parent_tree;
1272         }
1273     }
1274   while (tmp_tree != NULL);
1275
1276   if (y != node)
1277     {
1278       gint diff;
1279
1280       /* Copy the node over */
1281       if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1282         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
1283       else
1284         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
1285       if (y->children)
1286         {
1287           node->children = y->children;
1288           node->children->parent_node = node;
1289         }
1290       else
1291         {
1292           node->children = NULL;
1293         }
1294       _fixup_validation (tree, node);
1295       _fixup_total_count (tree, node);
1296       /* We want to see how different our height is from the previous node.
1297        * To do this, we compare our current height with our supposed height.
1298        */
1299       diff = y_height - GTK_RBNODE_GET_HEIGHT (node);
1300       tmp_tree = tree;
1301       tmp_node = node;
1302
1303       while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1304         {
1305           tmp_node->offset += diff;
1306           _fixup_validation (tmp_tree, tmp_node);
1307           _fixup_total_count (tmp_tree, tmp_node);
1308           tmp_node = tmp_node->parent;
1309           if (tmp_node == tmp_tree->nil)
1310             {
1311               tmp_node = tmp_tree->parent_node;
1312               tmp_tree = tmp_tree->parent_tree;
1313             }
1314         }
1315     }
1316
1317   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1318     _gtk_rbtree_remove_node_fixup (tree, x);
1319   _gtk_rbnode_free (y);
1320
1321 #ifdef G_ENABLE_DEBUG
1322   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1323     {
1324       g_print ("_gtk_rbtree_remove_node finished...\n");
1325       _gtk_rbtree_debug_spew (tree);
1326       g_print ("\n\n");
1327       _gtk_rbtree_test (G_STRLOC, tree);
1328     }
1329 #endif /* G_ENABLE_DEBUG */
1330 }
1331
1332 GtkRBNode *
1333 _gtk_rbtree_next (GtkRBTree *tree,
1334                   GtkRBNode *node)
1335 {
1336   g_return_val_if_fail (tree != NULL, NULL);
1337   g_return_val_if_fail (node != NULL, NULL);
1338
1339   /* Case 1: the node's below us. */
1340   if (node->right != tree->nil)
1341     {
1342       node = node->right;
1343       while (node->left != tree->nil)
1344         node = node->left;
1345       return node;
1346     }
1347
1348   /* Case 2: it's an ancestor */
1349   while (node->parent != tree->nil)
1350     {
1351       if (node->parent->right == node)
1352         node = node->parent;
1353       else
1354         return (node->parent);
1355     }
1356
1357   /* Case 3: There is no next node */
1358   return NULL;
1359 }
1360
1361 GtkRBNode *
1362 _gtk_rbtree_prev (GtkRBTree *tree,
1363                   GtkRBNode *node)
1364 {
1365   g_return_val_if_fail (tree != NULL, NULL);
1366   g_return_val_if_fail (node != NULL, NULL);
1367
1368   /* Case 1: the node's below us. */
1369   if (node->left != tree->nil)
1370     {
1371       node = node->left;
1372       while (node->right != tree->nil)
1373         node = node->right;
1374       return node;
1375     }
1376
1377   /* Case 2: it's an ancestor */
1378   while (node->parent != tree->nil)
1379     {
1380       if (node->parent->left == node)
1381         node = node->parent;
1382       else
1383         return (node->parent);
1384     }
1385
1386   /* Case 3: There is no next node */
1387   return NULL;
1388 }
1389
1390 void
1391 _gtk_rbtree_next_full (GtkRBTree  *tree,
1392                        GtkRBNode  *node,
1393                        GtkRBTree **new_tree,
1394                        GtkRBNode **new_node)
1395 {
1396   g_return_if_fail (tree != NULL);
1397   g_return_if_fail (node != NULL);
1398   g_return_if_fail (new_tree != NULL);
1399   g_return_if_fail (new_node != NULL);
1400
1401   if (node->children)
1402     {
1403       *new_tree = node->children;
1404       *new_node = (*new_tree)->root;
1405       while ((*new_node)->left != (*new_tree)->nil)
1406         *new_node = (*new_node)->left;
1407       return;
1408     }
1409
1410   *new_tree = tree;
1411   *new_node = _gtk_rbtree_next (tree, node);
1412
1413   while ((*new_node == NULL) &&
1414          (*new_tree != NULL))
1415     {
1416       *new_node = (*new_tree)->parent_node;
1417       *new_tree = (*new_tree)->parent_tree;
1418       if (*new_tree)
1419         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1420     }
1421 }
1422
1423 void
1424 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1425                        GtkRBNode  *node,
1426                        GtkRBTree **new_tree,
1427                        GtkRBNode **new_node)
1428 {
1429   g_return_if_fail (tree != NULL);
1430   g_return_if_fail (node != NULL);
1431   g_return_if_fail (new_tree != NULL);
1432   g_return_if_fail (new_node != NULL);
1433
1434   *new_tree = tree;
1435   *new_node = _gtk_rbtree_prev (tree, node);
1436
1437   if (*new_node == NULL)
1438     {
1439       *new_node = (*new_tree)->parent_node;
1440       *new_tree = (*new_tree)->parent_tree;
1441     }
1442   else
1443     {
1444       while ((*new_node)->children)
1445         {
1446           *new_tree = (*new_node)->children;
1447           *new_node = (*new_tree)->root;
1448           while ((*new_node)->right != (*new_tree)->nil)
1449             *new_node = (*new_node)->right;
1450         }
1451     }
1452 }
1453
1454 gint
1455 _gtk_rbtree_get_depth (GtkRBTree *tree)
1456 {
1457   GtkRBTree *tmp_tree;
1458   gint depth = 0;
1459
1460   tmp_tree = tree->parent_tree;
1461   while (tmp_tree)
1462     {
1463       ++depth;
1464       tmp_tree = tmp_tree->parent_tree;
1465     }
1466
1467   return depth;
1468 }
1469
1470 static void
1471 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1472                                 GtkRBNode             *node,
1473                                 GtkRBTreeTraverseFunc  func,
1474                                 gpointer               data)
1475 {
1476   if (node == tree->nil)
1477     return;
1478
1479   (* func) (tree, node, data);
1480   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1481   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1482 }
1483
1484 static void
1485 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1486                                  GtkRBNode             *node,
1487                                  GtkRBTreeTraverseFunc  func,
1488                                  gpointer               data)
1489 {
1490   if (node == tree->nil)
1491     return;
1492
1493   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1494   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1495   (* func) (tree, node, data);
1496 }
1497
1498 void
1499 _gtk_rbtree_traverse (GtkRBTree             *tree,
1500                       GtkRBNode             *node,
1501                       GTraverseType          order,
1502                       GtkRBTreeTraverseFunc  func,
1503                       gpointer               data)
1504 {
1505   g_return_if_fail (tree != NULL);
1506   g_return_if_fail (node != NULL);
1507   g_return_if_fail (func != NULL);
1508   g_return_if_fail (order <= G_LEVEL_ORDER);
1509
1510   switch (order)
1511     {
1512     case G_PRE_ORDER:
1513       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1514       break;
1515     case G_POST_ORDER:
1516       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1517       break;
1518     case G_IN_ORDER:
1519     case G_LEVEL_ORDER:
1520     default:
1521       g_warning ("unsupported traversal order.");
1522       break;
1523     }
1524 }
1525
1526 static inline
1527 void _fixup_validation (GtkRBTree *tree,
1528                         GtkRBNode *node)
1529 {
1530   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1531       GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1532       (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1533       (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1534       (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1535     {
1536       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1537     }
1538   else
1539     {
1540       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1541     }
1542 }
1543
1544 static inline
1545 void _fixup_total_count (GtkRBTree *tree,
1546                     GtkRBNode *node)
1547 {
1548   node->total_count = 1 +
1549     (node->children != NULL ? node->children->root->total_count : 0) +
1550     node->left->total_count + node->right->total_count;
1551 }
1552
1553 #ifdef G_ENABLE_DEBUG
1554 static guint
1555 get_total_count (GtkRBNode *node)
1556 {
1557   guint child_total = 0;
1558
1559   child_total += (guint) node->left->total_count;
1560   child_total += (guint) node->right->total_count;
1561
1562   if (node->children)
1563     child_total += (guint) node->children->root->total_count;
1564
1565   return child_total + 1;
1566 }
1567
1568 static guint
1569 count_total (GtkRBTree *tree,
1570              GtkRBNode *node)
1571 {
1572   guint res;
1573
1574   if (node == tree->nil)
1575     return 0;
1576
1577   res =
1578     count_total (tree, node->left) +
1579     count_total (tree, node->right) +
1580     (guint)1 +
1581     (node->children ? count_total (node->children, node->children->root) : 0);
1582
1583   if (res != node->total_count)
1584     g_print ("total count incorrect for node\n");
1585
1586   if (get_total_count (node) != node->total_count)
1587     g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1588
1589   return res;
1590 }
1591
1592 static gint
1593 _count_nodes (GtkRBTree *tree,
1594               GtkRBNode *node)
1595 {
1596   gint res;
1597   if (node == tree->nil)
1598     return 0;
1599
1600   g_assert (node->left);
1601   g_assert (node->right);
1602
1603   res = (_count_nodes (tree, node->left) +
1604          _count_nodes (tree, node->right) + 1);
1605
1606   if (res != node->count)
1607     g_print ("Tree failed\n");
1608   return res;
1609 }
1610
1611 static void
1612 _gtk_rbtree_test_height (GtkRBTree *tree,
1613                          GtkRBNode *node)
1614 {
1615   gint computed_offset = 0;
1616
1617   /* This whole test is sort of a useless truism. */
1618
1619   if (node->left != tree->nil)
1620     computed_offset += node->left->offset;
1621
1622   if (node->right != tree->nil)
1623     computed_offset += node->right->offset;
1624
1625   if (node->children && node->children->root != node->children->nil)
1626     computed_offset += node->children->root->offset;
1627
1628   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1629     g_error ("node has broken offset\n");
1630
1631   if (node->left != tree->nil)
1632     _gtk_rbtree_test_height (tree, node->left);
1633
1634   if (node->right != tree->nil)
1635     _gtk_rbtree_test_height (tree, node->right);
1636
1637   if (node->children && node->children->root != node->children->nil)
1638     _gtk_rbtree_test_height (node->children, node->children->root);
1639 }
1640
1641 static void
1642 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1643                         GtkRBNode *node,
1644                          gint      expected_dirtyness)
1645 {
1646
1647   if (expected_dirtyness)
1648     {
1649       g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1650                 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1651                 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1652                 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1653                 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1654     }
1655   else
1656     {
1657       g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1658                 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1659       if (node->left != tree->nil)
1660         g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1661       if (node->right != tree->nil)
1662         g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1663       if (node->children != NULL)
1664         g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1665     }
1666
1667   if (node->left != tree->nil)
1668     _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1669   if (node->right != tree->nil)
1670     _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1671   if (node->children != NULL && node->children->root != node->children->nil)
1672     _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1673 }
1674
1675 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1676
1677 static void
1678 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1679                                    GtkRBNode *node)
1680 {
1681   g_assert (node != tree->nil);
1682
1683   g_assert (node->left != NULL);
1684   g_assert (node->right != NULL);
1685   g_assert (node->parent != NULL);
1686
1687   if (node->left != tree->nil)
1688     {
1689       g_assert (node->left->parent == node);
1690       _gtk_rbtree_test_structure_helper (tree, node->left);
1691     }
1692   if (node->right != tree->nil)
1693     {
1694       g_assert (node->right->parent == node);
1695       _gtk_rbtree_test_structure_helper (tree, node->right);
1696     }
1697
1698   if (node->children != NULL)
1699     {
1700       g_assert (node->children->parent_tree == tree);
1701       g_assert (node->children->parent_node == node);
1702
1703       _gtk_rbtree_test_structure (node->children);
1704     }
1705 }
1706 static void
1707 _gtk_rbtree_test_structure (GtkRBTree *tree)
1708 {
1709   g_assert (tree->root);
1710   if (tree->root == tree->nil)
1711     return;
1712
1713   g_assert (tree->root->parent == tree->nil);
1714   _gtk_rbtree_test_structure_helper (tree, tree->root);
1715 }
1716
1717 static void
1718 _gtk_rbtree_test (const gchar *where,
1719                   GtkRBTree   *tree)
1720 {
1721   GtkRBTree *tmp_tree;
1722
1723   if (tree == NULL)
1724     return;
1725
1726   /* Test the entire tree */
1727   tmp_tree = tree;
1728   while (tmp_tree->parent_tree)
1729     tmp_tree = tmp_tree->parent_tree;
1730
1731   g_assert (tmp_tree->nil != NULL);
1732
1733   if (tmp_tree->root == tmp_tree->nil)
1734     return;
1735
1736   _gtk_rbtree_test_structure (tmp_tree);
1737
1738   g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1739              _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1740
1741
1742   _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1743   _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1744   g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
1745 }
1746
1747 static void
1748 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1749                                GtkRBNode *node,
1750                                gint       depth)
1751 {
1752   gint i;
1753   for (i = 0; i < depth; i++)
1754     g_print ("\t");
1755
1756   g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1757            node,
1758            (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1759            node->offset,
1760            node->total_count,
1761            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1762            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1763            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1764   if (node->children != NULL)
1765     {
1766       g_print ("Looking at child.\n");
1767       _gtk_rbtree_debug_spew (node->children);
1768       g_print ("Done looking at child.\n");
1769     }
1770   if (node->left != tree->nil)
1771     {
1772       _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1773     }
1774   if (node->right != tree->nil)
1775     {
1776       _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1777     }
1778 }
1779
1780 static void
1781 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1782 {
1783   g_return_if_fail (tree != NULL);
1784
1785   if (tree->root == tree->nil)
1786     g_print ("Empty tree...\n");
1787   else
1788     _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1789 }
1790 #endif /* G_ENABLE_DEBUG */