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