7d13966f33e3d5eeb140e4784903aab963ec937e
[wimlib] / include / wimlib / avl_tree.h
1 /*
2  * avl_tree.h
3  *
4  * Intrusive, nonrecursive AVL tree data structure (self-balancing binary search
5  * tree), header file.
6  *
7  * Author:  Eric Biggers
8  * Year:    2014
9  *
10  * This file is placed into the public domain.  You can do whatever you want
11  * with it.
12  */
13
14 #ifndef _AVL_TREE_H_
15 #define _AVL_TREE_H_
16
17 #include <stdbool.h>
18 #include <stddef.h>
19 #include <inttypes.h> /* for uintptr_t */
20
21 #ifdef __GNUC__
22 #  define AVL_INLINE inline __attribute__((always_inline))
23 #else
24 #  define AVL_INLINE inline
25 #  warning "AVL tree functions may not be inlined as intended"
26 #endif
27
28 /* Node in an AVL tree.  Embed this in some other data structure.  */
29 struct avl_tree_node {
30
31         /* Pointer to left child or NULL  */
32         struct avl_tree_node *left;
33
34         /* Pointer to right child or NULL  */
35         struct avl_tree_node *right;
36
37         /* Pointer to parent combined with the balance factor.  This saves 4 or
38          * 8 bytes of memory depending on the CPU architecture.
39          *
40          * Low 2 bits:  One greater than the balance factor of this subtree,
41          * which is equal to height(right) - height(left).  The mapping is:
42          *
43          * 00 => -1
44          * 01 =>  0
45          * 10 => +1
46          * 11 => undefined
47          *
48          * The rest of the bits are the pointer to the parent node.  It must be
49          * 4-byte aligned, and it will be NULL if this is the root node and
50          * therefore has no parent.  */
51         uintptr_t parent_balance;
52 };
53
54 /* Cast an AVL tree node to the containing data structure.  */
55 #define avl_tree_entry(entry, type, member) \
56         ((type*) ((char *)(entry) - offsetof(type, member)))
57
58 /* Returns a pointer to the parent of the specified AVL tree node, or NULL if it
59  * is already the root of the tree.  */
60 static AVL_INLINE struct avl_tree_node *
61 avl_get_parent(const struct avl_tree_node *node)
62 {
63         return (struct avl_tree_node *)(node->parent_balance & ~3);
64 }
65
66 /* Marks the specified AVL tree node as unlinked from any tree.  */
67 static AVL_INLINE void
68 avl_tree_node_set_unlinked(struct avl_tree_node *node)
69 {
70         node->parent_balance = (uintptr_t)node;
71 }
72
73 /* Returns true iff the specified AVL tree node has been marked with
74  * avl_tree_node_set_unlinked() and has not subsequently been inserted into a
75  * tree.  */
76 static AVL_INLINE bool
77 avl_tree_node_is_unlinked(const struct avl_tree_node *node)
78 {
79         return node->parent_balance == (uintptr_t)node;
80 }
81
82 /* (Internal use only)  */
83 extern void
84 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
85                                 struct avl_tree_node *inserted);
86
87 /*
88  * Looks up an item in the specified AVL tree.
89  *
90  * @root
91  *      Pointer to the root of the AVL tree.  (This can be NULL --- that just
92  *      means the tree is empty.)
93  *
94  * @cmp_ctx
95  *      First argument to pass to the comparison callback.  This generally
96  *      should be a pointer to an object equal to the one being searched for.
97  *
98  * @cmp
99  *      Comparison callback.  Must return < 0, 0, or > 0 if the first argument
100  *      is less than, equal to, or greater than the second argument,
101  *      respectively.  The first argument will be @cmp_ctx and the second
102  *      argument will be a pointer to the AVL tree node of an item in the tree.
103  *
104  * Returns a pointer to the AVL tree node of the resulting item, or NULL if the
105  * item was not found.
106  */
107 static AVL_INLINE struct avl_tree_node *
108 avl_tree_lookup(const struct avl_tree_node *root,
109                 const void *cmp_ctx,
110                 int (*cmp)(const void *, const struct avl_tree_node *))
111 {
112         const struct avl_tree_node *cur = root;
113
114         while (cur) {
115                 int res = (*cmp)(cmp_ctx, cur);
116                 if (res < 0)
117                         cur = cur->left;
118                 else if (res > 0)
119                         cur = cur->right;
120                 else
121                         break;
122         }
123         return (struct avl_tree_node*)cur;
124 }
125
126 /* Same as avl_tree_lookup(), but uses a more specific type for the comparison
127  * function.  Specifically, with this function the item being searched for is
128  * expected to be in the same format as those already in the tree, with an
129  * embedded 'struct avl_tree_node'.  */
130 static AVL_INLINE struct avl_tree_node *
131 avl_tree_lookup_node(const struct avl_tree_node *root,
132                      const struct avl_tree_node *node,
133                      int (*cmp)(const struct avl_tree_node *,
134                                 const struct avl_tree_node *))
135 {
136         return avl_tree_lookup(root,
137                                (const void *)node,
138                                (int (*) (const void *,
139                                          const struct avl_tree_node *))cmp);
140 }
141
142 /*
143  * Inserts an item into the specified AVL tree.
144  *
145  * @root_ptr
146  *      Location of the AVL tree's root pointer.  Indirection is needed because
147  *      the root node may change as a result of rotations caused by the
148  *      insertion.  Initialize *root_ptr to NULL for an empty tree.
149  *
150  * @item
151  *      Pointer to the `struct avl_tree_node' embedded in the item to insert.
152  *      No members in it need be pre-initialized, although members in the
153  *      containing structure should be pre-initialized so that @cmp can use them
154  *      in comparisons.
155  *
156  * @cmp
157  *      Comparison callback.  Must return < 0, 0, or > 0 if the first argument
158  *      is less than, equal to, or greater than the second argument,
159  *      respectively.  The first argument will be @item and the second
160  *      argument will be a pointer to an AVL tree node embedded in some
161  *      previously-inserted item to which @item is being compared.
162  *
163  * If no item in the tree is comparatively equal (via @cmp) to @item, inserts
164  * @item and returns NULL.  Otherwise does nothing and returns a pointer to the
165  * AVL tree node embedded in the previously-inserted item which compared equal
166  * to @item.
167  */
168 static AVL_INLINE struct avl_tree_node *
169 avl_tree_insert(struct avl_tree_node **root_ptr,
170                 struct avl_tree_node *item,
171                 int (*cmp)(const struct avl_tree_node *,
172                            const struct avl_tree_node *))
173 {
174         struct avl_tree_node **cur_ptr = root_ptr, *cur = NULL;
175         int res;
176
177         while (*cur_ptr) {
178                 cur = *cur_ptr;
179                 res = (*cmp)(item, cur);
180                 if (res < 0)
181                         cur_ptr = &cur->left;
182                 else if (res > 0)
183                         cur_ptr = &cur->right;
184                 else
185                         return cur;
186         }
187         *cur_ptr = item;
188         item->parent_balance = (uintptr_t)cur | 1;
189         avl_tree_rebalance_after_insert(root_ptr, item);
190         return NULL;
191 }
192
193 /* Removes an item from the specified AVL tree.
194  * See implementation for details.  */
195 extern void
196 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
197
198 /* Nonrecursive AVL tree traversal functions  */
199
200 extern struct avl_tree_node *
201 avl_tree_first_in_order(const struct avl_tree_node *root);
202
203 extern struct avl_tree_node *
204 avl_tree_next_in_order(const struct avl_tree_node *prev);
205
206 extern struct avl_tree_node *
207 avl_tree_first_in_postorder(const struct avl_tree_node *root);
208
209 extern struct avl_tree_node *
210 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
211                            const struct avl_tree_node *prev_parent);
212
213 #endif /* _AVL_TREE_H_ */