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->parity = 1;
 114   node->count = 1;
 115   node->children = NULL;
 116   node->offset = height;
 117   return node;
 118 }
 119
 120 static void
 121 _gtk_rbnode_free (GtkRBNode *node)
 122 {
 123   G_LOCK (current_allocator);
 124   node->left = current_allocator->free_nodes;
 125   current_allocator->free_nodes = node;
 126   if (gtk_debug_flags & GTK_DEBUG_TREE)
 127     {
 128       /* unfortunately node->left has to continue to point to
 129        * a node...
 130        */
 131       node->right = (gpointer) 0xdeadbeef;
 132       node->parent = (gpointer) 0xdeadbeef;
 133       node->offset = 56789;
 134       node->count = 56789;
 135       node->flags = 0;
 136     }
 137   G_UNLOCK (current_allocator);
 138 }
 139
 140 static void
 141 _gtk_rbnode_rotate_left (GtkRBTree *tree,
 142                          GtkRBNode *node)
 143 {
 144   gint node_height, right_height;
 145   guint node_parity, right_parity;
 146   GtkRBNode *right = node->right;
 147
 148   g_return_if_fail (node != tree->nil);
 149
 150   node_height = node->offset -
 151     (node->left?node->left->offset:0) -
 152     (node->right?node->right->offset:0) -
 153     (node->children?node->children->root->offset:0);
 154   right_height = right->offset -
 155     (right->left?right->left->offset:0) -
 156     (right->right?right->right->offset:0) -
 157     (right->children?right->children->root->offset:0);
 158
 159   node_parity = node->parity -
 160     (node->left?node->left->parity:0) -
 161     (node->right?node->right->parity:0) -
 162     (node->children?node->children->root->parity:0);
 163   right_parity = right->parity -
 164     (right->left?right->left->parity:0) -
 165     (right->right?right->right->parity:0) -
 166     (right->children?right->children->root->parity:0);
 167
 168   node->right = right->left;
 169   if (right->left != tree->nil)
 170     right->left->parent = node;
 171
 172   if (right != tree->nil)
 173     right->parent = node->parent;
 174   if (node->parent != tree->nil)
 175     {
 176       if (node == node->parent->left)
 177         node->parent->left = right;
 178       else
 179         node->parent->right = right;
 180     } else {
 181       tree->root = right;
 182     }
 183
 184   right->left = node;
 185   if (node != tree->nil)
 186     node->parent = right;
 187
 188   node->count = 1 + (node->left?node->left->count:0) +
 189     (node->right?node->right->count:0);
 190   right->count = 1 + (right->left?right->left->count:0) +
 191     (right->right?right->right->count:0);
 192
 193   node->offset = node_height +
 194     (node->left?node->left->offset:0) +
 195     (node->right?node->right->offset:0) +
 196     (node->children?node->children->root->offset:0);
 197   right->offset = right_height +
 198     (right->left?right->left->offset:0) +
 199     (right->right?right->right->offset:0) +
 200     (right->children?right->children->root->offset:0);
 201
 202   node->parity = node_parity +
 203     (node->left?node->left->parity:0) +
 204     (node->right?node->right->parity:0) +
 205     (node->children?node->children->root->parity:0);
 206   right->parity = right_parity +
 207     (right->left?right->left->parity:0) +
 208     (right->right?right->right->parity:0) +
 209     (right->children?right->children->root->parity:0);
 210 }
 211
 212 static void
 213 _gtk_rbnode_rotate_right (GtkRBTree *tree,
 214                           GtkRBNode *node)
 215 {
 216   gint node_height, left_height;
 217   guint node_parity, left_parity;
 218   GtkRBNode *left = node->left;
 219
 220   g_return_if_fail (node != tree->nil);
 221
 222   node_height = node->offset -
 223     (node->left?node->left->offset:0) -
 224     (node->right?node->right->offset:0) -
 225     (node->children?node->children->root->offset:0);
 226   left_height = left->offset -
 227     (left->left?left->left->offset:0) -
 228     (left->right?left->right->offset:0) -
 229     (left->children?left->children->root->offset:0);
 230
 231   node_parity = node->parity -
 232     (node->left?node->left->parity:0) -
 233     (node->right?node->right->parity:0) -
 234     (node->children?node->children->root->parity:0);
 235   left_parity = left->parity -
 236     (left->left?left->left->parity:0) -
 237     (left->right?left->right->parity:0) -
 238     (left->children?left->children->root->parity:0);
 239
 240   node->left = left->right;
 241   if (left->right != tree->nil)
 242     left->right->parent = node;
 243
 244   if (left != tree->nil)
 245     left->parent = node->parent;
 246   if (node->parent != tree->nil)
 247     {
 248       if (node == node->parent->right)
 249         node->parent->right = left;
 250       else
 251         node->parent->left = left;
 252     }
 253   else
 254     {
 255       tree->root = left;
 256     }
 257
 258   /* link node and left */
 259   left->right = node;
 260   if (node != tree->nil)
 261     node->parent = left;
 262
 263   node->count = 1 + (node->left?node->left->count:0) +
 264     (node->right?node->right->count:0);
 265   left->count = 1 + (left->left?left->left->count:0) +
 266     (left->right?left->right->count:0);
 267
 268   node->offset = node_height +
 269     (node->left?node->left->offset:0) +
 270     (node->right?node->right->offset:0) +
 271     (node->children?node->children->root->offset:0);
 272   left->offset = left_height +
 273     (left->left?left->left->offset:0) +
 274     (left->right?left->right->offset:0) +
 275     (left->children?left->children->root->offset:0);
 276
 277   node->parity = node_parity +
 278     (node->left?node->left->parity:0) +
 279     (node->right?node->right->parity:0) +
 280     (node->children?node->children->root->parity:0);
 281   left->parity = left_parity +
 282     (left->left?left->left->parity:0) +
 283     (left->right?left->right->parity:0) +
 284     (left->children?left->children->root->parity:0);
 285 }
 286
 287 static void
 288 _gtk_rbtree_insert_fixup (GtkRBTree *tree,
 289                           GtkRBNode *node)
 290 {
 291
 292   /* check Red-Black properties */
 293   while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)
 294     {
 295       /* we have a violation */
 296       if (node->parent == node->parent->parent->left)
 297         {
 298           GtkRBNode *y = node->parent->parent->right;
 299           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 300             {
 301                                 /* uncle is GTK_RBNODE_RED */
 302               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 303               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 304               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 305               node = node->parent->parent;
 306             }
 307           else
 308             {
 309                                 /* uncle is GTK_RBNODE_BLACK */
 310               if (node == node->parent->right)
 311                 {
 312                   /* make node a left child */
 313                   node = node->parent;
 314                   _gtk_rbnode_rotate_left (tree, node);
 315                 }
 316
 317                                 /* recolor and rotate */
 318               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 319               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 320               _gtk_rbnode_rotate_right(tree, node->parent->parent);
 321             }
 322         }
 323       else
 324         {
 325           /* mirror image of above code */
 326           GtkRBNode *y = node->parent->parent->left;
 327           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 328             {
 329                                 /* uncle is GTK_RBNODE_RED */
 330               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 331               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 332               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 333               node = node->parent->parent;
 334             }
 335           else
 336             {
 337                                 /* uncle is GTK_RBNODE_BLACK */
 338               if (node == node->parent->left)
 339                 {
 340                   node = node->parent;
 341                   _gtk_rbnode_rotate_right (tree, node);
 342                 }
 343               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 344               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 345               _gtk_rbnode_rotate_left (tree, node->parent->parent);
 346             }
 347         }
 348     }
 349   GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);
 350 }
 351
 352 static void
 353 _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
 354                                GtkRBNode *node)
 355 {
 356   while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
 357     {
 358       if (node == node->parent->left)
 359         {
 360           GtkRBNode *w = node->parent->right;
 361           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 362             {
 363               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 364               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
 365               _gtk_rbnode_rotate_left (tree, node->parent);
 366               w = node->parent->right;
 367             }
 368           if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 369             {
 370               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 371               node = node->parent;
 372             }
 373           else
 374             {
 375               if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 376                 {
 377                   GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 378                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 379                   _gtk_rbnode_rotate_right (tree, w);
 380                   w = node->parent->right;
 381                 }
 382               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
 383               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 384               GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 385               _gtk_rbnode_rotate_left (tree, node->parent);
 386               node = tree->root;
 387             }
 388         }
 389       else
 390         {
 391           GtkRBNode *w = node->parent->left;
 392           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 393             {
 394               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 395               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
 396               _gtk_rbnode_rotate_right (tree, node->parent);
 397               w = node->parent->left;
 398             }
 399           if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 400             {
 401               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 402               node = node->parent;
 403             }
 404           else
 405             {
 406               if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 407                 {
 408                   GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 409                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 410                   _gtk_rbnode_rotate_left (tree, w);
 411                   w = node->parent->left;
 412                 }
 413               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
 414               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 415               GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 416               _gtk_rbnode_rotate_right (tree, node->parent);
 417               node = tree->root;
 418             }
 419         }
 420     }
 421   GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
 422 }
 423
 424 /* Public functions */
 425 void
 426 _gtk_rbnode_push_allocator (GAllocator *allocator)
 427 {
 428   G_LOCK (current_allocator);
 429   _gtk_rbnode_validate_allocator ( allocator );
 430   allocator->last = current_allocator;
 431   current_allocator = allocator;
 432   G_UNLOCK (current_allocator);
 433 }
 434
 435 void
 436 _gtk_rbnode_pop_allocator (void)
 437 {
 438   G_LOCK (current_allocator);
 439   if (current_allocator)
 440     {
 441       GAllocator *allocator;
 442
 443       allocator = current_allocator;
 444       current_allocator = allocator->last;
 445       allocator->last = NULL;
 446       allocator->is_unused = TRUE;
 447     }
 448   G_UNLOCK (current_allocator);
 449 }
 450
 451 GtkRBTree *
 452 _gtk_rbtree_new (void)
 453 {
 454   GtkRBTree *retval;
 455
 456   retval = (GtkRBTree *) g_new (GtkRBTree, 1);
 457   retval->parent_tree = NULL;
 458   retval->parent_node = NULL;
 459
 460   retval->nil = g_new0 (GtkRBNode, 1);
 461   retval->nil->left = NULL;
 462   retval->nil->right = NULL;
 463   retval->nil->parent = NULL;
 464   retval->nil->flags = GTK_RBNODE_BLACK;
 465   retval->nil->count = 0;
 466   retval->nil->offset = 0;
 467   retval->nil->parity = 0;
 468
 469   retval->root = retval->nil;
 470   return retval;
 471 }
 472
 473 static void
 474 _gtk_rbtree_free_helper (GtkRBTree  *tree,
 475                          GtkRBNode  *node,
 476                          gpointer    data)
 477 {
 478   if (node->children)
 479     _gtk_rbtree_free (node->children);
 480
 481   _gtk_rbnode_free (node);
 482 }
 483
 484 void
 485 _gtk_rbtree_free (GtkRBTree *tree)
 486 {
 487   _gtk_rbtree_traverse (tree,
 488                         tree->root,
 489                         G_POST_ORDER,
 490                         _gtk_rbtree_free_helper,
 491                         NULL);
 492
 493   if (tree->parent_node &&
 494       tree->parent_node->children == tree)
 495     tree->parent_node->children = NULL;
 496   _gtk_rbnode_free (tree->nil);
 497   g_free (tree);
 498 }
 499
 500 void
 501 _gtk_rbtree_remove (GtkRBTree *tree)
 502 {
 503   GtkRBTree *tmp_tree;
 504   GtkRBNode *tmp_node;
 505
 506   gint height = tree->root->offset;
 507
 508   if (gtk_debug_flags & GTK_DEBUG_TREE)
 509     _gtk_rbtree_test (G_STRLOC, tree);
 510
 511   tmp_tree = tree->parent_tree;
 512   tmp_node = tree->parent_node;
 513
 514   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 515     {
 516       tmp_node->offset -= height;
 517
 518       /* If the removed tree was odd, flip all parents */
 519       if (tree->root->parity)
 520         tmp_node->parity = !tmp_node->parity;
 521
 522       tmp_node = tmp_node->parent;
 523       if (tmp_node == tmp_tree->nil)
 524         {
 525           tmp_node = tmp_tree->parent_node;
 526           tmp_tree = tmp_tree->parent_tree;
 527         }
 528     }
 529
 530   tmp_tree = tree->parent_tree;
 531
 532   _gtk_rbtree_free (tree);
 533
 534   if (gtk_debug_flags & GTK_DEBUG_TREE)
 535     _gtk_rbtree_test (G_STRLOC, tmp_tree);
 536 }
 537
 538
 539 GtkRBNode *
 540 _gtk_rbtree_insert_after (GtkRBTree  *tree,
 541                           GtkRBNode  *current,
 542                           gint        height)
 543 {
 544   GtkRBNode *node;
 545   gboolean right = TRUE;
 546   GtkRBNode *tmp_node;
 547   GtkRBTree *tmp_tree;
 548
 549   if (gtk_debug_flags & GTK_DEBUG_TREE)
 550     _gtk_rbtree_test (G_STRLOC, tree);
 551
 552   if (current != NULL && current->right != tree->nil)
 553     {
 554       current = current->right;
 555       while (current->left != tree->nil)
 556         current = current->left;
 557       right = FALSE;
 558     }
 559
 560   /* setup new node */
 561   node = _gtk_rbnode_new (tree, height);
 562   node->parent = (current?current:tree->nil);
 563
 564   /* insert node in tree */
 565   if (current)
 566     {
 567       if (right)
 568         current->right = node;
 569       else
 570         current->left = node;
 571       tmp_node = node->parent;
 572       tmp_tree = tree;
 573     }
 574   else
 575     {
 576       tree->root = node;
 577       tmp_node = tree->parent_node;
 578       tmp_tree = tree->parent_tree;
 579     }
 580
 581   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 582     {
 583       /* We only want to propagate the count if we are in the tree we
 584        * started in. */
 585       if (tmp_tree == tree)
 586         tmp_node->count++;
 587
 588       tmp_node->parity += 1;
 589       tmp_node->offset += height;
 590       tmp_node = tmp_node->parent;
 591       if (tmp_node == tmp_tree->nil)
 592         {
 593           tmp_node = tmp_tree->parent_node;
 594           tmp_tree = tmp_tree->parent_tree;
 595         }
 596     }
 597   _gtk_rbtree_insert_fixup (tree, node);
 598
 599   if (gtk_debug_flags & GTK_DEBUG_TREE)
 600     _gtk_rbtree_test (G_STRLOC, tree);
 601
 602   return node;
 603 }
 604
 605 GtkRBNode *
 606 _gtk_rbtree_insert_before (GtkRBTree  *tree,
 607                            GtkRBNode  *current,
 608                            gint        height)
 609 {
 610   GtkRBNode *node;
 611   gboolean left = TRUE;
 612   GtkRBNode *tmp_node;
 613   GtkRBTree *tmp_tree;
 614
 615   if (gtk_debug_flags & GTK_DEBUG_TREE)
 616     _gtk_rbtree_test (G_STRLOC, tree);
 617
 618   if (current != NULL && current->left != tree->nil)
 619     {
 620       current = current->left;
 621       while (current->right != tree->nil)
 622         current = current->right;
 623       left = FALSE;
 624     }
 625
 626   /* setup new node */
 627   node = _gtk_rbnode_new (tree, height);
 628   node->parent = (current?current:tree->nil);
 629
 630   /* insert node in tree */
 631   if (current)
 632     {
 633       if (left)
 634         current->left = node;
 635       else
 636         current->right = node;
 637       tmp_node = node->parent;
 638       tmp_tree = tree;
 639     }
 640   else
 641     {
 642       tree->root = node;
 643       tmp_node = tree->parent_node;
 644       tmp_tree = tree->parent_tree;
 645     }
 646
 647   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 648     {
 649       /* We only want to propagate the count if we are in the tree we
 650        * started in. */
 651       if (tmp_tree == tree)
 652         tmp_node->count++;
 653
 654       tmp_node->parity += 1;
 655       tmp_node->offset += height;
 656       tmp_node = tmp_node->parent;
 657       if (tmp_node == tmp_tree->nil)
 658         {
 659           tmp_node = tmp_tree->parent_node;
 660           tmp_tree = tmp_tree->parent_tree;
 661         }
 662     }
 663   _gtk_rbtree_insert_fixup (tree, node);
 664
 665   if (gtk_debug_flags & GTK_DEBUG_TREE)
 666     _gtk_rbtree_test (G_STRLOC, tree);
 667
 668   return node;
 669 }
 670
 671 GtkRBNode *
 672 _gtk_rbtree_find_count (GtkRBTree *tree,
 673                         gint       count)
 674 {
 675   GtkRBNode *node;
 676
 677   node = tree->root;
 678   while (node != tree->nil && (node->left->count + 1 != count))
 679     {
 680       if (node->left->count >= count)
 681         node = node->left;
 682       else
 683         {
 684           count -= (node->left->count + 1);
 685           node = node->right;
 686         }
 687     }
 688   if (node == tree->nil)
 689     return NULL;
 690   return node;
 691 }
 692
 693 void
 694 _gtk_rbtree_node_set_height (GtkRBTree *tree,
 695                              GtkRBNode *node,
 696                              gint       height)
 697 {
 698   gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
 699   GtkRBNode *tmp_node = node;
 700   GtkRBTree *tmp_tree = tree;
 701
 702   if (diff == 0)
 703     return;
 704
 705   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 706     {
 707       tmp_node->offset += diff;
 708       tmp_node = tmp_node->parent;
 709       if (tmp_node == tmp_tree->nil)
 710         {
 711           tmp_node = tmp_tree->parent_node;
 712           tmp_tree = tmp_tree->parent_tree;
 713         }
 714     }
 715 }
 716
 717 gint
 718 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 719                               GtkRBNode *node)
 720 {
 721   GtkRBNode *last;
 722   gint retval;
 723
 724   g_assert (node);
 725   g_assert (node->left);
 726
 727   retval = node->left->offset;
 728
 729   while (tree && node && node != tree->nil)
 730     {
 731       last = node;
 732       node = node->parent;
 733
 734       /* Add left branch, plus children, iff we came from the right */
 735       if (node->right == last)
 736         retval += node->offset - node->right->offset;
 737
 738       if (node == tree->nil)
 739         {
 740           node = tree->parent_node;
 741           tree = tree->parent_tree;
 742
 743           /* Add the parent node, plus the left branch. */
 744           if (node)
 745             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 746         }
 747     }
 748   return retval;
 749 }
 750
 751 gint
 752 _gtk_rbtree_node_find_parity (GtkRBTree *tree,
 753                               GtkRBNode *node)
 754 {
 755   GtkRBNode *last;
 756   gint retval;
 757
 758   g_assert (node);
 759   g_assert (node->left);
 760
 761   retval = node->left->parity;
 762
 763   while (tree && node && node != tree->nil)
 764     {
 765       last = node;
 766       node = node->parent;
 767
 768       /* Add left branch, plus children, iff we came from the right */
 769       if (node->right == last)
 770         retval += node->parity - node->right->parity;
 771
 772       if (node == tree->nil)
 773         {
 774           node = tree->parent_node;
 775           tree = tree->parent_tree;
 776
 777           /* Add the parent node, plus the left branch. */
 778           if (node)
 779             retval += node->left->parity + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
 780         }
 781     }
 782
 783   return retval % 2;
 784 }
 785
 786 gint
 787 _gtk_rbtree_find_offset (GtkRBTree  *tree,
 788                          gint        height,
 789                          GtkRBTree **new_tree,
 790                          GtkRBNode **new_node)
 791 {
 792   GtkRBNode *tmp_node;
 793
 794   if (height < 0)
 795     {
 796       *new_tree = NULL;
 797       *new_node = NULL;
 798       return 0;
 799     }
 800
 801   tmp_node = tree->root;
 802   while (tmp_node != tree->nil &&
 803          (tmp_node->left->offset > height ||
 804           (tmp_node->offset - tmp_node->right->offset) < height))
 805     {
 806       if (tmp_node->left->offset > height)
 807         tmp_node = tmp_node->left;
 808       else
 809         {
 810           height -= (tmp_node->offset - tmp_node->right->offset);
 811           tmp_node = tmp_node->right;
 812         }
 813     }
 814   if (tmp_node == tree->nil)
 815     {
 816       *new_tree = NULL;
 817       *new_node = NULL;
 818       return 0;
 819     }
 820   if (tmp_node->children)
 821     {
 822       if ((tmp_node->offset -
 823            tmp_node->right->offset -
 824            tmp_node->children->root->offset) > height)
 825         {
 826           *new_tree = tree;
 827           *new_node = tmp_node;
 828           return (height - tmp_node->left->offset);
 829         }
 830       return _gtk_rbtree_find_offset (tmp_node->children,
 831                                       height - tmp_node->left->offset -
 832                                       (tmp_node->offset -
 833                                        tmp_node->left->offset -
 834                                        tmp_node->right->offset -
 835                                        tmp_node->children->root->offset),
 836                                       new_tree,
 837                                       new_node);
 838     }
 839   *new_tree = tree;
 840   *new_node = tmp_node;
 841   return (height - tmp_node->left->offset);
 842 }
 843
 844
 845 void
 846 _gtk_rbtree_remove_node (GtkRBTree *tree,
 847                          GtkRBNode *node)
 848 {
 849   GtkRBNode *x, *y;
 850   GtkRBTree *tmp_tree;
 851   GtkRBNode *tmp_node;
 852
 853   g_return_if_fail (tree != NULL);
 854   g_return_if_fail (node != NULL);
 855
 856   /* make sure we're deleting a node that's actually in the tree */
 857   for (x = node; x->parent != tree->nil; x = x->parent)
 858     ;
 859   g_return_if_fail (x == tree->root);
 860
 861   if (gtk_debug_flags & GTK_DEBUG_TREE)
 862     _gtk_rbtree_test (G_STRLOC, tree);
 863
 864   if (node->left == tree->nil || node->right == tree->nil)
 865     {
 866       y = node;
 867     }
 868   else
 869     {
 870       y = node->right;
 871
 872       while (y->left != tree->nil)
 873         y = y->left;
 874     }
 875
 876   /* adjust count only beneath tree */
 877   for (x = y; x != tree->nil; x = x->parent)
 878     x->count--;
 879
 880   /*   y->count = node->count; */
 881
 882   /* offsets and parity adjust all the way up through parent trees */
 883
 884   tmp_tree = tree;
 885   tmp_node = y;
 886
 887   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 888     {
 889       /*       tmp_node->offset -= y->offset; */
 890       tmp_node->parity -= (guint) 1; /* parity of y is always 1 */
 891
 892       tmp_node = tmp_node->parent;
 893       if (tmp_node == tmp_tree->nil)
 894         {
 895           tmp_node = tmp_tree->parent_node;
 896           tmp_tree = tmp_tree->parent_tree;
 897         }
 898     }
 899
 900   /* x is y's only child */
 901   if (y->left != tree->nil)
 902     x = y->left;
 903   else
 904     x = y->right;
 905
 906   /* remove y from the parent chain */
 907   x->parent = y->parent;
 908   if (y->parent != tree->nil)
 909     if (y == y->parent->left)
 910       y->parent->left = x;
 911     else
 912       y->parent->right = x;
 913   else
 914     tree->root = x;
 915
 916   if (y != node)
 917     {
 918       /* Copy the node over */
 919       if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
 920         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
 921       else
 922         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
 923       node->children = y->children;
 924     }
 925
 926   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
 927     _gtk_rbtree_remove_node_fixup (tree, x);
 928
 929   _gtk_rbnode_free (y);
 930
 931   if (gtk_debug_flags & GTK_DEBUG_TREE)
 932     _gtk_rbtree_test (G_STRLOC, tree);
 933 }
 934
 935 GtkRBNode *
 936 _gtk_rbtree_next (GtkRBTree *tree,
 937                   GtkRBNode *node)
 938 {
 939   g_return_val_if_fail (tree != NULL, NULL);
 940   g_return_val_if_fail (node != NULL, NULL);
 941
 942   /* Case 1: the node's below us. */
 943   if (node->right != tree->nil)
 944     {
 945       node = node->right;
 946       while (node->left != tree->nil)
 947         node = node->left;
 948       return node;
 949     }
 950
 951   /* Case 2: it's an ancestor */
 952   while (node->parent != tree->nil)
 953     {
 954       if (node->parent->right == node)
 955         node = node->parent;
 956       else
 957         return (node->parent);
 958     }
 959
 960   /* Case 3: There is no next node */
 961   return NULL;
 962 }
 963
 964 GtkRBNode *
 965 _gtk_rbtree_prev (GtkRBTree *tree,
 966                   GtkRBNode *node)
 967 {
 968   g_return_val_if_fail (tree != NULL, NULL);
 969   g_return_val_if_fail (node != NULL, NULL);
 970
 971   /* Case 1: the node's below us. */
 972   if (node->left != tree->nil)
 973     {
 974       node = node->left;
 975       while (node->right != tree->nil)
 976         node = node->right;
 977       return node;
 978     }
 979
 980   /* Case 2: it's an ancestor */
 981   while (node->parent != tree->nil)
 982     {
 983       if (node->parent->left == node)
 984         node = node->parent;
 985       else
 986         return (node->parent);
 987     }
 988
 989   /* Case 3: There is no next node */
 990   return NULL;
 991 }
 992
 993 void
 994 _gtk_rbtree_next_full (GtkRBTree  *tree,
 995                        GtkRBNode  *node,
 996                        GtkRBTree **new_tree,
 997                        GtkRBNode **new_node)
 998 {
 999   g_return_if_fail (tree != NULL);
1000   g_return_if_fail (node != NULL);
1001   g_return_if_fail (new_tree != NULL);
1002   g_return_if_fail (new_node != NULL);
1003
1004   if (node->children)
1005     {
1006       *new_tree = node->children;
1007       *new_node = (*new_tree)->root;
1008       while ((*new_node)->left != (*new_tree)->nil)
1009         *new_node = (*new_node)->left;
1010       return;
1011     }
1012
1013   *new_tree = tree;
1014   *new_node = _gtk_rbtree_next (tree, node);
1015
1016   while ((*new_node == NULL) &&
1017          (*new_tree != NULL))
1018     {
1019       *new_node = (*new_tree)->parent_node;
1020       *new_tree = (*new_tree)->parent_tree;
1021       if (*new_tree)
1022         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1023     }
1024 }
1025
1026 void
1027 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1028                        GtkRBNode  *node,
1029                        GtkRBTree **new_tree,
1030                        GtkRBNode **new_node)
1031 {
1032   g_return_if_fail (tree != NULL);
1033   g_return_if_fail (node != NULL);
1034   g_return_if_fail (new_tree != NULL);
1035   g_return_if_fail (new_node != NULL);
1036
1037   *new_tree = tree;
1038   *new_node = _gtk_rbtree_prev (tree, node);
1039
1040   if (*new_node == NULL)
1041     {
1042       *new_node = (*new_tree)->parent_node;
1043       *new_tree = (*new_tree)->parent_tree;
1044     }
1045   else
1046     {
1047       while ((*new_node)->children)
1048         {
1049           *new_tree = (*new_node)->children;
1050           *new_node = (*new_tree)->root;
1051           while ((*new_node)->right != (*new_tree)->nil)
1052             *new_node = (*new_node)->right;
1053         }
1054     }
1055 }
1056
1057 gint
1058 _gtk_rbtree_get_depth (GtkRBTree *tree)
1059 {
1060   GtkRBTree *tmp_tree;
1061   gint depth = 0;
1062
1063   tmp_tree = tree->parent_tree;
1064   while (tmp_tree)
1065     {
1066       ++depth;
1067       tmp_tree = tmp_tree->parent_tree;
1068     }
1069
1070   return depth;
1071 }
1072
1073 static void
1074 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1075                                 GtkRBNode             *node,
1076                                 GtkRBTreeTraverseFunc  func,
1077                                 gpointer               data)
1078 {
1079   if (node == tree->nil)
1080     return;
1081
1082   (* func) (tree, node, data);
1083   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1084   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1085 }
1086
1087 static void
1088 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1089                                  GtkRBNode             *node,
1090                                  GtkRBTreeTraverseFunc  func,
1091                                  gpointer               data)
1092 {
1093   if (node == tree->nil)
1094     return;
1095
1096   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1097   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1098   (* func) (tree, node, data);
1099 }
1100
1101 void
1102 _gtk_rbtree_traverse (GtkRBTree             *tree,
1103                       GtkRBNode             *node,
1104                       GTraverseType          order,
1105                       GtkRBTreeTraverseFunc  func,
1106                       gpointer               data)
1107 {
1108   g_return_if_fail (tree != NULL);
1109   g_return_if_fail (node != NULL);
1110   g_return_if_fail (func != NULL);
1111   g_return_if_fail (order <= G_LEVEL_ORDER);
1112
1113   switch (order)
1114     {
1115     case G_PRE_ORDER:
1116       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1117       break;
1118     case G_POST_ORDER:
1119       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1120       break;
1121     case G_IN_ORDER:
1122     case G_LEVEL_ORDER:
1123     default:
1124       g_warning ("unsupported traversal order.");
1125       break;
1126     }
1127 }
1128
1129 static gint
1130 _count_nodes (GtkRBTree *tree,
1131               GtkRBNode *node)
1132 {
1133   gint res;
1134   if (node == tree->nil)
1135     return 0;
1136
1137   g_assert (node->left);
1138   g_assert (node->right);
1139
1140   res = (_count_nodes (tree, node->left) +
1141          _count_nodes (tree, node->right) + 1);
1142
1143   if (res != node->count)
1144     g_print ("Tree failed\n");
1145   return res;
1146 }
1147
1148 static guint
1149 get_parity (GtkRBNode *node)
1150 {
1151   guint child_total = 0;
1152   guint rem;
1153
1154   /* The parity of a node is node->parity minus
1155    * the parity of left, right, and children.
1156    *
1157    * This is equivalent to saying that if left, right, children
1158    * sum to 0 parity, then node->parity is the parity of node,
1159    * and if left, right, children are odd parity, then
1160    * node->parity is the reverse of the node's parity.
1161    */
1162
1163   child_total += (guint) node->left->parity;
1164   child_total += (guint) node->right->parity;
1165
1166   if (node->children)
1167     child_total += (guint) node->children->root->parity;
1168
1169   rem = child_total % 2;
1170
1171   if (rem == 0)
1172     return node->parity;
1173   else
1174     return !node->parity;
1175 }
1176
1177 static guint
1178 count_parity (GtkRBTree *tree,
1179               GtkRBNode *node)
1180 {
1181   guint res;
1182
1183   if (node == tree->nil)
1184     return 0;
1185
1186   res =
1187     count_parity (tree, node->left) +
1188     count_parity (tree, node->right) +
1189     (guint)1 +
1190     (node->children ? count_parity (node->children, node->children->root) : 0);
1191
1192   res = res % (guint)2;
1193
1194   if (res != node->parity)
1195     g_print ("parity incorrect for node\n");
1196
1197   if (get_parity (node) != 1)
1198     g_error ("Node has incorrect parity %d", get_parity (node));
1199
1200   return res;
1201 }
1202
1203 static void
1204 _gtk_rbtree_test_height (GtkRBTree *tree,
1205                          GtkRBNode *node)
1206 {
1207   gint computed_offset = 0;
1208
1209   /* This whole test is sort of a useless truism. */
1210
1211   if (node->left != tree->nil)
1212     computed_offset += node->left->offset;
1213
1214   if (node->right != tree->nil)
1215     computed_offset += node->right->offset;
1216
1217   if (node->children && node->children->root != node->children->nil)
1218     computed_offset += node->children->root->offset;
1219
1220   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1221     g_error ("node has broken offset\n");
1222
1223   if (node->left != tree->nil)
1224     _gtk_rbtree_test_height (tree, node->left);
1225
1226   if (node->right != tree->nil)
1227     _gtk_rbtree_test_height (tree, node->right);
1228
1229   if (node->children && node->children->root != node->children->nil)
1230     _gtk_rbtree_test_height (node->children, node->children->root);
1231 }
1232
1233 void
1234 _gtk_rbtree_test (const gchar *where,
1235                   GtkRBTree   *tree)
1236 {
1237   GtkRBTree *tmp_tree;
1238
1239   /* Test the entire tree */
1240   tmp_tree = tree;
1241   while (tmp_tree->parent_tree)
1242     tmp_tree = tmp_tree->parent_tree;
1243
1244   g_print ("%s: whole tree offset is %d\n", where, tmp_tree->root->offset);
1245
1246   if (tmp_tree->root != tmp_tree->nil)
1247     {
1248       g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1249                  _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1250
1251
1252       _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1253
1254       g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
1255     }
1256 }
1257