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