X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Favl_tree.c;h=50ed1777cf9f52e4e78ae1dfa35d5eb51f1ba57c;hb=b3cbd2e7f9cf7249c8499909b63d3535b346042c;hp=86eb38823477e72b9f13a37c17153eb281e54cc8;hpb=4a0639235f5f6e28ce9c9cbd21edc71199f85d09;p=wimlib

diff --git a/src/avl_tree.c b/src/avl_tree.c
index 86eb3882..50ed1777 100644
--- a/src/avl_tree.c
+++ b/src/avl_tree.c
@@ -1,51 +1,104 @@
 /*
- * avl_tree.c
+ * avl_tree.c - intrusive, nonrecursive AVL tree data structure (self-balancing
+ *		binary search tree), implementation file
  *
- * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search
- * tree), implementation file.
+ * The following copying information applies to this specific source code file:
  *
- * Author:  Eric Biggers
- * Year:    2014
+ * Written in 2014-2016 by Eric Biggers <ebiggers3@gmail.com>
  *
- * The author dedicates this file to the public domain.
- * You can do whatever you want with this file.
+ * To the extent possible under law, the author(s) have dedicated all copyright
+ * and related and neighboring rights to this software to the public domain
+ * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
+ * Dedication (the "CC0").
+ *
+ * This software 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 CC0 for more details.
+ *
+ * You should have received a copy of the CC0 along with this software; if not
+ * see <http://creativecommons.org/publicdomain/zero/1.0/>.
  */
 
-#include <wimlib/avl_tree.h>
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif
 
-/* Starts an in-order traversal of the tree: returns the least-valued node, or
- * NULL if the tree is empty.  */
-struct avl_tree_node *
-avl_tree_first_in_order(const struct avl_tree_node *root)
+#include "wimlib/avl_tree.h"
+
+/* Returns the left child (sign < 0) or the right child (sign > 0) of the
+ * specified AVL tree node.
+ * Note: for all calls of this, 'sign' is constant at compilation time,
+ * so the compiler can remove the conditional.  */
+static AVL_INLINE struct avl_tree_node *
+avl_get_child(const struct avl_tree_node *parent, int sign)
+{
+	if (sign < 0)
+		return parent->left;
+	else
+		return parent->right;
+}
+
+static AVL_INLINE struct avl_tree_node *
+avl_tree_first_or_last_in_order(const struct avl_tree_node *root, int sign)
 {
 	const struct avl_tree_node *first = root;
 
 	if (first)
-		while (first->left)
-			first = first->left;
+		while (avl_get_child(first, +sign))
+			first = avl_get_child(first, +sign);
 	return (struct avl_tree_node *)first;
 }
 
-/* Continues an in-order traversal of the tree: returns the next-greatest-valued
- * node, or NULL if there is none.  */
+/* Starts an in-order traversal of the tree: returns the least-valued node, or
+ * NULL if the tree is empty.  */
 struct avl_tree_node *
-avl_tree_next_in_order(const struct avl_tree_node *prev)
+avl_tree_first_in_order(const struct avl_tree_node *root)
+{
+	return avl_tree_first_or_last_in_order(root, -1);
+}
+
+/* Starts a *reverse* in-order traversal of the tree: returns the
+ * greatest-valued node, or NULL if the tree is empty.  */
+struct avl_tree_node *
+avl_tree_last_in_order(const struct avl_tree_node *root)
+{
+	return avl_tree_first_or_last_in_order(root, 1);
+}
+
+static AVL_INLINE struct avl_tree_node *
+avl_tree_next_or_prev_in_order(const struct avl_tree_node *node, int sign)
 {
 	const struct avl_tree_node *next;
 
-	if (prev->right)
-		for (next = prev->right;
-		     next->left;
-		     next = next->left)
+	if (avl_get_child(node, +sign))
+		for (next = avl_get_child(node, +sign);
+		     avl_get_child(next, -sign);
+		     next = avl_get_child(next, -sign))
 			;
 	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 == avl_get_child(next, +sign);
+		     node = next, next = avl_get_parent(next))
 			;
 	return (struct avl_tree_node *)next;
 }
 
+/* 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 *node)
+{
+	return avl_tree_next_or_prev_in_order(node, 1);
+}
+
+/* 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)
+{
+	return avl_tree_next_or_prev_in_order(node, -1);
+}
+
 /* Starts a postorder traversal of the tree.  */
 struct avl_tree_node *
 avl_tree_first_in_postorder(const struct avl_tree_node *root)
@@ -77,19 +130,6 @@ avl_tree_next_in_postorder(const struct avl_tree_node *prev,
 	return (struct avl_tree_node *)next;
 }
 
-/* Returns the left child (sign < 0) or the right child (sign > 0) of the
- * specified AVL tree node.
- * Note: for all calls of this, 'sign' is constant at compilation time,
- * so the compiler can remove the conditional.  */
-static AVL_INLINE struct avl_tree_node *
-avl_get_child(const struct avl_tree_node *parent, int sign)
-{
-	if (sign < 0)
-		return parent->left;
-	else
-		return parent->right;
-}
-
 /* Sets the left child (sign < 0) or the right child (sign > 0) of the
  * specified AVL tree node.
  * Note: for all calls of this, 'sign' is constant at compilation time,
@@ -693,8 +733,7 @@ avl_tree_swap_with_successor(struct avl_tree_node **root_ptr,
  *	remove from the tree.
  *
  * Note: This function *only* removes the node and rebalances the tree.
- * It does not free any memory, nor does it do the equivalent of
- * avl_tree_node_set_unlinked().
+ * It does not free any memory.
  */
 void
 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node)