pintos-os.org Git - pspp/blob - src/ui/gui/pspp-rb-tree.c

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