/* gtkrbtree.c

 * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Library General Public

 * License as published by the Free Software Foundation; either

 * version 2 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Library General Public License for more details.

 *

 * You should have received a copy of the GNU Library General Public

 * License along with this library; if not, write to the

 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

 * Boston, MA 02111-1307, USA.

 */

#include "config.h"

#include "gtkrbtree.h"

#include "gtkdebug.h"

#include "gtkalias.h"

static GtkRBNode * _gtk_rbnode_new                (GtkRBTree  *tree,

						   gint        height);

static void        _gtk_rbnode_free               (GtkRBNode  *node);

static void        _gtk_rbnode_rotate_left        (GtkRBTree  *tree,

						   GtkRBNode  *node);

static void        _gtk_rbnode_rotate_right       (GtkRBTree  *tree,

						   GtkRBNode  *node);

static void        _gtk_rbtree_insert_fixup       (GtkRBTree  *tree,

						   GtkRBNode  *node);

static void        _gtk_rbtree_remove_node_fixup  (GtkRBTree  *tree,

						   GtkRBNode  *node);

static inline void _fixup_validation              (GtkRBTree  *tree,

						   GtkRBNode  *node);

static inline void _fixup_parity                  (GtkRBTree  *tree,

						   GtkRBNode  *node);

static GtkRBNode *

_gtk_rbnode_new (GtkRBTree *tree,

		 gint       height)

{

  GtkRBNode *node = g_slice_new (GtkRBNode);

  node->left = tree->nil;

  node->right = tree->nil;

  node->parent = tree->nil;

  node->flags = GTK_RBNODE_RED;

  node->parity = 1;

  node->count = 1;

  node->children = NULL;

  node->offset = height;

  return node;

}

static void

_gtk_rbnode_free (GtkRBNode *node)

{

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    {

      node->left = (gpointer) 0xdeadbeef;

      node->right = (gpointer) 0xdeadbeef;

      node->parent = (gpointer) 0xdeadbeef;

      node->offset = 56789;

      node->count = 56789;

      node->flags = 0;

    }

  g_slice_free (GtkRBNode, node);

}

static void

_gtk_rbnode_rotate_left (GtkRBTree *tree,

			 GtkRBNode *node)

{

  gint node_height, right_height;

  GtkRBNode *right = node->right;

  g_return_if_fail (node != tree->nil);

  node_height = node->offset -

    (node->left?node->left->offset:0) -

    (node->right?node->right->offset:0) -

    (node->children?node->children->root->offset:0);

  right_height = right->offset -

    (right->left?right->left->offset:0) -

    (right->right?right->right->offset:0) -

    (right->children?right->children->root->offset:0);

  node->right = right->left;

  if (right->left != tree->nil)

    right->left->parent = node;

  if (right != tree->nil)

    right->parent = node->parent;

  if (node->parent != tree->nil)

    {

      if (node == node->parent->left)

	node->parent->left = right;

      else

	node->parent->right = right;

    } else {

      tree->root = right;

    }

  right->left = node;

  if (node != tree->nil)

    node->parent = right;

  node->count = 1 + (node->left?node->left->count:0) +

    (node->right?node->right->count:0);

  right->count = 1 + (right->left?right->left->count:0) +

    (right->right?right->right->count:0);

  node->offset = node_height +

    (node->left?node->left->offset:0) +

    (node->right?node->right->offset:0) +

    (node->children?node->children->root->offset:0);

  right->offset = right_height +

    (right->left?right->left->offset:0) +

    (right->right?right->right->offset:0) +

    (right->children?right->children->root->offset:0);

  _fixup_validation (tree, node);

  _fixup_validation (tree, right);

  _fixup_parity (tree, node);

  _fixup_parity (tree, right);

}

static void

_gtk_rbnode_rotate_right (GtkRBTree *tree,

			  GtkRBNode *node)

{

  gint node_height, left_height;

  GtkRBNode *left = node->left;

  g_return_if_fail (node != tree->nil);

  node_height = node->offset -

    (node->left?node->left->offset:0) -

    (node->right?node->right->offset:0) -

    (node->children?node->children->root->offset:0);

  left_height = left->offset -

    (left->left?left->left->offset:0) -

    (left->right?left->right->offset:0) -

    (left->children?left->children->root->offset:0);

  node->left = left->right;

  if (left->right != tree->nil)

    left->right->parent = node;

  if (left != tree->nil)

    left->parent = node->parent;

  if (node->parent != tree->nil)

    {

      if (node == node->parent->right)

	node->parent->right = left;

      else

	node->parent->left = left;

    }

  else

    {

      tree->root = left;

    }

  /* link node and left */

  left->right = node;

  if (node != tree->nil)

    node->parent = left;

  node->count = 1 + (node->left?node->left->count:0) +

    (node->right?node->right->count:0);

  left->count = 1 + (left->left?left->left->count:0) +

    (left->right?left->right->count:0);

  node->offset = node_height +

    (node->left?node->left->offset:0) +

    (node->right?node->right->offset:0) +

    (node->children?node->children->root->offset:0);

  left->offset = left_height +

    (left->left?left->left->offset:0) +

    (left->right?left->right->offset:0) +

    (left->children?left->children->root->offset:0);

  _fixup_validation (tree, node);

  _fixup_validation (tree, left);

  _fixup_parity (tree, node);

  _fixup_parity (tree, left);

}

static void

_gtk_rbtree_insert_fixup (GtkRBTree *tree,

			  GtkRBNode *node)

{

  /* check Red-Black properties */

  while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)

    {

      /* we have a violation */

      if (node->parent == node->parent->parent->left)

	{

	  GtkRBNode *y = node->parent->parent->right;

	  if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)

	    {

				/* uncle is GTK_RBNODE_RED */

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);

	      node = node->parent->parent;

	    }

	  else

	    {

				/* uncle is GTK_RBNODE_BLACK */

	      if (node == node->parent->right)

		{

		  /* make node a left child */

		  node = node->parent;

		  _gtk_rbnode_rotate_left (tree, node);

		}

				/* recolor and rotate */

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);

	      _gtk_rbnode_rotate_right(tree, node->parent->parent);

	    }

	}

      else

	{

	  /* mirror image of above code */

	  GtkRBNode *y = node->parent->parent->left;

	  if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)

	    {

				/* uncle is GTK_RBNODE_RED */

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);

	      node = node->parent->parent;

	    }

	  else

	    {

				/* uncle is GTK_RBNODE_BLACK */

	      if (node == node->parent->left)

		{

		  node = node->parent;

		  _gtk_rbnode_rotate_right (tree, node);

		}

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);

	      _gtk_rbnode_rotate_left (tree, node->parent->parent);

	    }

	}

    }

  GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);

}

static void

_gtk_rbtree_remove_node_fixup (GtkRBTree *tree,

			       GtkRBNode *node)

{

  while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)

    {

      if (node == node->parent->left)

	{

	  GtkRBNode *w = node->parent->right;

	  if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)

	    {

	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);

	      _gtk_rbnode_rotate_left (tree, node->parent);

	      w = node->parent->right;

	    }

	  if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)

	    {

	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);

	      node = node->parent;

	    }

	  else

	    {

	      if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)

		{

		  GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);

		  GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);

		  _gtk_rbnode_rotate_right (tree, w);

		  w = node->parent->right;

		}

	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);

	      _gtk_rbnode_rotate_left (tree, node->parent);

	      node = tree->root;

	    }

	}

      else

	{

	  GtkRBNode *w = node->parent->left;

	  if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)

	    {

	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);

	      _gtk_rbnode_rotate_right (tree, node->parent);

	      w = node->parent->left;

	    }

	  if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)

	    {

	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);

	      node = node->parent;

	    }

	  else

	    {

	      if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)

		{

		  GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);

		  GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);

		  _gtk_rbnode_rotate_left (tree, w);

		  w = node->parent->left;

		}

	      GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));

	      GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);

	      GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);

	      _gtk_rbnode_rotate_right (tree, node->parent);

	      node = tree->root;

	    }

	}

    }

  GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);

}

GtkRBTree *

_gtk_rbtree_new (void)

{

  GtkRBTree *retval;

  retval = g_new (GtkRBTree, 1);

  retval->parent_tree = NULL;

  retval->parent_node = NULL;

  retval->nil = g_slice_new (GtkRBNode);

  retval->nil->left = NULL;

  retval->nil->right = NULL;

  retval->nil->parent = NULL;

  retval->nil->flags = GTK_RBNODE_BLACK;

  retval->nil->count = 0;

  retval->nil->offset = 0;

  retval->nil->parity = 0;

  retval->root = retval->nil;

  return retval;

}

static void

_gtk_rbtree_free_helper (GtkRBTree  *tree,

			 GtkRBNode  *node,

			 gpointer    data)

{

  if (node->children)

    _gtk_rbtree_free (node->children);

  _gtk_rbnode_free (node);

}

void

_gtk_rbtree_free (GtkRBTree *tree)

{

  _gtk_rbtree_traverse (tree,

			tree->root,

			G_POST_ORDER,

			_gtk_rbtree_free_helper,

			NULL);

  if (tree->parent_node &&

      tree->parent_node->children == tree)

    tree->parent_node->children = NULL;

  _gtk_rbnode_free (tree->nil);

  g_free (tree);

}

void

_gtk_rbtree_remove (GtkRBTree *tree)

{

  GtkRBTree *tmp_tree;

  GtkRBNode *tmp_node;

  gint height = tree->root->offset;

#ifdef G_ENABLE_DEBUG  

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    _gtk_rbtree_test (G_STRLOC, tree);

#endif

  tmp_tree = tree->parent_tree;

  tmp_node = tree->parent_node;

  /* ugly hack to make _fixup_validation work in the first iteration of the

   * loop below */

  GTK_RBNODE_UNSET_FLAG (tree->root, GTK_RBNODE_DESCENDANTS_INVALID);

  while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)

    {

      _fixup_validation (tmp_tree, tmp_node);

      tmp_node->offset -= height;

      /* If the removed tree was odd, flip all parents */

      if (tree->root->parity)

        tmp_node->parity = !tmp_node->parity;

      tmp_node = tmp_node->parent;

      if (tmp_node == tmp_tree->nil)

	{

	  tmp_node = tmp_tree->parent_node;

	  tmp_tree = tmp_tree->parent_tree;

	}

    }

  tmp_tree = tree->parent_tree;

  tmp_node = tree->parent_node;

  _gtk_rbtree_free (tree);

#ifdef G_ENABLE_DEBUG  

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    _gtk_rbtree_test (G_STRLOC, tmp_tree);

#endif

}

GtkRBNode *

_gtk_rbtree_insert_after (GtkRBTree *tree,

			  GtkRBNode *current,

			  gint       height,

			  gboolean   valid)

{

  GtkRBNode *node;

  gboolean right = TRUE;

  GtkRBNode *tmp_node;

  GtkRBTree *tmp_tree;  

#ifdef G_ENABLE_DEBUG  

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    {

      g_print ("\n\n_gtk_rbtree_insert_after: %p\n", current);

      _gtk_rbtree_debug_spew (tree);

      _gtk_rbtree_test (G_STRLOC, tree);

    }

#endif /* G_ENABLE_DEBUG */  

  if (current != NULL && current->right != tree->nil)

    {

      current = current->right;

      while (current->left != tree->nil)

	current = current->left;

      right = FALSE;

    }

  /* setup new node */

  node = _gtk_rbnode_new (tree, height);

  node->parent = (current?current:tree->nil);

  /* insert node in tree */

  if (current)

    {

      if (right)

	current->right = node;

      else

	current->left = node;

      tmp_node = node->parent;

      tmp_tree = tree;

    }

  else

    {

      tree->root = node;

      tmp_node = tree->parent_node;

      tmp_tree = tree->parent_tree;

    }

  while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)

    {

      /* We only want to propagate the count if we are in the tree we

       * started in. */

      if (tmp_tree == tree)

	tmp_node->count++;

      tmp_node->parity += 1;

      tmp_node->offset += height;

      tmp_node = tmp_node->parent;

      if (tmp_node == tmp_tree->nil)

	{

	  tmp_node = tmp_tree->parent_node;

	  tmp_tree = tmp_tree->parent_tree;

	}

    }

  if (valid)

    _gtk_rbtree_node_mark_valid (tree, node);

  else

    _gtk_rbtree_node_mark_invalid (tree, node);

  _gtk_rbtree_insert_fixup (tree, node);

#ifdef G_ENABLE_DEBUG  

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    {

      g_print ("_gtk_rbtree_insert_after finished...\n");

      _gtk_rbtree_debug_spew (tree);

      g_print ("\n\n");

      _gtk_rbtree_test (G_STRLOC, tree);

    }

#endif /* G_ENABLE_DEBUG */  

  return node;

}

GtkRBNode *

_gtk_rbtree_insert_before (GtkRBTree *tree,

			   GtkRBNode *current,

			   gint       height,

			   gboolean   valid)

{

  GtkRBNode *node;

  gboolean left = TRUE;

  GtkRBNode *tmp_node;

  GtkRBTree *tmp_tree;

#ifdef G_ENABLE_DEBUG  

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    {

      g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current);

      _gtk_rbtree_debug_spew (tree);

      _gtk_rbtree_test (G_STRLOC, tree);

    }

#endif /* G_ENABLE_DEBUG */

  if (current != NULL && current->left != tree->nil)

    {

      current = current->left;

      while (current->right != tree->nil)

	current = current->right;

      left = FALSE;

    }

  /* setup new node */

  node = _gtk_rbnode_new (tree, height);

  node->parent = (current?current:tree->nil);

  /* insert node in tree */

  if (current)

    {

      if (left)

	current->left = node;

      else

	current->right = node;

      tmp_node = node->parent;

      tmp_tree = tree;

    }

  else

    {

      tree->root = node;

      tmp_node = tree->parent_node;

      tmp_tree = tree->parent_tree;

    }

  while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)

    {

      /* We only want to propagate the count if we are in the tree we

       * started in. */

      if (tmp_tree == tree)

	tmp_node->count++;

      tmp_node->parity += 1;

      tmp_node->offset += height;

      tmp_node = tmp_node->parent;

      if (tmp_node == tmp_tree->nil)

	{

	  tmp_node = tmp_tree->parent_node;

	  tmp_tree = tmp_tree->parent_tree;

	}

    }

  if (valid)

    _gtk_rbtree_node_mark_valid (tree, node);

  else

    _gtk_rbtree_node_mark_invalid (tree, node);

  _gtk_rbtree_insert_fixup (tree, node);

#ifdef G_ENABLE_DEBUG  

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    {

      g_print ("_gtk_rbtree_insert_before finished...\n");

      _gtk_rbtree_debug_spew (tree);

      g_print ("\n\n");

      _gtk_rbtree_test (G_STRLOC, tree);

    }

#endif /* G_ENABLE_DEBUG */

  return node;

}

GtkRBNode *

_gtk_rbtree_find_count (GtkRBTree *tree,

			gint       count)

{

  GtkRBNode *node;

  node = tree->root;

  while (node != tree->nil && (node->left->count + 1 != count))

    {

      if (node->left->count >= count)

	node = node->left;

      else

	{

	  count -= (node->left->count + 1);

	  node = node->right;

	}

    }

  if (node == tree->nil)

    return NULL;

  return node;

}

void

_gtk_rbtree_node_set_height (GtkRBTree *tree,

			     GtkRBNode *node,

			     gint       height)

{

  gint diff = height - GTK_RBNODE_GET_HEIGHT (node);

  GtkRBNode *tmp_node = node;

  GtkRBTree *tmp_tree = tree;

  if (diff == 0)

    return;

  while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)

    {

      tmp_node->offset += diff;

      tmp_node = tmp_node->parent;

      if (tmp_node == tmp_tree->nil)

	{

	  tmp_node = tmp_tree->parent_node;

	  tmp_tree = tmp_tree->parent_tree;

	}

    }

#ifdef G_ENABLE_DEBUG  

  if (gtk_debug_flags & GTK_DEBUG_TREE)

    _gtk_rbtree_test (G_STRLOC, tree);

#endif

}

void

_gtk_rbtree_node_mark_invalid (GtkRBTree *tree,

			       GtkRBNode *node)

{

  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))

    return;

  GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);

  do

    {

      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))

	return;

      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);

      node = node->parent;

      if (node == tree->nil)

	{

	  node = tree->parent_node;

	  tree = tree->parent_tree;

	}

    }

  while (node);

}

#if 0

/* Draconian version. */

void

_gtk_rbtree_node_mark_invalid (GtkRBTree *tree,

			       GtkRBNode *node)

{

  GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);

  do

    {

      _fixup_validation (tree, node);

      node = node->parent;

      if (node == tree->nil)

	{

	  node = tree->parent_node;

	  tree = tree->parent_tree;

	}

    }

  while (node);

}

#endif

void

_gtk_rbtree_node_mark_valid (GtkRBTree *tree,

			     GtkRBNode *node)

{

  if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&

      (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))

    return;

  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);

  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);

  do

    {

      if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||

	  (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||

	  (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||

	  (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||

	  (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))

	return;

      GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);

      node = node->parent;

      if (node == tree->nil)

	{

	  node = tree->parent_node;

	  tree = tree->parent_tree;

	}

    }

  while (node);

}

#if 0

/* Draconian version */

void

_gtk_rbtree_node_mark_valid (GtkRBTree *tree,

			     GtkRBNode *node)

{

  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);

  GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);

  do

    {

      _fixup_validation (tree, node);

      node = node->parent;

      if (node == tree->nil)

	{

	  node = tree->parent_node;

	  tree = tree->parent_tree;

	}

    }

  while (node);

}

#endif

/* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.

 */

void

_gtk_rbtree_column_invalid (GtkRBTree *tree)

{

  GtkRBNode *node;

  if (tree == NULL)

    return;

  node = tree->root;

  g_assert (node);

  while (node->left != tree->nil)

    node = node->left;

  do

    {

      if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))

	GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);

      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);

      if (node->children)

	_gtk_rbtree_column_invalid (node->children);

    }

  while ((node = _gtk_rbtree_next (tree, node)) != NULL);

}

void

_gtk_rbtree_mark_invalid (GtkRBTree *tree)

{

  GtkRBNode *node;

  if (tree == NULL)

    return;

  node = tree->root;

  g_assert (node);

  while (node->left != tree->nil)

    node = node->left;

  do

    {

      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);

      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);

      if (node->children)

	_gtk_rbtree_mark_invalid (node->children);

    }

  while ((node = _gtk_rbtree_next (tree, node)) != NULL);

}

void

_gtk_rbtree_set_fixed_height (GtkRBTree *tree,

			      gint       height,

			      gboolean   mark_valid)

{

  GtkRBNode *node;

  if (tree == NULL)

    return;

  node = tree->root;

  g_assert (node);

  while (node->left != tree->nil)

    node = node->left;

  do

    {

      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))

        {

	  _gtk_rbtree_node_set_height (tree, node, height);

	  if (mark_valid)

	    _gtk_rbtree_node_mark_valid (tree, node);

	}

      if (node->children)

	_gtk_rbtree_set_fixed_height (node->children, height, mark_valid);

    }

  while ((node = _gtk_rbtree_next (tree, node)) != NULL);

}

typedef struct _GtkRBReorder

{

  GtkRBTree *children;

  gint height;

  gint flags;

  gint order;

  gint invert_order;

  gint parity;

} GtkRBReorder;

static int

gtk_rbtree_reorder_sort_func (gconstpointer a,

			      gconstpointer b)

{

  return ((GtkRBReorder *) a)->order - ((GtkRBReorder *) b)->order;

}

static int

gtk_rbtree_reorder_invert_func (gconstpointer a,

				gconstpointer b)

{

  return ((GtkRBReorder *) a)->invert_order - ((GtkRBReorder *) b)->invert_order;

}

static void

gtk_rbtree_reorder_fixup (GtkRBTree *tree,

			  GtkRBNode *node)

{

  if (node == tree->nil)

    return;

  node->parity = 1;

  if (node->left != tree->nil)

    {

      gtk_rbtree_reorder_fixup (tree, node->left);

      node->offset += node->left->offset;

      node->parity += node->left->parity;

    }

  if (node->right != tree->nil)

    {

      gtk_rbtree_reorder_fixup (tree, node->right);

      node->offset += node->right->offset;

      node->parity += node->right->parity;

    }

  if (node->children)

    {

      node->offset += node->children->root->offset;

      node->parity += node->children->root->parity;

    }

  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||

      (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||