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

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