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