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