Sync AVL tree code from project

diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h
index 8f7559156f90a7008b8cb5f9ff7a0dbe8401afe2..ed615edc3931e9646dac5af5ab6adf9174c6bf02 100644 (file)
--- a/include/wimlib/avl_tree.h
+++ b/include/wimlib/avl_tree.h
@@ -4,7 +4,7 @@
  *
  * The following copying information applies to this specific source code file:
  *
  *
  * The following copying information applies to this specific source code file:
  *

- * Written in 2014 by Eric Biggers <ebiggers3@gmail.com>
+ * Written in 2014-2016 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
  *
  * 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


@@ -23,6 +23,7 @@
 #define _AVL_TREE_H_
 
 #include "wimlib/types.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 {
 
 /* Node in an AVL tree.  Embed this in some other data structure.  */
 struct avl_tree_node {


@@ -56,7 +57,7 @@ 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.  */
 
 /* 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);
 avl_get_parent(const struct avl_tree_node *node)
 {
        return (struct avl_tree_node *)(node->parent_balance & ~3);


@@ -115,7 +116,7 @@ avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
  *     return result ? true : false;
  * }
  */
  *     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 *))
 avl_tree_lookup(const struct avl_tree_node *root,
                const void *cmp_ctx,
                int (*cmp)(const void *, const struct avl_tree_node *))


@@ -138,7 +139,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'.  */
  * 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 *,
 avl_tree_lookup_node(const struct avl_tree_node *root,
                     const struct avl_tree_node *node,
                     int (*cmp)(const struct avl_tree_node *,


@@ -210,7 +211,7 @@ avl_tree_lookup_node(const struct avl_tree_node *root,
  *     return true;
  * }
  */
  *     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 *,
 avl_tree_insert(struct avl_tree_node **root_ptr,
                struct avl_tree_node *item,
                int (*cmp)(const struct avl_tree_node *,


@@ -245,6 +246,9 @@ avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
 extern struct avl_tree_node *
 avl_tree_first_in_order(const struct avl_tree_node *root);
 
 extern struct avl_tree_node *
 avl_tree_first_in_order(const struct avl_tree_node *root);
 

+extern struct avl_tree_node *
+avl_tree_last_in_order(const struct avl_tree_node *root);
+

 extern struct avl_tree_node *
 avl_tree_next_in_order(const struct avl_tree_node *node);
 
 extern struct avl_tree_node *
 avl_tree_next_in_order(const struct avl_tree_node *node);
 


@@ -296,6 +300,18 @@ avl_tree_next_in_postorder(const struct avl_tree_node *prev,
                                     struct_member), 1);                \
             _cur = avl_tree_next_in_order(_cur))
 
                                     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.
 /*
  * Like avl_tree_for_each_in_order(), but iterates through the nodes in
  * postorder, so the current node may be deleted or freed.

diff --git a/src/avl_tree.c b/src/avl_tree.c
index 38a8ecc5b449b989a8648802ae46dcaba992097b..50ed1777cf9f52e4e78ae1dfa35d5eb51f1ba57c 100644 (file)
--- a/src/avl_tree.c
+++ b/src/avl_tree.c
@@ -4,7 +4,7 @@
  *
  * The following copying information applies to this specific source code file:
  *
  *
  * The following copying information applies to this specific source code file:
  *

- * Written in 2014 by Eric Biggers <ebiggers3@gmail.com>
+ * Written in 2014-2016 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
  *
  * 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


@@ -25,57 +25,78 @@
 
 #include "wimlib/avl_tree.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)
 {
        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;
 }
 
        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 *
 struct avl_tree_node *

-avl_tree_next_in_order(const struct avl_tree_node *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_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;
 
 {
        const struct avl_tree_node *next;
 

-       if (node->right)
-               for (next = node->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(node);
                        ;
        else
                for (next = avl_get_parent(node);

-                    next && node == next->right;
+                    next && node == avl_get_child(next, +sign);

                     node = next, next = avl_get_parent(next))
                        ;
        return (struct avl_tree_node *)next;
 }
 
                     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)
 {
 /* 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)
 {

-       const struct avl_tree_node *prev;
-
-       if (node->left)
-               for (prev = node->left;
-                    prev->right;
-                    prev = prev->right)
-                       ;
-       else
-               for (prev = avl_get_parent(node);
-                    prev && node == prev->left;
-                    node = prev, prev = avl_get_parent(prev))
-                       ;
-       return (struct avl_tree_node *)prev;
+       return avl_tree_next_or_prev_in_order(node, -1);

 }
 
 /* Starts a postorder traversal of the tree.  */
 }
 
 /* Starts a postorder traversal of the tree.  */


@@ -109,24 +130,11 @@ avl_tree_next_in_postorder(const struct avl_tree_node *prev,
        return (struct avl_tree_node *)next;
 }
 
        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 forceinline 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,
  * so the compiler can remove the conditional.  */
 /* 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,
  * so the compiler can remove the conditional.  */

-static forceinline void
+static AVL_INLINE void

 avl_set_child(struct avl_tree_node *parent, int sign,
              struct avl_tree_node *child)
 {
 avl_set_child(struct avl_tree_node *parent, int sign,
              struct avl_tree_node *child)
 {


@@ -137,7 +145,7 @@ avl_set_child(struct avl_tree_node *parent, int sign,
 }
 
 /* Sets the parent and balance factor of the specified AVL tree node.  */
 }
 
 /* Sets the parent and balance factor of the specified AVL tree node.  */

-static forceinline void
+static AVL_INLINE void

 avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent,
                       int balance_factor)
 {
 avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent,
                       int balance_factor)
 {


@@ -145,7 +153,7 @@ avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent,
 }
 
 /* Sets the parent of the specified AVL tree node.  */
 }
 
 /* Sets the parent of the specified AVL tree node.  */

-static forceinline void
+static AVL_INLINE void

 avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent)
 {
        node->parent_balance = (uintptr_t)parent | (node->parent_balance & 3);
 avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent)
 {
        node->parent_balance = (uintptr_t)parent | (node->parent_balance & 3);


@@ -153,7 +161,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.  */
 
 /* 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 forceinline int
+static AVL_INLINE int

 avl_get_balance_factor(const struct avl_tree_node *node)
 {
        return (int)(node->parent_balance & 3) - 1;
 avl_get_balance_factor(const struct avl_tree_node *node)
 {
        return (int)(node->parent_balance & 3) - 1;


@@ -162,13 +170,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).  */
 /* 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 forceinline void
+static AVL_INLINE void

 avl_adjust_balance_factor(struct avl_tree_node *node, int amount)
 {
        node->parent_balance += amount;
 }
 
 avl_adjust_balance_factor(struct avl_tree_node *node, int amount)
 {
        node->parent_balance += amount;
 }
 

-static forceinline void
+static AVL_INLINE void

 avl_replace_child(struct avl_tree_node **root_ptr,
                  struct avl_tree_node *parent,
                  struct avl_tree_node *old_child,
 avl_replace_child(struct avl_tree_node **root_ptr,
                  struct avl_tree_node *parent,
                  struct avl_tree_node *old_child,


@@ -211,7 +219,7 @@ avl_replace_child(struct avl_tree_node **root_ptr,
  *
  * This updates pointers but not balance factors!
  */
  *
  * This updates pointers but not balance factors!
  */

-static forceinline void
+static AVL_INLINE void

 avl_rotate(struct avl_tree_node ** const root_ptr,
           struct avl_tree_node * const A, const int sign)
 {
 avl_rotate(struct avl_tree_node ** const root_ptr,
           struct avl_tree_node * const A, const int sign)
 {


@@ -270,7 +278,7 @@ avl_rotate(struct avl_tree_node ** const root_ptr,
  * See comment in avl_handle_subtree_growth() for explanation of balance
  * factor updates.
  */
  * See comment in avl_handle_subtree_growth() for explanation of balance
  * factor updates.
  */

-static forceinline struct avl_tree_node *
+static AVL_INLINE 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)
 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)


@@ -328,7 +336,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.
  */
  * Indeed, a single node insertion cannot require that more than one
  * (single or double) rotation be done.
  */

-static forceinline bool
+static AVL_INLINE bool

 avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr,
                          struct avl_tree_node * const node,
                          struct avl_tree_node * const parent,
 avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr,
                          struct avl_tree_node * const node,
                          struct avl_tree_node * const parent,


@@ -533,7 +541,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.
  */
  * decreased in height by 1.  Also in the latter case, *left_deleted_ret
  * will be set.
  */

-static forceinline struct avl_tree_node *
+static AVL_INLINE struct avl_tree_node *

 avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr,
                          struct avl_tree_node *parent,
                          const int sign,
 avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr,
                          struct avl_tree_node *parent,
                          const int sign,


@@ -647,7 +655,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.  */
 /* 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 forceinline struct avl_tree_node *
+static AVL_INLINE struct avl_tree_node *

 avl_tree_swap_with_successor(struct avl_tree_node **root_ptr,
                             struct avl_tree_node *X,
                             bool *left_deleted_ret)
 avl_tree_swap_with_successor(struct avl_tree_node **root_ptr,
                             struct avl_tree_node *X,
                             bool *left_deleted_ret)