2 * avl_tree.h - intrusive, nonrecursive AVL tree data structure (self-balancing
3 * binary search tree), header file
5 * The following copying information applies to this specific source code file:
7 * Written in 2014 by Eric Biggers <ebiggers3@gmail.com>
9 * To the extent possible under law, the author(s) have dedicated all copyright
10 * and related and neighboring rights to this software to the public domain
11 * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
12 * Dedication (the "CC0").
14 * This software is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
18 * You should have received a copy of the CC0 along with this software; if not
19 * see <http://creativecommons.org/publicdomain/zero/1.0/>.
25 #include "wimlib/types.h"
27 /* Node in an AVL tree. Embed this in some other data structure. */
28 struct avl_tree_node {
30 /* Pointer to left child or NULL */
31 struct avl_tree_node *left;
33 /* Pointer to right child or NULL */
34 struct avl_tree_node *right;
36 /* Pointer to parent combined with the balance factor. This saves 4 or
37 * 8 bytes of memory depending on the CPU architecture.
39 * Low 2 bits: One greater than the balance factor of this subtree,
40 * which is equal to height(right) - height(left). The mapping is:
47 * The rest of the bits are the pointer to the parent node. It must be
48 * 4-byte aligned, and it will be NULL if this is the root node and
49 * therefore has no parent. */
50 uintptr_t parent_balance;
53 /* Cast an AVL tree node to the containing data structure. */
54 #define avl_tree_entry(entry, type, member) \
55 ((type*) ((char *)(entry) - offsetof(type, member)))
57 /* Returns a pointer to the parent of the specified AVL tree node, or NULL if it
58 * is already the root of the tree. */
59 static forceinline struct avl_tree_node *
60 avl_get_parent(const struct avl_tree_node *node)
62 return (struct avl_tree_node *)(node->parent_balance & ~3);
65 /* Marks the specified AVL tree node as unlinked from any tree. */
66 static forceinline void
67 avl_tree_node_set_unlinked(struct avl_tree_node *node)
69 node->parent_balance = (uintptr_t)node;
72 /* Returns true iff the specified AVL tree node has been marked with
73 * avl_tree_node_set_unlinked() and has not subsequently been inserted into a
75 static forceinline bool
76 avl_tree_node_is_unlinked(const struct avl_tree_node *node)
78 return node->parent_balance == (uintptr_t)node;
81 /* (Internal use only) */
83 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
84 struct avl_tree_node *inserted);
87 * Looks up an item in the specified AVL tree.
90 * Pointer to the root of the AVL tree. (This can be NULL --- that just
91 * means the tree is empty.)
94 * First argument to pass to the comparison callback. This generally
95 * should be a pointer to an object equal to the one being searched for.
98 * Comparison callback. Must return < 0, 0, or > 0 if the first argument
99 * is less than, equal to, or greater than the second argument,
100 * respectively. The first argument will be @cmp_ctx and the second
101 * argument will be a pointer to the AVL tree node of an item in the tree.
103 * Returns a pointer to the AVL tree node of the resulting item, or NULL if the
104 * item was not found.
108 * struct int_wrapper {
110 * struct avl_tree_node index_node;
113 * static int _avl_cmp_int_to_node(const void *intptr,
114 * const struct avl_tree_node *nodeptr)
116 * int n1 = *(const int *)intptr;
117 * int n2 = avl_tree_entry(nodeptr, struct int_wrapper, index_node)->data;
126 * bool contains_int(struct avl_tree_node *root, int n)
128 * struct avl_tree_node *result;
130 * result = avl_tree_lookup(root, &n, _avl_cmp_int_to_node);
131 * return result ? true : false;
134 static forceinline struct avl_tree_node *
135 avl_tree_lookup(const struct avl_tree_node *root,
137 int (*cmp)(const void *, const struct avl_tree_node *))
139 const struct avl_tree_node *cur = root;
142 int res = (*cmp)(cmp_ctx, cur);
150 return (struct avl_tree_node*)cur;
153 /* Same as avl_tree_lookup(), but uses a more specific type for the comparison
154 * function. Specifically, with this function the item being searched for is
155 * expected to be in the same format as those already in the tree, with an
156 * embedded 'struct avl_tree_node'. */
157 static forceinline struct avl_tree_node *
158 avl_tree_lookup_node(const struct avl_tree_node *root,
159 const struct avl_tree_node *node,
160 int (*cmp)(const struct avl_tree_node *,
161 const struct avl_tree_node *))
163 return avl_tree_lookup(root,
165 (int (*) (const void *,
166 const struct avl_tree_node *))cmp);
170 * Inserts an item into the specified AVL tree.
173 * Location of the AVL tree's root pointer. Indirection is needed because
174 * the root node may change as a result of rotations caused by the
175 * insertion. Initialize *root_ptr to NULL for an empty tree.
178 * Pointer to the `struct avl_tree_node' embedded in the item to insert.
179 * No members in it need be pre-initialized, although members in the
180 * containing structure should be pre-initialized so that @cmp can use them
184 * Comparison callback. Must return < 0, 0, or > 0 if the first argument
185 * is less than, equal to, or greater than the second argument,
186 * respectively. The first argument will be @item and the second
187 * argument will be a pointer to an AVL tree node embedded in some
188 * previously-inserted item to which @item is being compared.
190 * If no item in the tree is comparatively equal (via @cmp) to @item, inserts
191 * @item and returns NULL. Otherwise does nothing and returns a pointer to the
192 * AVL tree node embedded in the previously-inserted item which compared equal
197 * struct int_wrapper {
199 * struct avl_tree_node index_node;
202 * #define GET_DATA(i) avl_tree_entry((i), struct int_wrapper, index_node)->data
204 * static int _avl_cmp_ints(const struct avl_tree_node *node1,
205 * const struct avl_tree_node *node2)
207 * int n1 = GET_DATA(node1);
208 * int n2 = GET_DATA(node2);
217 * bool insert_int(struct avl_tree_node **root_ptr, int data)
219 * struct int_wrapper *i = malloc(sizeof(struct int_wrapper));
221 * if (avl_tree_insert(root_ptr, &i->index_node, _avl_cmp_ints)) {
229 static forceinline struct avl_tree_node *
230 avl_tree_insert(struct avl_tree_node **root_ptr,
231 struct avl_tree_node *item,
232 int (*cmp)(const struct avl_tree_node *,
233 const struct avl_tree_node *))
235 struct avl_tree_node **cur_ptr = root_ptr, *cur = NULL;
240 res = (*cmp)(item, cur);
242 cur_ptr = &cur->left;
244 cur_ptr = &cur->right;
249 item->parent_balance = (uintptr_t)cur | 1;
250 avl_tree_rebalance_after_insert(root_ptr, item);
254 /* Removes an item from the specified AVL tree.
255 * See implementation for details. */
257 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
259 /* Nonrecursive AVL tree traversal functions */
261 extern struct avl_tree_node *
262 avl_tree_first_in_order(const struct avl_tree_node *root);
264 extern struct avl_tree_node *
265 avl_tree_next_in_order(const struct avl_tree_node *prev);
267 extern struct avl_tree_node *
268 avl_tree_first_in_postorder(const struct avl_tree_node *root);
270 extern struct avl_tree_node *
271 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
272 const struct avl_tree_node *prev_parent);
275 * Iterate through the nodes in an AVL tree in sorted order.
276 * You may not modify the tree during the iteration.
279 * Variable that will receive a pointer to each struct inserted into the
282 * Root of the AVL tree.
284 * Type of *child_struct.
286 * Member of @struct_name type that is the AVL tree node.
290 * struct int_wrapper {
292 * struct avl_tree_node index_node;
295 * void print_ints(struct avl_tree_node *root)
297 * struct int_wrapper *i;
299 * avl_tree_for_each_in_order(i, root, struct int_wrapper, index_node)
300 * printf("%d\n", i->data);
303 #define avl_tree_for_each_in_order(child_struct, root, \
304 struct_name, struct_member) \
305 for (struct avl_tree_node *_cur = \
306 avl_tree_first_in_order(root); \
307 _cur && ((child_struct) = \
308 avl_tree_entry(_cur, struct_name, \
309 struct_member), 1); \
310 _cur = avl_tree_next_in_order(_cur))
313 * Like avl_tree_for_each_in_order(), but iterates through the nodes in
314 * postorder, so the current node may be deleted or freed.
316 #define avl_tree_for_each_in_postorder(child_struct, root, \
317 struct_name, struct_member) \
318 for (struct avl_tree_node *_cur = \
319 avl_tree_first_in_postorder(root), *_parent; \
320 _cur && ((child_struct) = \
321 avl_tree_entry(_cur, struct_name, \
323 && (_parent = avl_get_parent(_cur), 1); \
324 _cur = avl_tree_next_in_postorder(_cur, _parent))
326 #endif /* _AVL_TREE_H_ */