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 = node->left->offset;
 645
 646   while (tree && node && node != tree->nil)
 647     {
 648       last = node;
 649       node = node->parent;
 650       if (node->right == last)
 651         retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 652       if (node == tree->nil)
 653         {
 654           node = tree->parent_node;
 655           tree = tree->parent_tree;
 656           if (node)
 657             retval += node->left->offset;
 658         }
 659     }
 660   return retval;
 661 }
 662
 663 gint
 664 _gtk_rbtree_find_offset (GtkRBTree  *tree,
 665                          gint        height,
 666                          GtkRBTree **new_tree,
 667                          GtkRBNode **new_node)
 668 {
 669   GtkRBNode *tmp_node;
 670
 671   if (height < 0)
 672     {
 673       *new_tree = NULL;
 674       *new_node = NULL;
 675       return 0;
 676     }
 677
 678   tmp_node = tree->root;
 679   while (tmp_node != tree->nil &&
 680          (tmp_node->left->offset > height ||
 681           (tmp_node->offset - tmp_node->right->offset) < height))
 682     {
 683       if (tmp_node->left->offset > height)
 684         tmp_node = tmp_node->left;
 685       else
 686         {
 687           height -= (tmp_node->offset - tmp_node->right->offset);
 688           tmp_node = tmp_node->right;
 689         }
 690     }
 691   if (tmp_node == tree->nil)
 692     {
 693       *new_tree = NULL;
 694       *new_node = NULL;
 695       return 0;
 696     }
 697   if (tmp_node->children)
 698     {
 699       if ((tmp_node->offset -
 700            tmp_node->right->offset -
 701            tmp_node->children->root->offset) > height)
 702         {
 703           *new_tree = tree;
 704           *new_node = tmp_node;
 705           return (height - tmp_node->left->offset);
 706         }
 707       return _gtk_rbtree_find_offset (tmp_node->children,
 708                                       height - tmp_node->left->offset -
 709                                       (tmp_node->offset -
 710                                        tmp_node->left->offset -
 711                                        tmp_node->right->offset -
 712                                        tmp_node->children->root->offset),
 713                                       new_tree,
 714                                       new_node);
 715     }
 716   *new_tree = tree;
 717   *new_node = tmp_node;
 718   return (height - tmp_node->left->offset);
 719 }
 720
 721
 722 void
 723 _gtk_rbtree_remove_node (GtkRBTree *tree,
 724                          GtkRBNode *node)
 725 {
 726   GtkRBNode *x, *y;
 727
 728   g_return_if_fail (tree != NULL);
 729   g_return_if_fail (node != NULL);
 730   /* make sure we're deleting a node that's actually in the tree */
 731   for (x = node; x->parent != tree->nil; x = x->parent)
 732     ;
 733   g_return_if_fail (x == tree->root);
 734
 735   if (node->left == tree->nil || node->right == tree->nil)
 736     {
 737       y = node;
 738     }
 739   else
 740     {
 741       y = node->right;
 742
 743       while (y->left != tree->nil)
 744         y = y->left;
 745     }
 746   for (x = y; x != tree->nil; x = x->parent)
 747     x->count--;
 748   y->count = node->count;
 749   /* x is y's only child */
 750   if (y->left != tree->nil)
 751     x = y->left;
 752   else
 753     x = y->right;
 754
 755   /* remove y from the parent chain */
 756   x->parent = y->parent;
 757   if (y->parent != tree->nil)
 758     if (y == y->parent->left)
 759       y->parent->left = x;
 760     else
 761       y->parent->right = x;
 762   else
 763     tree->root = x;
 764
 765   if (y != node)
 766     node->children = y->children;
 767
 768   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
 769     _gtk_rbtree_remove_node_fixup (tree, x);
 770
 771   G_LOCK (current_allocator);
 772   y->left = current_allocator->free_nodes;
 773   current_allocator->free_nodes = y;
 774   G_UNLOCK (current_allocator);
 775
 776   if (gtk_debug_flags & GTK_DEBUG_TREE)
 777     _gtk_rbtree_test (tree);
 778 }
 779
 780 GtkRBNode *
 781 _gtk_rbtree_next (GtkRBTree *tree,
 782                   GtkRBNode *node)
 783 {
 784   g_return_val_if_fail (tree != NULL, NULL);
 785   g_return_val_if_fail (node != NULL, NULL);
 786
 787   /* Case 1: the node's below us. */
 788   if (node->right != tree->nil)
 789     {
 790       node = node->right;
 791       while (node->left != tree->nil)
 792         node = node->left;
 793       return node;
 794     }
 795
 796   /* Case 2: it's an ancestor */
 797   while (node->parent != tree->nil)
 798     {
 799       if (node->parent->right == node)
 800         node = node->parent;
 801       else
 802         return (node->parent);
 803     }
 804
 805   /* Case 3: There is no next node */
 806   return NULL;
 807 }
 808
 809 GtkRBNode *
 810 _gtk_rbtree_prev (GtkRBTree *tree,
 811                   GtkRBNode *node)
 812 {
 813   g_return_val_if_fail (tree != NULL, NULL);
 814   g_return_val_if_fail (node != NULL, NULL);
 815
 816   /* Case 1: the node's below us. */
 817   if (node->left != tree->nil)
 818     {
 819       node = node->left;
 820       while (node->right != tree->nil)
 821         node = node->right;
 822       return node;
 823     }
 824
 825   /* Case 2: it's an ancestor */
 826   while (node->parent != tree->nil)
 827     {
 828       if (node->parent->left == node)
 829         node = node->parent;
 830       else
 831         return (node->parent);
 832     }
 833
 834   /* Case 3: There is no next node */
 835   return NULL;
 836 }
 837
 838 void
 839 _gtk_rbtree_next_full (GtkRBTree  *tree,
 840                        GtkRBNode  *node,
 841                        GtkRBTree **new_tree,
 842                        GtkRBNode **new_node)
 843 {
 844   g_return_if_fail (tree != NULL);
 845   g_return_if_fail (node != NULL);
 846   g_return_if_fail (new_tree != NULL);
 847   g_return_if_fail (new_node != NULL);
 848
 849   if (node->children)
 850     {
 851       *new_tree = node->children;
 852       *new_node = (*new_tree)->root;
 853       while ((*new_node)->left != (*new_tree)->nil)
 854         *new_node = (*new_node)->left;
 855       return;
 856     }
 857
 858   *new_tree = tree;
 859   *new_node = _gtk_rbtree_next (tree, node);
 860
 861   while ((*new_node == NULL) &&
 862          (*new_tree != NULL))
 863     {
 864       *new_node = (*new_tree)->parent_node;
 865       *new_tree = (*new_tree)->parent_tree;
 866       if (*new_tree)
 867         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
 868     }
 869 }
 870
 871 void
 872 _gtk_rbtree_prev_full (GtkRBTree  *tree,
 873                        GtkRBNode  *node,
 874                        GtkRBTree **new_tree,
 875                        GtkRBNode **new_node)
 876 {
 877   g_return_if_fail (tree != NULL);
 878   g_return_if_fail (node != NULL);
 879   g_return_if_fail (new_tree != NULL);
 880   g_return_if_fail (new_node != NULL);
 881
 882   *new_tree = tree;
 883   *new_node = _gtk_rbtree_prev (tree, node);
 884
 885   if (*new_node == NULL)
 886     {
 887       *new_node = (*new_tree)->parent_node;
 888       *new_tree = (*new_tree)->parent_tree;
 889     }
 890   else
 891     {
 892       while ((*new_node)->children)
 893         {
 894           *new_tree = (*new_node)->children;
 895           *new_node = (*new_tree)->root;
 896           while ((*new_node)->right != (*new_tree)->nil)
 897             *new_node = (*new_node)->right;
 898         }
 899     }
 900 }
 901
 902 static void
 903 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
 904                                 GtkRBNode             *node,
 905                                 GtkRBTreeTraverseFunc  func,
 906                                 gpointer               data)
 907 {
 908   if (node == tree->nil)
 909     return;
 910
 911   (* func) (tree, node, data);
 912   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
 913   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
 914 }
 915
 916 static void
 917 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
 918                                  GtkRBNode             *node,
 919                                  GtkRBTreeTraverseFunc  func,
 920                                  gpointer               data)
 921 {
 922   if (node == tree->nil)
 923     return;
 924
 925   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
 926   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
 927   (* func) (tree, node, data);
 928 }
 929
 930 void
 931 _gtk_rbtree_traverse (GtkRBTree             *tree,
 932                       GtkRBNode             *node,
 933                       GTraverseType          order,
 934                       GtkRBTreeTraverseFunc  func,
 935                       gpointer               data)
 936 {
 937   g_return_if_fail (tree != NULL);
 938   g_return_if_fail (node != NULL);
 939   g_return_if_fail (func != NULL);
 940   g_return_if_fail (order <= G_LEVEL_ORDER);
 941
 942   switch (order)
 943     {
 944     case G_PRE_ORDER:
 945       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
 946       break;
 947     case G_POST_ORDER:
 948       _gtk_rbtree_traverse_post_order (tree, node, func, data);
 949       break;
 950     case G_IN_ORDER:
 951     case G_LEVEL_ORDER:
 952     default:
 953       g_warning ("unsupported traversal order.");
 954       break;
 955     }
 956 }
 957
 958 static gint
 959 _count_nodes (GtkRBTree *tree,
 960               GtkRBNode *node)
 961 {
 962   gint res;
 963   if (node == tree->nil)
 964     return 0;
 965
 966   res = (_count_nodes (tree, node->left) +
 967          _count_nodes (tree, node->right) + 1);
 968
 969   if (res != node->count)
 970     g_print ("Tree failed\n");
 971   return res;
 972 }
 973
 974 void
 975 _gtk_rbtree_test (GtkRBTree *tree)
 976 {
 977   if ((_count_nodes (tree, tree->root->left) +
 978        _count_nodes (tree, tree->root->right) + 1) == tree->root->count)
 979     g_print ("Tree passed\n");
 980   else
 981     g_print ("Tree failed\n");
 982
 983 }
 984
 985 static void
 986 _gtk_rbtree_test_height_helper (GtkRBTree *tree,
 987                                 GtkRBNode *node,
 988                                 gint       height)
 989 {
 990   if (node == tree->nil)
 991     return;
 992
 993   if (node->offset -
 994       (node->left?node->left->offset:0) -
 995       (node->right?node->right->offset:0) -
 996       (node->children?node->children->root->offset:0) != height)
 997     g_error ("tree failed\n");
 998
 999   _gtk_rbtree_test_height_helper (tree, node->left, height);
1000   _gtk_rbtree_test_height_helper (tree, node->right, height);
1001   if (node->children)
1002     _gtk_rbtree_test_height_helper (node->children, node->children->root, height);
1003
1004 }
1005
1006 void
1007 _gtk_rbtree_test_height (GtkRBTree *tree,
1008                          gint       height)
1009 {
1010   _gtk_rbtree_test_height_helper (tree, tree->root, height);
1011 }