* avl_tree.c - intrusive, nonrecursive AVL tree data structure (self-balancing
* binary search tree), implementation file
*
- * The following copying information applies to this specific source code file:
- *
- * Written in 2014 by Eric Biggers <ebiggers3@gmail.com>
- *
- * 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/>.
+ * Copyright 2022 Eric Biggers
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
*/
#ifdef HAVE_CONFIG_H
#include "wimlib/avl_tree.h"
-/* 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)
+/* 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_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_next_in_order(const struct avl_tree_node *prev)
+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)
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,
* 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)
git://wimlib.net / wimlib / blobdiff