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 "gtkalias.h"
  22 #include "gtkrbtree.h"
  23 #include "gtkdebug.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 {
 900   GtkRBNode *node;
 901
 902   if (tree == NULL)
 903     return;
 904
 905   node = tree->root;
 906   g_assert (node);
 907
 908   while (node->left != tree->nil)
 909     node = node->left;
 910
 911   do
 912     {
 913       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 914         _gtk_rbtree_node_set_height (tree, node, height);
 915
 916       if (node->children)
 917         _gtk_rbtree_set_fixed_height (node->children, height);
 918     }
 919   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 920 }
 921
 922 typedef struct _GtkRBReorder
 923 {
 924   GtkRBTree *children;
 925   gint height;
 926   gint flags;
 927   gint order;
 928   gint invert_order;
 929   gint parity;
 930 } GtkRBReorder;
 931
 932 static int
 933 gtk_rbtree_reorder_sort_func (gconstpointer a,
 934                               gconstpointer b)
 935 {
 936   return ((GtkRBReorder *) a)->order - ((GtkRBReorder *) b)->order;
 937 }
 938
 939 static int
 940 gtk_rbtree_reorder_invert_func (gconstpointer a,
 941                                 gconstpointer b)
 942 {
 943   return ((GtkRBReorder *) a)->invert_order - ((GtkRBReorder *) b)->invert_order;
 944 }
 945
 946 static void
 947 gtk_rbtree_reorder_fixup (GtkRBTree *tree,
 948                           GtkRBNode *node)
 949 {
 950   if (node == tree->nil)
 951     return;
 952
 953   node->parity = 1;
 954
 955   if (node->left != tree->nil)
 956     {
 957       gtk_rbtree_reorder_fixup (tree, node->left);
 958       node->offset += node->left->offset;
 959       node->parity += node->left->parity;
 960     }
 961   if (node->right != tree->nil)
 962     {
 963       gtk_rbtree_reorder_fixup (tree, node->right);
 964       node->offset += node->right->offset;
 965       node->parity += node->right->parity;
 966     }
 967
 968   if (node->children)
 969     {
 970       node->offset += node->children->root->offset;
 971       node->parity += node->children->root->parity;
 972     }
 973
 974   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
 975       (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 976       (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 977       (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 978     GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 979   else
 980     GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 981 }
 982
 983 /* It basically pulls everything out of the tree, rearranges it, and puts it
 984  * back together.  Our strategy is to keep the old RBTree intact, and just
 985  * rearrange the contents.  When that is done, we go through and update the
 986  * heights.  There is probably a more elegant way to write this function.  If
 987  * anyone wants to spend the time writing it, patches will be accepted.
 988  */
 989 void
 990 _gtk_rbtree_reorder (GtkRBTree *tree,
 991                      gint      *new_order,
 992                      gint       length)
 993 {
 994   GtkRBReorder reorder = {0, };
 995   GArray *array;
 996   GtkRBNode *node;
 997   gint i;
 998
 999   g_return_if_fail (tree != NULL);
1000   g_return_if_fail (length > 0);
1001   g_return_if_fail (tree->root->count == length);
1002
1003   /* Sort the trees values in the new tree. */
1004   array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
1005   for (i = 0; i < length; i++)
1006     {
1007       reorder.order = new_order[i];
1008       reorder.invert_order = i;
1009       g_array_append_val (array, reorder);
1010     }
1011
1012   g_array_sort(array, gtk_rbtree_reorder_sort_func);
1013
1014   /* rewind node*/
1015   node = tree->root;
1016   while (node && node->left != tree->nil)
1017     node = node->left;
1018
1019   for (i = 0; i < length; i++)
1020     {
1021       g_assert (node != tree->nil);
1022       g_array_index (array, GtkRBReorder, i).children = node->children;
1023       g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
1024       g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
1025
1026       node = _gtk_rbtree_next (tree, node);
1027     }
1028
1029   g_array_sort (array, gtk_rbtree_reorder_invert_func);
1030
1031   /* rewind node*/
1032   node = tree->root;
1033   while (node && node->left != tree->nil)
1034     node = node->left;
1035
1036   /* Go through the tree and change the values to the new ones. */
1037   for (i = 0; i < length; i++)
1038     {
1039       reorder = g_array_index (array, GtkRBReorder, i);
1040       node->children = reorder.children;
1041       if (node->children)
1042         node->children->parent_node = node;
1043       node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
1044       /* We temporarily set the height to this. */
1045       node->offset = reorder.height;
1046       node = _gtk_rbtree_next (tree, node);
1047     }
1048   gtk_rbtree_reorder_fixup (tree, tree->root);
1049
1050   g_array_free (array, TRUE);
1051 }
1052
1053
1054 gint
1055 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
1056                               GtkRBNode *node)
1057 {
1058   GtkRBNode *last;
1059   gint retval;
1060
1061   g_assert (node);
1062   g_assert (node->left);
1063
1064   retval = node->left->offset;
1065
1066   while (tree && node && node != tree->nil)
1067     {
1068       last = node;
1069       node = node->parent;
1070
1071       /* Add left branch, plus children, iff we came from the right */
1072       if (node->right == last)
1073         retval += node->offset - node->right->offset;
1074
1075       if (node == tree->nil)
1076         {
1077           node = tree->parent_node;
1078           tree = tree->parent_tree;
1079
1080           /* Add the parent node, plus the left branch. */
1081           if (node)
1082             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
1083         }
1084     }
1085   return retval;
1086 }
1087
1088 gint
1089 _gtk_rbtree_node_find_parity (GtkRBTree *tree,
1090                               GtkRBNode *node)
1091 {
1092   GtkRBNode *last;
1093   gint retval;
1094
1095   g_assert (node);
1096   g_assert (node->left);
1097
1098   retval = node->left->parity;
1099
1100   while (tree && node && node != tree->nil)
1101     {
1102       last = node;
1103       node = node->parent;
1104
1105       /* Add left branch, plus children, iff we came from the right */
1106       if (node->right == last)
1107         retval += node->parity - node->right->parity;
1108
1109       if (node == tree->nil)
1110         {
1111           node = tree->parent_node;
1112           tree = tree->parent_tree;
1113
1114           /* Add the parent node, plus the left branch. */
1115           if (node)
1116             retval += node->left->parity + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
1117         }
1118     }
1119
1120   return retval % 2;
1121 }
1122
1123 gint
1124 _gtk_rbtree_real_find_offset (GtkRBTree  *tree,
1125                               gint        height,
1126                               GtkRBTree **new_tree,
1127                               GtkRBNode **new_node)
1128 {
1129   GtkRBNode *tmp_node;
1130
1131   g_assert (tree);
1132
1133   if (height < 0)
1134     {
1135       *new_tree = NULL;
1136       *new_node = NULL;
1137
1138       return 0;
1139     }
1140
1141
1142   tmp_node = tree->root;
1143   while (tmp_node != tree->nil &&
1144          (tmp_node->left->offset > height ||
1145           (tmp_node->offset - tmp_node->right->offset) < height))
1146     {
1147       if (tmp_node->left->offset > height)
1148         tmp_node = tmp_node->left;
1149       else
1150         {
1151           height -= (tmp_node->offset - tmp_node->right->offset);
1152           tmp_node = tmp_node->right;
1153         }
1154     }
1155   if (tmp_node == tree->nil)
1156     {
1157       *new_tree = NULL;
1158       *new_node = NULL;
1159       return 0;
1160     }
1161   if (tmp_node->children)
1162     {
1163       if ((tmp_node->offset -
1164            tmp_node->right->offset -
1165            tmp_node->children->root->offset) > height)
1166         {
1167           *new_tree = tree;
1168           *new_node = tmp_node;
1169           return (height - tmp_node->left->offset);
1170         }
1171       return _gtk_rbtree_real_find_offset (tmp_node->children,
1172                                            height - tmp_node->left->offset -
1173                                            (tmp_node->offset -
1174                                             tmp_node->left->offset -
1175                                             tmp_node->right->offset -
1176                                             tmp_node->children->root->offset),
1177                                            new_tree,
1178                                            new_node);
1179     }
1180   *new_tree = tree;
1181   *new_node = tmp_node;
1182   return (height - tmp_node->left->offset);
1183 }
1184
1185 gint
1186 _gtk_rbtree_find_offset (GtkRBTree  *tree,
1187                               gint        height,
1188                               GtkRBTree **new_tree,
1189                               GtkRBNode **new_node)
1190 {
1191   g_assert (tree);
1192
1193   if ((height < 0) ||
1194       (height >= tree->root->offset))
1195     {
1196       *new_tree = NULL;
1197       *new_node = NULL;
1198
1199       return 0;
1200     }
1201   return _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1202 }
1203
1204 void
1205 _gtk_rbtree_remove_node (GtkRBTree *tree,
1206                          GtkRBNode *node)
1207 {
1208   GtkRBNode *x, *y;
1209   GtkRBTree *tmp_tree;
1210   GtkRBNode *tmp_node;
1211   gint node_height;
1212   gint y_height;
1213
1214   g_return_if_fail (tree != NULL);
1215   g_return_if_fail (node != NULL);
1216
1217
1218 #ifdef G_ENABLE_DEBUG
1219   if (gtk_debug_flags & GTK_DEBUG_TREE)
1220     {
1221       g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1222       _gtk_rbtree_debug_spew (tree);
1223       _gtk_rbtree_test (G_STRLOC, tree);
1224     }
1225 #endif /* G_ENABLE_DEBUG */
1226
1227   /* make sure we're deleting a node that's actually in the tree */
1228   for (x = node; x->parent != tree->nil; x = x->parent)
1229     ;
1230   g_return_if_fail (x == tree->root);
1231
1232 #ifdef G_ENABLE_DEBUG
1233   if (gtk_debug_flags & GTK_DEBUG_TREE)
1234     _gtk_rbtree_test (G_STRLOC, tree);
1235 #endif
1236
1237   if (node->left == tree->nil || node->right == tree->nil)
1238     {
1239       y = node;
1240     }
1241   else
1242     {
1243       y = node->right;
1244
1245       while (y->left != tree->nil)
1246         y = y->left;
1247     }
1248
1249   /* adjust count only beneath tree */
1250   for (x = y; x != tree->nil; x = x->parent)
1251     {
1252       x->count--;
1253     }
1254
1255   /* offsets and parity adjust all the way up through parent trees */
1256   y_height = GTK_RBNODE_GET_HEIGHT (y);
1257   node_height = GTK_RBNODE_GET_HEIGHT (node) + (node->children?node->children->root->offset:0);
1258
1259   tmp_tree = tree;
1260   tmp_node = y;
1261   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1262     {
1263       tmp_node->offset -= (y_height + (y->children?y->children->root->offset:0));
1264       _fixup_validation (tmp_tree, tmp_node);
1265       _fixup_parity (tmp_tree, tmp_node);
1266       tmp_node = tmp_node->parent;
1267       if (tmp_node == tmp_tree->nil)
1268         {
1269           tmp_node = tmp_tree->parent_node;
1270           tmp_tree = tmp_tree->parent_tree;
1271         }
1272     }
1273
1274   /* x is y's only child, or nil */
1275   if (y->left != tree->nil)
1276     x = y->left;
1277   else
1278     x = y->right;
1279
1280   /* remove y from the parent chain */
1281   x->parent = y->parent;
1282   if (y->parent != tree->nil)
1283     {
1284       if (y == y->parent->left)
1285         y->parent->left = x;
1286       else
1287         y->parent->right = x;
1288     }
1289   else
1290     {
1291       tree->root = x;
1292     }
1293
1294   /* We need to clean up the validity of the tree.
1295    */
1296
1297   tmp_tree = tree;
1298   tmp_node = x;
1299   do
1300     {
1301       /* We skip the first time, iff x is nil */
1302       if (tmp_node != tmp_tree->nil)
1303         {
1304           _fixup_validation (tmp_tree, tmp_node);
1305           _fixup_parity (tmp_tree, tmp_node);
1306         }
1307       tmp_node = tmp_node->parent;
1308       if (tmp_node == tmp_tree->nil)
1309         {
1310           tmp_node = tmp_tree->parent_node;
1311           tmp_tree = tmp_tree->parent_tree;
1312         }
1313     }
1314   while (tmp_tree != NULL);
1315
1316   if (y != node)
1317     {
1318       gint diff;
1319
1320       /* Copy the node over */
1321       if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1322         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
1323       else
1324         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
1325       node->children = y->children;
1326       if (y->children)
1327         {
1328           node->children = y->children;
1329           node->children->parent_node = node;
1330         }
1331       else
1332         {
1333           node->children = NULL;
1334         }
1335       _fixup_validation (tree, node);
1336       _fixup_parity (tree, node);
1337       /* We want to see how different our height is from the previous node.
1338        * To do this, we compare our current height with our supposed height.
1339        */
1340       diff = y_height - GTK_RBNODE_GET_HEIGHT (node);
1341       tmp_tree = tree;
1342       tmp_node = node;
1343
1344       while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1345         {
1346           tmp_node->offset += diff;
1347           _fixup_validation (tmp_tree, tmp_node);
1348           _fixup_parity (tmp_tree, tmp_node);
1349           tmp_node = tmp_node->parent;
1350           if (tmp_node == tmp_tree->nil)
1351             {
1352               tmp_node = tmp_tree->parent_node;
1353               tmp_tree = tmp_tree->parent_tree;
1354             }
1355         }
1356     }
1357
1358   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1359     _gtk_rbtree_remove_node_fixup (tree, x);
1360   _gtk_rbnode_free (y);
1361
1362 #ifdef G_ENABLE_DEBUG
1363   if (gtk_debug_flags & GTK_DEBUG_TREE)
1364     {
1365       g_print ("_gtk_rbtree_remove_node finished...\n");
1366       _gtk_rbtree_debug_spew (tree);
1367       g_print ("\n\n");
1368       _gtk_rbtree_test (G_STRLOC, tree);
1369     }
1370 #endif /* G_ENABLE_DEBUG */
1371 }
1372
1373 GtkRBNode *
1374 _gtk_rbtree_next (GtkRBTree *tree,
1375                   GtkRBNode *node)
1376 {
1377   g_return_val_if_fail (tree != NULL, NULL);
1378   g_return_val_if_fail (node != NULL, NULL);
1379
1380   /* Case 1: the node's below us. */
1381   if (node->right != tree->nil)
1382     {
1383       node = node->right;
1384       while (node->left != tree->nil)
1385         node = node->left;
1386       return node;
1387     }
1388
1389   /* Case 2: it's an ancestor */
1390   while (node->parent != tree->nil)
1391     {
1392       if (node->parent->right == node)
1393         node = node->parent;
1394       else
1395         return (node->parent);
1396     }
1397
1398   /* Case 3: There is no next node */
1399   return NULL;
1400 }
1401
1402 GtkRBNode *
1403 _gtk_rbtree_prev (GtkRBTree *tree,
1404                   GtkRBNode *node)
1405 {
1406   g_return_val_if_fail (tree != NULL, NULL);
1407   g_return_val_if_fail (node != NULL, NULL);
1408
1409   /* Case 1: the node's below us. */
1410   if (node->left != tree->nil)
1411     {
1412       node = node->left;
1413       while (node->right != tree->nil)
1414         node = node->right;
1415       return node;
1416     }
1417
1418   /* Case 2: it's an ancestor */
1419   while (node->parent != tree->nil)
1420     {
1421       if (node->parent->left == node)
1422         node = node->parent;
1423       else
1424         return (node->parent);
1425     }
1426
1427   /* Case 3: There is no next node */
1428   return NULL;
1429 }
1430
1431 void
1432 _gtk_rbtree_next_full (GtkRBTree  *tree,
1433                        GtkRBNode  *node,
1434                        GtkRBTree **new_tree,
1435                        GtkRBNode **new_node)
1436 {
1437   g_return_if_fail (tree != NULL);
1438   g_return_if_fail (node != NULL);
1439   g_return_if_fail (new_tree != NULL);
1440   g_return_if_fail (new_node != NULL);
1441
1442   if (node->children)
1443     {
1444       *new_tree = node->children;
1445       *new_node = (*new_tree)->root;
1446       while ((*new_node)->left != (*new_tree)->nil)
1447         *new_node = (*new_node)->left;
1448       return;
1449     }
1450
1451   *new_tree = tree;
1452   *new_node = _gtk_rbtree_next (tree, node);
1453
1454   while ((*new_node == NULL) &&
1455          (*new_tree != NULL))
1456     {
1457       *new_node = (*new_tree)->parent_node;
1458       *new_tree = (*new_tree)->parent_tree;
1459       if (*new_tree)
1460         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1461     }
1462 }
1463
1464 void
1465 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1466                        GtkRBNode  *node,
1467                        GtkRBTree **new_tree,
1468                        GtkRBNode **new_node)
1469 {
1470   g_return_if_fail (tree != NULL);
1471   g_return_if_fail (node != NULL);
1472   g_return_if_fail (new_tree != NULL);
1473   g_return_if_fail (new_node != NULL);
1474
1475   *new_tree = tree;
1476   *new_node = _gtk_rbtree_prev (tree, node);
1477
1478   if (*new_node == NULL)
1479     {
1480       *new_node = (*new_tree)->parent_node;
1481       *new_tree = (*new_tree)->parent_tree;
1482     }
1483   else
1484     {
1485       while ((*new_node)->children)
1486         {
1487           *new_tree = (*new_node)->children;
1488           *new_node = (*new_tree)->root;
1489           while ((*new_node)->right != (*new_tree)->nil)
1490             *new_node = (*new_node)->right;
1491         }
1492     }
1493 }
1494
1495 gint
1496 _gtk_rbtree_get_depth (GtkRBTree *tree)
1497 {
1498   GtkRBTree *tmp_tree;
1499   gint depth = 0;
1500
1501   tmp_tree = tree->parent_tree;
1502   while (tmp_tree)
1503     {
1504       ++depth;
1505       tmp_tree = tmp_tree->parent_tree;
1506     }
1507
1508   return depth;
1509 }
1510
1511 static void
1512 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1513                                 GtkRBNode             *node,
1514                                 GtkRBTreeTraverseFunc  func,
1515                                 gpointer               data)
1516 {
1517   if (node == tree->nil)
1518     return;
1519
1520   (* func) (tree, node, data);
1521   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1522   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1523 }
1524
1525 static void
1526 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1527                                  GtkRBNode             *node,
1528                                  GtkRBTreeTraverseFunc  func,
1529                                  gpointer               data)
1530 {
1531   if (node == tree->nil)
1532     return;
1533
1534   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1535   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1536   (* func) (tree, node, data);
1537 }
1538
1539 void
1540 _gtk_rbtree_traverse (GtkRBTree             *tree,
1541                       GtkRBNode             *node,
1542                       GTraverseType          order,
1543                       GtkRBTreeTraverseFunc  func,
1544                       gpointer               data)
1545 {
1546   g_return_if_fail (tree != NULL);
1547   g_return_if_fail (node != NULL);
1548   g_return_if_fail (func != NULL);
1549   g_return_if_fail (order <= G_LEVEL_ORDER);
1550
1551   switch (order)
1552     {
1553     case G_PRE_ORDER:
1554       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1555       break;
1556     case G_POST_ORDER:
1557       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1558       break;
1559     case G_IN_ORDER:
1560     case G_LEVEL_ORDER:
1561     default:
1562       g_warning ("unsupported traversal order.");
1563       break;
1564     }
1565 }
1566
1567 static gint
1568 _count_nodes (GtkRBTree *tree,
1569               GtkRBNode *node)
1570 {
1571   gint res;
1572   if (node == tree->nil)
1573     return 0;
1574
1575   g_assert (node->left);
1576   g_assert (node->right);
1577
1578   res = (_count_nodes (tree, node->left) +
1579          _count_nodes (tree, node->right) + 1);
1580
1581   if (res != node->count)
1582     g_print ("Tree failed\n");
1583   return res;
1584 }
1585
1586 static inline
1587 void _fixup_validation (GtkRBTree *tree,
1588                         GtkRBNode *node)
1589 {
1590   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1591       GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1592       (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1593       (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1594       (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1595     {
1596       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1597     }
1598   else
1599     {
1600       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1601     }
1602 }
1603
1604 static inline
1605 void _fixup_parity (GtkRBTree *tree,
1606                     GtkRBNode *node)
1607 {
1608   node->parity = 1 +
1609     ((node->children != NULL && node->children->root != node->children->nil) ? node->children->root->parity : 0) +
1610     ((node->left != tree->nil) ? node->left->parity : 0) +
1611     ((node->right != tree->nil) ? node->right->parity : 0);
1612 }
1613
1614 #ifdef G_ENABLE_DEBUG
1615 static guint
1616 get_parity (GtkRBNode *node)
1617 {
1618   guint child_total = 0;
1619   guint rem;
1620
1621   /* The parity of a node is node->parity minus
1622    * the parity of left, right, and children.
1623    *
1624    * This is equivalent to saying that if left, right, children
1625    * sum to 0 parity, then node->parity is the parity of node,
1626    * and if left, right, children are odd parity, then
1627    * node->parity is the reverse of the node's parity.
1628    */
1629
1630   child_total += (guint) node->left->parity;
1631   child_total += (guint) node->right->parity;
1632
1633   if (node->children)
1634     child_total += (guint) node->children->root->parity;
1635
1636   rem = child_total % 2;
1637
1638   if (rem == 0)
1639     return node->parity;
1640   else
1641     return !node->parity;
1642 }
1643
1644 static guint
1645 count_parity (GtkRBTree *tree,
1646               GtkRBNode *node)
1647 {
1648   guint res;
1649
1650   if (node == tree->nil)
1651     return 0;
1652
1653   res =
1654     count_parity (tree, node->left) +
1655     count_parity (tree, node->right) +
1656     (guint)1 +
1657     (node->children ? count_parity (node->children, node->children->root) : 0);
1658
1659   res = res % (guint)2;
1660
1661   if (res != node->parity)
1662     g_print ("parity incorrect for node\n");
1663
1664   if (get_parity (node) != 1)
1665     g_error ("Node has incorrect parity %d", get_parity (node));
1666
1667   return res;
1668 }
1669
1670 static void
1671 _gtk_rbtree_test_height (GtkRBTree *tree,
1672                          GtkRBNode *node)
1673 {
1674   gint computed_offset = 0;
1675
1676   /* This whole test is sort of a useless truism. */
1677
1678   if (node->left != tree->nil)
1679     computed_offset += node->left->offset;
1680
1681   if (node->right != tree->nil)
1682     computed_offset += node->right->offset;
1683
1684   if (node->children && node->children->root != node->children->nil)
1685     computed_offset += node->children->root->offset;
1686
1687   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1688     g_error ("node has broken offset\n");
1689
1690   if (node->left != tree->nil)
1691     _gtk_rbtree_test_height (tree, node->left);
1692
1693   if (node->right != tree->nil)
1694     _gtk_rbtree_test_height (tree, node->right);
1695
1696   if (node->children && node->children->root != node->children->nil)
1697     _gtk_rbtree_test_height (node->children, node->children->root);
1698 }
1699
1700 static void
1701 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1702                         GtkRBNode *node,
1703                          gint      expected_dirtyness)
1704 {
1705
1706   if (expected_dirtyness)
1707     {
1708       g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1709                 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1710                 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1711                 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1712                 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1713     }
1714   else
1715     {
1716       g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1717                 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1718       if (node->left != tree->nil)
1719         g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1720       if (node->right != tree->nil)
1721         g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1722       if (node->children != NULL)
1723         g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1724     }
1725
1726   if (node->left != tree->nil)
1727     _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1728   if (node->right != tree->nil)
1729     _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1730   if (node->children != NULL && node->children->root != node->children->nil)
1731     _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1732 }
1733
1734 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1735
1736 static void
1737 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1738                                    GtkRBNode *node)
1739 {
1740   g_assert (node != tree->nil);
1741
1742   g_assert (node->left != NULL);
1743   g_assert (node->right != NULL);
1744   g_assert (node->parent != NULL);
1745
1746   if (node->left != tree->nil)
1747     {
1748       g_assert (node->left->parent == node);
1749       _gtk_rbtree_test_structure_helper (tree, node->left);
1750     }
1751   if (node->right != tree->nil)
1752     {
1753       g_assert (node->right->parent == node);
1754       _gtk_rbtree_test_structure_helper (tree, node->right);
1755     }
1756
1757   if (node->children != NULL)
1758     {
1759       g_assert (node->children->parent_tree == tree);
1760       g_assert (node->children->parent_node == node);
1761
1762       _gtk_rbtree_test_structure (node->children);
1763     }
1764 }
1765 static void
1766 _gtk_rbtree_test_structure (GtkRBTree *tree)
1767 {
1768   g_assert (tree->root);
1769   if (tree->root == tree->nil)
1770     return;
1771
1772   g_assert (tree->root->parent == tree->nil);
1773   _gtk_rbtree_test_structure_helper (tree, tree->root);
1774 }
1775
1776 void
1777 _gtk_rbtree_test (const gchar *where,
1778                   GtkRBTree   *tree)
1779 {
1780   GtkRBTree *tmp_tree;
1781
1782   if (tree == NULL)
1783     return;
1784
1785   /* Test the entire tree */
1786   tmp_tree = tree;
1787   while (tmp_tree->parent_tree)
1788     tmp_tree = tmp_tree->parent_tree;
1789
1790   g_assert (tmp_tree->nil != NULL);
1791
1792   if (tmp_tree->root == tmp_tree->nil)
1793     return;
1794
1795   _gtk_rbtree_test_structure (tmp_tree);
1796
1797   g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1798              _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1799
1800
1801   _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1802   _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1803   g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
1804 }
1805
1806 static void
1807 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1808                                GtkRBNode *node,
1809                                gint       depth)
1810 {
1811   gint i;
1812   for (i = 0; i < depth; i++)
1813     g_print ("\t");
1814
1815   g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1816            node,
1817            (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1818            node->offset,
1819            node->parity?1:0,
1820            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1821            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1822            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1823   if (node->children != NULL)
1824     {
1825       g_print ("Looking at child.\n");
1826       _gtk_rbtree_debug_spew (node->children);
1827       g_print ("Done looking at child.\n");
1828     }
1829   if (node->left != tree->nil)
1830     {
1831       _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1832     }
1833   if (node->right != tree->nil)
1834     {
1835       _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1836     }
1837 }
1838
1839 void
1840 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1841 {
1842   g_return_if_fail (tree != NULL);
1843
1844   if (tree->root == tree->nil)
1845     g_print ("Empty tree...\n");
1846   else
1847     _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1848 }
1849 #endif /* G_ENABLE_DEBUG */