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                           gboolean   valid)
 578 {
 579   GtkRBNode *node;
 580   gboolean right = TRUE;
 581   GtkRBNode *tmp_node;
 582   GtkRBTree *tmp_tree;
 583
 584   if (gtk_debug_flags & GTK_DEBUG_TREE)
 585     _gtk_rbtree_test (G_STRLOC, tree);
 586
 587   if (current != NULL && current->right != tree->nil)
 588     {
 589       current = current->right;
 590       while (current->left != tree->nil)
 591         current = current->left;
 592       right = FALSE;
 593     }
 594
 595   /* setup new node */
 596   node = _gtk_rbnode_new (tree, height);
 597   node->parent = (current?current:tree->nil);
 598
 599   /* insert node in tree */
 600   if (current)
 601     {
 602       if (right)
 603         current->right = node;
 604       else
 605         current->left = node;
 606       tmp_node = node->parent;
 607       tmp_tree = tree;
 608     }
 609   else
 610     {
 611       tree->root = node;
 612       tmp_node = tree->parent_node;
 613       tmp_tree = tree->parent_tree;
 614     }
 615
 616   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 617     {
 618       /* We only want to propagate the count if we are in the tree we
 619        * started in. */
 620       if (tmp_tree == tree)
 621         tmp_node->count++;
 622
 623       tmp_node->parity += 1;
 624       tmp_node->offset += height;
 625       tmp_node = tmp_node->parent;
 626       if (tmp_node == tmp_tree->nil)
 627         {
 628           tmp_node = tmp_tree->parent_node;
 629           tmp_tree = tmp_tree->parent_tree;
 630         }
 631     }
 632   _gtk_rbtree_insert_fixup (tree, node);
 633
 634   if (gtk_debug_flags & GTK_DEBUG_TREE)
 635     _gtk_rbtree_test (G_STRLOC, tree);
 636
 637   if (valid)
 638     _gtk_rbtree_node_mark_valid (tree, node);
 639   else
 640     _gtk_rbtree_node_mark_invalid (tree, node);
 641
 642   return node;
 643 }
 644
 645 GtkRBNode *
 646 _gtk_rbtree_insert_before (GtkRBTree *tree,
 647                            GtkRBNode *current,
 648                            gint       height,
 649                            gboolean   valid)
 650 {
 651   GtkRBNode *node;
 652   gboolean left = TRUE;
 653   GtkRBNode *tmp_node;
 654   GtkRBTree *tmp_tree;
 655
 656   if (gtk_debug_flags & GTK_DEBUG_TREE)
 657     _gtk_rbtree_test (G_STRLOC, tree);
 658
 659   if (current != NULL && current->left != tree->nil)
 660     {
 661       current = current->left;
 662       while (current->right != tree->nil)
 663         current = current->right;
 664       left = FALSE;
 665     }
 666
 667   /* setup new node */
 668   node = _gtk_rbnode_new (tree, height);
 669   node->parent = (current?current:tree->nil);
 670
 671   /* insert node in tree */
 672   if (current)
 673     {
 674       if (left)
 675         current->left = node;
 676       else
 677         current->right = node;
 678       tmp_node = node->parent;
 679       tmp_tree = tree;
 680     }
 681   else
 682     {
 683       tree->root = node;
 684       tmp_node = tree->parent_node;
 685       tmp_tree = tree->parent_tree;
 686     }
 687
 688   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 689     {
 690       /* We only want to propagate the count if we are in the tree we
 691        * started in. */
 692       if (tmp_tree == tree)
 693         tmp_node->count++;
 694
 695       tmp_node->parity += 1;
 696       tmp_node->offset += height;
 697       tmp_node = tmp_node->parent;
 698       if (tmp_node == tmp_tree->nil)
 699         {
 700           tmp_node = tmp_tree->parent_node;
 701           tmp_tree = tmp_tree->parent_tree;
 702         }
 703     }
 704   _gtk_rbtree_insert_fixup (tree, node);
 705
 706   if (gtk_debug_flags & GTK_DEBUG_TREE)
 707     _gtk_rbtree_test (G_STRLOC, tree);
 708
 709   if (valid)
 710     _gtk_rbtree_node_mark_valid (tree, node);
 711   else
 712     _gtk_rbtree_node_mark_invalid (tree, node);
 713
 714   return node;
 715 }
 716
 717 GtkRBNode *
 718 _gtk_rbtree_find_count (GtkRBTree *tree,
 719                         gint       count)
 720 {
 721   GtkRBNode *node;
 722
 723   node = tree->root;
 724   while (node != tree->nil && (node->left->count + 1 != count))
 725     {
 726       if (node->left->count >= count)
 727         node = node->left;
 728       else
 729         {
 730           count -= (node->left->count + 1);
 731           node = node->right;
 732         }
 733     }
 734   if (node == tree->nil)
 735     return NULL;
 736   return node;
 737 }
 738
 739 void
 740 _gtk_rbtree_node_set_height (GtkRBTree *tree,
 741                              GtkRBNode *node,
 742                              gint       height)
 743 {
 744   gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
 745   GtkRBNode *tmp_node = node;
 746   GtkRBTree *tmp_tree = tree;
 747
 748   if (diff == 0)
 749     return;
 750
 751   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
 752     {
 753       tmp_node->offset += diff;
 754       tmp_node = tmp_node->parent;
 755       if (tmp_node == tmp_tree->nil)
 756         {
 757           tmp_node = tmp_tree->parent_node;
 758           tmp_tree = tmp_tree->parent_tree;
 759         }
 760     }
 761 }
 762
 763 void
 764 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
 765                                GtkRBNode *node)
 766 {
 767   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
 768     return;
 769
 770   GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
 771   do
 772     {
 773       if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
 774         return;
 775       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 776       node = node->parent;
 777       if (node == NULL)
 778         {
 779           node = tree->parent_node;
 780           tree = tree->parent_tree;
 781         }
 782     }
 783   while (node);
 784 }
 785
 786 void
 787 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 788                              GtkRBNode *node)
 789 {
 790   if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
 791       (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))
 792     return;
 793
 794   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
 795   GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 796
 797   do
 798     {
 799       if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||
 800           (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||
 801           (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 802           (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 803           (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
 804         return;
 805
 806       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 807       node = node->parent;
 808       if (node == NULL)
 809         {
 810           node = tree->parent_node;
 811           tree = tree->parent_tree;
 812         }
 813     }
 814   while (node);
 815 }
 816
 817
 818 /* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
 819  */
 820 void
 821 _gtk_rbtree_column_invalid (GtkRBTree *tree)
 822 {
 823   GtkRBNode *node;
 824
 825   if (tree == NULL)
 826     return;
 827   node = tree->root;
 828   g_assert (node);
 829
 830   while (node->left != tree->nil)
 831     node = node->left;
 832
 833   do
 834     {
 835       if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))
 836         GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
 837       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 838
 839       if (node->children)
 840         _gtk_rbtree_column_invalid (node->children);
 841     }
 842   while ((node = _gtk_rbtree_next (tree, node)) != NULL);
 843 }
 844
 845 typedef struct _GtkRBReorder
 846 {
 847   GtkRBTree *children;
 848   gint height;
 849   gint flags;
 850   gint order;
 851   gint invert_order;
 852   gint parity;
 853 } GtkRBReorder;
 854
 855 static int
 856 gtk_rbtree_reorder_sort_func (gconstpointer a,
 857                               gconstpointer b)
 858 {
 859   return ((GtkRBReorder *) a)->order > ((GtkRBReorder *) b)->order;
 860 }
 861
 862 static int
 863 gtk_rbtree_reorder_invert_func (gconstpointer a,
 864                                 gconstpointer b)
 865 {
 866   return ((GtkRBReorder *) a)->invert_order > ((GtkRBReorder *) b)->invert_order;
 867 }
 868
 869 static void
 870 gtk_rbtree_reorder_fixup (GtkRBTree *tree,
 871                           GtkRBNode *node)
 872 {
 873   if (node == tree->nil)
 874     return;
 875
 876   node->parity = 1;
 877
 878   if (node->left != tree->nil)
 879     {
 880       gtk_rbtree_reorder_fixup (tree, node->left);
 881       node->offset += node->left->offset;
 882       node->parity += node->left->parity;
 883     }
 884   if (node->right != tree->nil)
 885     {
 886       gtk_rbtree_reorder_fixup (tree, node->right);
 887       node->offset += node->right->offset;
 888       node->parity += node->right->parity;
 889     }
 890
 891   if (node->children)
 892     {
 893       node->offset += node->children->root->offset;
 894       node->parity += node->children->root->parity;
 895     }
 896
 897   if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
 898       (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 899       (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
 900       (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
 901     GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 902   else
 903     GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
 904 }
 905
 906 /* It basically pulls everything out of the tree, rearranges it, and puts it
 907  * back together.  Our strategy is to keep the old RBTree intact, and just
 908  * rearrange the contents.  When that is done, we go through and update the
 909  * heights.  There is probably a more elegant way to write this function.  If
 910  * anyone wants to spend the time writing it, patches will be accepted.
 911  */
 912 void
 913 _gtk_rbtree_reorder (GtkRBTree *tree,
 914                      gint      *new_order,
 915                      gint       length)
 916 {
 917   GtkRBReorder reorder;
 918   GArray *array;
 919   GtkRBNode *node;
 920   gint i;
 921
 922   g_return_if_fail (tree != NULL);
 923   g_return_if_fail (length > 0);
 924   g_return_if_fail (tree->root->count == length);
 925
 926   /* Sort the trees values in the new tree. */
 927   array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
 928   for (i = 0; i < length; i++)
 929     {
 930       reorder.order = new_order[i];
 931       reorder.invert_order = i;
 932       g_array_append_val (array, reorder);
 933     }
 934
 935   g_array_sort(array, gtk_rbtree_reorder_sort_func);
 936
 937   /* rewind node*/
 938   node = tree->root;
 939   while (node && node->left != tree->nil)
 940     node = node->left;
 941
 942   for (i = 0; i < length; i++)
 943     {
 944       g_assert (node != tree->nil);
 945       g_array_index (array, GtkRBReorder, i).children = node->children;
 946       g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
 947       g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
 948
 949       node = _gtk_rbtree_next (tree, node);
 950     }
 951
 952   g_array_sort (array, gtk_rbtree_reorder_invert_func);
 953
 954   /* rewind node*/
 955   node = tree->root;
 956   while (node && node->left != tree->nil)
 957     node = node->left;
 958
 959   /* Go through the tree and change the values to the new ones. */
 960   for (i = 0; i < length; i++)
 961     {
 962       reorder = g_array_index (array, GtkRBReorder, i);
 963       node->children = reorder.children;
 964       if (node->children)
 965         node->children->parent_node = node;
 966       node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
 967       /* We temporarily set the height to this. */
 968       node->offset = reorder.height;
 969       node = _gtk_rbtree_next (tree, node);
 970     }
 971   gtk_rbtree_reorder_fixup (tree, tree->root);
 972 }
 973
 974
 975 gint
 976 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
 977                               GtkRBNode *node)
 978 {
 979   GtkRBNode *last;
 980   gint retval;
 981
 982   g_assert (node);
 983   g_assert (node->left);
 984
 985   retval = node->left->offset;
 986
 987   while (tree && node && node != tree->nil)
 988     {
 989       last = node;
 990       node = node->parent;
 991
 992       /* Add left branch, plus children, iff we came from the right */
 993       if (node->right == last)
 994         retval += node->offset - node->right->offset;
 995
 996       if (node == tree->nil)
 997         {
 998           node = tree->parent_node;
 999           tree = tree->parent_tree;
1000
1001           /* Add the parent node, plus the left branch. */
1002           if (node)
1003             retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
1004         }
1005     }
1006   return retval;
1007 }
1008
1009 gint
1010 _gtk_rbtree_node_find_parity (GtkRBTree *tree,
1011                               GtkRBNode *node)
1012 {
1013   GtkRBNode *last;
1014   gint retval;
1015
1016   g_assert (node);
1017   g_assert (node->left);
1018
1019   retval = node->left->parity;
1020
1021   while (tree && node && node != tree->nil)
1022     {
1023       last = node;
1024       node = node->parent;
1025
1026       /* Add left branch, plus children, iff we came from the right */
1027       if (node->right == last)
1028         retval += node->parity - node->right->parity;
1029
1030       if (node == tree->nil)
1031         {
1032           node = tree->parent_node;
1033           tree = tree->parent_tree;
1034
1035           /* Add the parent node, plus the left branch. */
1036           if (node)
1037             retval += node->left->parity + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
1038         }
1039     }
1040
1041   return retval % 2;
1042 }
1043
1044 gint
1045 _gtk_rbtree_real_find_offset (GtkRBTree  *tree,
1046                               gint        height,
1047                               GtkRBTree **new_tree,
1048                               GtkRBNode **new_node)
1049 {
1050   GtkRBNode *tmp_node;
1051
1052   g_assert (tree);
1053
1054   if (height < 0)
1055     {
1056       *new_tree = NULL;
1057       *new_node = NULL;
1058
1059       return 0;
1060     }
1061
1062
1063   tmp_node = tree->root;
1064   while (tmp_node != tree->nil &&
1065          (tmp_node->left->offset > height ||
1066           (tmp_node->offset - tmp_node->right->offset) < height))
1067     {
1068       if (tmp_node->left->offset > height)
1069         tmp_node = tmp_node->left;
1070       else
1071         {
1072           height -= (tmp_node->offset - tmp_node->right->offset);
1073           tmp_node = tmp_node->right;
1074         }
1075     }
1076   if (tmp_node == tree->nil)
1077     {
1078       *new_tree = NULL;
1079       *new_node = NULL;
1080       return 0;
1081     }
1082   if (tmp_node->children)
1083     {
1084       if ((tmp_node->offset -
1085            tmp_node->right->offset -
1086            tmp_node->children->root->offset) > height)
1087         {
1088           *new_tree = tree;
1089           *new_node = tmp_node;
1090           return (height - tmp_node->left->offset);
1091         }
1092       return _gtk_rbtree_real_find_offset (tmp_node->children,
1093                                            height - tmp_node->left->offset -
1094                                            (tmp_node->offset -
1095                                             tmp_node->left->offset -
1096                                             tmp_node->right->offset -
1097                                             tmp_node->children->root->offset),
1098                                            new_tree,
1099                                            new_node);
1100     }
1101   *new_tree = tree;
1102   *new_node = tmp_node;
1103   return (height - tmp_node->left->offset);
1104 }
1105
1106 gint
1107 _gtk_rbtree_find_offset (GtkRBTree  *tree,
1108                               gint        height,
1109                               GtkRBTree **new_tree,
1110                               GtkRBNode **new_node)
1111 {
1112   GtkRBNode *tmp_node;
1113
1114   g_assert (tree);
1115
1116   if ((height < 0) ||
1117       (height >= tree->root->offset))
1118     {
1119       *new_tree = NULL;
1120       *new_node = NULL;
1121
1122       return 0;
1123     }
1124   _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1125 }
1126
1127 void
1128 _gtk_rbtree_remove_node (GtkRBTree *tree,
1129                          GtkRBNode *node)
1130 {
1131   GtkRBNode *x, *y;
1132   GtkRBTree *tmp_tree;
1133   GtkRBNode *tmp_node;
1134   gint node_height;
1135   gint y_height;
1136
1137   g_return_if_fail (tree != NULL);
1138   g_return_if_fail (node != NULL);
1139
1140   /* make sure we're deleting a node that's actually in the tree */
1141   for (x = node; x->parent != tree->nil; x = x->parent)
1142     ;
1143   g_return_if_fail (x == tree->root);
1144
1145   if (gtk_debug_flags & GTK_DEBUG_TREE)
1146     _gtk_rbtree_test (G_STRLOC, tree);
1147
1148   if (node->left == tree->nil || node->right == tree->nil)
1149     {
1150       y = node;
1151     }
1152   else
1153     {
1154       y = node->right;
1155
1156       while (y->left != tree->nil)
1157         y = y->left;
1158     }
1159
1160   /* adjust count only beneath tree */
1161   for (x = y; x != tree->nil; x = x->parent)
1162     x->count--;
1163
1164   /*   y->count = node->count; */
1165
1166   /* offsets and parity adjust all the way up through parent trees */
1167   y_height = GTK_RBNODE_GET_HEIGHT (y);
1168   node_height = GTK_RBNODE_GET_HEIGHT (node) + (node->children?node->children->root->offset:0);
1169
1170   /* Do this twice for code clarities sake. */
1171   tmp_tree = tree;
1172   tmp_node = y;
1173   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1174     {
1175       tmp_node->offset -= (y_height + (y->children?y->children->root->offset:0));
1176       tmp_node->parity -= (1 + (y->children?y->children->root->parity:0));
1177
1178       tmp_node = tmp_node->parent;
1179       if (tmp_node == tmp_tree->nil)
1180         {
1181           tmp_node = tmp_tree->parent_node;
1182           tmp_tree = tmp_tree->parent_tree;
1183         }
1184     }
1185
1186   /* x is y's only child */
1187   if (y->left != tree->nil)
1188     x = y->left;
1189   else
1190     x = y->right;
1191
1192   /* remove y from the parent chain */
1193   x->parent = y->parent;
1194   if (y->parent != tree->nil)
1195     if (y == y->parent->left)
1196       y->parent->left = x;
1197     else
1198       y->parent->right = x;
1199   else
1200     tree->root = x;
1201
1202   if (y != node)
1203     {
1204       gint diff;
1205
1206       /* Copy the node over */
1207       if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1208         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
1209       else
1210         node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
1211       node->children = y->children;
1212
1213       /* We want to see how different our height is from the previous node.
1214        * To do this, we compare our current height with our supposed height.
1215        */
1216       diff = y_height - GTK_RBNODE_GET_HEIGHT (node);
1217       if (diff != 0)
1218         {
1219           tmp_tree = tree;
1220           tmp_node = node;
1221
1222           while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1223             {
1224               tmp_node->offset += diff;
1225               tmp_node = tmp_node->parent;
1226               if (tmp_node == tmp_tree->nil)
1227                 {
1228                   tmp_node = tmp_tree->parent_node;
1229                   tmp_tree = tmp_tree->parent_tree;
1230                 }
1231             }
1232         }
1233     }
1234
1235   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1236     _gtk_rbtree_remove_node_fixup (tree, x);
1237
1238   _gtk_rbnode_free (y);
1239
1240   if (gtk_debug_flags & GTK_DEBUG_TREE)
1241     _gtk_rbtree_test (G_STRLOC, tree);
1242 }
1243
1244 GtkRBNode *
1245 _gtk_rbtree_next (GtkRBTree *tree,
1246                   GtkRBNode *node)
1247 {
1248   g_return_val_if_fail (tree != NULL, NULL);
1249   g_return_val_if_fail (node != NULL, NULL);
1250
1251   /* Case 1: the node's below us. */
1252   if (node->right != tree->nil)
1253     {
1254       node = node->right;
1255       while (node->left != tree->nil)
1256         node = node->left;
1257       return node;
1258     }
1259
1260   /* Case 2: it's an ancestor */
1261   while (node->parent != tree->nil)
1262     {
1263       if (node->parent->right == node)
1264         node = node->parent;
1265       else
1266         return (node->parent);
1267     }
1268
1269   /* Case 3: There is no next node */
1270   return NULL;
1271 }
1272
1273 GtkRBNode *
1274 _gtk_rbtree_prev (GtkRBTree *tree,
1275                   GtkRBNode *node)
1276 {
1277   g_return_val_if_fail (tree != NULL, NULL);
1278   g_return_val_if_fail (node != NULL, NULL);
1279
1280   /* Case 1: the node's below us. */
1281   if (node->left != tree->nil)
1282     {
1283       node = node->left;
1284       while (node->right != tree->nil)
1285         node = node->right;
1286       return node;
1287     }
1288
1289   /* Case 2: it's an ancestor */
1290   while (node->parent != tree->nil)
1291     {
1292       if (node->parent->left == node)
1293         node = node->parent;
1294       else
1295         return (node->parent);
1296     }
1297
1298   /* Case 3: There is no next node */
1299   return NULL;
1300 }
1301
1302 void
1303 _gtk_rbtree_next_full (GtkRBTree  *tree,
1304                        GtkRBNode  *node,
1305                        GtkRBTree **new_tree,
1306                        GtkRBNode **new_node)
1307 {
1308   g_return_if_fail (tree != NULL);
1309   g_return_if_fail (node != NULL);
1310   g_return_if_fail (new_tree != NULL);
1311   g_return_if_fail (new_node != NULL);
1312
1313   if (node->children)
1314     {
1315       *new_tree = node->children;
1316       *new_node = (*new_tree)->root;
1317       while ((*new_node)->left != (*new_tree)->nil)
1318         *new_node = (*new_node)->left;
1319       return;
1320     }
1321
1322   *new_tree = tree;
1323   *new_node = _gtk_rbtree_next (tree, node);
1324
1325   while ((*new_node == NULL) &&
1326          (*new_tree != NULL))
1327     {
1328       *new_node = (*new_tree)->parent_node;
1329       *new_tree = (*new_tree)->parent_tree;
1330       if (*new_tree)
1331         *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1332     }
1333 }
1334
1335 void
1336 _gtk_rbtree_prev_full (GtkRBTree  *tree,
1337                        GtkRBNode  *node,
1338                        GtkRBTree **new_tree,
1339                        GtkRBNode **new_node)
1340 {
1341   g_return_if_fail (tree != NULL);
1342   g_return_if_fail (node != NULL);
1343   g_return_if_fail (new_tree != NULL);
1344   g_return_if_fail (new_node != NULL);
1345
1346   *new_tree = tree;
1347   *new_node = _gtk_rbtree_prev (tree, node);
1348
1349   if (*new_node == NULL)
1350     {
1351       *new_node = (*new_tree)->parent_node;
1352       *new_tree = (*new_tree)->parent_tree;
1353     }
1354   else
1355     {
1356       while ((*new_node)->children)
1357         {
1358           *new_tree = (*new_node)->children;
1359           *new_node = (*new_tree)->root;
1360           while ((*new_node)->right != (*new_tree)->nil)
1361             *new_node = (*new_node)->right;
1362         }
1363     }
1364 }
1365
1366 gint
1367 _gtk_rbtree_get_depth (GtkRBTree *tree)
1368 {
1369   GtkRBTree *tmp_tree;
1370   gint depth = 0;
1371
1372   tmp_tree = tree->parent_tree;
1373   while (tmp_tree)
1374     {
1375       ++depth;
1376       tmp_tree = tmp_tree->parent_tree;
1377     }
1378
1379   return depth;
1380 }
1381
1382 static void
1383 _gtk_rbtree_traverse_pre_order (GtkRBTree             *tree,
1384                                 GtkRBNode             *node,
1385                                 GtkRBTreeTraverseFunc  func,
1386                                 gpointer               data)
1387 {
1388   if (node == tree->nil)
1389     return;
1390
1391   (* func) (tree, node, data);
1392   _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1393   _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1394 }
1395
1396 static void
1397 _gtk_rbtree_traverse_post_order (GtkRBTree             *tree,
1398                                  GtkRBNode             *node,
1399                                  GtkRBTreeTraverseFunc  func,
1400                                  gpointer               data)
1401 {
1402   if (node == tree->nil)
1403     return;
1404
1405   _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1406   _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1407   (* func) (tree, node, data);
1408 }
1409
1410 void
1411 _gtk_rbtree_traverse (GtkRBTree             *tree,
1412                       GtkRBNode             *node,
1413                       GTraverseType          order,
1414                       GtkRBTreeTraverseFunc  func,
1415                       gpointer               data)
1416 {
1417   g_return_if_fail (tree != NULL);
1418   g_return_if_fail (node != NULL);
1419   g_return_if_fail (func != NULL);
1420   g_return_if_fail (order <= G_LEVEL_ORDER);
1421
1422   switch (order)
1423     {
1424     case G_PRE_ORDER:
1425       _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1426       break;
1427     case G_POST_ORDER:
1428       _gtk_rbtree_traverse_post_order (tree, node, func, data);
1429       break;
1430     case G_IN_ORDER:
1431     case G_LEVEL_ORDER:
1432     default:
1433       g_warning ("unsupported traversal order.");
1434       break;
1435     }
1436 }
1437
1438 static gint
1439 _count_nodes (GtkRBTree *tree,
1440               GtkRBNode *node)
1441 {
1442   gint res;
1443   if (node == tree->nil)
1444     return 0;
1445
1446   g_assert (node->left);
1447   g_assert (node->right);
1448
1449   res = (_count_nodes (tree, node->left) +
1450          _count_nodes (tree, node->right) + 1);
1451
1452   if (res != node->count)
1453     g_print ("Tree failed\n");
1454   return res;
1455 }
1456
1457 static guint
1458 get_parity (GtkRBNode *node)
1459 {
1460   guint child_total = 0;
1461   guint rem;
1462
1463   /* The parity of a node is node->parity minus
1464    * the parity of left, right, and children.
1465    *
1466    * This is equivalent to saying that if left, right, children
1467    * sum to 0 parity, then node->parity is the parity of node,
1468    * and if left, right, children are odd parity, then
1469    * node->parity is the reverse of the node's parity.
1470    */
1471
1472   child_total += (guint) node->left->parity;
1473   child_total += (guint) node->right->parity;
1474
1475   if (node->children)
1476     child_total += (guint) node->children->root->parity;
1477
1478   rem = child_total % 2;
1479
1480   if (rem == 0)
1481     return node->parity;
1482   else
1483     return !node->parity;
1484 }
1485
1486 static guint
1487 count_parity (GtkRBTree *tree,
1488               GtkRBNode *node)
1489 {
1490   guint res;
1491
1492   if (node == tree->nil)
1493     return 0;
1494
1495   res =
1496     count_parity (tree, node->left) +
1497     count_parity (tree, node->right) +
1498     (guint)1 +
1499     (node->children ? count_parity (node->children, node->children->root) : 0);
1500
1501   res = res % (guint)2;
1502
1503   if (res != node->parity)
1504     g_print ("parity incorrect for node\n");
1505
1506   if (get_parity (node) != 1)
1507     g_error ("Node has incorrect parity %d", get_parity (node));
1508
1509   return res;
1510 }
1511
1512 static void
1513 _gtk_rbtree_test_height (GtkRBTree *tree,
1514                          GtkRBNode *node)
1515 {
1516   gint computed_offset = 0;
1517
1518   /* This whole test is sort of a useless truism. */
1519
1520   if (node->left != tree->nil)
1521     computed_offset += node->left->offset;
1522
1523   if (node->right != tree->nil)
1524     computed_offset += node->right->offset;
1525
1526   if (node->children && node->children->root != node->children->nil)
1527     computed_offset += node->children->root->offset;
1528
1529   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1530     g_error ("node has broken offset\n");
1531
1532   if (node->left != tree->nil)
1533     _gtk_rbtree_test_height (tree, node->left);
1534
1535   if (node->right != tree->nil)
1536     _gtk_rbtree_test_height (tree, node->right);
1537
1538   if (node->children && node->children->root != node->children->nil)
1539     _gtk_rbtree_test_height (node->children, node->children->root);
1540 }
1541
1542 void
1543 _gtk_rbtree_test (const gchar *where,
1544                   GtkRBTree   *tree)
1545 {
1546   GtkRBTree *tmp_tree;
1547
1548   /* Test the entire tree */
1549   tmp_tree = tree;
1550   while (tmp_tree->parent_tree)
1551     tmp_tree = tmp_tree->parent_tree;
1552
1553   g_print ("%s: whole tree offset is %d\n", where, tmp_tree->root->offset);
1554
1555   if (tmp_tree->root != tmp_tree->nil)
1556     {
1557       g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1558                  _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1559
1560
1561       _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1562
1563       g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
1564     }
1565 }
1566