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
  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   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
 212     {
 213       if ((! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
 214           (node->right != tree->nil && ! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 215           (node->left != tree->nil && ! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 216           (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 217         GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 218     }
 219   if (GTK_RBNODE_FLAG_SET (right, GTK_RBNODE_DESCENDANTS_INVALID))
 220     {
 221       if ((! GTK_RBNODE_FLAG_SET (right, GTK_RBNODE_INVALID)) &&
 222           (right->right != tree->nil && ! GTK_RBNODE_FLAG_SET (right->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 223           (right->left != tree->nil && ! GTK_RBNODE_FLAG_SET (right->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 224           (right->children && GTK_RBNODE_FLAG_SET (right->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 225         GTK_RBNODE_UNSET_FLAG (right, GTK_RBNODE_DESCENDANTS_INVALID);
 226     }
 227 }
 228
 229 static void
 230 _gtk_rbnode_rotate_right (GtkRBTree *tree,
 231                           GtkRBNode *node)
 232 {
 233   gint node_height, left_height;
 234   guint node_parity, left_parity;
 235   GtkRBNode *left = node->left;
 236
 237   g_return_if_fail (node != tree->nil);
 238
 239   node_height = node->offset -
 240     (node->left?node->left->offset:0) -
 241     (node->right?node->right->offset:0) -
 242     (node->children?node->children->root->offset:0);
 243   left_height = left->offset -
 244     (left->left?left->left->offset:0) -
 245     (left->right?left->right->offset:0) -
 246     (left->children?left->children->root->offset:0);
 247
 248   node_parity = node->parity -
 249     (node->left?node->left->parity:0) -
 250     (node->right?node->right->parity:0) -
 251     (node->children?node->children->root->parity:0);
 252   left_parity = left->parity -
 253     (left->left?left->left->parity:0) -
 254     (left->right?left->right->parity:0) -
 255     (left->children?left->children->root->parity:0);
 256
 257   node->left = left->right;
 258   if (left->right != tree->nil)
 259     left->right->parent = node;
 260
 261   if (left != tree->nil)
 262     left->parent = node->parent;
 263   if (node->parent != tree->nil)
 264     {
 265       if (node == node->parent->right)
 266         node->parent->right = left;
 267       else
 268         node->parent->left = left;
 269     }
 270   else
 271     {
 272       tree->root = left;
 273     }
 274
 275   /* link node and left */
 276   left->right = node;
 277   if (node != tree->nil)
 278     node->parent = left;
 279
 280   node->count = 1 + (node->left?node->left->count:0) +
 281     (node->right?node->right->count:0);
 282   left->count = 1 + (left->left?left->left->count:0) +
 283     (left->right?left->right->count:0);
 284
 285   node->offset = node_height +
 286     (node->left?node->left->offset:0) +
 287     (node->right?node->right->offset:0) +
 288     (node->children?node->children->root->offset:0);
 289   left->offset = left_height +
 290     (left->left?left->left->offset:0) +
 291     (left->right?left->right->offset:0) +
 292     (left->children?left->children->root->offset:0);
 293
 294   node->parity = node_parity +
 295     (node->left?node->left->parity:0) +
 296     (node->right?node->right->parity:0) +
 297     (node->children?node->children->root->parity:0);
 298   left->parity = left_parity +
 299     (left->left?left->left->parity:0) +
 300     (left->right?left->right->parity:0) +
 301     (left->children?left->children->root->parity:0);
 302
 303   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
 304     {
 305       if ((! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
 306           (node->right != tree->nil && ! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 307           (node->left != tree->nil && ! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 308           (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 309         GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 310     }
 311   if (GTK_RBNODE_FLAG_SET (left, GTK_RBNODE_DESCENDANTS_INVALID))
 312     {
 313       if ((! GTK_RBNODE_FLAG_SET (left, GTK_RBNODE_INVALID)) &&
 314           (left->right != tree->nil && ! GTK_RBNODE_FLAG_SET (left->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 315           (left->left != tree->nil && ! GTK_RBNODE_FLAG_SET (left->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
 316           (left->children && GTK_RBNODE_FLAG_SET (left->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 317         GTK_RBNODE_UNSET_FLAG (left, GTK_RBNODE_DESCENDANTS_INVALID);
 318     }
 319 }
 320
 321 static void
 322 _gtk_rbtree_insert_fixup (GtkRBTree *tree,
 323                           GtkRBNode *node)
 324 {
 325
 326   /* check Red-Black properties */
 327   while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)
 328     {
 329       /* we have a violation */
 330       if (node->parent == node->parent->parent->left)
 331         {
 332           GtkRBNode *y = node->parent->parent->right;
 333           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 334             {
 335                                 /* uncle is GTK_RBNODE_RED */
 336               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 337               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 338               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 339               node = node->parent->parent;
 340             }
 341           else
 342             {
 343                                 /* uncle is GTK_RBNODE_BLACK */
 344               if (node == node->parent->right)
 345                 {
 346                   /* make node a left child */
 347                   node = node->parent;
 348                   _gtk_rbnode_rotate_left (tree, node);
 349                 }
 350
 351                                 /* recolor and rotate */
 352               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 353               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 354               _gtk_rbnode_rotate_right(tree, node->parent->parent);
 355             }
 356         }
 357       else
 358         {
 359           /* mirror image of above code */
 360           GtkRBNode *y = node->parent->parent->left;
 361           if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
 362             {
 363                                 /* uncle is GTK_RBNODE_RED */
 364               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 365               GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
 366               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 367               node = node->parent->parent;
 368             }
 369           else
 370             {
 371                                 /* uncle is GTK_RBNODE_BLACK */
 372               if (node == node->parent->left)
 373                 {
 374                   node = node->parent;
 375                   _gtk_rbnode_rotate_right (tree, node);
 376                 }
 377               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 378               GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
 379               _gtk_rbnode_rotate_left (tree, node->parent->parent);
 380             }
 381         }
 382     }
 383   GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);
 384 }
 385
 386 static void
 387 _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
 388                                GtkRBNode *node)
 389 {
 390   while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
 391     {
 392       if (node == node->parent->left)
 393         {
 394           GtkRBNode *w = node->parent->right;
 395           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 396             {
 397               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 398               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
 399               _gtk_rbnode_rotate_left (tree, node->parent);
 400               w = node->parent->right;
 401             }
 402           if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 403             {
 404               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 405               node = node->parent;
 406             }
 407           else
 408             {
 409               if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
 410                 {
 411                   GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 412                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 413                   _gtk_rbnode_rotate_right (tree, w);
 414                   w = node->parent->right;
 415                 }
 416               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
 417               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 418               GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 419               _gtk_rbnode_rotate_left (tree, node->parent);
 420               node = tree->root;
 421             }
 422         }
 423       else
 424         {
 425           GtkRBNode *w = node->parent->left;
 426           if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
 427             {
 428               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
 429               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
 430               _gtk_rbnode_rotate_right (tree, node->parent);
 431               w = node->parent->left;
 432             }
 433           if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 434             {
 435               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 436               node = node->parent;
 437             }
 438           else
 439             {
 440               if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
 441                 {
 442                   GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
 443                   GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
 444                   _gtk_rbnode_rotate_left (tree, w);
 445                   w = node->parent->left;
 446                 }
 447               GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
 448               GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
 449               GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
 450               _gtk_rbnode_rotate_right (tree, node->parent);
 451               node = tree->root;
 452             }
 453         }
 454     }
 455   GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
 456 }
 457
 458 /* Public functions */
 459 void
 460 _gtk_rbnode_push_allocator (GAllocator *allocator)
 461 {
 462   G_LOCK (current_allocator);
 463   _gtk_rbnode_validate_allocator ( allocator );
 464   allocator->last = current_allocator;
 465   current_allocator = allocator;
 466   G_UNLOCK (current_allocator);
 467 }
 468
 469 void
 470 _gtk_rbnode_pop_allocator (void)
 471 {
 472   G_LOCK (current_allocator);
 473   if (current_allocator)
 474     {
 475       GAllocator *allocator;
 476
 477       allocator = current_allocator;
 478       current_allocator = allocator->last;
 479       allocator->last = NULL;
 480       allocator->is_unused = TRUE;
 481     }
 482   G_UNLOCK (current_allocator);
 483 }
 484
 485 GtkRBTree *
 486 _gtk_rbtree_new (void)
 487 {
 488   GtkRBTree *retval;
 489
 490   retval = (GtkRBTree *) g_new (GtkRBTree, 1);
 491   retval->parent_tree = NULL;
 492   retval->parent_node = NULL;
 493
 494   retval->nil = g_new0 (GtkRBNode, 1);
 495   retval->nil->left = NULL;
 496   retval->nil->right = NULL;
 497   retval->nil->parent = NULL;
 498   retval->nil->flags = GTK_RBNODE_BLACK;
 499   retval->nil->count = 0;
 500   retval->nil->offset = 0;
 501   retval->nil->parity = 0;
 502
 503   retval->root = retval->nil;
 504   return retval;
 505 }
 506
 507 static void
 508 _gtk_rbtree_free_helper (GtkRBTree  *tree,
 509                          GtkRBNode  *node,
 510                          gpointer    data)
 511 {
 512   if (node->children)
 513     _gtk_rbtree_free (node->children);
 514
 515   _gtk_rbnode_free (node);
 516 }
 517
 518 void
 519 _gtk_rbtree_free (GtkRBTree *tree)
 520 {
 521   _gtk_rbtree_traverse (tree,
 522                         tree->root,
 523                         G_POST_ORDER,
 524                         _gtk_rbtree_free_helper,
 525                         NULL);
 526
 527   if (tree->parent_node &&
 528       tree->parent_node->children == tree)
 529     tree->parent_node->children = NULL;
 530   _gtk_rbnode_free (tree->nil);
 531   g_free (tree);
 532 }
 533
 534 void
 535 _gtk_rbtree_remove (GtkRBTree *tree)
 536 {
 537   GtkRBTree *tmp_tree;
 538   GtkRBNode *tmp_node;
 539
 540   gint height = tree->root->offset;
 541
 542   if (gtk_debug_flags & GTK_DEBUG_TREE)
 543     _gtk_rbtree_test (G_STRLOC, tree);
 544
 545   tmp_tree = tree->parent_tree;
 546   tmp_node = tree->parent_node;
 547
 548   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 549     {
 550       tmp_node->offset -= height;
 551
 552       /* If the removed tree was odd, flip all parents */
 553       if (tree->root->parity)
 554         tmp_node->parity = !tmp_node->parity;
 555
 556       tmp_node = tmp_node->parent;
 557       if (tmp_node == tmp_tree->nil)
 558         {
 559           tmp_node = tmp_tree->parent_node;
 560           tmp_tree = tmp_tree->parent_tree;
 561         }
 562     }
 563
 564   tmp_tree = tree->parent_tree;
 565   tmp_node = tree->parent_node;
 566   _gtk_rbtree_free (tree);
 567
 568   if (gtk_debug_flags & GTK_DEBUG_TREE)
 569     _gtk_rbtree_test (G_STRLOC, tmp_tree);
 570 }
 571
 572
 573 GtkRBNode *
 574 _gtk_rbtree_insert_after (GtkRBTree  *tree,
 575                           GtkRBNode  *current,
 576                           gint        height)
 577 {
 578   GtkRBNode *node;
 579   gboolean right = TRUE;
 580   GtkRBNode *tmp_node;
 581   GtkRBTree *tmp_tree;
 582
 583   if (gtk_debug_flags & GTK_DEBUG_TREE)
 584     _gtk_rbtree_test (G_STRLOC, tree);
 585
 586   if (current != NULL && current->right != tree->nil)
 587     {
 588       current = current->right;
 589       while (current->left != tree->nil)
 590         current = current->left;
 591       right = FALSE;
 592     }
 593
 594   /* setup new node */
 595   node = _gtk_rbnode_new (tree, height);
 596   node->parent = (current?current:tree->nil);
 597
 598   /* insert node in tree */
 599   if (current)
 600     {
 601       if (right)
 602         current->right = node;
 603       else
 604         current->left = node;
 605       tmp_node = node->parent;
 606       tmp_tree = tree;
 607     }
 608   else
 609     {
 610       tree->root = node;
 611       tmp_node = tree->parent_node;
 612       tmp_tree = tree->parent_tree;
 613     }
 614
 615   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 616     {
 617       /* We only want to propagate the count if we are in the tree we
 618        * started in. */
 619       if (tmp_tree == tree)
 620         tmp_node->count++;
 621
 622       tmp_node->parity += 1;
 623       tmp_node->offset += height;
 624       tmp_node = tmp_node->parent;
 625       if (tmp_node == tmp_tree->nil)
 626         {
 627           tmp_node = tmp_tree->parent_node;
 628           tmp_tree = tmp_tree->parent_tree;
 629         }
 630     }
 631   _gtk_rbtree_insert_fixup (tree, node);
 632
 633   if (gtk_debug_flags & GTK_DEBUG_TREE)
 634     _gtk_rbtree_test (G_STRLOC, tree);
 635
 636   return node;
 637 }
 638
 639 GtkRBNode *
 640 _gtk_rbtree_insert_before (GtkRBTree  *tree,
 641                            GtkRBNode  *current,
 642                            gint        height)
 643 {
 644   GtkRBNode *node;
 645   gboolean left = TRUE;
 646   GtkRBNode *tmp_node;
 647   GtkRBTree *tmp_tree;
 648
 649   if (gtk_debug_flags & GTK_DEBUG_TREE)
 650     _gtk_rbtree_test (G_STRLOC, tree);
 651
 652   if (current != NULL && current->left != tree->nil)
 653     {
 654       current = current->left;
 655       while (current->right != tree->nil)
 656         current = current->right;
 657       left = FALSE;
 658     }
 659
 660   /* setup new node */
 661   node = _gtk_rbnode_new (tree, height);
 662   node->parent = (current?current:tree->nil);
 663
 664   /* insert node in tree */
 665   if (current)
 666     {
 667       if (left)
 668         current->left = node;
 669       else
 670         current->right = node;
 671       tmp_node = node->parent;
 672       tmp_tree = tree;
 673     }
 674   else
 675     {
 676       tree->root = node;
 677       tmp_node = tree->parent_node;
 678       tmp_tree = tree->parent_tree;
 679     }
 680
 681   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 682     {
 683       /* We only want to propagate the count if we are in the tree we
 684        * started in. */
 685       if (tmp_tree == tree)
 686         tmp_node->count++;
 687
 688       tmp_node->parity += 1;
 689       tmp_node->offset += height;
 690       tmp_node = tmp_node->parent;
 691       if (tmp_node == tmp_tree->nil)
 692         {
 693           tmp_node = tmp_tree->parent_node;
 694           tmp_tree = tmp_tree->parent_tree;
 695         }
 696     }
 697   _gtk_rbtree_insert_fixup (tree, node);
 698
 699   if (gtk_debug_flags & GTK_DEBUG_TREE)
 700     _gtk_rbtree_test (G_STRLOC, tree);
 701
 702   return node;
 703 }
 704
 705 GtkRBNode *
 706 _gtk_rbtree_find_count (GtkRBTree *tree,
 707                         gint       count)
 708 {
 709   GtkRBNode *node;
 710
 711   node = tree->root;
 712   while (node != tree->nil && (node->left->count + 1 != count))
 713     {
 714       if (node->left->count >= count)
 715         node = node->left;
 716       else
 717         {
 718           count -= (node->left->count + 1);
 719           node = node->right;
 720         }
 721     }
 722   if (node == tree->nil)
 723     return NULL;
 724   return node;
 725 }
 726
 727 void
 728 _gtk_rbtree_node_set_height (GtkRBTree *tree,
 729                              GtkRBNode *node,
 730                              gint       height)
 731 {
 732   gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
 733   GtkRBNode *tmp_node = node;
 734   GtkRBTree *tmp_tree = tree;
 735
 736   if (diff == 0)
 737     return;
 738
 739   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 740     {
 741       tmp_node->offset += diff;
 742       tmp_node = tmp_node->parent;
 743       if (tmp_node == tmp_tree->nil)
 744         {
 745           tmp_node = tmp_tree->parent_node;
 746           tmp_tree = tmp_tree->parent_tree;
 747         }
 748     }
 749 }
 750
 751 void
 752 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
 753                                GtkRBNode *node)
 754 {
 755   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 756     return;
 757
 758   GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 759   do
 760     {
 761       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
 762         return;
 763       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 764       node = node->parent;
 765       if (node == NULL)
 766         {
 767           node = tree->parent_node;
 768           tree = tree->parent_tree;
 769         }
 770     }
 771   while (node);
 772 }
 773
 774 void
 775 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 776                              GtkRBNode *node)
 777 {
 778   if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 779     return;
 780
 781   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
 782   do
 783     {
 784       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
 785           (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 786           (node->left && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 787           (node->right && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
 788         return;
 789
 790       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 791       node = node->parent;
 792       if (node == NULL)
 793         {
 794           node = tree->parent_node;
 795           tree = tree->parent_tree;
 796         }
 797     }
 798   while (node);
 799 }
 800
 801 typedef struct _GtkRBReorder
 802 {
 803   GtkRBTree *children;
 804   gint height;
 805   gint flags;
 806   gint order;
 807   gint invert_order;
 808   gint parity;
 809 } GtkRBReorder;
 810
 811 static int
 812 gtk_rbtree_reorder_sort_func (gconstpointer a,
 813                               gconstpointer b)
 814 {
 815   return ((GtkRBReorder *) a)->order > ((GtkRBReorder *) b)->order;
 816 }
 817
 818 static int
 819 gtk_rbtree_reorder_invert_func (gconstpointer a,
 820                                 gconstpointer b)
 821 {
 822   return ((GtkRBReorder *) a)->invert_order > ((GtkRBReorder *) b)->invert_order;
 823 }
 824
 825 static void
 826 gtk_rbtree_reorder_fixup (GtkRBTree *tree,
 827                           GtkRBNode *node)
 828 {
 829   if (node == tree->nil)
 830     return;
 831
 832   node->parity = 1;
 833
 834   if (node->left != tree->nil)
 835     {
 836       gtk_rbtree_reorder_fixup (tree, node->left);
 837       node->offset += node->left->offset;
 838       node->parity += node->left->parity;
 839     }
 840   if (node->right != tree->nil)
 841     {
 842       gtk_rbtree_reorder_fixup (tree, node->right);
 843       node->offset += node->right->offset;
 844       node->parity += node->right->parity;
 845     }
 846
 847   if (node->children)
 848     {
 849       node->offset += node->children->root->offset;
 850       node->parity += node->children->root->parity;
 851     }
 852 }
 853
 854 /* It basically pulls everything out of the tree, rearranges it, and puts it
 855  * back together.  Our strategy is to keep the old RBTree intact, and just
 856  * rearrange the contents.  When that is done, we go through and update the
 857  * heights.  There is probably a more elegant way to write this function.  If
 858  * anyone wants to spend the time writing it, patches will be accepted.
 859  */
 860 void
 861 _gtk_rbtree_reorder (GtkRBTree *tree,
 862                      gint      *new_order,
 863                      gint       length)
 864 {
 865   GtkRBReorder reorder;
 866   GArray *array;
 867   GtkRBNode *node;
 868   gint i;
 869
 870   g_return_if_fail (tree != NULL);
 871   g_return_if_fail (length > 0);
 872   g_return_if_fail (tree->root->count == length);
 873
 874   /* Sort the trees values in the new tree. */
 875   array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
 876   for (i = 0; i < length; i++)
 877     {
 878       reorder.order = new_order[i];
 879       reorder.invert_order = i;
 880       g_array_append_val (array, reorder);
 881     }
 882
 883   g_array_sort(array, gtk_rbtree_reorder_sort_func);
 884
 885   /* rewind node*/
 886   node = tree->root;
 887   while (node && node->left != tree->nil)
 888     node = node->left;
 889
 890   for (i = 0; i < length; i++)
 891     {
 892       g_assert (node != tree->nil);
 893       g_array_index (array, GtkRBReorder, i).children = node->children;
 894       g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
 895       g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
 896
 897       node = _gtk_rbtree_next (tree, node);
 898     }
 899
 900   g_array_sort (array, gtk_rbtree_reorder_invert_func);
 901
 902   /* rewind node*/
 903   node = tree->root;
 904   while (node && node->left != tree->nil)
 905     node = node->left;
 906
 907   /* Go through the tree and change the values to the new ones. */
 908   for (i = 0; i < length; i++)
 909     {
 910       reorder = g_array_index (array, GtkRBReorder, i);
 911       node->children = reorder.children;
 912       if (node->children)
 913         node->children->parent_node = node;
 914       node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
 915       /* We temporarily set the height to this. */
 916       node->offset = reorder.height;
 917       node = _gtk_rbtree_next (tree, node);
 918     }
 919   gtk_rbtree_reorder_fixup (tree, tree->root);
 920 }
 921
 922
 923 gint
 924 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 925                               GtkRBNode *node)
 926 {
 927   GtkRBNode *last;
 928   gint retval;
 929
 930   g_assert (node);
 931   g_assert (node->left);
 932
 933   retval = node->left->offset;
 934
 935   while (tree && node && node != tree->nil)
 936     {
 937       last = node;
 938       node = node->parent;
 939
 940       /* Add left branch, plus children, iff we came from the right */
 941       if (node->right == last)
 942         retval += node->offset - node->right->offset;
 943
 944       if (node == tree->nil)
 945         {
 946           node = tree->parent_node;
 947           tree = tree->parent_tree;
 948
 949           /* Add the parent node, plus the left branch. */
 950           if (node)
 951             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 952         }
 953     }
 954   return retval;
 955 }
 956
 957 gint
 958 _gtk_rbtree_node_find_parity (GtkRBTree *tree,
 959                               GtkRBNode *node)
 960 {
 961   GtkRBNode *last;
 962   gint retval;
 963
 964   g_assert (node);
 965   g_assert (node->left);
 966
 967   retval = node->left->parity;
 968
 969   while (tree && node && node != tree->nil)
 970     {
 971       last = node;
 972       node = node->parent;
 973
 974       /* Add left branch, plus children, iff we came from the right */
 975       if (node->right == last)
 976         retval += node->parity - node->right->parity;
 977
 978       if (node == tree->nil)
 979         {
 980           node = tree->parent_node;
 981           tree = tree->parent_tree;
 982
 983           /* Add the parent node, plus the left branch. */
 984           if (node)
 985             retval += node->left->parity + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
 986         }
 987     }
 988
 989   return retval % 2;
 990 }
 991
 992 gint
 993 _gtk_rbtree_find_offset (GtkRBTree  *tree,
 994                          gint        height,
 995                          GtkRBTree **new_tree,
 996                          GtkRBNode **new_node)
 997 {
 998   GtkRBNode *tmp_node;
 999
1000   if (height < 0)
1001     {
1002       *new_tree = NULL;
1003       *new_node = NULL;
1004       return 0;
1005     }
1006
1007   tmp_node = tree->root;
1008   while (tmp_node != tree->nil &&
1009          (tmp_node->left->offset > height ||
1010           (tmp_node->offset - tmp_node->right->offset) < height))
1011     {
1012       if (tmp_node->left->offset > height)
1013         tmp_node = tmp_node->left;
1014       else
1015         {
1016           height -= (tmp_node->offset - tmp_node->right->offset);
1017           tmp_node = tmp_node->right;
1018         }
1019     }
1020   if (tmp_node == tree->nil)
1021     {
1022       *new_tree = NULL;
1023       *new_node = NULL;
1024       return 0;
1025     }
1026   if (tmp_node->children)
1027     {
1028       if ((tmp_node->offset -
1029            tmp_node->right->offset -
1030            tmp_node->children->root->offset) > height)
1031         {
1032           *new_tree = tree;
1033           *new_node = tmp_node;
1034           return (height - tmp_node->left->offset);
1035         }
1036       return _gtk_rbtree_find_offset (tmp_node->children,
1037                                       height - tmp_node->left->offset -
1038                                       (tmp_node->offset -
1039                                        tmp_node->left->offset -
1040                                        tmp_node->right->offset -
1041                                        tmp_node->children->root->offset),
1042                                       new_tree,
1043                                       new_node);
1044     }
1045   *new_tree = tree;
1046   *new_node = tmp_node;
1047   return (height - tmp_node->left->offset);
1048 }
1049
1050
1051 void
1052 _gtk_rbtree_remove_node (GtkRBTree *tree,
1053                          GtkRBNode *node)
1054 {
1055   GtkRBNode *x, *y;
1056   GtkRBTree *tmp_tree;
1057   GtkRBNode *tmp_node;
1058
1059   g_return_if_fail (tree != NULL);
1060   g_return_if_fail (node != NULL);
1061
1062   /* make sure we're deleting a node that's actually in the tree */
1063   for (x = node; x->parent != tree->nil; x = x->parent)
1064     ;
1065   g_return_if_fail (x == tree->root);
1066
1067   if (gtk_debug_flags & GTK_DEBUG_TREE)
1068     _gtk_rbtree_test (G_STRLOC, tree);
1069
1070   if (node->left == tree->nil || node->right == tree->nil)
1071     {
1072       y = node;
1073     }
1074   else
1075     {
1076       y = node->right;
1077
1078       while (y->left != tree->nil)
1079         y = y->left;
1080     }
1081
1082   /* adjust count only beneath tree */
1083   for (x = y; x != tree->nil; x = x->parent)
1084     x->count--;
1085
1086   /*   y->count = node->count; */
1087
1088   /* offsets and parity adjust all the way up through parent trees */
1089
1090   tmp_tree = tree;
1091   tmp_node = y;
1092
1093   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1094     {
1095       /*       tmp_node->offset -= y->offset; */
1096       tmp_node->parity -= (guint) 1; /* parity of y is always 1 */
1097
1098       tmp_node = tmp_node->parent;
1099       if (tmp_node == tmp_tree->nil)
1100         {
1101           tmp_node = tmp_tree->parent_node;
1102           tmp_tree = tmp_tree->parent_tree;
1103         }
1104     }
1105
1106   /* x is y's only child */
1107   if (y->left != tree->nil)
1108     x = y->left;
1109   else
1110     x = y->right;
1111
1112   /* remove y from the parent chain */
1113   x->parent = y->parent;
1114   if (y->parent != tree->nil)
1115     if (y == y->parent->left)
1116       y->parent->left = x;
1117     else
1118       y->parent->right = x;
1119   else
1120     tree->root = x;
1121
1122   if (y != node)
1123     {
1124       /* Copy the node over */
1125       if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1126         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
1127       else
1128         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
1129       node->children = y->children;
1130     }
1131
1132   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1133     _gtk_rbtree_remove_node_fixup (tree, x);
1134
1135   _gtk_rbnode_free (y);
1136
1137   if (gtk_debug_flags & GTK_DEBUG_TREE)
1138     _gtk_rbtree_test (G_STRLOC, tree);
1139 }
1140
1141 GtkRBNode *
1142 _gtk_rbtree_next (GtkRBTree *tree,
1143                   GtkRBNode *node)
1144 {
1145   g_return_val_if_fail (tree != NULL, NULL);
1146   g_return_val_if_fail (node != NULL, NULL);
1147
1148   /* Case 1: the node's below us. */
1149   if (node->right != tree->nil)
1150     {
1151       node = node->right;
1152       while (node->left != tree->nil)
1153         node = node->left;
1154       return node;
1155     }
1156
1157   /* Case 2: it's an ancestor */
1158   while (node->parent != tree->nil)
1159     {
1160       if (node->parent->right == node)
1161         node = node->parent;
1162       else
1163         return (node->parent);
1164     }
1165
1166   /* Case 3: There is no next node */
1167   return NULL;
1168 }
1169
1170 GtkRBNode *
1171 _gtk_rbtree_prev (GtkRBTree *tree,
1172                   GtkRBNode *node)
1173 {
1174   g_return_val_if_fail (tree != NULL, NULL);
1175   g_return_val_if_fail (node != NULL, NULL);
1176
1177   /* Case 1: the node's below us. */
1178   if (node->left != tree->nil)
1179     {
1180       node = node->left;
1181       while (node->right != tree->nil)
1182         node = node->right;
1183       return node;
1184     }
1185
1186   /* Case 2: it's an ancestor */
1187   while (node->parent != tree->nil)
1188     {
1189       if (node->parent->left == node)
1190         node = node->parent;
1191       else
1192         return (node->parent);
1193     }
1194
1195   /* Case 3: There is no next node */
1196   return NULL;
1197 }
1198
1199 void
1200 _gtk_rbtree_next_full (GtkRBTree  *tree,
1201                        GtkRBNode  *node,
1202                        GtkRBTree **new_tree,
1203                        GtkRBNode **new_node)
1204 {
1205   g_return_if_fail (tree != NULL);
1206   g_return_if_fail (node != NULL);
1207   g_return_if_fail (new_tree != NULL);
1208   g_return_if_fail (new_node != NULL);
1209
1210   if (node->children)
1211     {
1212       *new_tree = node->children;
1213       *new_node = (*new_tree)->root;
1214       while ((*new_node)->left != (*new_tree)->nil)
1215         *new_node = (*new_node)->left;
1216       return;
1217     }
1218
1219   *new_tree = tree;
1220   *new_node = _gtk_rbtree_next (tree, node);
1221
1222   while ((*new_node == NULL) &&
1223          (*new_tree != NULL))
1224     {
1225       *new_node = (*new_tree)->parent_node;
1226       *new_tree = (*new_tree)->parent_tree;
1227       if (*new_tree)
1228         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1229     }
1230 }
1231
1232 void
1233 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1234                        GtkRBNode  *node,
1235                        GtkRBTree **new_tree,
1236                        GtkRBNode **new_node)
1237 {
1238   g_return_if_fail (tree != NULL);
1239   g_return_if_fail (node != NULL);
1240   g_return_if_fail (new_tree != NULL);
1241   g_return_if_fail (new_node != NULL);
1242
1243   *new_tree = tree;
1244   *new_node = _gtk_rbtree_prev (tree, node);
1245
1246   if (*new_node == NULL)
1247     {
1248       *new_node = (*new_tree)->parent_node;
1249       *new_tree = (*new_tree)->parent_tree;
1250     }
1251   else
1252     {
1253       while ((*new_node)->children)
1254         {
1255           *new_tree = (*new_node)->children;
1256           *new_node = (*new_tree)->root;
1257           while ((*new_node)->right != (*new_tree)->nil)
1258             *new_node = (*new_node)->right;
1259         }
1260     }
1261 }
1262
1263 gint
1264 _gtk_rbtree_get_depth (GtkRBTree *tree)
1265 {
1266   GtkRBTree *tmp_tree;
1267   gint depth = 0;
1268
1269   tmp_tree = tree->parent_tree;
1270   while (tmp_tree)
1271     {
1272       ++depth;
1273       tmp_tree = tmp_tree->parent_tree;
1274     }
1275
1276   return depth;
1277 }
1278
1279 static void
1280 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1281                                 GtkRBNode             *node,
1282                                 GtkRBTreeTraverseFunc  func,
1283                                 gpointer               data)
1284 {
1285   if (node == tree->nil)
1286     return;
1287
1288   (* func) (tree, node, data);
1289   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1290   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1291 }
1292
1293 static void
1294 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1295                                  GtkRBNode             *node,
1296                                  GtkRBTreeTraverseFunc  func,
1297                                  gpointer               data)
1298 {
1299   if (node == tree->nil)
1300     return;
1301
1302   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1303   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1304   (* func) (tree, node, data);
1305 }
1306
1307 void
1308 _gtk_rbtree_traverse (GtkRBTree             *tree,
1309                       GtkRBNode             *node,
1310                       GTraverseType          order,
1311                       GtkRBTreeTraverseFunc  func,
1312                       gpointer               data)
1313 {
1314   g_return_if_fail (tree != NULL);
1315   g_return_if_fail (node != NULL);
1316   g_return_if_fail (func != NULL);
1317   g_return_if_fail (order <= G_LEVEL_ORDER);
1318
1319   switch (order)
1320     {
1321     case G_PRE_ORDER:
1322       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1323       break;
1324     case G_POST_ORDER:
1325       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1326       break;
1327     case G_IN_ORDER:
1328     case G_LEVEL_ORDER:
1329     default:
1330       g_warning ("unsupported traversal order.");
1331       break;
1332     }
1333 }
1334
1335 static gint
1336 _count_nodes (GtkRBTree *tree,
1337               GtkRBNode *node)
1338 {
1339   gint res;
1340   if (node == tree->nil)
1341     return 0;
1342
1343   g_assert (node->left);
1344   g_assert (node->right);
1345
1346   res = (_count_nodes (tree, node->left) +
1347          _count_nodes (tree, node->right) + 1);
1348
1349   if (res != node->count)
1350     g_print ("Tree failed\n");
1351   return res;
1352 }
1353
1354 static guint
1355 get_parity (GtkRBNode *node)
1356 {
1357   guint child_total = 0;
1358   guint rem;
1359
1360   /* The parity of a node is node->parity minus
1361    * the parity of left, right, and children.
1362    *
1363    * This is equivalent to saying that if left, right, children
1364    * sum to 0 parity, then node->parity is the parity of node,
1365    * and if left, right, children are odd parity, then
1366    * node->parity is the reverse of the node's parity.
1367    */
1368
1369   child_total += (guint) node->left->parity;
1370   child_total += (guint) node->right->parity;
1371
1372   if (node->children)
1373     child_total += (guint) node->children->root->parity;
1374
1375   rem = child_total % 2;
1376
1377   if (rem == 0)
1378     return node->parity;
1379   else
1380     return !node->parity;
1381 }
1382
1383 static guint
1384 count_parity (GtkRBTree *tree,
1385               GtkRBNode *node)
1386 {
1387   guint res;
1388
1389   if (node == tree->nil)
1390     return 0;
1391
1392   res =
1393     count_parity (tree, node->left) +
1394     count_parity (tree, node->right) +
1395     (guint)1 +
1396     (node->children ? count_parity (node->children, node->children->root) : 0);
1397
1398   res = res % (guint)2;
1399
1400   if (res != node->parity)
1401     g_print ("parity incorrect for node\n");
1402
1403   if (get_parity (node) != 1)
1404     g_error ("Node has incorrect parity %d", get_parity (node));
1405
1406   return res;
1407 }
1408
1409 static void
1410 _gtk_rbtree_test_height (GtkRBTree *tree,
1411                          GtkRBNode *node)
1412 {
1413   gint computed_offset = 0;
1414
1415   /* This whole test is sort of a useless truism. */
1416
1417   if (node->left != tree->nil)
1418     computed_offset += node->left->offset;
1419
1420   if (node->right != tree->nil)
1421     computed_offset += node->right->offset;
1422
1423   if (node->children && node->children->root != node->children->nil)
1424     computed_offset += node->children->root->offset;
1425
1426   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1427     g_error ("node has broken offset\n");
1428
1429   if (node->left != tree->nil)
1430     _gtk_rbtree_test_height (tree, node->left);
1431
1432   if (node->right != tree->nil)
1433     _gtk_rbtree_test_height (tree, node->right);
1434
1435   if (node->children && node->children->root != node->children->nil)
1436     _gtk_rbtree_test_height (node->children, node->children->root);
1437 }
1438
1439 void
1440 _gtk_rbtree_test (const gchar *where,
1441                   GtkRBTree   *tree)
1442 {
1443   GtkRBTree *tmp_tree;
1444
1445   /* Test the entire tree */
1446   tmp_tree = tree;
1447   while (tmp_tree->parent_tree)
1448     tmp_tree = tmp_tree->parent_tree;
1449
1450   g_print ("%s: whole tree offset is %d\n", where, tmp_tree->root->offset);
1451
1452   if (tmp_tree->root != tmp_tree->nil)
1453     {
1454       g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1455                  _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1456
1457
1458       _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1459
1460       g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
1461     }
1462 }
1463