#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.h> /* for uintptr_t */
-
-#ifdef __GNUC__
-# define AVL_INLINE inline __attribute__((always_inline))
-#else
-# define AVL_INLINE inline
-# warning "AVL tree functions may not be inlined as intended"
-#endif
+#include "wimlib/types.h"
/* 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 AVL_INLINE struct avl_tree_node *
+static forceinline 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 AVL_INLINE void
+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 AVL_INLINE bool
+static forceinline bool
avl_tree_node_is_unlinked(const struct avl_tree_node *node)
{
return node->parent_balance == (uintptr_t)node;
* return result ? true : false;
* }
*/
-static AVL_INLINE struct avl_tree_node *
+static forceinline 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 AVL_INLINE struct avl_tree_node *
+static forceinline 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 *,
* return true;
* }
*/
-static AVL_INLINE struct avl_tree_node *
+static forceinline 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 *,
* 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)
* 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)
{
}
/* 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)
{
}
/* 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);
/* 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;
/* 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,
*
* 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)
{
* 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)
* 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,
* 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,
/* 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)