X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Favl_tree.h;h=2e07e03c5b7e3dff40663ce0eff81fbd774609ab;hp=a5d2511aecf66d89d3577951491cf19c3967d2cc;hb=a60aa6bebc8cc1d72e89be6b9cfb7338f092158d;hpb=d1bfffba93b1d841e243c923e739e0e39ee692f2

diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h
index a5d2511a..2e07e03c 100644
--- a/include/wimlib/avl_tree.h
+++ b/include/wimlib/avl_tree.h
@@ -1,29 +1,28 @@
 /*
- * 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 by Eric Biggers <ebiggers3@gmail.com>
  *
- * This file is placed into the public domain.  You can do whatever you want
- * with it.
+ * 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"
 
 /* Node in an AVL tree.  Embed this in some other data structure.  */
 struct avl_tree_node {
@@ -57,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;
@@ -73,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;
@@ -132,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 *))
@@ -155,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 *,
@@ -227,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 *,
@@ -263,7 +262,10 @@ 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_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);