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