X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Favl_tree.c;h=de95270ee99c56ff538af526875fbff32f8f168b;hp=d3afae4e2114e7de667113b433d905af98dc6c24;hb=a60aa6bebc8cc1d72e89be6b9cfb7338f092158d;hpb=eb3e3b72db23ecaa7789a807afeb9577962653fe diff --git a/src/avl_tree.c b/src/avl_tree.c index d3afae4e..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) @@ -93,7 +113,7 @@ avl_tree_next_in_postorder(const struct avl_tree_node *prev, * 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 * +static forceinline struct avl_tree_node * avl_get_child(const struct avl_tree_node *parent, int sign) { if (sign < 0) @@ -106,7 +126,7 @@ avl_get_child(const struct avl_tree_node *parent, int sign) * 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 void +static forceinline void avl_set_child(struct avl_tree_node *parent, int sign, struct avl_tree_node *child) { @@ -117,7 +137,7 @@ avl_set_child(struct avl_tree_node *parent, int sign, } /* Sets the parent and balance factor of the specified AVL tree node. */ -static AVL_INLINE void +static forceinline void avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent, int balance_factor) { @@ -125,7 +145,7 @@ avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent, } /* Sets the parent of the specified AVL tree node. */ -static AVL_INLINE void +static forceinline void avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent) { node->parent_balance = (uintptr_t)parent | (node->parent_balance & 3); @@ -133,7 +153,7 @@ avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent) /* Returns the balance factor of the specified AVL tree node --- that is, the * height of its right subtree minus the height of its left subtree. */ -static AVL_INLINE int +static forceinline int avl_get_balance_factor(const struct avl_tree_node *node) { return (int)(node->parent_balance & 3) - 1; @@ -142,13 +162,13 @@ avl_get_balance_factor(const struct avl_tree_node *node) /* Adds @amount to the balance factor of the specified AVL tree node. * The caller must ensure this still results in a valid balance factor * (-1, 0, or 1). */ -static AVL_INLINE void +static forceinline void avl_adjust_balance_factor(struct avl_tree_node *node, int amount) { node->parent_balance += amount; } -static AVL_INLINE void +static forceinline void avl_replace_child(struct avl_tree_node **root_ptr, struct avl_tree_node *parent, struct avl_tree_node *old_child, @@ -191,7 +211,7 @@ avl_replace_child(struct avl_tree_node **root_ptr, * * This updates pointers but not balance factors! */ -static AVL_INLINE void +static forceinline void avl_rotate(struct avl_tree_node ** const root_ptr, struct avl_tree_node * const A, const int sign) { @@ -250,7 +270,7 @@ avl_rotate(struct avl_tree_node ** const root_ptr, * See comment in avl_handle_subtree_growth() for explanation of balance * factor updates. */ -static AVL_INLINE struct avl_tree_node * +static forceinline struct avl_tree_node * avl_do_double_rotate(struct avl_tree_node ** const root_ptr, struct avl_tree_node * const B, struct avl_tree_node * const A, const int sign) @@ -308,7 +328,7 @@ avl_do_double_rotate(struct avl_tree_node ** const root_ptr, * Indeed, a single node insertion cannot require that more than one * (single or double) rotation be done. */ -static AVL_INLINE bool +static forceinline bool avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr, struct avl_tree_node * const node, struct avl_tree_node * const parent, @@ -513,7 +533,7 @@ avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr, * decreased in height by 1. Also in the latter case, *left_deleted_ret * will be set. */ -static AVL_INLINE struct avl_tree_node * +static forceinline struct avl_tree_node * avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr, struct avl_tree_node *parent, const int sign, @@ -627,7 +647,7 @@ avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr, /* Swaps node X, which must have 2 children, with its in-order successor, then * unlinks node X. Returns the parent of X just before unlinking, without its * balance factor having been updated to account for the unlink. */ -static AVL_INLINE struct avl_tree_node * +static forceinline struct avl_tree_node * avl_tree_swap_with_successor(struct avl_tree_node **root_ptr, struct avl_tree_node *X, bool *left_deleted_ret)