avl_tree: remove now-unused support for "unlinked" marker

[wimlib] / src / avl_tree.c

diff --git a/src/avl_tree.c b/src/avl_tree.c
index 208880ebab1f3258f33763bacf2eaca0d9e55599..38a8ecc5b449b989a8648802ae46dcaba992097b 100644 (file)
--- 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)
@@ -705,8 +725,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)