avl_tree.h: avoid bad function pointer cast

[wimlib] / include / wimlib / avl_tree.h

diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h
index a281d635a60cf65c7e492e6f0a5a8cde3c61b763..b7a9bb1b27fb3958bc8734cb160f36944d66981c 100644 (file)
--- a/include/wimlib/avl_tree.h
+++ b/include/wimlib/avl_tree.h
@@ -1,29 +1,29 @@
 /*
- * avl_tree.h
+ * avl_tree.h - intrusive, nonrecursive AVL tree data structure (self-balancing
+ *             binary search tree), header file
  *
- * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search
- * tree), header file.
+ * The following copying information applies to this specific source code file:
  *
- * Author:  Eric Biggers
- * Year:    2014
+ * Written in 2014-2016 by Eric Biggers <ebiggers3@gmail.com>
  *
- * 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 <http://creativecommons.org/publicdomain/zero/1.0/>.
  */
 
 #ifndef _AVL_TREE_H_
 #define _AVL_TREE_H_
 
-#include <stdbool.h>
-#include <stddef.h>
-#include <inttypes.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"
+#define AVL_INLINE forceinline
 
 /* Node in an AVL tree.  Embed this in some other data structure.  */
 struct avl_tree_node {
@@ -63,22 +63,6 @@ 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
-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
-avl_tree_node_is_unlinked(const struct avl_tree_node *node)
-{
-       return node->parent_balance == (uintptr_t)node;
-}
-
 /* (Internal use only)  */
 extern void
 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
@@ -161,10 +145,18 @@ avl_tree_lookup_node(const struct avl_tree_node *root,
                     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;
 }
 
 /*
@@ -263,7 +255,13 @@ extern 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);
+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_prev_in_order(const struct avl_tree_node *node);
 
 extern struct avl_tree_node *
 avl_tree_first_in_postorder(const struct avl_tree_node *root);
@@ -310,6 +308,18 @@ avl_tree_next_in_postorder(const struct avl_tree_node *prev,
                                     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.