* avl_tree.h - intrusive, nonrecursive AVL tree data structure (self-balancing
* binary search tree), header file
*
- * The following copying information applies to this specific source code file:
+ * Copyright 2022 Eric Biggers
*
- * Written in 2014 by Eric Biggers <ebiggers3@gmail.com>
+ * 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:
*
- * 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").
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
*
- * 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/>.
+ * 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.
*/
#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_
#include "wimlib/types.h"
+#define AVL_INLINE forceinline
/* Node in an AVL tree. Embed this in some other data structure. */
struct avl_tree_node {
/* Returns a pointer to the parent of the specified AVL tree node, or NULL if it
* is already the root of the tree. */
-static forceinline struct avl_tree_node *
+static AVL_INLINE struct avl_tree_node *
avl_get_parent(const struct avl_tree_node *node)
{
return (struct avl_tree_node *)(node->parent_balance & ~3);
}
-/* Marks the specified AVL tree node as unlinked from any tree. */
-static forceinline void
-avl_tree_node_set_unlinked(struct avl_tree_node *node)
-{
- node->parent_balance = (uintptr_t)node;
-}
-
-/* Returns true iff the specified AVL tree node has been marked with
- * avl_tree_node_set_unlinked() and has not subsequently been inserted into a
- * tree. */
-static forceinline bool
-avl_tree_node_is_unlinked(const struct avl_tree_node *node)
-{
- return node->parent_balance == (uintptr_t)node;
-}
-
/* (Internal use only) */
-extern void
+void
avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
struct avl_tree_node *inserted);
* return result ? true : false;
* }
*/
-static forceinline struct avl_tree_node *
+static AVL_INLINE struct avl_tree_node *
avl_tree_lookup(const struct avl_tree_node *root,
const void *cmp_ctx,
int (*cmp)(const void *, const struct avl_tree_node *))
* function. Specifically, with this function the item being searched for is
* expected to be in the same format as those already in the tree, with an
* embedded 'struct avl_tree_node'. */
-static forceinline struct avl_tree_node *
+static AVL_INLINE struct avl_tree_node *
avl_tree_lookup_node(const struct avl_tree_node *root,
const struct avl_tree_node *node,
int (*cmp)(const struct avl_tree_node *,
const struct avl_tree_node *))
{
- return avl_tree_lookup(root,
- (const void *)node,
- (int (*) (const void *,
- const struct avl_tree_node *))cmp);
+ const struct avl_tree_node *cur = root;
+
+ while (cur) {
+ int res = (*cmp)(node, cur);
+ if (res < 0)
+ cur = cur->left;
+ else if (res > 0)
+ cur = cur->right;
+ else
+ break;
+ }
+ return (struct avl_tree_node*)cur;
}
/*
* return true;
* }
*/
-static forceinline struct avl_tree_node *
+static AVL_INLINE struct avl_tree_node *
avl_tree_insert(struct avl_tree_node **root_ptr,
struct avl_tree_node *item,
int (*cmp)(const struct avl_tree_node *,
/* Removes an item from the specified AVL tree.
* See implementation for details. */
-extern void
+void
avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
/* Nonrecursive AVL tree traversal functions */
-extern struct avl_tree_node *
+struct avl_tree_node *
avl_tree_first_in_order(const struct avl_tree_node *root);
-extern struct avl_tree_node *
-avl_tree_next_in_order(const struct avl_tree_node *prev);
+struct avl_tree_node *
+avl_tree_last_in_order(const struct avl_tree_node *root);
-extern struct avl_tree_node *
+struct avl_tree_node *
+avl_tree_next_in_order(const struct avl_tree_node *node);
+
+struct avl_tree_node *
+avl_tree_prev_in_order(const struct avl_tree_node *node);
+
+struct avl_tree_node *
avl_tree_first_in_postorder(const struct avl_tree_node *root);
-extern struct avl_tree_node *
+struct avl_tree_node *
avl_tree_next_in_postorder(const struct avl_tree_node *prev,
const struct avl_tree_node *prev_parent);
struct_member), 1); \
_cur = avl_tree_next_in_order(_cur))
+/*
+ * Like avl_tree_for_each_in_order(), but uses the reverse order.
+ */
+#define avl_tree_for_each_in_reverse_order(child_struct, root, \
+ struct_name, struct_member) \
+ for (struct avl_tree_node *_cur = \
+ avl_tree_last_in_order(root); \
+ _cur && ((child_struct) = \
+ avl_tree_entry(_cur, struct_name, \
+ struct_member), 1); \
+ _cur = avl_tree_prev_in_order(_cur))
+
/*
* Like avl_tree_for_each_in_order(), but iterates through the nodes in
* postorder, so the current node may be deleted or freed.
git://wimlib.net / wimlib / blobdiff