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