X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=include%2Fwimlib%2Favl_tree.h;h=ed615edc3931e9646dac5af5ab6adf9174c6bf02;hb=442113f2d338903274e4bb30e91c2564919145f3;hp=516f52715febeb9137045ea15c5294ff16123f6f;hpb=eb3e3b72db23ecaa7789a807afeb9577962653fe;p=wimlib

diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h
index 516f5271..ed615edc 100644
--- 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:
  *
- * 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
@@ -22,16 +22,8 @@
 #ifndef _AVL_TREE_H_
 #define _AVL_TREE_H_
 
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.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 {
@@ -71,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,
@@ -271,7 +247,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);
@@ -318,6 +300,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.