From: Eric Biggers <ebiggers3@gmail.com>
Date: Tue, 26 Jul 2016 02:14:21 +0000 (-0700)
Subject: avl_tree: add avl_tree_prev_in_order()
X-Git-Tag: v1.10.0~11
X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=a60aa6bebc8cc1d72e89be6b9cfb7338f092158d;hp=d5ecf54ce90b9c8942743e0fa5c34620f7140ae2

avl_tree: add avl_tree_prev_in_order()
---

diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h
index ddc1ba7c..2e07e03c 100644
--- a/include/wimlib/avl_tree.h
+++ b/include/wimlib/avl_tree.h
@@ -262,7 +262,10 @@ extern struct avl_tree_node *
 avl_tree_first_in_order(const struct avl_tree_node *root);
 
 extern struct avl_tree_node *
-avl_tree_next_in_order(const struct avl_tree_node *prev);
+avl_tree_next_in_order(const struct avl_tree_node *node);
+
+extern struct avl_tree_node *
+avl_tree_prev_in_order(const struct avl_tree_node *node);
 
 extern struct avl_tree_node *
 avl_tree_first_in_postorder(const struct avl_tree_node *root);
diff --git a/src/avl_tree.c b/src/avl_tree.c
index 208880eb..de95270e 100644
--- a/src/avl_tree.c
+++ b/src/avl_tree.c
@@ -41,23 +41,43 @@ avl_tree_first_in_order(const struct avl_tree_node *root)
 /* Continues an in-order traversal of the tree: returns the next-greatest-valued
  * node, or NULL if there is none.  */
 struct avl_tree_node *
-avl_tree_next_in_order(const struct avl_tree_node *prev)
+avl_tree_next_in_order(const struct avl_tree_node *node)
 {
 	const struct avl_tree_node *next;
 
-	if (prev->right)
-		for (next = prev->right;
+	if (node->right)
+		for (next = node->right;
 		     next->left;
 		     next = next->left)
 			;
 	else
-		for (next = avl_get_parent(prev);
-		     next && prev == next->right;
-		     prev = next, next = avl_get_parent(next))
+		for (next = avl_get_parent(node);
+		     next && node == next->right;
+		     node = next, next = avl_get_parent(next))
 			;
 	return (struct avl_tree_node *)next;
 }
 
+/* Continues a *reverse* in-order traversal of the tree: returns the
+ * previous-greatest-valued node, or NULL if there is none.  */
+struct avl_tree_node *
+avl_tree_prev_in_order(const struct avl_tree_node *node)
+{
+	const struct avl_tree_node *prev;
+
+	if (node->left)
+		for (prev = node->left;
+		     prev->right;
+		     prev = prev->right)
+			;
+	else
+		for (prev = avl_get_parent(node);
+		     prev && node == prev->left;
+		     node = prev, prev = avl_get_parent(prev))
+			;
+	return (struct avl_tree_node *)prev;
+}
+
 /* Starts a postorder traversal of the tree.  */
 struct avl_tree_node *
 avl_tree_first_in_postorder(const struct avl_tree_node *root)