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   GtkRBNode *parent = node->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   x->parent = y->parent;
1188   if (y->parent != tree->nil)
1189     {
1190       if (y == y->parent->left)
1191         y->parent->left = x;
1192       else
1193         y->parent->right = x;
1194     }
1195   else
1196     {
1197       tree->root = x;
1198     }
1199
1200   /* We need to clean up the validity of the tree.
1201    */
1202   gtk_rbnode_adjust (tree, y, -1, - y_total_count, - y_height);
1203
1204   if (y != node)
1205     {
1206       gint node_height, node_total_count;
1207
1208       /* We want to see how much we remove from the aggregate values.
1209        * This is all the children we remove plus the node's values.
1210        */
1211       node_height = GTK_RBNODE_GET_HEIGHT (node)
1212                     + (node->children ? node->children->root->offset : 0);
1213       node_total_count = 1
1214                          + (node->children ? node->children->root->total_count : 0);
1215
1216       /* Move the node over */
1217       if (GTK_RBNODE_GET_COLOR (node) != GTK_RBNODE_GET_COLOR (y))
1218         {
1219           node->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
1220           y->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
1221         }
1222
1223       y->left = node->left;
1224       if (y->left != tree->nil)
1225         y->left->parent = y;
1226       y->right = node->right;
1227       if (y->right != tree->nil)
1228         y->right->parent = y;
1229       y->parent = node->parent;
1230       if (y->parent != tree->nil)
1231         {
1232           if (y->parent->left == node)
1233             y->parent->left = y;
1234           else
1235             y->parent->right = y;
1236         }
1237       else
1238         {
1239           tree->root = y;
1240         }
1241       y->count = node->count;
1242       y->total_count = node->total_count;
1243       y->offset = node->offset;
1244
1245       gtk_rbnode_adjust (tree, y,
1246                          0,
1247                          y_total_count - node_total_count,
1248                          y_height - node_height);
1249     }
1250
1251   if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1252     _gtk_rbtree_remove_node_fixup (tree, x);
1253   _gtk_rbnode_free (node);
1254
1255 #ifdef G_ENABLE_DEBUG
1256   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1257     {
1258       g_print ("_gtk_rbtree_remove_node finished...\n");
1259       _gtk_rbtree_debug_spew (tree);
1260       g_print ("\n\n");
1261       _gtk_rbtree_test (G_STRLOC, tree);
1262     }
1263 #endif /* G_ENABLE_DEBUG */
1264 }
1265
1266 GtkRBNode *
1267 _gtk_rbtree_next (GtkRBTree *tree,
1268                   GtkRBNode *node)
1269 {
1270   g_return_val_if_fail (tree != NULL, NULL);
1271   g_return_val_if_fail (node != NULL, NULL);
1272
1273   /* Case 1: the node's below us. */
1274   if (node->right != tree->nil)
1275     {
1276       node = node->right;
1277       while (node->left != tree->nil)
1278         node = node->left;
1279       return node;
1280     }
1281
1282   /* Case 2: it's an ancestor */
1283   while (node->parent != tree->nil)
1284     {
1285       if (node->parent->right == node)
1286         node = node->parent;
1287       else
1288         return (node->parent);
1289     }
1290
1291   /* Case 3: There is no next node */
1292   return NULL;
1293 }
1294
1295 GtkRBNode *
1296 _gtk_rbtree_prev (GtkRBTree *tree,
1297                   GtkRBNode *node)
1298 {
1299   g_return_val_if_fail (tree != NULL, NULL);
1300   g_return_val_if_fail (node != NULL, NULL);
1301
1302   /* Case 1: the node's below us. */
1303   if (node->left != tree->nil)
1304     {
1305       node = node->left;
1306       while (node->right != tree->nil)
1307         node = node->right;
1308       return node;
1309     }
1310
1311   /* Case 2: it's an ancestor */
1312   while (node->parent != tree->nil)
1313     {
1314       if (node->parent->left == node)
1315         node = node->parent;
1316       else
1317         return (node->parent);
1318     }
1319
1320   /* Case 3: There is no next node */
1321   return NULL;
1322 }
1323
1324 void
1325 _gtk_rbtree_next_full (GtkRBTree  *tree,
1326                        GtkRBNode  *node,
1327                        GtkRBTree **new_tree,
1328                        GtkRBNode **new_node)
1329 {
1330   g_return_if_fail (tree != NULL);
1331   g_return_if_fail (node != NULL);
1332   g_return_if_fail (new_tree != NULL);
1333   g_return_if_fail (new_node != NULL);
1334
1335   if (node->children)
1336     {
1337       *new_tree = node->children;
1338       *new_node = (*new_tree)->root;
1339       while ((*new_node)->left != (*new_tree)->nil)
1340         *new_node = (*new_node)->left;
1341       return;
1342     }
1343
1344   *new_tree = tree;
1345   *new_node = _gtk_rbtree_next (tree, node);
1346
1347   while ((*new_node == NULL) &&
1348          (*new_tree != NULL))
1349     {
1350       *new_node = (*new_tree)->parent_node;
1351       *new_tree = (*new_tree)->parent_tree;
1352       if (*new_tree)
1353         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1354     }
1355 }
1356
1357 void
1358 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1359                        GtkRBNode  *node,
1360                        GtkRBTree **new_tree,
1361                        GtkRBNode **new_node)
1362 {
1363   g_return_if_fail (tree != NULL);
1364   g_return_if_fail (node != NULL);
1365   g_return_if_fail (new_tree != NULL);
1366   g_return_if_fail (new_node != NULL);
1367
1368   *new_tree = tree;
1369   *new_node = _gtk_rbtree_prev (tree, node);
1370
1371   if (*new_node == NULL)
1372     {
1373       *new_node = (*new_tree)->parent_node;
1374       *new_tree = (*new_tree)->parent_tree;
1375     }
1376   else
1377     {
1378       while ((*new_node)->children)
1379         {
1380           *new_tree = (*new_node)->children;
1381           *new_node = (*new_tree)->root;
1382           while ((*new_node)->right != (*new_tree)->nil)
1383             *new_node = (*new_node)->right;
1384         }
1385     }
1386 }
1387
1388 gint
1389 _gtk_rbtree_get_depth (GtkRBTree *tree)
1390 {
1391   GtkRBTree *tmp_tree;
1392   gint depth = 0;
1393
1394   tmp_tree = tree->parent_tree;
1395   while (tmp_tree)
1396     {
1397       ++depth;
1398       tmp_tree = tmp_tree->parent_tree;
1399     }
1400
1401   return depth;
1402 }
1403
1404 static void
1405 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1406                                 GtkRBNode             *node,
1407                                 GtkRBTreeTraverseFunc  func,
1408                                 gpointer               data)
1409 {
1410   if (node == tree->nil)
1411     return;
1412
1413   (* func) (tree, node, data);
1414   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1415   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1416 }
1417
1418 static void
1419 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1420                                  GtkRBNode             *node,
1421                                  GtkRBTreeTraverseFunc  func,
1422                                  gpointer               data)
1423 {
1424   if (node == tree->nil)
1425     return;
1426
1427   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1428   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1429   (* func) (tree, node, data);
1430 }
1431
1432 void
1433 _gtk_rbtree_traverse (GtkRBTree             *tree,
1434                       GtkRBNode             *node,
1435                       GTraverseType          order,
1436                       GtkRBTreeTraverseFunc  func,
1437                       gpointer               data)
1438 {
1439   g_return_if_fail (tree != NULL);
1440   g_return_if_fail (node != NULL);
1441   g_return_if_fail (func != NULL);
1442   g_return_if_fail (order <= G_LEVEL_ORDER);
1443
1444   switch (order)
1445     {
1446     case G_PRE_ORDER:
1447       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1448       break;
1449     case G_POST_ORDER:
1450       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1451       break;
1452     case G_IN_ORDER:
1453     case G_LEVEL_ORDER:
1454     default:
1455       g_warning ("unsupported traversal order.");
1456       break;
1457     }
1458 }
1459
1460 static inline
1461 void _fixup_validation (GtkRBTree *tree,
1462                         GtkRBNode *node)
1463 {
1464   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1465       GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1466       (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1467       (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1468       (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1469     {
1470       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1471     }
1472   else
1473     {
1474       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1475     }
1476 }
1477
1478 static inline
1479 void _fixup_total_count (GtkRBTree *tree,
1480                     GtkRBNode *node)
1481 {
1482   node->total_count = 1 +
1483     (node->children != NULL ? node->children->root->total_count : 0) +
1484     node->left->total_count + node->right->total_count;
1485 }
1486
1487 #ifdef G_ENABLE_DEBUG
1488 static guint
1489 get_total_count (GtkRBNode *node)
1490 {
1491   guint child_total = 0;
1492
1493   child_total += (guint) node->left->total_count;
1494   child_total += (guint) node->right->total_count;
1495
1496   if (node->children)
1497     child_total += (guint) node->children->root->total_count;
1498
1499   return child_total + 1;
1500 }
1501
1502 static guint
1503 count_total (GtkRBTree *tree,
1504              GtkRBNode *node)
1505 {
1506   guint res;
1507
1508   if (node == tree->nil)
1509     return 0;
1510
1511   res =
1512     count_total (tree, node->left) +
1513     count_total (tree, node->right) +
1514     (guint)1 +
1515     (node->children ? count_total (node->children, node->children->root) : 0);
1516
1517   if (res != node->total_count)
1518     g_print ("total count incorrect for node\n");
1519
1520   if (get_total_count (node) != node->total_count)
1521     g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1522
1523   return res;
1524 }
1525
1526 static gint
1527 _count_nodes (GtkRBTree *tree,
1528               GtkRBNode *node)
1529 {
1530   gint res;
1531   if (node == tree->nil)
1532     return 0;
1533
1534   g_assert (node->left);
1535   g_assert (node->right);
1536
1537   res = (_count_nodes (tree, node->left) +
1538          _count_nodes (tree, node->right) + 1);
1539
1540   if (res != node->count)
1541     g_print ("Tree failed\n");
1542   return res;
1543 }
1544
1545 static void
1546 _gtk_rbtree_test_height (GtkRBTree *tree,
1547                          GtkRBNode *node)
1548 {
1549   gint computed_offset = 0;
1550
1551   /* This whole test is sort of a useless truism. */
1552
1553   if (node->left != tree->nil)
1554     computed_offset += node->left->offset;
1555
1556   if (node->right != tree->nil)
1557     computed_offset += node->right->offset;
1558
1559   if (node->children && node->children->root != node->children->nil)
1560     computed_offset += node->children->root->offset;
1561
1562   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1563     g_error ("node has broken offset\n");
1564
1565   if (node->left != tree->nil)
1566     _gtk_rbtree_test_height (tree, node->left);
1567
1568   if (node->right != tree->nil)
1569     _gtk_rbtree_test_height (tree, node->right);
1570
1571   if (node->children && node->children->root != node->children->nil)
1572     _gtk_rbtree_test_height (node->children, node->children->root);
1573 }
1574
1575 static void
1576 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1577                         GtkRBNode *node,
1578                          gint      expected_dirtyness)
1579 {
1580
1581   if (expected_dirtyness)
1582     {
1583       g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1584                 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1585                 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1586                 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1587                 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1588     }
1589   else
1590     {
1591       g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1592                 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1593       if (node->left != tree->nil)
1594         g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1595       if (node->right != tree->nil)
1596         g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1597       if (node->children != NULL)
1598         g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1599     }
1600
1601   if (node->left != tree->nil)
1602     _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1603   if (node->right != tree->nil)
1604     _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1605   if (node->children != NULL && node->children->root != node->children->nil)
1606     _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1607 }
1608
1609 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1610
1611 static void
1612 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1613                                    GtkRBNode *node)
1614 {
1615   g_assert (node != tree->nil);
1616
1617   g_assert (node->left != NULL);
1618   g_assert (node->right != NULL);
1619   g_assert (node->parent != NULL);
1620
1621   if (node->left != tree->nil)
1622     {
1623       g_assert (node->left->parent == node);
1624       _gtk_rbtree_test_structure_helper (tree, node->left);
1625     }
1626   if (node->right != tree->nil)
1627     {
1628       g_assert (node->right->parent == node);
1629       _gtk_rbtree_test_structure_helper (tree, node->right);
1630     }
1631
1632   if (node->children != NULL)
1633     {
1634       g_assert (node->children->parent_tree == tree);
1635       g_assert (node->children->parent_node == node);
1636
1637       _gtk_rbtree_test_structure (node->children);
1638     }
1639 }
1640 static void
1641 _gtk_rbtree_test_structure (GtkRBTree *tree)
1642 {
1643   g_assert (tree->root);
1644   if (tree->root == tree->nil)
1645     return;
1646
1647   g_assert (tree->root->parent == tree->nil);
1648   _gtk_rbtree_test_structure_helper (tree, tree->root);
1649 }
1650
1651 static void
1652 _gtk_rbtree_test (const gchar *where,
1653                   GtkRBTree   *tree)
1654 {
1655   GtkRBTree *tmp_tree;
1656
1657   if (tree == NULL)
1658     return;
1659
1660   /* Test the entire tree */
1661   tmp_tree = tree;
1662   while (tmp_tree->parent_tree)
1663     tmp_tree = tmp_tree->parent_tree;
1664
1665   g_assert (tmp_tree->nil != NULL);
1666
1667   if (tmp_tree->root == tmp_tree->nil)
1668     return;
1669
1670   _gtk_rbtree_test_structure (tmp_tree);
1671
1672   g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1673              _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1674
1675
1676   _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1677   _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1678   g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
1679 }
1680
1681 static void
1682 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1683                                GtkRBNode *node,
1684                                gint       depth)
1685 {
1686   gint i;
1687   for (i = 0; i < depth; i++)
1688     g_print ("\t");
1689
1690   g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1691            node,
1692            (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1693            node->offset,
1694            node->total_count,
1695            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1696            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1697            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1698   if (node->children != NULL)
1699     {
1700       g_print ("Looking at child.\n");
1701       _gtk_rbtree_debug_spew (node->children);
1702       g_print ("Done looking at child.\n");
1703     }
1704   if (node->left != tree->nil)
1705     {
1706       _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1707     }
1708   if (node->right != tree->nil)
1709     {
1710       _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1711     }
1712 }
1713
1714 static void
1715 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1716 {
1717   g_return_if_fail (tree != NULL);
1718
1719   if (tree->root == tree->nil)
1720     g_print ("Empty tree...\n");
1721   else
1722     _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1723 }
1724 #endif /* G_ENABLE_DEBUG */