875c9f02a83da8f51acf594f47d02b14a4da3b15
[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 #endif
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 note 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 /* Extracts the parent pointer from the specified AVL tree node.
58  * Returns the parent pointer, or NULL if @node is the root node.  */
59 static AVL_INLINE 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 /* Mark the node as unlinked from any tree.  */
66 static AVL_INLINE 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 node has been marked with
73  * avl_tree_node_set_unlinked() and has not subsequently been inserted into a
74  * tree.  */
75 static AVL_INLINE 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  * Look up an item in an 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 --- generally a
95  *      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 embedded in the resulting item, or
104  * NULL if the item was not found.
105  */
106 static AVL_INLINE struct avl_tree_node *
107 avl_tree_lookup(const struct avl_tree_node *root,
108                 const void *cmp_ctx,
109                 int (*cmp)(const void *, const struct avl_tree_node *))
110 {
111         const struct avl_tree_node *cur = root;
112
113         while (cur) {
114                 int res = (*cmp)(cmp_ctx, cur);
115                 if (res < 0)
116                         cur = cur->left;
117                 else if (res > 0)
118                         cur = cur->right;
119                 else
120                         break;
121         }
122         return (struct avl_tree_node*)cur;
123 }
124
125 /* Same as avl_tree_lookup(), just uses a more specific type for the comparison
126  * function.  Specifically, the item being searched for is expected to be in the
127  * same format as those already in the tree, with an embedded 'struct
128  * avl_tree_node'.  */
129 static AVL_INLINE struct avl_tree_node *
130 avl_tree_lookup_node(const struct avl_tree_node *root,
131                      const struct avl_tree_node *node,
132                      int (*cmp)(const struct avl_tree_node *,
133                                 const struct avl_tree_node *))
134 {
135         return avl_tree_lookup(root,
136                                (const void *)node,
137                                (int (*) (const void *,
138                                          const struct avl_tree_node *))cmp);
139 }
140
141 /*
142  * Insert an item into an AVL tree.
143  *
144  * @root_ptr
145  *      Pointer to the pointer to the root of the AVL tree.  (Indirection is
146  *      needed because the root node may change.)  Initialize *root_ptr to NULL
147  *      for an empty tree.
148  *
149  * @item
150  *      Pointer to the `struct avl_tree_node' embedded in the item to insert.
151  *      No members in it need be pre-initialized, although members in the
152  *      containing structure should be pre-initialized so that @cmp can use them
153  *      in comparisons.
154  *
155  * @cmp
156  *      Comparison callback.  Must return < 0, 0, or > 0 if the first argument
157  *      is less than, equal to, or greater than the second argument,
158  *      respectively.  The first argument will be @item and the second
159  *      argument will be a pointer to an AVL tree node embedded in some
160  *      previously-inserted item that @item is being compared with.
161  *
162  * Returns NULL if the item was successfully inserted, otherwise the node of a
163  * previously-inserted item which compared equal to @item and prevented the new
164  * insertion of @item.
165  */
166 static AVL_INLINE struct avl_tree_node *
167 avl_tree_insert(struct avl_tree_node **root_ptr,
168                 struct avl_tree_node *item,
169                 int (*cmp)(const struct avl_tree_node *,
170                            const struct avl_tree_node *))
171 {
172         struct avl_tree_node **cur_ptr = root_ptr, *cur = NULL;
173         int res;
174
175         while (*cur_ptr) {
176                 cur = *cur_ptr;
177                 res = (*cmp)(item, cur);
178                 if (res < 0)
179                         cur_ptr = &cur->left;
180                 else if (res > 0)
181                         cur_ptr = &cur->right;
182                 else
183                         return cur;
184         }
185         *cur_ptr = item;
186         item->parent_balance = (uintptr_t)cur | 1;
187         avl_tree_rebalance_after_insert(root_ptr, item);
188         return NULL;
189 }
190
191 extern void
192 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node);
193
194 /* Nonrecursive AVL tree traversal functions  */
195
196 extern struct avl_tree_node *
197 avl_tree_first_in_order(const struct avl_tree_node *root);
198
199 extern struct avl_tree_node *
200 avl_tree_next_in_order(const struct avl_tree_node *prev);
201
202 extern struct avl_tree_node *
203 avl_tree_first_in_postorder(const struct avl_tree_node *root);
204
205 extern struct avl_tree_node *
206 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
207                            const struct avl_tree_node *prev_parent);
208
209 #endif /* _AVL_TREE_H_ */