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 y_height;
1217
1218   g_return_if_fail (tree != NULL);
1219   g_return_if_fail (node != NULL);
1220
1221
1222 #ifdef G_ENABLE_DEBUG
1223   if (gtk_debug_flags & GTK_DEBUG_TREE)
1224     {
1225       g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1226       _gtk_rbtree_debug_spew (tree);
1227       _gtk_rbtree_test (G_STRLOC, tree);
1228     }
1229 #endif /* G_ENABLE_DEBUG */
1230
1231   /* make sure we're deleting a node that's actually in the tree */
1232   for (x = node; x->parent != tree->nil; x = x->parent)
1233     ;
1234   g_return_if_fail (x == tree->root);
1235
1236 #ifdef G_ENABLE_DEBUG
1237   if (gtk_debug_flags & GTK_DEBUG_TREE)
1238     _gtk_rbtree_test (G_STRLOC, tree);
1239 #endif
1240
1241   if (node->left == tree->nil || node->right == tree->nil)
1242     {
1243       y = node;
1244     }
1245   else
1246     {
1247       y = node->right;
1248
1249       while (y->left != tree->nil)
1250         y = y->left;
1251     }
1252
1253   /* adjust count only beneath tree */
1254   for (x = y; x != tree->nil; x = x->parent)
1255     {
1256       x->count--;
1257     }
1258
1259   /* offsets and parity adjust all the way up through parent trees */
1260   y_height = GTK_RBNODE_GET_HEIGHT (y);
1261
1262   tmp_tree = tree;
1263   tmp_node = y;
1264   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1265     {
1266       tmp_node->offset -= (y_height + (y->children?y->children->root->offset:0));
1267       _fixup_validation (tmp_tree, tmp_node);
1268       _fixup_parity (tmp_tree, tmp_node);
1269       tmp_node = tmp_node->parent;
1270       if (tmp_node == tmp_tree->nil)
1271         {
1272           tmp_node = tmp_tree->parent_node;
1273           tmp_tree = tmp_tree->parent_tree;
1274         }
1275     }
1276
1277   /* x is y's only child, or nil */
1278   if (y->left != tree->nil)
1279     x = y->left;
1280   else
1281     x = y->right;
1282
1283   /* remove y from the parent chain */
1284   x->parent = y->parent;
1285   if (y->parent != tree->nil)
1286     {
1287       if (y == y->parent->left)
1288         y->parent->left = x;
1289       else
1290         y->parent->right = x;
1291     }
1292   else
1293     {
1294       tree->root = x;
1295     }
1296
1297   /* We need to clean up the validity of the tree.
1298    */
1299
1300   tmp_tree = tree;
1301   tmp_node = x;
1302   do
1303     {
1304       /* We skip the first time, iff x is nil */
1305       if (tmp_node != tmp_tree->nil)
1306         {
1307           _fixup_validation (tmp_tree, tmp_node);
1308           _fixup_parity (tmp_tree, tmp_node);
1309         }
1310       tmp_node = tmp_node->parent;
1311       if (tmp_node == tmp_tree->nil)
1312         {
1313           tmp_node = tmp_tree->parent_node;
1314           tmp_tree = tmp_tree->parent_tree;
1315         }
1316     }
1317   while (tmp_tree != NULL);
1318
1319   if (y != node)
1320     {
1321       gint diff;
1322
1323       /* Copy the node over */
1324       if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1325         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
1326       else
1327         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
1328       node->children = y->children;
1329       if (y->children)
1330         {
1331           node->children = y->children;
1332           node->children->parent_node = node;
1333         }
1334       else
1335         {
1336           node->children = NULL;
1337         }
1338       _fixup_validation (tree, node);
1339       _fixup_parity (tree, node);
1340       /* We want to see how different our height is from the previous node.
1341        * To do this, we compare our current height with our supposed height.
1342        */
1343       diff = y_height - GTK_RBNODE_GET_HEIGHT (node);
1344       tmp_tree = tree;
1345       tmp_node = node;
1346
1347       while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1348         {
1349           tmp_node->offset += diff;
1350           _fixup_validation (tmp_tree, tmp_node);
1351           _fixup_parity (tmp_tree, tmp_node);
1352           tmp_node = tmp_node->parent;
1353           if (tmp_node == tmp_tree->nil)
1354             {
1355               tmp_node = tmp_tree->parent_node;
1356               tmp_tree = tmp_tree->parent_tree;
1357             }
1358         }
1359     }
1360
1361   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1362     _gtk_rbtree_remove_node_fixup (tree, x);
1363   _gtk_rbnode_free (y);
1364
1365 #ifdef G_ENABLE_DEBUG
1366   if (gtk_debug_flags & GTK_DEBUG_TREE)
1367     {
1368       g_print ("_gtk_rbtree_remove_node finished...\n");
1369       _gtk_rbtree_debug_spew (tree);
1370       g_print ("\n\n");
1371       _gtk_rbtree_test (G_STRLOC, tree);
1372     }
1373 #endif /* G_ENABLE_DEBUG */
1374 }
1375
1376 GtkRBNode *
1377 _gtk_rbtree_next (GtkRBTree *tree,
1378                   GtkRBNode *node)
1379 {
1380   g_return_val_if_fail (tree != NULL, NULL);
1381   g_return_val_if_fail (node != NULL, NULL);
1382
1383   /* Case 1: the node's below us. */
1384   if (node->right != tree->nil)
1385     {
1386       node = node->right;
1387       while (node->left != tree->nil)
1388         node = node->left;
1389       return node;
1390     }
1391
1392   /* Case 2: it's an ancestor */
1393   while (node->parent != tree->nil)
1394     {
1395       if (node->parent->right == node)
1396         node = node->parent;
1397       else
1398         return (node->parent);
1399     }
1400
1401   /* Case 3: There is no next node */
1402   return NULL;
1403 }
1404
1405 GtkRBNode *
1406 _gtk_rbtree_prev (GtkRBTree *tree,
1407                   GtkRBNode *node)
1408 {
1409   g_return_val_if_fail (tree != NULL, NULL);
1410   g_return_val_if_fail (node != NULL, NULL);
1411
1412   /* Case 1: the node's below us. */
1413   if (node->left != tree->nil)
1414     {
1415       node = node->left;
1416       while (node->right != tree->nil)
1417         node = node->right;
1418       return node;
1419     }
1420
1421   /* Case 2: it's an ancestor */
1422   while (node->parent != tree->nil)
1423     {
1424       if (node->parent->left == node)
1425         node = node->parent;
1426       else
1427         return (node->parent);
1428     }
1429
1430   /* Case 3: There is no next node */
1431   return NULL;
1432 }
1433
1434 void
1435 _gtk_rbtree_next_full (GtkRBTree  *tree,
1436                        GtkRBNode  *node,
1437                        GtkRBTree **new_tree,
1438                        GtkRBNode **new_node)
1439 {
1440   g_return_if_fail (tree != NULL);
1441   g_return_if_fail (node != NULL);
1442   g_return_if_fail (new_tree != NULL);
1443   g_return_if_fail (new_node != NULL);
1444
1445   if (node->children)
1446     {
1447       *new_tree = node->children;
1448       *new_node = (*new_tree)->root;
1449       while ((*new_node)->left != (*new_tree)->nil)
1450         *new_node = (*new_node)->left;
1451       return;
1452     }
1453
1454   *new_tree = tree;
1455   *new_node = _gtk_rbtree_next (tree, node);
1456
1457   while ((*new_node == NULL) &&
1458          (*new_tree != NULL))
1459     {
1460       *new_node = (*new_tree)->parent_node;
1461       *new_tree = (*new_tree)->parent_tree;
1462       if (*new_tree)
1463         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1464     }
1465 }
1466
1467 void
1468 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1469                        GtkRBNode  *node,
1470                        GtkRBTree **new_tree,
1471                        GtkRBNode **new_node)
1472 {
1473   g_return_if_fail (tree != NULL);
1474   g_return_if_fail (node != NULL);
1475   g_return_if_fail (new_tree != NULL);
1476   g_return_if_fail (new_node != NULL);
1477
1478   *new_tree = tree;
1479   *new_node = _gtk_rbtree_prev (tree, node);
1480
1481   if (*new_node == NULL)
1482     {
1483       *new_node = (*new_tree)->parent_node;
1484       *new_tree = (*new_tree)->parent_tree;
1485     }
1486   else
1487     {
1488       while ((*new_node)->children)
1489         {
1490           *new_tree = (*new_node)->children;
1491           *new_node = (*new_tree)->root;
1492           while ((*new_node)->right != (*new_tree)->nil)
1493             *new_node = (*new_node)->right;
1494         }
1495     }
1496 }
1497
1498 gint
1499 _gtk_rbtree_get_depth (GtkRBTree *tree)
1500 {
1501   GtkRBTree *tmp_tree;
1502   gint depth = 0;
1503
1504   tmp_tree = tree->parent_tree;
1505   while (tmp_tree)
1506     {
1507       ++depth;
1508       tmp_tree = tmp_tree->parent_tree;
1509     }
1510
1511   return depth;
1512 }
1513
1514 static void
1515 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1516                                 GtkRBNode             *node,
1517                                 GtkRBTreeTraverseFunc  func,
1518                                 gpointer               data)
1519 {
1520   if (node == tree->nil)
1521     return;
1522
1523   (* func) (tree, node, data);
1524   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1525   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1526 }
1527
1528 static void
1529 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1530                                  GtkRBNode             *node,
1531                                  GtkRBTreeTraverseFunc  func,
1532                                  gpointer               data)
1533 {
1534   if (node == tree->nil)
1535     return;
1536
1537   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1538   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1539   (* func) (tree, node, data);
1540 }
1541
1542 void
1543 _gtk_rbtree_traverse (GtkRBTree             *tree,
1544                       GtkRBNode             *node,
1545                       GTraverseType          order,
1546                       GtkRBTreeTraverseFunc  func,
1547                       gpointer               data)
1548 {
1549   g_return_if_fail (tree != NULL);
1550   g_return_if_fail (node != NULL);
1551   g_return_if_fail (func != NULL);
1552   g_return_if_fail (order <= G_LEVEL_ORDER);
1553
1554   switch (order)
1555     {
1556     case G_PRE_ORDER:
1557       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1558       break;
1559     case G_POST_ORDER:
1560       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1561       break;
1562     case G_IN_ORDER:
1563     case G_LEVEL_ORDER:
1564     default:
1565       g_warning ("unsupported traversal order.");
1566       break;
1567     }
1568 }
1569
1570 static gint
1571 _count_nodes (GtkRBTree *tree,
1572               GtkRBNode *node)
1573 {
1574   gint res;
1575   if (node == tree->nil)
1576     return 0;
1577
1578   g_assert (node->left);
1579   g_assert (node->right);
1580
1581   res = (_count_nodes (tree, node->left) +
1582          _count_nodes (tree, node->right) + 1);
1583
1584   if (res != node->count)
1585     g_print ("Tree failed\n");
1586   return res;
1587 }
1588
1589 static inline
1590 void _fixup_validation (GtkRBTree *tree,
1591                         GtkRBNode *node)
1592 {
1593   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1594       GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1595       (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1596       (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1597       (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1598     {
1599       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1600     }
1601   else
1602     {
1603       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1604     }
1605 }
1606
1607 static inline
1608 void _fixup_parity (GtkRBTree *tree,
1609                     GtkRBNode *node)
1610 {
1611   node->parity = 1 +
1612     ((node->children != NULL && node->children->root != node->children->nil) ? node->children->root->parity : 0) +
1613     ((node->left != tree->nil) ? node->left->parity : 0) +
1614     ((node->right != tree->nil) ? node->right->parity : 0);
1615 }
1616
1617 #ifdef G_ENABLE_DEBUG
1618 static guint
1619 get_parity (GtkRBNode *node)
1620 {
1621   guint child_total = 0;
1622   guint rem;
1623
1624   /* The parity of a node is node->parity minus
1625    * the parity of left, right, and children.
1626    *
1627    * This is equivalent to saying that if left, right, children
1628    * sum to 0 parity, then node->parity is the parity of node,
1629    * and if left, right, children are odd parity, then
1630    * node->parity is the reverse of the node's parity.
1631    */
1632
1633   child_total += (guint) node->left->parity;
1634   child_total += (guint) node->right->parity;
1635
1636   if (node->children)
1637     child_total += (guint) node->children->root->parity;
1638
1639   rem = child_total % 2;
1640
1641   if (rem == 0)
1642     return node->parity;
1643   else
1644     return !node->parity;
1645 }
1646
1647 static guint
1648 count_parity (GtkRBTree *tree,
1649               GtkRBNode *node)
1650 {
1651   guint res;
1652
1653   if (node == tree->nil)
1654     return 0;
1655
1656   res =
1657     count_parity (tree, node->left) +
1658     count_parity (tree, node->right) +
1659     (guint)1 +
1660     (node->children ? count_parity (node->children, node->children->root) : 0);
1661
1662   res = res % (guint)2;
1663
1664   if (res != node->parity)
1665     g_print ("parity incorrect for node\n");
1666
1667   if (get_parity (node) != 1)
1668     g_error ("Node has incorrect parity %d", get_parity (node));
1669
1670   return res;
1671 }
1672
1673 static void
1674 _gtk_rbtree_test_height (GtkRBTree *tree,
1675                          GtkRBNode *node)
1676 {
1677   gint computed_offset = 0;
1678
1679   /* This whole test is sort of a useless truism. */
1680
1681   if (node->left != tree->nil)
1682     computed_offset += node->left->offset;
1683
1684   if (node->right != tree->nil)
1685     computed_offset += node->right->offset;
1686
1687   if (node->children && node->children->root != node->children->nil)
1688     computed_offset += node->children->root->offset;
1689
1690   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1691     g_error ("node has broken offset\n");
1692
1693   if (node->left != tree->nil)
1694     _gtk_rbtree_test_height (tree, node->left);
1695
1696   if (node->right != tree->nil)
1697     _gtk_rbtree_test_height (tree, node->right);
1698
1699   if (node->children && node->children->root != node->children->nil)
1700     _gtk_rbtree_test_height (node->children, node->children->root);
1701 }
1702
1703 static void
1704 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1705                         GtkRBNode *node,
1706                          gint      expected_dirtyness)
1707 {
1708
1709   if (expected_dirtyness)
1710     {
1711       g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1712                 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1713                 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1714                 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1715                 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1716     }
1717   else
1718     {
1719       g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1720                 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1721       if (node->left != tree->nil)
1722         g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1723       if (node->right != tree->nil)
1724         g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1725       if (node->children != NULL)
1726         g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1727     }
1728
1729   if (node->left != tree->nil)
1730     _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1731   if (node->right != tree->nil)
1732     _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1733   if (node->children != NULL && node->children->root != node->children->nil)
1734     _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1735 }
1736
1737 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1738
1739 static void
1740 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1741                                    GtkRBNode *node)
1742 {
1743   g_assert (node != tree->nil);
1744
1745   g_assert (node->left != NULL);
1746   g_assert (node->right != NULL);
1747   g_assert (node->parent != NULL);
1748
1749   if (node->left != tree->nil)
1750     {
1751       g_assert (node->left->parent == node);
1752       _gtk_rbtree_test_structure_helper (tree, node->left);
1753     }
1754   if (node->right != tree->nil)
1755     {
1756       g_assert (node->right->parent == node);
1757       _gtk_rbtree_test_structure_helper (tree, node->right);
1758     }
1759
1760   if (node->children != NULL)
1761     {
1762       g_assert (node->children->parent_tree == tree);
1763       g_assert (node->children->parent_node == node);
1764
1765       _gtk_rbtree_test_structure (node->children);
1766     }
1767 }
1768 static void
1769 _gtk_rbtree_test_structure (GtkRBTree *tree)
1770 {
1771   g_assert (tree->root);
1772   if (tree->root == tree->nil)
1773     return;
1774
1775   g_assert (tree->root->parent == tree->nil);
1776   _gtk_rbtree_test_structure_helper (tree, tree->root);
1777 }
1778
1779 void
1780 _gtk_rbtree_test (const gchar *where,
1781                   GtkRBTree   *tree)
1782 {
1783   GtkRBTree *tmp_tree;
1784
1785   if (tree == NULL)
1786     return;
1787
1788   /* Test the entire tree */
1789   tmp_tree = tree;
1790   while (tmp_tree->parent_tree)
1791     tmp_tree = tmp_tree->parent_tree;
1792
1793   g_assert (tmp_tree->nil != NULL);
1794
1795   if (tmp_tree->root == tmp_tree->nil)
1796     return;
1797
1798   _gtk_rbtree_test_structure (tmp_tree);
1799
1800   g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1801              _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1802
1803
1804   _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1805   _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1806   g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
1807 }
1808
1809 static void
1810 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1811                                GtkRBNode *node,
1812                                gint       depth)
1813 {
1814   gint i;
1815   for (i = 0; i < depth; i++)
1816     g_print ("\t");
1817
1818   g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1819            node,
1820            (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1821            node->offset,
1822            node->parity?1:0,
1823            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1824            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1825            (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1826   if (node->children != NULL)
1827     {
1828       g_print ("Looking at child.\n");
1829       _gtk_rbtree_debug_spew (node->children);
1830       g_print ("Done looking at child.\n");
1831     }
1832   if (node->left != tree->nil)
1833     {
1834       _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1835     }
1836   if (node->right != tree->nil)
1837     {
1838       _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1839     }
1840 }
1841
1842 void
1843 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1844 {
1845   g_return_if_fail (tree != NULL);
1846
1847   if (tree->root == tree->nil)
1848     g_print ("Empty tree...\n");
1849   else
1850     _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1851 }
1852 #endif /* G_ENABLE_DEBUG */