X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Favl_tree.c;h=208880ebab1f3258f33763bacf2eaca0d9e55599;hp=a8477aa46e149ad15d99eb3b331879f883fa0261;hb=181cc78dc68e62f3e005e1590f5cda12d3e287f5;hpb=7de21bb98b71281359af1193c9c842ca1799c234 diff --git a/src/avl_tree.c b/src/avl_tree.c index a8477aa4..208880eb 100644 --- a/src/avl_tree.c +++ b/src/avl_tree.c @@ -1,14 +1,22 @@ /* - * 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 by Eric Biggers * - * The author dedicates this file to the public domain. - * You can do whatever you want with this file. + * 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 . */ #ifdef HAVE_CONFIG_H @@ -85,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) @@ -98,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) { @@ -109,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) { @@ -117,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); @@ -125,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; @@ -134,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, @@ -183,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) { @@ -242,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) @@ -300,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, @@ -505,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, @@ -619,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)