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 } GtkRBReorder;
 809
 810 static int
 811 gtk_rbtree_reorder_sort_func (gconstpointer a,
 812                               gconstpointer b)
 813 {
 814   return ((GtkRBReorder *) a)->order > ((GtkRBReorder *) b)->order;
 815 }
 816
 817 static int
 818 gtk_rbtree_reorder_invert_func (gconstpointer a,
 819                                 gconstpointer b)
 820 {
 821   return ((GtkRBReorder *) a)->invert_order > ((GtkRBReorder *) b)->invert_order;
 822 }
 823
 824 static void
 825 gtk_rbtree_reorder_fixup (GtkRBTree *tree,
 826                           GtkRBNode *node)
 827 {
 828   if (node == tree->nil)
 829     return;
 830
 831   if (node->left != tree->nil)
 832     {
 833       gtk_rbtree_reorder_fixup (tree, node->left);
 834       node->offset += node->left->offset;
 835     }
 836   if (node->right != tree->nil)
 837     {
 838       gtk_rbtree_reorder_fixup (tree, node->right);
 839       node->offset += node->right->offset;
 840     }
 841
 842   if (node->children)
 843     node->offset += node->children->root->offset;
 844 }
 845
 846 /* It basically pulls everything out of the tree, rearranges it, and puts it
 847  * back together.  Our strategy is to keep the old RBTree intact, and just
 848  * rearrange the contents.  When that is done, we go through and update the
 849  * heights.  There is probably a more elegant way to write this function.  If
 850  * anyone wants to spend the time writing it, patches will be accepted.
 851  */
 852
 853 void
 854 _gtk_rbtree_reorder (GtkRBTree *tree,
 855                      gint      *new_order,
 856                      gint       length)
 857 {
 858   GtkRBReorder reorder;
 859   GArray *array;
 860   GtkRBNode *node;
 861   gint i;
 862
 863   g_return_if_fail (tree != NULL);
 864   g_return_if_fail (length > 0);
 865   g_return_if_fail (tree->root->count == length);
 866
 867   /* Sort the trees values in the new tree. */
 868   array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
 869   for (i = 0; i < length; i++)
 870     {
 871       reorder.order = new_order[i];
 872       reorder.invert_order = i;
 873       g_array_append_val (array, reorder);
 874     }
 875
 876   g_array_sort(array, gtk_rbtree_reorder_sort_func);
 877
 878   /* rewind node*/
 879   node = tree->root;
 880   while (node && node->left != tree->nil)
 881     node = node->left;
 882
 883   for (i = 0; i < length; i++)
 884     {
 885       g_assert (node != tree->nil);
 886       g_array_index (array, GtkRBReorder, i).children = node->children;
 887       g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
 888       g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
 889
 890       node = _gtk_rbtree_next (tree, node);
 891     }
 892
 893   g_array_sort (array, gtk_rbtree_reorder_invert_func);
 894
 895   /* rewind node*/
 896   node = tree->root;
 897   while (node && node->left != tree->nil)
 898     node = node->left;
 899
 900   /* Go through the tree and change the values to the new ones. */
 901   for (i = 0; i < length; i++)
 902     {
 903       reorder = g_array_index (array, GtkRBReorder, i);
 904       node->children = reorder.children;
 905       if (node->children)
 906         node->children->parent_node = node;
 907       node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
 908       /* We temporarily set the height to this. */
 909       node->offset = reorder.height;
 910       node = _gtk_rbtree_next (tree, node);
 911     }
 912   gtk_rbtree_reorder_fixup (tree, tree->root);
 913 }
 914
 915
 916 gint
 917 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 918                               GtkRBNode *node)
 919 {
 920   GtkRBNode *last;
 921   gint retval;
 922
 923   g_assert (node);
 924   g_assert (node->left);
 925
 926   retval = node->left->offset;
 927
 928   while (tree && node && node != tree->nil)
 929     {
 930       last = node;
 931       node = node->parent;
 932
 933       /* Add left branch, plus children, iff we came from the right */
 934       if (node->right == last)
 935         retval += node->offset - node->right->offset;
 936
 937       if (node == tree->nil)
 938         {
 939           node = tree->parent_node;
 940           tree = tree->parent_tree;
 941
 942           /* Add the parent node, plus the left branch. */
 943           if (node)
 944             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
 945         }
 946     }
 947   return retval;
 948 }
 949
 950 gint
 951 _gtk_rbtree_node_find_parity (GtkRBTree *tree,
 952                               GtkRBNode *node)
 953 {
 954   GtkRBNode *last;
 955   gint retval;
 956
 957   g_assert (node);
 958   g_assert (node->left);
 959
 960   retval = node->left->parity;
 961
 962   while (tree && node && node != tree->nil)
 963     {
 964       last = node;
 965       node = node->parent;
 966
 967       /* Add left branch, plus children, iff we came from the right */
 968       if (node->right == last)
 969         retval += node->parity - node->right->parity;
 970
 971       if (node == tree->nil)
 972         {
 973           node = tree->parent_node;
 974           tree = tree->parent_tree;
 975
 976           /* Add the parent node, plus the left branch. */
 977           if (node)
 978             retval += node->left->parity + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
 979         }
 980     }
 981
 982   return retval % 2;
 983 }
 984
 985 gint
 986 _gtk_rbtree_find_offset (GtkRBTree  *tree,
 987                          gint        height,
 988                          GtkRBTree **new_tree,
 989                          GtkRBNode **new_node)
 990 {
 991   GtkRBNode *tmp_node;
 992
 993   if (height < 0)
 994     {
 995       *new_tree = NULL;
 996       *new_node = NULL;
 997       return 0;
 998     }
 999
1000   tmp_node = tree->root;
1001   while (tmp_node != tree->nil &&
1002          (tmp_node->left->offset > height ||
1003           (tmp_node->offset - tmp_node->right->offset) < height))
1004     {
1005       if (tmp_node->left->offset > height)
1006         tmp_node = tmp_node->left;
1007       else
1008         {
1009           height -= (tmp_node->offset - tmp_node->right->offset);
1010           tmp_node = tmp_node->right;
1011         }
1012     }
1013   if (tmp_node == tree->nil)
1014     {
1015       *new_tree = NULL;
1016       *new_node = NULL;
1017       return 0;
1018     }
1019   if (tmp_node->children)
1020     {
1021       if ((tmp_node->offset -
1022            tmp_node->right->offset -
1023            tmp_node->children->root->offset) > height)
1024         {
1025           *new_tree = tree;
1026           *new_node = tmp_node;
1027           return (height - tmp_node->left->offset);
1028         }
1029       return _gtk_rbtree_find_offset (tmp_node->children,
1030                                       height - tmp_node->left->offset -
1031                                       (tmp_node->offset -
1032                                        tmp_node->left->offset -
1033                                        tmp_node->right->offset -
1034                                        tmp_node->children->root->offset),
1035                                       new_tree,
1036                                       new_node);
1037     }
1038   *new_tree = tree;
1039   *new_node = tmp_node;
1040   return (height - tmp_node->left->offset);
1041 }
1042
1043
1044 void
1045 _gtk_rbtree_remove_node (GtkRBTree *tree,
1046                          GtkRBNode *node)
1047 {
1048   GtkRBNode *x, *y;
1049   GtkRBTree *tmp_tree;
1050   GtkRBNode *tmp_node;
1051
1052   g_return_if_fail (tree != NULL);
1053   g_return_if_fail (node != NULL);
1054
1055   /* make sure we're deleting a node that's actually in the tree */
1056   for (x = node; x->parent != tree->nil; x = x->parent)
1057     ;
1058   g_return_if_fail (x == tree->root);
1059
1060   if (gtk_debug_flags & GTK_DEBUG_TREE)
1061     _gtk_rbtree_test (G_STRLOC, tree);
1062
1063   if (node->left == tree->nil || node->right == tree->nil)
1064     {
1065       y = node;
1066     }
1067   else
1068     {
1069       y = node->right;
1070
1071       while (y->left != tree->nil)
1072         y = y->left;
1073     }
1074
1075   /* adjust count only beneath tree */
1076   for (x = y; x != tree->nil; x = x->parent)
1077     x->count--;
1078
1079   /*   y->count = node->count; */
1080
1081   /* offsets and parity adjust all the way up through parent trees */
1082
1083   tmp_tree = tree;
1084   tmp_node = y;
1085
1086   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1087     {
1088       /*       tmp_node->offset -= y->offset; */
1089       tmp_node->parity -= (guint) 1; /* parity of y is always 1 */
1090
1091       tmp_node = tmp_node->parent;
1092       if (tmp_node == tmp_tree->nil)
1093         {
1094           tmp_node = tmp_tree->parent_node;
1095           tmp_tree = tmp_tree->parent_tree;
1096         }
1097     }
1098
1099   /* x is y's only child */
1100   if (y->left != tree->nil)
1101     x = y->left;
1102   else
1103     x = y->right;
1104
1105   /* remove y from the parent chain */
1106   x->parent = y->parent;
1107   if (y->parent != tree->nil)
1108     if (y == y->parent->left)
1109       y->parent->left = x;
1110     else
1111       y->parent->right = x;
1112   else
1113     tree->root = x;
1114
1115   if (y != node)
1116     {
1117       /* Copy the node over */
1118       if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1119         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
1120       else
1121         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
1122       node->children = y->children;
1123     }
1124
1125   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1126     _gtk_rbtree_remove_node_fixup (tree, x);
1127
1128   _gtk_rbnode_free (y);
1129
1130   if (gtk_debug_flags & GTK_DEBUG_TREE)
1131     _gtk_rbtree_test (G_STRLOC, tree);
1132 }
1133
1134 GtkRBNode *
1135 _gtk_rbtree_next (GtkRBTree *tree,
1136                   GtkRBNode *node)
1137 {
1138   g_return_val_if_fail (tree != NULL, NULL);
1139   g_return_val_if_fail (node != NULL, NULL);
1140
1141   /* Case 1: the node's below us. */
1142   if (node->right != tree->nil)
1143     {
1144       node = node->right;
1145       while (node->left != tree->nil)
1146         node = node->left;
1147       return node;
1148     }
1149
1150   /* Case 2: it's an ancestor */
1151   while (node->parent != tree->nil)
1152     {
1153       if (node->parent->right == node)
1154         node = node->parent;
1155       else
1156         return (node->parent);
1157     }
1158
1159   /* Case 3: There is no next node */
1160   return NULL;
1161 }
1162
1163 GtkRBNode *
1164 _gtk_rbtree_prev (GtkRBTree *tree,
1165                   GtkRBNode *node)
1166 {
1167   g_return_val_if_fail (tree != NULL, NULL);
1168   g_return_val_if_fail (node != NULL, NULL);
1169
1170   /* Case 1: the node's below us. */
1171   if (node->left != tree->nil)
1172     {
1173       node = node->left;
1174       while (node->right != tree->nil)
1175         node = node->right;
1176       return node;
1177     }
1178
1179   /* Case 2: it's an ancestor */
1180   while (node->parent != tree->nil)
1181     {
1182       if (node->parent->left == node)
1183         node = node->parent;
1184       else
1185         return (node->parent);
1186     }
1187
1188   /* Case 3: There is no next node */
1189   return NULL;
1190 }
1191
1192 void
1193 _gtk_rbtree_next_full (GtkRBTree  *tree,
1194                        GtkRBNode  *node,
1195                        GtkRBTree **new_tree,
1196                        GtkRBNode **new_node)
1197 {
1198   g_return_if_fail (tree != NULL);
1199   g_return_if_fail (node != NULL);
1200   g_return_if_fail (new_tree != NULL);
1201   g_return_if_fail (new_node != NULL);
1202
1203   if (node->children)
1204     {
1205       *new_tree = node->children;
1206       *new_node = (*new_tree)->root;
1207       while ((*new_node)->left != (*new_tree)->nil)
1208         *new_node = (*new_node)->left;
1209       return;
1210     }
1211
1212   *new_tree = tree;
1213   *new_node = _gtk_rbtree_next (tree, node);
1214
1215   while ((*new_node == NULL) &&
1216          (*new_tree != NULL))
1217     {
1218       *new_node = (*new_tree)->parent_node;
1219       *new_tree = (*new_tree)->parent_tree;
1220       if (*new_tree)
1221         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1222     }
1223 }
1224
1225 void
1226 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1227                        GtkRBNode  *node,
1228                        GtkRBTree **new_tree,
1229                        GtkRBNode **new_node)
1230 {
1231   g_return_if_fail (tree != NULL);
1232   g_return_if_fail (node != NULL);
1233   g_return_if_fail (new_tree != NULL);
1234   g_return_if_fail (new_node != NULL);
1235
1236   *new_tree = tree;
1237   *new_node = _gtk_rbtree_prev (tree, node);
1238
1239   if (*new_node == NULL)
1240     {
1241       *new_node = (*new_tree)->parent_node;
1242       *new_tree = (*new_tree)->parent_tree;
1243     }
1244   else
1245     {
1246       while ((*new_node)->children)
1247         {
1248           *new_tree = (*new_node)->children;
1249           *new_node = (*new_tree)->root;
1250           while ((*new_node)->right != (*new_tree)->nil)
1251             *new_node = (*new_node)->right;
1252         }
1253     }
1254 }
1255
1256 gint
1257 _gtk_rbtree_get_depth (GtkRBTree *tree)
1258 {
1259   GtkRBTree *tmp_tree;
1260   gint depth = 0;
1261
1262   tmp_tree = tree->parent_tree;
1263   while (tmp_tree)
1264     {
1265       ++depth;
1266       tmp_tree = tmp_tree->parent_tree;
1267     }
1268
1269   return depth;
1270 }
1271
1272 static void
1273 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1274                                 GtkRBNode             *node,
1275                                 GtkRBTreeTraverseFunc  func,
1276                                 gpointer               data)
1277 {
1278   if (node == tree->nil)
1279     return;
1280
1281   (* func) (tree, node, data);
1282   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1283   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1284 }
1285
1286 static void
1287 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1288                                  GtkRBNode             *node,
1289                                  GtkRBTreeTraverseFunc  func,
1290                                  gpointer               data)
1291 {
1292   if (node == tree->nil)
1293     return;
1294
1295   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1296   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1297   (* func) (tree, node, data);
1298 }
1299
1300 void
1301 _gtk_rbtree_traverse (GtkRBTree             *tree,
1302                       GtkRBNode             *node,
1303                       GTraverseType          order,
1304                       GtkRBTreeTraverseFunc  func,
1305                       gpointer               data)
1306 {
1307   g_return_if_fail (tree != NULL);
1308   g_return_if_fail (node != NULL);
1309   g_return_if_fail (func != NULL);
1310   g_return_if_fail (order <= G_LEVEL_ORDER);
1311
1312   switch (order)
1313     {
1314     case G_PRE_ORDER:
1315       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1316       break;
1317     case G_POST_ORDER:
1318       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1319       break;
1320     case G_IN_ORDER:
1321     case G_LEVEL_ORDER:
1322     default:
1323       g_warning ("unsupported traversal order.");
1324       break;
1325     }
1326 }
1327
1328 static gint
1329 _count_nodes (GtkRBTree *tree,
1330               GtkRBNode *node)
1331 {
1332   gint res;
1333   if (node == tree->nil)
1334     return 0;
1335
1336   g_assert (node->left);
1337   g_assert (node->right);
1338
1339   res = (_count_nodes (tree, node->left) +
1340          _count_nodes (tree, node->right) + 1);
1341
1342   if (res != node->count)
1343     g_print ("Tree failed\n");
1344   return res;
1345 }
1346
1347 static guint
1348 get_parity (GtkRBNode *node)
1349 {
1350   guint child_total = 0;
1351   guint rem;
1352
1353   /* The parity of a node is node->parity minus
1354    * the parity of left, right, and children.
1355    *
1356    * This is equivalent to saying that if left, right, children
1357    * sum to 0 parity, then node->parity is the parity of node,
1358    * and if left, right, children are odd parity, then
1359    * node->parity is the reverse of the node's parity.
1360    */
1361
1362   child_total += (guint) node->left->parity;
1363   child_total += (guint) node->right->parity;
1364
1365   if (node->children)
1366     child_total += (guint) node->children->root->parity;
1367
1368   rem = child_total % 2;
1369
1370   if (rem == 0)
1371     return node->parity;
1372   else
1373     return !node->parity;
1374 }
1375
1376 static guint
1377 count_parity (GtkRBTree *tree,
1378               GtkRBNode *node)
1379 {
1380   guint res;
1381
1382   if (node == tree->nil)
1383     return 0;
1384
1385   res =
1386     count_parity (tree, node->left) +
1387     count_parity (tree, node->right) +
1388     (guint)1 +
1389     (node->children ? count_parity (node->children, node->children->root) : 0);
1390
1391   res = res % (guint)2;
1392
1393   if (res != node->parity)
1394     g_print ("parity incorrect for node\n");
1395
1396   if (get_parity (node) != 1)
1397     g_error ("Node has incorrect parity %d", get_parity (node));
1398
1399   return res;
1400 }
1401
1402 static void
1403 _gtk_rbtree_test_height (GtkRBTree *tree,
1404                          GtkRBNode *node)
1405 {
1406   gint computed_offset = 0;
1407
1408   /* This whole test is sort of a useless truism. */
1409
1410   if (node->left != tree->nil)
1411     computed_offset += node->left->offset;
1412
1413   if (node->right != tree->nil)
1414     computed_offset += node->right->offset;
1415
1416   if (node->children && node->children->root != node->children->nil)
1417     computed_offset += node->children->root->offset;
1418
1419   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1420     g_error ("node has broken offset\n");
1421
1422   if (node->left != tree->nil)
1423     _gtk_rbtree_test_height (tree, node->left);
1424
1425   if (node->right != tree->nil)
1426     _gtk_rbtree_test_height (tree, node->right);
1427
1428   if (node->children && node->children->root != node->children->nil)
1429     _gtk_rbtree_test_height (node->children, node->children->root);
1430 }
1431
1432 void
1433 _gtk_rbtree_test (const gchar *where,
1434                   GtkRBTree   *tree)
1435 {
1436   GtkRBTree *tmp_tree;
1437
1438   /* Test the entire tree */
1439   tmp_tree = tree;
1440   while (tmp_tree->parent_tree)
1441     tmp_tree = tmp_tree->parent_tree;
1442
1443   g_print ("%s: whole tree offset is %d\n", where, tmp_tree->root->offset);
1444
1445   if (tmp_tree->root != tmp_tree->nil)
1446     {
1447       g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1448                  _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1449
1450
1451       _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1452
1453       g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
1454     }
1455 }
1456