Pileus Git - ~andy/gtk/blob - gtk/gtkrbtree.c

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