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

diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h
index 7d13966f..516f5271 100644
--- a/include/wimlib/avl_tree.h
+++ b/include/wimlib/avl_tree.h
@@ -1,14 +1,22 @@
 /*
- * 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_
@@ -16,7 +24,7 @@
 
 #include <stdbool.h>
 #include <stddef.h>
-#include <inttypes.h> /* for uintptr_t */
+#include <stdint.h> /* for uintptr_t */
 
 #ifdef __GNUC__
 #  define AVL_INLINE inline __attribute__((always_inline))
@@ -103,6 +111,34 @@ avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
  *
  * Returns a pointer to the AVL tree node of the resulting item, or NULL if the
  * item was not found.
+ *
+ * Example:
+ *
+ * struct int_wrapper {
+ *	int data;
+ *	struct avl_tree_node index_node;
+ * };
+ *
+ * static int _avl_cmp_int_to_node(const void *intptr,
+ *				   const struct avl_tree_node *nodeptr)
+ * {
+ *	int n1 = *(const int *)intptr;
+ *	int n2 = avl_tree_entry(nodeptr, struct int_wrapper, index_node)->data;
+ *	if (n1 < n2)
+ *		return -1;
+ *	else if (n1 > n2)
+ *		return 1;
+ *	else
+ *		return 0;
+ * }
+ *
+ * bool contains_int(struct avl_tree_node *root, int n)
+ * {
+ *	struct avl_tree_node *result;
+ *
+ *	result = avl_tree_lookup(root, &n, _avl_cmp_int_to_node);
+ *	return result ? true : false;
+ * }
  */
 static AVL_INLINE struct avl_tree_node *
 avl_tree_lookup(const struct avl_tree_node *root,
@@ -164,6 +200,40 @@ avl_tree_lookup_node(const struct avl_tree_node *root,
  * @item and returns NULL.  Otherwise does nothing and returns a pointer to the
  * AVL tree node embedded in the previously-inserted item which compared equal
  * to @item.
+ *
+ * Example:
+ *
+ * struct int_wrapper {
+ *	int data;
+ *	struct avl_tree_node index_node;
+ * };
+ *
+ * #define GET_DATA(i) avl_tree_entry((i), struct int_wrapper, index_node)->data
+ *
+ * static int _avl_cmp_ints(const struct avl_tree_node *node1,
+ *			    const struct avl_tree_node *node2)
+ * {
+ *	int n1 = GET_DATA(node1);
+ *	int n2 = GET_DATA(node2);
+ *	if (n1 < n2)
+ *		return -1;
+ *	else if (n1 > n2)
+ *		return 1;
+ *	else
+ *		return 0;
+ * }
+ *
+ * bool insert_int(struct avl_tree_node **root_ptr, int data)
+ * {
+ *	struct int_wrapper *i = malloc(sizeof(struct int_wrapper));
+ *	i->data = data;
+ *	if (avl_tree_insert(root_ptr, &i->index_node, _avl_cmp_ints)) {
+ *		// Duplicate.
+ *		free(i);
+ *		return false;
+ *	}
+ *	return true;
+ * }
  */
 static AVL_INLINE struct avl_tree_node *
 avl_tree_insert(struct avl_tree_node **root_ptr,
@@ -210,4 +280,56 @@ extern struct avl_tree_node *
 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
 			   const struct avl_tree_node *prev_parent);
 
+/*
+ * Iterate through the nodes in an AVL tree in sorted order.
+ * You may not modify the tree during the iteration.
+ *
+ * @child_struct
+ *	Variable that will receive a pointer to each struct inserted into the
+ *	tree.
+ * @root
+ *	Root of the AVL tree.
+ * @struct_name
+ *	Type of *child_struct.
+ * @struct_member
+ *	Member of @struct_name type that is the AVL tree node.
+ *
+ * Example:
+ *
+ * struct int_wrapper {
+ *	int data;
+ *	struct avl_tree_node index_node;
+ * };
+ *
+ * void print_ints(struct avl_tree_node *root)
+ * {
+ *	struct int_wrapper *i;
+ *
+ *	avl_tree_for_each_in_order(i, root, struct int_wrapper, index_node)
+ *		printf("%d\n", i->data);
+ * }
+ */
+#define avl_tree_for_each_in_order(child_struct, root,			\
+				   struct_name, struct_member)		\
+	for (struct avl_tree_node *_cur =				\
+		avl_tree_first_in_order(root);				\
+	     _cur && ((child_struct) =					\
+		      avl_tree_entry(_cur, struct_name,			\
+				     struct_member), 1);		\
+	     _cur = avl_tree_next_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.
+ */
+#define avl_tree_for_each_in_postorder(child_struct, root,		\
+				       struct_name, struct_member)	\
+	for (struct avl_tree_node *_cur =				\
+		avl_tree_first_in_postorder(root), *_parent;		\
+	     _cur && ((child_struct) =					\
+		      avl_tree_entry(_cur, struct_name,			\
+				     struct_member), 1)			\
+	          && (_parent = avl_get_parent(_cur), 1);		\
+	     _cur = avl_tree_next_in_postorder(_cur, _parent))
+
 #endif /* _AVL_TREE_H_ */