* 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.
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
*/
#include "config.h"
{
GtkRBNode *node = g_slice_new (GtkRBNode);
- node->left = tree->nil;
- node->right = tree->nil;
- node->parent = tree->nil;
+ node->left = (GtkRBNode *) &nil;
+ node->right = (GtkRBNode *) &nil;
+ node->parent = (GtkRBNode *) &nil;
node->flags = GTK_RBNODE_RED;
node->total_count = 1;
node->count = 1;
GtkRBNode *node)
{
gint node_height, right_height;
- GtkRBNode *right = node->right;
+ GtkRBNode *right;
g_return_if_fail (!_gtk_rbtree_is_nil (node));
+ g_return_if_fail (!_gtk_rbtree_is_nil (node->right));
- 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);
+ right = node->right;
+
+ node_height = GTK_RBNODE_GET_HEIGHT (node);
+ right_height = GTK_RBNODE_GET_HEIGHT (right);
node->right = right->left;
if (!_gtk_rbtree_is_nil (right->left))
right->left->parent = node;
- if (!_gtk_rbtree_is_nil (right))
- right->parent = node->parent;
+ right->parent = node->parent;
if (!_gtk_rbtree_is_nil (node->parent))
{
if (node == node->parent->left)
}
right->left = node;
- if (!_gtk_rbtree_is_nil (node))
- 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);
+ node->parent = right;
+
+ node->count = 1 + node->left->count + node->right->count;
+ right->count = 1 + right->left->count + right->right->count;
+
+ node->offset = node_height + node->left->offset + node->right->offset +
+ (node->children ? node->children->root->offset : 0);
+ right->offset = right_height + right->left->offset + right->right->offset +
+ (right->children ? right->children->root->offset : 0);
_fixup_validation (tree, node);
_fixup_validation (tree, right);
GtkRBNode *node)
{
gint node_height, left_height;
- GtkRBNode *left = node->left;
+ GtkRBNode *left;
g_return_if_fail (!_gtk_rbtree_is_nil (node));
+ g_return_if_fail (!_gtk_rbtree_is_nil (node->left));
+
+ left = node->left;
- 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_height = GTK_RBNODE_GET_HEIGHT (node);
+ left_height = GTK_RBNODE_GET_HEIGHT (left);
node->left = left->right;
if (!_gtk_rbtree_is_nil (left->right))
left->right->parent = node;
- if (!_gtk_rbtree_is_nil (left))
- left->parent = node->parent;
+ left->parent = node->parent;
if (!_gtk_rbtree_is_nil (node->parent))
{
if (node == node->parent->right)
/* link node and left */
left->right = node;
- if (!_gtk_rbtree_is_nil (node))
- 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);
+ node->parent = left;
+
+ node->count = 1 + node->left->count + node->right->count;
+ left->count = 1 + left->left->count + left->right->count;
+
+ node->offset = node_height + node->left->offset + node->right->offset +
+ (node->children ? node->children->root->offset : 0);
+ left->offset = left_height + left->left->offset + left->right->offset +
+ (left->children?left->children->root->offset:0);
_fixup_validation (tree, node);
_fixup_validation (tree, left);
retval->parent_tree = NULL;
retval->parent_node = NULL;
- retval->nil = (GtkRBNode *) &nil;
+ retval->root = (GtkRBNode *) &nil;
- retval->root = retval->nil;
return retval;
}
}
/* setup new node */
node = _gtk_rbnode_new (tree, height);
- node->parent = (current?current:tree->nil);
/* insert node in tree */
if (current)
{
+ node->parent = current;
if (right)
current->right = node;
else
/* setup new node */
node = _gtk_rbnode_new (tree, height);
- node->parent = (current?current:tree->nil);
/* insert node in tree */
if (current)
{
+ node->parent = current;
if (left)
current->left = node;
else
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)) ||
- (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
- (!_gtk_rbtree_is_nil (node->right) && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
+ (GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+ (GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
return;
GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
while ((node = _gtk_rbtree_next (tree, node)) != NULL);
}
-typedef struct _GtkRBReorder
-{
- GtkRBTree *children;
- gint height;
- gint flags;
- gint order;
- gint invert_order;
- guint total_count;
-} GtkRBReorder;
-
-static int
-gtk_rbtree_reorder_sort_func (gconstpointer a,
- gconstpointer b)
+static void
+reorder_prepare (GtkRBTree *tree,
+ GtkRBNode *node,
+ gpointer data)
{
- return ((GtkRBReorder *) a)->order - ((GtkRBReorder *) b)->order;
+ node->offset -= node->left->offset + node->right->offset;
+ GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
}
-static int
-gtk_rbtree_reorder_invert_func (gconstpointer a,
- gconstpointer b)
+static void
+reorder_fixup (GtkRBTree *tree,
+ GtkRBNode *node,
+ gpointer data)
{
- return ((GtkRBReorder *) a)->invert_order - ((GtkRBReorder *) b)->invert_order;
+ node->offset += node->left->offset + node->right->offset;
+ node->count = 1 + node->left->count + node->right->count;
+ _fixup_validation (tree, node);
+ _fixup_total_count (tree, node);
}
static void
-gtk_rbtree_reorder_fixup (GtkRBTree *tree,
- GtkRBNode *node)
+reorder_copy_node (GtkRBTree *tree,
+ GtkRBNode *to,
+ GtkRBNode *from)
{
- if (_gtk_rbtree_is_nil (node))
- return;
-
- node->total_count = 1;
-
- if (!_gtk_rbtree_is_nil (node->left))
- {
- gtk_rbtree_reorder_fixup (tree, node->left);
- node->offset += node->left->offset;
- node->total_count += node->left->total_count;
- }
- if (!_gtk_rbtree_is_nil (node->right))
- {
- gtk_rbtree_reorder_fixup (tree, node->right);
- node->offset += node->right->offset;
- node->total_count += node->right->total_count;
- }
-
- if (node->children)
- {
- node->offset += node->children->root->offset;
- node->total_count += node->children->root->total_count;
- }
-
- if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
- (!_gtk_rbtree_is_nil (node->right) && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
- (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
- (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
- GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
- else
- GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
+ to->flags = (to->flags & GTK_RBNODE_NON_COLORS) | GTK_RBNODE_GET_COLOR (from);
+
+ to->left = from->left;
+ if (!_gtk_rbtree_is_nil (to->left))
+ to->left->parent = to;
+
+ to->right = from->right;
+ if (!_gtk_rbtree_is_nil (to->right))
+ to->right->parent = to;
+
+ to->parent = from->parent;
+ if (_gtk_rbtree_is_nil (to->parent))
+ tree->root = to;
+ else if (to->parent->left == from)
+ to->parent->left = to;
+ else if (to->parent->right == from)
+ to->parent->right = to;
}
/* It basically pulls everything out of the tree, rearranges it, and puts it
gint *new_order,
gint length)
{
- GtkRBReorder reorder = { NULL };
- GArray *array;
+ GtkRBNode **nodes;
GtkRBNode *node;
- gint i;
+ gint i, j;
g_return_if_fail (tree != NULL);
g_return_if_fail (length > 0);
g_return_if_fail (tree->root->count == length);
- /* Sort the trees values in the new tree. */
- array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
- for (i = 0; i < length; i++)
- {
- reorder.order = new_order[i];
- reorder.invert_order = i;
- g_array_append_val (array, reorder);
- }
+ nodes = g_new (GtkRBNode *, length);
- g_array_sort(array, gtk_rbtree_reorder_sort_func);
+ _gtk_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL);
- /* rewind node*/
- node = _gtk_rbtree_first (tree);
+ for (node = _gtk_rbtree_first (tree), i = 0;
+ node;
+ node = _gtk_rbtree_next (tree, node), i++)
+ {
+ nodes[i] = node;
+ }
for (i = 0; i < length; i++)
{
- g_assert (!_gtk_rbtree_is_nil (node));
- g_array_index (array, GtkRBReorder, i).children = node->children;
- g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
- g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
+ GtkRBNode tmp = { 0, };
+ GSList *l, *cycle = NULL;
- node = _gtk_rbtree_next (tree, node);
- }
+ tmp.offset = -1;
- g_array_sort (array, gtk_rbtree_reorder_invert_func);
-
- /* rewind node*/
- node = _gtk_rbtree_first (tree);
+ /* already swapped */
+ if (nodes[i] == NULL)
+ continue;
+ /* no need to swap */
+ if (new_order[i] == i)
+ continue;
- /* Go through the tree and change the values to the new ones. */
- for (i = 0; i < length; i++)
- {
- reorder = g_array_index (array, GtkRBReorder, i);
- node->children = reorder.children;
- if (node->children)
- node->children->parent_node = node;
- node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
- /* We temporarily set the height to this. */
- node->offset = reorder.height;
- node = _gtk_rbtree_next (tree, node);
+ /* make a list out of the pending nodes */
+ for (j = i; new_order[j] != i; j = new_order[j])
+ {
+ cycle = g_slist_prepend (cycle, nodes[j]);
+ nodes[j] = NULL;
+ }
+
+ node = nodes[j];
+ reorder_copy_node (tree, &tmp, node);
+ for (l = cycle; l; l = l->next)
+ {
+ reorder_copy_node (tree, node, l->data);
+ node = l->data;
+ }
+
+ reorder_copy_node (tree, node, &tmp);
+ nodes[j] = NULL;
+ g_slist_free (cycle);
}
- gtk_rbtree_reorder_fixup (tree, tree->root);
- g_array_free (array, TRUE);
+ _gtk_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL);
+
+ g_free (nodes);
}
+/**
+ * _gtk_rbtree_contains:
+ * @tree: a tree
+ * @potential_child: a potential child of @tree
+ *
+ * Checks if @potential_child is a child (direct or via intermediate
+ * trees) of @tree.
+ *
+ * Returns: %TRUE if @potentitial_child is a child of @tree.
+ **/
+gboolean
+_gtk_rbtree_contains (GtkRBTree *tree,
+ GtkRBTree *potential_child)
+{
+ g_return_val_if_fail (tree != NULL, FALSE);
+ g_return_val_if_fail (potential_child != NULL, FALSE);
+
+ do {
+ potential_child = potential_child->parent_tree;
+ if (potential_child == tree)
+ return TRUE;
+ } while (potential_child != NULL);
+
+ return FALSE;
+}
gint
_gtk_rbtree_node_find_offset (GtkRBTree *tree,
return retval;
}
-gint
-_gtk_rbtree_real_find_offset (GtkRBTree *tree,
- gint height,
- GtkRBTree **new_tree,
- GtkRBNode **new_node)
+static gint
+gtk_rbtree_real_find_offset (GtkRBTree *tree,
+ gint height,
+ GtkRBTree **new_tree,
+ GtkRBNode **new_node)
{
GtkRBNode *tmp_node;
*new_node = tmp_node;
return (height - tmp_node->left->offset);
}
- return _gtk_rbtree_real_find_offset (tmp_node->children,
- height - tmp_node->left->offset -
- (tmp_node->offset -
- tmp_node->left->offset -
- tmp_node->right->offset -
- tmp_node->children->root->offset),
- new_tree,
- new_node);
+ return gtk_rbtree_real_find_offset (tmp_node->children,
+ height - tmp_node->left->offset -
+ (tmp_node->offset -
+ tmp_node->left->offset -
+ tmp_node->right->offset -
+ tmp_node->children->root->offset),
+ new_tree,
+ new_node);
}
*new_tree = tree;
*new_node = tmp_node;
gint
_gtk_rbtree_find_offset (GtkRBTree *tree,
- gint height,
- GtkRBTree **new_tree,
- GtkRBNode **new_node)
+ gint height,
+ GtkRBTree **new_tree,
+ GtkRBNode **new_node)
{
g_assert (tree);
return 0;
}
- return _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
+ return gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
}
gboolean
{
if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
- (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
- (!_gtk_rbtree_is_nil (node->right) && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+ GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
+ GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
(node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
{
GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
{
g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
- (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
- (!_gtk_rbtree_is_nil (node->right) && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+ GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
+ GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
(node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
}
else
while (tmp_tree->parent_tree)
tmp_tree = tmp_tree->parent_tree;
- g_assert (tmp_tree->nil != NULL);
-
if (_gtk_rbtree_is_nil (tmp_tree->root))
return;
projects / ~andy / gtk / blobdiff