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