X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Favl_tree.c;h=8b8e07bbe5d608b26975a47d60e443c044c5d033;hp=95e0e187923590129bbee8375e4881c13c70d501;hb=56f881eba91349abe40dd250ecbf08310cb88ce8;hpb=0b9e604afe3742154fd283d448d481670d7f2636

diff --git a/src/avl_tree.c b/src/avl_tree.c
index 95e0e187..8b8e07bb 100644
--- a/src/avl_tree.c
+++ b/src/avl_tree.c
@@ -274,7 +274,9 @@ avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr,
 			  struct avl_tree_node * const parent,
 			  const int sign)
 {
-	/* Height of @node subtree of @parent has increased by 1.
+	/* The subtree rooted at @node, which is a child of @parent, has
+	 * increased by 1.
+	 *
 	 * Adjust @parent's balance factor and check whether rotations need to
 	 * be done.  */
 
@@ -386,24 +388,47 @@ avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
 				struct avl_tree_node *inserted)
 {
 	struct avl_tree_node *node, *parent;
-	bool done = false;
+	bool done;
 
 	inserted->left = NULL;
 	inserted->right = NULL;
 
-	for (node = inserted, parent = avl_get_parent(node);
-	     parent && !done;
-	     node = parent, parent = avl_get_parent(parent))
-	{
-		/* Height of @node subtree has increased by 1  */
+	node = inserted;
 
+	/* Adjust balance factor of new node's parent.
+	 * No rotation will need to be done at this level.  */
+
+	parent = avl_get_parent(node);
+	if (!parent)
+		return;
+
+	if (node == parent->left)
+		avl_adjust_balance_factor(parent, -1);
+	else
+		avl_adjust_balance_factor(parent, +1);
+
+	if (avl_get_balance_factor(parent) == 0)
+		/* @parent did not change in height.  Nothing more to do.  */
+		return;
+
+	/* The subtree rooted at @parent increased in height by 1.  */
+
+	do {
+		/* Adjust balance factor of next ancestor.  */
+
+		node = parent;
+		parent = avl_get_parent(node);
+		if (!parent)
+			return;
+
+		/* The subtree rooted at @node has increased in height by 1.  */
 		if (node == parent->left)
 			done = avl_handle_subtree_growth(root_ptr, node,
 							 parent, -1);
 		else
 			done = avl_handle_subtree_growth(root_ptr, node,
 							 parent, +1);
-	}
+	} while (!done);
 }
 
 static AVL_INLINE struct avl_tree_node *