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