X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Favl_tree.c;h=de95270ee99c56ff538af526875fbff32f8f168b;hp=a8477aa46e149ad15d99eb3b331879f883fa0261;hb=a60aa6bebc8cc1d72e89be6b9cfb7338f092158d;hpb=7de21bb98b71281359af1193c9c842ca1799c234 diff --git a/src/avl_tree.c b/src/avl_tree.c index a8477aa4..de95270e 100644 --- a/src/avl_tree.c +++ b/src/avl_tree.c @@ -1,14 +1,22 @@ /* - * 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 by Eric Biggers * - * 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 . */ #ifdef HAVE_CONFIG_H @@ -33,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) @@ -85,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) @@ -98,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) { @@ -109,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) { @@ -117,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); @@ -125,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; @@ -134,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, @@ -183,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) { @@ -242,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) @@ -300,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, @@ -505,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, @@ -619,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)