avl_tree: replace 'AVL_INLINE' with 'forceinline'
[wimlib] / include / wimlib / avl_tree.h
1 /*
2  * avl_tree.h - intrusive, nonrecursive AVL tree data structure (self-balancing
3  *              binary search tree), header file
4  *
5  * The following copying information applies to this specific source code file:
6  *
7  * Written in 2014 by Eric Biggers <ebiggers3@gmail.com>
8  *
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").
13  *
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.
17  *
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/>.
20  */
21
22 #ifndef _AVL_TREE_H_
23 #define _AVL_TREE_H_
24
25 #include "wimlib/types.h"
26
27 /* Node in an AVL tree.  Embed this in some other data structure.  */
28 struct avl_tree_node {
29
30         /* Pointer to left child or NULL  */
31         struct avl_tree_node *left;
32
33         /* Pointer to right child or NULL  */
34         struct avl_tree_node *right;
35
36         /* Pointer to parent combined with the balance factor.  This saves 4 or
37          * 8 bytes of memory depending on the CPU architecture.
38          *
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:
41          *
42          * 00 => -1
43          * 01 =>  0
44          * 10 => +1
45          * 11 => undefined
46          *
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;
51 };
52
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)))
56
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)
61 {
62         return (struct avl_tree_node *)(node->parent_balance & ~3);
63 }
64
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)
68 {
69         node->parent_balance = (uintptr_t)node;
70 }
71
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
74  * tree.  */
75 static forceinline bool
76 avl_tree_node_is_unlinked(const struct avl_tree_node *node)
77 {
78         return node->parent_balance == (uintptr_t)node;
79 }
80
81 /* (Internal use only)  */
82 extern void
83 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
84                                 struct avl_tree_node *inserted);
85
86 /*
87  * Looks up an item in the specified AVL tree.
88  *
89  * @root
90  *      Pointer to the root of the AVL tree.  (This can be NULL --- that just
91  *      means the tree is empty.)
92  *
93  * @cmp_ctx
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.
96  *
97  * @cmp
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.
102  *
103  * Returns a pointer to the AVL tree node of the resulting item, or NULL if the
104  * item was not found.
105  *
106  * Example:
107  *
108  * struct int_wrapper {
109  *      int data;
110  *      struct avl_tree_node index_node;
111  * };
112  *
113  * static int _avl_cmp_int_to_node(const void *intptr,
114  *                                 const struct avl_tree_node *nodeptr)
115  * {
116  *      int n1 = *(const int *)intptr;
117  *      int n2 = avl_tree_entry(nodeptr, struct int_wrapper, index_node)->data;
118  *      if (n1 < n2)
119  *              return -1;
120  *      else if (n1 > n2)
121  *              return 1;
122  *      else
123  *              return 0;
124  * }
125  *
126  * bool contains_int(struct avl_tree_node *root, int n)
127  * {
128  *      struct avl_tree_node *result;
129  *
130  *      result = avl_tree_lookup(root, &n, _avl_cmp_int_to_node);
131  *      return result ? true : false;
132  * }
133  */
134 static forceinline struct avl_tree_node *
135 avl_tree_lookup(const struct avl_tree_node *root,
136                 const void *cmp_ctx,
137                 int (*cmp)(const void *, const struct avl_tree_node *))
138 {
139         const struct avl_tree_node *cur = root;
140
141         while (cur) {
142                 int res = (*cmp)(cmp_ctx, cur);
143                 if (res < 0)
144                         cur = cur->left;
145                 else if (res > 0)
146                         cur = cur->right;
147                 else
148                         break;
149         }
150         return (struct avl_tree_node*)cur;
151 }
152
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 *))
162 {
163         return avl_tree_lookup(root,
164                                (const void *)node,
165                                (int (*) (const void *,
166                                          const struct avl_tree_node *))cmp);
167 }
168
169 /*
170  * Inserts an item into the specified AVL tree.
171  *
172  * @root_ptr
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.
176  *
177  * @item
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
181  *      in comparisons.
182  *
183  * @cmp
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.
189  *
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
193  * to @item.
194  *
195  * Example:
196  *
197  * struct int_wrapper {
198  *      int data;
199  *      struct avl_tree_node index_node;
200  * };
201  *
202  * #define GET_DATA(i) avl_tree_entry((i), struct int_wrapper, index_node)->data
203  *
204  * static int _avl_cmp_ints(const struct avl_tree_node *node1,
205  *                          const struct avl_tree_node *node2)
206  * {
207  *      int n1 = GET_DATA(node1);
208  *      int n2 = GET_DATA(node2);
209  *      if (n1 < n2)
210  *              return -1;
211  *      else if (n1 > n2)
212  *              return 1;
213  *      else
214  *              return 0;
215  * }
216  *
217  * bool insert_int(struct avl_tree_node **root_ptr, int data)
218  * {
219  *      struct int_wrapper *i = malloc(sizeof(struct int_wrapper));
220  *      i->data = data;
221  *      if (avl_tree_insert(root_ptr, &i->index_node, _avl_cmp_ints)) {
222  *              // Duplicate.
223  *              free(i);
224  *              return false;
225  *      }
226  *      return true;
227  * }
228  */
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 *))
234 {
235         struct avl_tree_node **cur_ptr = root_ptr, *cur = NULL;
236         int res;
237
238         while (*cur_ptr) {
239                 cur = *cur_ptr;
240                 res = (*cmp)(item, cur);
241                 if (res < 0)
242                         cur_ptr = &cur->left;
243                 else if (res > 0)
244                         cur_ptr = &cur->right;
245                 else
246                         return cur;
247         }
248         *cur_ptr = item;
249         item->parent_balance = (uintptr_t)cur | 1;
250         avl_tree_rebalance_after_insert(root_ptr, item);
251         return NULL;
252 }
253
254 /* Removes an item from the specified AVL tree.
255  * See implementation for details.  */
256 extern void
257 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
258
259 /* Nonrecursive AVL tree traversal functions  */
260
261 extern struct avl_tree_node *
262 avl_tree_first_in_order(const struct avl_tree_node *root);
263
264 extern struct avl_tree_node *
265 avl_tree_next_in_order(const struct avl_tree_node *prev);
266
267 extern struct avl_tree_node *
268 avl_tree_first_in_postorder(const struct avl_tree_node *root);
269
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);
273
274 /*
275  * Iterate through the nodes in an AVL tree in sorted order.
276  * You may not modify the tree during the iteration.
277  *
278  * @child_struct
279  *      Variable that will receive a pointer to each struct inserted into the
280  *      tree.
281  * @root
282  *      Root of the AVL tree.
283  * @struct_name
284  *      Type of *child_struct.
285  * @struct_member
286  *      Member of @struct_name type that is the AVL tree node.
287  *
288  * Example:
289  *
290  * struct int_wrapper {
291  *      int data;
292  *      struct avl_tree_node index_node;
293  * };
294  *
295  * void print_ints(struct avl_tree_node *root)
296  * {
297  *      struct int_wrapper *i;
298  *
299  *      avl_tree_for_each_in_order(i, root, struct int_wrapper, index_node)
300  *              printf("%d\n", i->data);
301  * }
302  */
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))
311
312 /*
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.
315  */
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,                 \
322                                      struct_member), 1)                 \
323                   && (_parent = avl_get_parent(_cur), 1);               \
324              _cur = avl_tree_next_in_postorder(_cur, _parent))
325
326 #endif /* _AVL_TREE_H_ */