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