X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Favl_tree.c;h=50ed1777cf9f52e4e78ae1dfa35d5eb51f1ba57c;hb=8f7d929a9eaf15773fc0647204bdf5911001939f;hp=caaba3ed6905471e8307ff359e94915456066c8b;hpb=54d3007554444024077d89091d63e4a250fedd01;p=wimlib diff --git a/src/avl_tree.c b/src/avl_tree.c index caaba3ed..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 * - * This file is placed into the public domain. You can do whatever you want - * with it. + * 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 . */ -#include +#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, @@ -127,15 +167,6 @@ avl_get_balance_factor(const struct avl_tree_node *node) return (int)(node->parent_balance & 3) - 1; } -/* Sets the balance factor of the specified AVL tree node. This must be - * -1, 0, or 1. */ -static AVL_INLINE void -avl_set_balance_factor(struct avl_tree_node *node, int balance_factor) -{ - node->parent_balance = - (node->parent_balance & ~3) | (balance_factor + 1); -} - /* 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). */ @@ -380,12 +411,10 @@ avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr, */ avl_rotate(root_ptr, parent, -sign); - /* Equivalent to: - * avl_set_balance_factor(parent, 0); */ + /* Equivalent to setting @parent's balance factor to 0. */ avl_adjust_balance_factor(parent, -sign); /* A */ - /* Equivalent to: - * avl_set_balance_factor(node, 0); */ + /* Equivalent to setting @node's balance factor to 0. */ avl_adjust_balance_factor(node, -sign); /* B */ } else { /* @node (B below) is heavy in the direction opposite @@ -704,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)