Pileus Git - ~andy/gtk/blob - gtk/gtkrbtree.c

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