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

   1 /* gtkrbtree.c
   2  * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include "gtkrbtree.h"
  21 #include "gtkdebug.h"
  22
  23 static void       _gtk_rbnode_validate_allocator (GAllocator *allocator);
  24 static GtkRBNode *_gtk_rbnode_new                (GtkRBTree  *tree,
  25                                                   gint        height);
  26 static void       _gtk_rbnode_free               (GtkRBNode  *node);
  27 static void       _gtk_rbnode_rotate_left        (GtkRBTree  *tree,
  28                                                   GtkRBNode  *node);
  29 static void       _gtk_rbnode_rotate_left        (GtkRBTree  *tree,
  30                                                   GtkRBNode  *node);
  31 static void       _gtk_rbtree_insert_fixup       (GtkRBTree  *tree,
  32                                                   GtkRBNode  *node);
  33 static void       _gtk_rbtree_remove_node_fixup  (GtkRBTree  *tree,
  34                                                   GtkRBNode  *node);
  35 static gint       _count_nodes                   (GtkRBTree  *tree,
  36                                                   GtkRBNode  *node);
  37
  38
  39 /* node allocation
  40  */
  41 struct _GAllocator /* from gmem.c */
  42 {
  43   gchar      *name;
  44   guint16     n_preallocs;
  45   guint       is_unused : 1;
  46   guint       type : 4;
  47   GAllocator *last;
  48   GMemChunk  *mem_chunk;
  49   GtkRBNode  *free_nodes; /* implementation specific */
  50 };
  51
  52
  53 G_LOCK_DEFINE_STATIC (current_allocator);
  54 static GAllocator *current_allocator = NULL;
  55
  56 /* HOLDS: current_allocator_lock */
  57 static void
  58 _gtk_rbnode_validate_allocator (GAllocator *allocator)
  59 {
  60   g_return_if_fail (allocator != NULL);
  61   g_return_if_fail (allocator->is_unused == TRUE);
  62
  63   if (allocator->type != G_ALLOCATOR_NODE)
  64     {
  65       allocator->type = G_ALLOCATOR_NODE;
  66       if (allocator->mem_chunk)
  67         {
  68           g_mem_chunk_destroy (allocator->mem_chunk);
  69           allocator->mem_chunk = NULL;
  70         }
  71     }
  72
  73   if (!allocator->mem_chunk)
  74     {
  75       allocator->mem_chunk = g_mem_chunk_new (allocator->name,
  76                                               sizeof (GtkRBNode),
  77                                               sizeof (GtkRBNode) * allocator->n_preallocs,
  78                                               G_ALLOC_ONLY);
  79       allocator->free_nodes = NULL;
  80     }
  81
  82   allocator->is_unused = FALSE;
  83 }
  84
  85 static GtkRBNode *
  86 _gtk_rbnode_new (GtkRBTree *tree,
  87                  gint       height)
  88 {
  89   GtkRBNode *node;
  90
  91   G_LOCK (current_allocator);
  92   if (!current_allocator)
  93     {
  94       GAllocator *allocator = g_allocator_new ("GTK+ default GtkRBNode allocator",
  95                                                128);
  96       _gtk_rbnode_validate_allocator (allocator);
  97       allocator->last = NULL;
  98       current_allocator = allocator;
  99     }
 100   if (!current_allocator->free_nodes)
 101     node = g_chunk_new (GtkRBNode, current_allocator->mem_chunk);
 102   else
 103     {
 104       node = current_allocator->free_nodes;
 105       current_allocator->free_nodes = node->left;
 106     }
 107   G_UNLOCK (current_allocator);
 108
 109   node->left = tree->nil;
 110   node->right = tree->nil;
 111   node->parent = tree->nil;
 112   node->flags = GTK_RBNODE_RED;
 113   node->count = 1;
 114   node->children = NULL;
 115   node->offset = height;
 116   return node;
 117 }
 118
 119 static void
 120 _gtk_rbnode_free (GtkRBNode *node)
 121 {
 122   G_LOCK (current_allocator);
 123   node->left = current_allocator->free_nodes;
 124   current_allocator->free_nodes = node;
 125   G_UNLOCK (current_allocator);
 126 }
 127
 128 static void
 129 _gtk_rbnode_rotate_left (GtkRBTree *tree,
 130                          GtkRBNode *node)
 131 {
 132   gint node_height, right_height;
 133   GtkRBNode *right = node->right;
 134
 135   g_return_if_fail (node != tree->nil);
 136
 137   node_height = node->offset -
 138     (node->left?node->left->offset:0) -
 139     (node->right?node->right->offset:0) -
 140     (node->children?node->children->root->offset:0);
 141   right_height = right->offset -
 142     (right->left?right->left->offset:0) -
 143     (right->right?right->right->offset:0) -
 144     (right->children?right->children->root->offset:0);
 145
 146   node->right = right->left;
 147   if (right->left != tree->nil)
 148     right->left->parent = node;
 149
 150   if (right != tree->nil)
 151     right->parent = node->parent;
 152   if (node->parent != tree->nil)
 153     {
 154       if (node == node->parent->left)
 155         node->parent->left = right;
 156       else
 157         node->parent->right = right;
 158     } else {
 159       tree->root = right;
 160     }
 161
 162   right->left = node;
 163   if (node != tree->nil)
 164     node->parent = right;
 165
 166   node->count = 1 + (node->left?node->left->count:0) +
 167     (node->right?node->right->count:0);
 168   right->count = 1 + (right->left?right->left->count:0) +
 169     (right->right?right->right->count:0);
 170   node->offset = node_height +
 171     (node->left?node->left->offset:0) +
 172     (node->right?node->right->offset:0) +
 173     (node->children?node->children->root->offset:0);
 174   right->offset = right_height +
 175     (right->left?right->left->offset:0) +
 176     (right->right?right->right->offset:0) +
 177     (right->children?right->children->root->offset:0);
 178 }
 179
 180 static void
 181 _gtk_rbnode_rotate_right (GtkRBTree *tree,
 182                           GtkRBNode *node)
 183 {
 184   gint node_height, left_height;
 185   GtkRBNode *left = node->left;
 186
 187   g_return_if_fail (node != tree->nil);
 188
 189   node_height = node->offset -
 190     (node->left?node->left->offset:0) -
 191     (node->right?node->right->offset:0) -
 192     (node->children?node->children->root->offset:0);
 193   left_height = left->offset -
 194     (left->left?left->left->offset:0) -
 195     (left->right?left->right->offset:0) -
 196     (left->children?left->children->root->offset:0);
 197
 198   node->left = left->right;
 199   if (left->right != tree->nil)
 200     left->right->parent = node;
 201
 202   if (left != tree->nil)
 203     left->parent = node->parent;
 204   if (node->parent != tree->nil)
 205     {
 206       if (node == node->parent->right)
 207         node->parent->right = left;
 208       else
 209         node->parent->left = left;
 210     }
 211   else
 212     {
 213       tree->root = left;
 214     }
 215
 216   /* link node and left */
 217   left->right = node;
 218   if (node != tree->nil)
 219     node->parent = left;
 220
 221   node->count = 1 + (node->left?node->left->count:0) +
 222     (node->right?node->right->count:0);
 223   left->count = 1 + (left->left?left->left->count:0) +
 224     (left->right?left->right->count:0);
 225   node->offset = node_height +
 226     (node->left?node->left->offset:0) +
 227     (node->right?node->right->offset:0) +
 228     (node->children?node->children->root->offset:0);
 229   left->offset = left_height +
 230     (left->left?left->left->offset:0) +
 231     (left->right?left->right->offset:0) +
 232     (left->children?left->children->root->offset:0);
 233 }
 234
 235 static void
 236 _gtk_rbtree_insert_fixup (GtkRBTree *tree,
 237                           GtkRBNode *node)
 238 {
 239
 240   /* check Red-Black properties */
 241   while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)
 242     {
 243       /* we have a violation */
 244       if (node->parent == node->parent->parent->left)
 245         {
 246           GtkRBNode *y = node->parent->parent->right;
 247           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 248             {
 249                                 /* uncle is GTK_RBNODE_RED */
 250               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 251               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 252               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 253               node = node->parent->parent;
 254             }
 255           else
 256             {
 257                                 /* uncle is GTK_RBNODE_BLACK */
 258               if (node == node->parent->right)
 259                 {
 260                   /* make node a left child */
 261                   node = node->parent;
 262                   _gtk_rbnode_rotate_left (tree, node);
 263                 }
 264
 265                                 /* recolor and rotate */
 266               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 267               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 268               _gtk_rbnode_rotate_right(tree, node->parent->parent);
 269             }
 270         }
 271       else
 272         {
 273           /* mirror image of above code */
 274           GtkRBNode *y = node->parent->parent->left;
 275           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 276             {
 277                                 /* uncle is GTK_RBNODE_RED */
 278               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 279               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 280               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 281               node = node->parent->parent;
 282             }
 283           else
 284             {
 285                                 /* uncle is GTK_RBNODE_BLACK */
 286               if (node == node->parent->left)
 287                 {
 288                   node = node->parent;
 289                   _gtk_rbnode_rotate_right (tree, node);
 290                 }
 291               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 292               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 293               _gtk_rbnode_rotate_left (tree, node->parent->parent);
 294             }
 295         }
 296     }
 297   GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);
 298 }
 299
 300 static void
 301 _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
 302                                GtkRBNode *node)
 303 {
 304   while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
 305     {
 306       if (node == node->parent->left)
 307         {
 308           GtkRBNode *w = node->parent->right;
 309           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 310             {
 311               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 312               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
 313               _gtk_rbnode_rotate_left (tree, node->parent);
 314               w = node->parent->right;
 315             }
 316           if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 317             {
 318               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 319               node = node->parent;
 320             }
 321           else
 322             {
 323               if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 324                 {
 325                   GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 326                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 327                   _gtk_rbnode_rotate_right (tree, w);
 328                   w = node->parent->right;
 329                 }
 330               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
 331               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 332               GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 333               _gtk_rbnode_rotate_left (tree, node->parent);
 334               node = tree->root;
 335             }
 336         }
 337       else
 338         {
 339           GtkRBNode *w = node->parent->left;
 340           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 341             {
 342               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 343               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
 344               _gtk_rbnode_rotate_right (tree, node->parent);
 345               w = node->parent->left;
 346             }
 347           if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 348             {
 349               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 350               node = node->parent;
 351             }
 352           else
 353             {
 354               if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 355                 {
 356                   GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 357                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 358                   _gtk_rbnode_rotate_left (tree, w);
 359                   w = node->parent->left;
 360                 }
 361               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
 362               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 363               GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 364               _gtk_rbnode_rotate_right (tree, node->parent);
 365               node = tree->root;
 366             }
 367         }
 368     }
 369   GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
 370 }
 371
 372 /* Public functions */
 373 void
 374 _gtk_rbnode_push_allocator (GAllocator *allocator)
 375 {
 376   G_LOCK (current_allocator);
 377   _gtk_rbnode_validate_allocator ( allocator );
 378   allocator->last = current_allocator;
 379   current_allocator = allocator;
 380   G_UNLOCK (current_allocator);
 381 }
 382
 383 void
 384 _gtk_rbnode_pop_allocator (void)
 385 {
 386   G_LOCK (current_allocator);
 387   if (current_allocator)
 388     {
 389       GAllocator *allocator;
 390
 391       allocator = current_allocator;
 392       current_allocator = allocator->last;
 393       allocator->last = NULL;
 394       allocator->is_unused = TRUE;
 395     }
 396   G_UNLOCK (current_allocator);
 397 }
 398
 399 GtkRBTree *
 400 _gtk_rbtree_new (void)
 401 {
 402   GtkRBTree *retval;
 403
 404   retval = (GtkRBTree *) g_new (GtkRBTree, 1);
 405   retval->parent_tree = NULL;
 406   retval->parent_node = NULL;
 407
 408   retval->nil = g_new0 (GtkRBNode, 1);
 409   retval->nil->left = NULL;
 410   retval->nil->right = NULL;
 411   retval->nil->parent = NULL;
 412   retval->nil->flags = GTK_RBNODE_BLACK;
 413   retval->nil->count = 0;
 414   retval->nil->offset = 0;
 415
 416   retval->root = retval->nil;
 417   return retval;
 418 }
 419
 420 static void
 421 _gtk_rbtree_free_helper (GtkRBTree  *tree,
 422                          GtkRBNode  *node,
 423                          gpointer    data)
 424 {
 425   if (node->children)
 426     _gtk_rbtree_free (node->children);
 427
 428   _gtk_rbnode_free (node);
 429 }
 430
 431 void
 432 _gtk_rbtree_free (GtkRBTree *tree)
 433 {
 434   _gtk_rbtree_traverse (tree,
 435                         tree->root,
 436                         G_POST_ORDER,
 437                         _gtk_rbtree_free_helper,
 438                         NULL);
 439
 440   if (tree->parent_node &&
 441       tree->parent_node->children == tree)
 442     tree->parent_node->children = NULL;
 443   _gtk_rbnode_free (tree->nil);
 444   g_free (tree);
 445 }
 446
 447 void
 448 _gtk_rbtree_remove (GtkRBTree *tree)
 449 {
 450   GtkRBTree *tmp_tree;
 451   GtkRBNode *tmp_node;
 452
 453   gint height = tree->root->offset;
 454   tmp_tree = tree->parent_tree;
 455   tmp_node = tree->parent_node;
 456
 457   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 458     {
 459       tmp_node->offset -= height;
 460       tmp_node = tmp_node->parent;
 461       if (tmp_node == tmp_tree->nil)
 462         {
 463           tmp_node = tmp_tree->parent_node;
 464           tmp_tree = tmp_tree->parent_tree;
 465         }
 466     }
 467   _gtk_rbtree_free (tree);
 468 }
 469
 470
 471 GtkRBNode *
 472 _gtk_rbtree_insert_after (GtkRBTree  *tree,
 473                           GtkRBNode  *current,
 474                           gint        height)
 475 {
 476   GtkRBNode *node;
 477   gboolean right = TRUE;
 478   GtkRBNode *tmp_node;
 479   GtkRBTree *tmp_tree;
 480
 481   if (current != NULL && current->right != tree->nil)
 482     {
 483       current = current->right;
 484       while (current->left != tree->nil)
 485         current = current->left;
 486       right = FALSE;
 487     }
 488
 489   /* setup new node */
 490   node = _gtk_rbnode_new (tree, height);
 491   node->parent = (current?current:tree->nil);
 492
 493   /* insert node in tree */
 494   if (current)
 495     {
 496       if (right)
 497         current->right = node;
 498       else
 499         current->left = node;
 500       tmp_node = node->parent;
 501       tmp_tree = tree;
 502     }
 503   else
 504     {
 505       tree->root = node;
 506       tmp_node = tree->parent_node;
 507       tmp_tree = tree->parent_tree;
 508     }
 509
 510   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 511     {
 512       /* We only want to propagate the count if we are in the tree we
 513        * started in. */
 514       if (tmp_tree == tree)
 515         tmp_node->count++;
 516       tmp_node->offset += height;
 517       tmp_node = tmp_node->parent;
 518       if (tmp_node == tmp_tree->nil)
 519         {
 520           tmp_node = tmp_tree->parent_node;
 521           tmp_tree = tmp_tree->parent_tree;
 522         }
 523     }
 524   _gtk_rbtree_insert_fixup (tree, node);
 525
 526   if (gtk_debug_flags & GTK_DEBUG_TREE)
 527     _gtk_rbtree_test (tree);
 528
 529   return node;
 530 }
 531
 532 GtkRBNode *
 533 _gtk_rbtree_insert_before (GtkRBTree  *tree,
 534                            GtkRBNode  *current,
 535                            gint        height)
 536 {
 537   GtkRBNode *node;
 538   gboolean left = TRUE;
 539   GtkRBNode *tmp_node;
 540   GtkRBTree *tmp_tree;
 541
 542   if (current != NULL && current->left != tree->nil)
 543     {
 544       current = current->left;
 545       while (current->right != tree->nil)
 546         current = current->right;
 547       left = FALSE;
 548     }
 549
 550   /* setup new node */
 551   node = _gtk_rbnode_new (tree, height);
 552   node->parent = (current?current:tree->nil);
 553
 554   /* insert node in tree */
 555   if (current)
 556     {
 557       if (left)
 558         current->left = node;
 559       else
 560         current->right = node;
 561       tmp_node = node->parent;
 562       tmp_tree = tree;
 563     }
 564   else
 565     {
 566       tree->root = node;
 567       tmp_node = tree->parent_node;
 568       tmp_tree = tree->parent_tree;
 569     }
 570
 571   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 572     {
 573       /* We only want to propagate the count if we are in the tree we
 574        * started in. */
 575       if (tmp_tree == tree)
 576         tmp_node->count++;
 577       tmp_node->offset += height;
 578       tmp_node = tmp_node->parent;
 579       if (tmp_node == tmp_tree->nil)
 580         {
 581           tmp_node = tmp_tree->parent_node;
 582           tmp_tree = tmp_tree->parent_tree;
 583         }
 584     }
 585   _gtk_rbtree_insert_fixup (tree, node);
 586
 587   if (gtk_debug_flags & GTK_DEBUG_TREE)
 588     _gtk_rbtree_test (tree);
 589
 590   return node;
 591 }
 592
 593 GtkRBNode *
 594 _gtk_rbtree_find_count (GtkRBTree *tree,
 595                         gint       count)
 596 {
 597   GtkRBNode *node;
 598
 599   node = tree->root;
 600   while (node != tree->nil && (node->left->count + 1 != count))
 601     {
 602       if (node->left->count >= count)
 603         node = node->left;
 604       else
 605         {
 606           count -= (node->left->count + 1);
 607           node = node->right;
 608         }
 609     }
 610   if (node == tree->nil)
 611     return NULL;
 612   return node;
 613 }
 614
 615 void
 616 _gtk_rbtree_node_set_height (GtkRBTree *tree,
 617                              GtkRBNode *node,
 618                              gint       height)
 619 {
 620   gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
 621   GtkRBNode *tmp_node = node;
 622   GtkRBTree *tmp_tree = tree;
 623
 624   if (diff == 0)
 625     return;
 626
 627   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 628     {
 629       tmp_node->offset += diff;
 630       tmp_node = tmp_node->parent;
 631       if (tmp_node == tmp_tree->nil)
 632         {
 633           tmp_node = tmp_tree->parent_node;
 634           tmp_tree = tmp_tree->parent_tree;
 635         }
 636     }
 637 }
 638
 639 gint
 640 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 641                               GtkRBNode *node)
 642 {
 643   GtkRBNode *last;
 644   gint retval;
 645
 646   g_assert (node);
 647   g_assert (node->left);
 648
 649   retval = node->left->offset;
 650
 651   while (tree && node && node != tree->nil)
 652     {
 653       last = node;
 654       node = node->parent;
 655
 656       /* Add left branch, plus children, iff we came from the right */
 657       if (node->right == last)
 658         retval += node->offset - node->right->offset;
 659
 660       if (node == tree->nil)
 661         {
 662           node = tree->parent_node;
 663           tree = tree->parent_tree;
 664
 665           /* Add the parent node, plus the left branch. */
 666           if (node)
 667             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 668         }
 669     }
 670   return retval;
 671 }
 672
 673 gint
 674 _gtk_rbtree_find_offset (GtkRBTree  *tree,
 675                          gint        height,
 676                          GtkRBTree **new_tree,
 677                          GtkRBNode **new_node)
 678 {
 679   GtkRBNode *tmp_node;
 680
 681   if (height < 0)
 682     {
 683       *new_tree = NULL;
 684       *new_node = NULL;
 685       return 0;
 686     }
 687
 688   tmp_node = tree->root;
 689   while (tmp_node != tree->nil &&
 690          (tmp_node->left->offset > height ||
 691           (tmp_node->offset - tmp_node->right->offset) < height))
 692     {
 693       if (tmp_node->left->offset > height)
 694         tmp_node = tmp_node->left;
 695       else
 696         {
 697           height -= (tmp_node->offset - tmp_node->right->offset);
 698           tmp_node = tmp_node->right;
 699         }
 700     }
 701   if (tmp_node == tree->nil)
 702     {
 703       *new_tree = NULL;
 704       *new_node = NULL;
 705       return 0;
 706     }
 707   if (tmp_node->children)
 708     {
 709       if ((tmp_node->offset -
 710            tmp_node->right->offset -
 711            tmp_node->children->root->offset) > height)
 712         {
 713           *new_tree = tree;
 714           *new_node = tmp_node;
 715           return (height - tmp_node->left->offset);
 716         }
 717       return _gtk_rbtree_find_offset (tmp_node->children,
 718                                       height - tmp_node->left->offset -
 719                                       (tmp_node->offset -
 720                                        tmp_node->left->offset -
 721                                        tmp_node->right->offset -
 722                                        tmp_node->children->root->offset),
 723                                       new_tree,
 724                                       new_node);
 725     }
 726   *new_tree = tree;
 727   *new_node = tmp_node;
 728   return (height - tmp_node->left->offset);
 729 }
 730
 731
 732 void
 733 _gtk_rbtree_remove_node (GtkRBTree *tree,
 734                          GtkRBNode *node)
 735 {
 736   GtkRBNode *x, *y;
 737
 738   g_return_if_fail (tree != NULL);
 739   g_return_if_fail (node != NULL);
 740   /* make sure we're deleting a node that's actually in the tree */
 741   for (x = node; x->parent != tree->nil; x = x->parent)
 742     ;
 743   g_return_if_fail (x == tree->root);
 744
 745   if (node->left == tree->nil || node->right == tree->nil)
 746     {
 747       y = node;
 748     }
 749   else
 750     {
 751       y = node->right;
 752
 753       while (y->left != tree->nil)
 754         y = y->left;
 755     }
 756   for (x = y; x != tree->nil; x = x->parent)
 757     x->count--;
 758   y->count = node->count;
 759   /* x is y's only child */
 760   if (y->left != tree->nil)
 761     x = y->left;
 762   else
 763     x = y->right;
 764
 765   /* remove y from the parent chain */
 766   x->parent = y->parent;
 767   if (y->parent != tree->nil)
 768     if (y == y->parent->left)
 769       y->parent->left = x;
 770     else
 771       y->parent->right = x;
 772   else
 773     tree->root = x;
 774
 775   if (y != node)
 776     node->children = y->children;
 777
 778   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
 779     _gtk_rbtree_remove_node_fixup (tree, x);
 780
 781   G_LOCK (current_allocator);
 782   y->left = current_allocator->free_nodes;
 783   current_allocator->free_nodes = y;
 784   G_UNLOCK (current_allocator);
 785
 786   if (gtk_debug_flags & GTK_DEBUG_TREE)
 787     _gtk_rbtree_test (tree);
 788 }
 789
 790 GtkRBNode *
 791 _gtk_rbtree_next (GtkRBTree *tree,
 792                   GtkRBNode *node)
 793 {
 794   g_return_val_if_fail (tree != NULL, NULL);
 795   g_return_val_if_fail (node != NULL, NULL);
 796
 797   /* Case 1: the node's below us. */
 798   if (node->right != tree->nil)
 799     {
 800       node = node->right;
 801       while (node->left != tree->nil)
 802         node = node->left;
 803       return node;
 804     }
 805
 806   /* Case 2: it's an ancestor */
 807   while (node->parent != tree->nil)
 808     {
 809       if (node->parent->right == node)
 810         node = node->parent;
 811       else
 812         return (node->parent);
 813     }
 814
 815   /* Case 3: There is no next node */
 816   return NULL;
 817 }
 818
 819 GtkRBNode *
 820 _gtk_rbtree_prev (GtkRBTree *tree,
 821                   GtkRBNode *node)
 822 {
 823   g_return_val_if_fail (tree != NULL, NULL);
 824   g_return_val_if_fail (node != NULL, NULL);
 825
 826   /* Case 1: the node's below us. */
 827   if (node->left != tree->nil)
 828     {
 829       node = node->left;
 830       while (node->right != tree->nil)
 831         node = node->right;
 832       return node;
 833     }
 834
 835   /* Case 2: it's an ancestor */
 836   while (node->parent != tree->nil)
 837     {
 838       if (node->parent->left == node)
 839         node = node->parent;
 840       else
 841         return (node->parent);
 842     }
 843
 844   /* Case 3: There is no next node */
 845   return NULL;
 846 }
 847
 848 void
 849 _gtk_rbtree_next_full (GtkRBTree  *tree,
 850                        GtkRBNode  *node,
 851                        GtkRBTree **new_tree,
 852                        GtkRBNode **new_node)
 853 {
 854   g_return_if_fail (tree != NULL);
 855   g_return_if_fail (node != NULL);
 856   g_return_if_fail (new_tree != NULL);
 857   g_return_if_fail (new_node != NULL);
 858
 859   if (node->children)
 860     {
 861       *new_tree = node->children;
 862       *new_node = (*new_tree)->root;
 863       while ((*new_node)->left != (*new_tree)->nil)
 864         *new_node = (*new_node)->left;
 865       return;
 866     }
 867
 868   *new_tree = tree;
 869   *new_node = _gtk_rbtree_next (tree, node);
 870
 871   while ((*new_node == NULL) &&
 872          (*new_tree != NULL))
 873     {
 874       *new_node = (*new_tree)->parent_node;
 875       *new_tree = (*new_tree)->parent_tree;
 876       if (*new_tree)
 877         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
 878     }
 879 }
 880
 881 void
 882 _gtk_rbtree_prev_full (GtkRBTree  *tree,
 883                        GtkRBNode  *node,
 884                        GtkRBTree **new_tree,
 885                        GtkRBNode **new_node)
 886 {
 887   g_return_if_fail (tree != NULL);
 888   g_return_if_fail (node != NULL);
 889   g_return_if_fail (new_tree != NULL);
 890   g_return_if_fail (new_node != NULL);
 891
 892   *new_tree = tree;
 893   *new_node = _gtk_rbtree_prev (tree, node);
 894
 895   if (*new_node == NULL)
 896     {
 897       *new_node = (*new_tree)->parent_node;
 898       *new_tree = (*new_tree)->parent_tree;
 899     }
 900   else
 901     {
 902       while ((*new_node)->children)
 903         {
 904           *new_tree = (*new_node)->children;
 905           *new_node = (*new_tree)->root;
 906           while ((*new_node)->right != (*new_tree)->nil)
 907             *new_node = (*new_node)->right;
 908         }
 909     }
 910 }
 911
 912 gint
 913 _gtk_rbtree_get_depth (GtkRBTree *tree)
 914 {
 915   GtkRBTree *tmp_tree;
 916   gint depth = 0;
 917
 918   tmp_tree = tree->parent_tree;
 919   while (tmp_tree)
 920     {
 921       ++depth;
 922       tmp_tree = tmp_tree->parent_tree;
 923     }
 924
 925   return depth;
 926 }
 927
 928 static void
 929 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
 930                                 GtkRBNode             *node,
 931                                 GtkRBTreeTraverseFunc  func,
 932                                 gpointer               data)
 933 {
 934   if (node == tree->nil)
 935     return;
 936
 937   (* func) (tree, node, data);
 938   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
 939   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
 940 }
 941
 942 static void
 943 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
 944                                  GtkRBNode             *node,
 945                                  GtkRBTreeTraverseFunc  func,
 946                                  gpointer               data)
 947 {
 948   if (node == tree->nil)
 949     return;
 950
 951   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
 952   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
 953   (* func) (tree, node, data);
 954 }
 955
 956 void
 957 _gtk_rbtree_traverse (GtkRBTree             *tree,
 958                       GtkRBNode             *node,
 959                       GTraverseType          order,
 960                       GtkRBTreeTraverseFunc  func,
 961                       gpointer               data)
 962 {
 963   g_return_if_fail (tree != NULL);
 964   g_return_if_fail (node != NULL);
 965   g_return_if_fail (func != NULL);
 966   g_return_if_fail (order <= G_LEVEL_ORDER);
 967
 968   switch (order)
 969     {
 970     case G_PRE_ORDER:
 971       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
 972       break;
 973     case G_POST_ORDER:
 974       _gtk_rbtree_traverse_post_order (tree, node, func, data);
 975       break;
 976     case G_IN_ORDER:
 977     case G_LEVEL_ORDER:
 978     default:
 979       g_warning ("unsupported traversal order.");
 980       break;
 981     }
 982 }
 983
 984 static gint
 985 _count_nodes (GtkRBTree *tree,
 986               GtkRBNode *node)
 987 {
 988   gint res;
 989   if (node == tree->nil)
 990     return 0;
 991
 992   res = (_count_nodes (tree, node->left) +
 993          _count_nodes (tree, node->right) + 1);
 994
 995   if (res != node->count)
 996     g_print ("Tree failed\n");
 997   return res;
 998 }
 999
1000 void
1001 _gtk_rbtree_test (GtkRBTree *tree)
1002 {
1003   if ((_count_nodes (tree, tree->root->left) +
1004        _count_nodes (tree, tree->root->right) + 1) == tree->root->count)
1005     g_print ("Tree passed\n");
1006   else
1007     g_print ("Tree failed\n");
1008
1009 }
1010
1011 static void
1012 _gtk_rbtree_test_height_helper (GtkRBTree *tree,
1013                                 GtkRBNode *node,
1014                                 gint       height)
1015 {
1016   if (node == tree->nil)
1017     return;
1018
1019   if (node->offset -
1020       (node->left?node->left->offset:0) -
1021       (node->right?node->right->offset:0) -
1022       (node->children?node->children->root->offset:0) != height)
1023     g_error ("tree failed\n");
1024
1025   _gtk_rbtree_test_height_helper (tree, node->left, height);
1026   _gtk_rbtree_test_height_helper (tree, node->right, height);
1027   if (node->children)
1028     _gtk_rbtree_test_height_helper (node->children, node->children->root, height);
1029
1030 }
1031
1032 void
1033 _gtk_rbtree_test_height (GtkRBTree *tree,
1034                          gint       height)
1035 {
1036   _gtk_rbtree_test_height_helper (tree, tree->root, height);
1037 }