Pileus Git - ~andy/gtk/blob - gtk/gtkrbtree.c

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