From: Eric Biggers Date: Tue, 19 Jul 2016 16:00:17 +0000 (-0700) Subject: avl_tree: replace 'AVL_INLINE' with 'forceinline' X-Git-Tag: v1.10.0~16 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=181cc78dc68e62f3e005e1590f5cda12d3e287f5 avl_tree: replace 'AVL_INLINE' with 'forceinline' --- diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h index 516f5271..ddc1ba7c 100644 --- a/include/wimlib/avl_tree.h +++ b/include/wimlib/avl_tree.h @@ -22,16 +22,7 @@ #ifndef _AVL_TREE_H_ #define _AVL_TREE_H_ -#include -#include -#include /* 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 { @@ -65,14 +56,14 @@ 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; @@ -81,7 +72,7 @@ avl_tree_node_set_unlinked(struct avl_tree_node *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; @@ -140,7 +131,7 @@ avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr, * 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 *)) @@ -163,7 +154,7 @@ avl_tree_lookup(const struct avl_tree_node *root, * 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 *, @@ -235,7 +226,7 @@ avl_tree_lookup_node(const struct avl_tree_node *root, * 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 *, diff --git a/src/avl_tree.c b/src/avl_tree.c index d3afae4e..208880eb 100644 --- a/src/avl_tree.c +++ b/src/avl_tree.c @@ -93,7 +93,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) @@ -106,7 +106,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) { @@ -117,7 +117,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) { @@ -125,7 +125,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); @@ -133,7 +133,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; @@ -142,13 +142,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, @@ -191,7 +191,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) { @@ -250,7 +250,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) @@ -308,7 +308,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, @@ -513,7 +513,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, @@ -627,7 +627,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)