1 #pragma once
2
3 /*
4 * https://github.com/ebiggers/avl_tree
5 *
6 * iwavl.h - intrusive, nonrecursive AVL tree data structure (self-balancing
7 * binary search tree), header file
8 *
9 * Written in 2014-2016 by Eric Biggers <ebiggers3@gmail.com>
10 *
11 * To the extent possible under law, the author(s) have dedicated all copyright
12 * and related and neighboring rights to this software to the public domain
13 * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
14 * Dedication (the "CC0").
15 *
16 * This software is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18 * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
19 *
20 * You should have received a copy of the CC0 along with this software; if not
21 * see <http://creativecommons.org/publicdomain/zero/1.0/>.
22 */
23
24 #ifndef IWAVL_H
25 #define IWAVL_H
26
27 #include "basedefs.h"
28
29 /* Node in an AVL tree. Embed this in some other data structure. */
30 struct iwavl_node {
31 /* Pointer to left child or NULL */
32 struct iwavl_node *left;
33
34 /* Pointer to right child or NULL */
35 struct iwavl_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 iwavl_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. */
iwavl_get_parent(const struct iwavl_node * node)60 IW_INLINE struct iwavl_node* iwavl_get_parent(const struct iwavl_node *node) {
61 return (struct iwavl_node*) (node->parent_balance & ~3);
62 }
63
64 /* Marks the specified AVL tree node as unlinked from any tree. */
iwavl_node_set_unlinked(struct iwavl_node * node)65 IW_INLINE void iwavl_node_set_unlinked(struct iwavl_node *node) {
66 node->parent_balance = (uintptr_t) node;
67 }
68
69 /* Returns true iff the specified AVL tree node has been marked with
70 * iwavl_node_set_unlinked() and has not subsequently been inserted into a
71 * tree. */
iwavl_node_is_unlinked(const struct iwavl_node * node)72 IW_INLINE bool iwavl_node_is_unlinked(const struct iwavl_node *node) {
73 return node->parent_balance == (uintptr_t) node;
74 }
75
76 /* (Internal use only) */
77 extern void iwavl_rebalance_after_insert(
78 struct iwavl_node **root_ptr,
79 struct iwavl_node *inserted);
80
81 /*
82 * Looks up an item in the specified AVL tree.
83 *
84 * @root
85 * Pointer to the root of the AVL tree. (This can be NULL --- that just
86 * means the tree is empty.)
87 *
88 * @cmp_ctx
89 * First argument to pass to the comparison callback. This generally
90 * should be a pointer to an object equal to the one being searched for.
91 *
92 * @cmp
93 * Comparison callback. Must return < 0, 0, or > 0 if the first argument
94 * is less than, equal to, or greater than the second argument,
95 * respectively. The first argument will be @cmp_ctx and the second
96 * argument will be a pointer to the AVL tree node of an item in the tree.
97 *
98 * Returns a pointer to the AVL tree node of the resulting item, or NULL if the
99 * item was not found.
100 *
101 * Example:
102 *
103 * struct int_wrapper {
104 * int data;
105 * struct iwavl_node index_node;
106 * };
107 *
108 * static int _avl_cmp_int_to_node(const void *intptr,
109 * const struct iwavl_node *nodeptr)
110 * {
111 * int n1 = *(const int *)intptr;
112 * int n2 = iwavl_entry(nodeptr, struct int_wrapper, index_node)->data;
113 * if (n1 < n2)
114 * return -1;
115 * else if (n1 > n2)
116 * return 1;
117 * else
118 * return 0;
119 * }
120 *
121 * bool contains_int(struct iwavl_node *root, int n)
122 * {
123 * struct iwavl_node *result;
124 *
125 * result = iwavl_lookup(root, &n, _avl_cmp_int_to_node);
126 * return result ? true : false;
127 * }
128 */
iwavl_lookup(const struct iwavl_node * root,const void * cmp_ctx,int (* cmp)(const void *,const struct iwavl_node *))129 IW_INLINE struct iwavl_node* iwavl_lookup(
130 const struct iwavl_node *root,
131 const void *cmp_ctx,
132 int (*cmp)(const void*, const struct iwavl_node*)
133 ) {
134 const struct iwavl_node *cur = root;
135
136 while (cur) {
137 int res = (*cmp)(cmp_ctx, cur);
138 if (res < 0) {
139 cur = cur->left;
140 } else if (res > 0) {
141 cur = cur->right;
142 } else {
143 break;
144 }
145 }
146 return (struct iwavl_node*) cur;
147 }
148
iwavl_lookup_bounds(const struct iwavl_node * root,const void * cmp_ctx,int (* cmp)(const void *,const struct iwavl_node *),const struct iwavl_node ** lb,const struct iwavl_node ** ub)149 IW_INLINE void iwavl_lookup_bounds(
150 const struct iwavl_node *root,
151 const void *cmp_ctx,
152 int (*cmp)(const void*, const struct iwavl_node*),
153 const struct iwavl_node **lb,
154 const struct iwavl_node **ub
155 ) {
156 *lb = *ub = 0;
157 const struct iwavl_node *cur = root;
158
159 while (cur) {
160 int res = (*cmp)(cmp_ctx, cur);
161 if (res < 0) {
162 *ub = cur;
163 cur = cur->left;
164 } else if (res > 0) {
165 *lb = cur;
166 cur = cur->right;
167 } else {
168 *lb = *ub = cur;
169 break;
170 }
171 }
172 }
173
174 /* Same as iwavl_lookup(), but uses a more specific type for the comparison
175 * function. Specifically, with this function the item being searched for is
176 * expected to be in the same format as those already in the tree, with an
177 * embedded 'struct iwavl_node'. */
iwavl_lookup_node(const struct iwavl_node * root,const struct iwavl_node * node,int (* cmp)(const struct iwavl_node *,const struct iwavl_node *))178 IW_INLINE struct iwavl_node* iwavl_lookup_node(
179 const struct iwavl_node *root,
180 const struct iwavl_node *node,
181 int ( *cmp )(const struct iwavl_node*,
182 const struct iwavl_node*)
183 ) {
184 const struct iwavl_node *cur = root;
185
186 while (cur) {
187 int res = (*cmp)(node, cur);
188 if (res < 0) {
189 cur = cur->left;
190 } else if (res > 0) {
191 cur = cur->right;
192 } else {
193 break;
194 }
195 }
196 return (struct iwavl_node*) cur;
197 }
198
199 /*
200 * Inserts an item into the specified AVL tree.
201 *
202 * @root_ptr
203 * Location of the AVL tree's root pointer. Indirection is needed because
204 * the root node may change as a result of rotations caused by the
205 * insertion. Initialize *root_ptr to NULL for an empty tree.
206 *
207 * @item
208 * Pointer to the `struct iwavl_node' embedded in the item to insert.
209 * No members in it need be pre-initialized, although members in the
210 * containing structure should be pre-initialized so that @cmp can use them
211 * in comparisons.
212 *
213 * @cmp
214 * Comparison callback. Must return < 0, 0, or > 0 if the first argument
215 * is less than, equal to, or greater than the second argument,
216 * respectively. The first argument will be @item and the second
217 * argument will be a pointer to an AVL tree node embedded in some
218 * previously-inserted item to which @item is being compared.
219 *
220 * If no item in the tree is comparatively equal (via @cmp) to @item, inserts
221 * @item and returns NULL. Otherwise does nothing and returns a pointer to the
222 * AVL tree node embedded in the previously-inserted item which compared equal
223 * to @item.
224 *
225 * Example:
226 *
227 * struct int_wrapper {
228 * int data;
229 * struct iwavl_node index_node;
230 * };
231 *
232 * #define GET_DATA(i) iwavl_entry((i), struct int_wrapper, index_node)->data
233 *
234 * static int _avl_cmp_ints(const struct iwavl_node *node1,
235 * const struct iwavl_node *node2)
236 * {
237 * int n1 = GET_DATA(node1);
238 * int n2 = GET_DATA(node2);
239 * if (n1 < n2)
240 * return -1;
241 * else if (n1 > n2)
242 * return 1;
243 * else
244 * return 0;
245 * }
246 *
247 * bool insert_int(struct iwavl_node **root_ptr, int data)
248 * {
249 * struct int_wrapper *i = malloc(sizeof(struct int_wrapper));
250 * i->data = data;
251 * if (iwavl_insert(root_ptr, &i->index_node, _avl_cmp_ints)) {
252 * // Duplicate.
253 * free(i);
254 * return false;
255 * }
256 * return true;
257 * }
258 */
iwavl_insert(struct iwavl_node ** root_ptr,struct iwavl_node * item,int (* cmp)(const struct iwavl_node *,const struct iwavl_node *))259 IW_INLINE struct iwavl_node* iwavl_insert(
260 struct iwavl_node **root_ptr,
261 struct iwavl_node *item,
262 int ( *cmp )(const struct iwavl_node*,
263 const struct iwavl_node*)
264 ) {
265 struct iwavl_node **cur_ptr = root_ptr, *cur = NULL;
266 int res;
267
268 while (*cur_ptr) {
269 cur = *cur_ptr;
270 res = (*cmp)(item, cur);
271 if (res < 0) {
272 cur_ptr = &cur->left;
273 } else if (res > 0) {
274 cur_ptr = &cur->right;
275 } else {
276 return cur;
277 }
278 }
279 *cur_ptr = item;
280 item->parent_balance = (uintptr_t) cur | 1;
281 iwavl_rebalance_after_insert(root_ptr, item);
282 return NULL;
283 }
284
285 /* Removes an item from the specified AVL tree.
286 * See implementation for details. */
287 extern void iwavl_remove(struct iwavl_node **root_ptr, struct iwavl_node *node);
288
289 /* Nonrecursive AVL tree traversal functions */
290
291 extern struct iwavl_node* iwavl_first_in_order(const struct iwavl_node *root);
292
293 extern struct iwavl_node* iwavl_last_in_order(const struct iwavl_node *root);
294
295 extern struct iwavl_node* iwavl_next_in_order(const struct iwavl_node *node);
296
297 extern struct iwavl_node* iwavl_prev_in_order(const struct iwavl_node *node);
298
299 extern struct iwavl_node* iwavl_first_in_postorder(const struct iwavl_node *root);
300
301 extern struct iwavl_node* iwavl_next_in_postorder(
302 const struct iwavl_node *prev,
303 const struct iwavl_node *prev_parent);
304
305 /*
306 * Iterate through the nodes in an AVL tree in sorted order.
307 * You may not modify the tree during the iteration.
308 *
309 * @child_struct
310 * Variable that will receive a pointer to each struct inserted into the
311 * tree.
312 * @root
313 * Root of the AVL tree.
314 * @struct_name
315 * Type of *child_struct.
316 * @struct_member
317 * Member of @struct_name type that is the AVL tree node.
318 *
319 * Example:
320 *
321 * struct int_wrapper {
322 * int data;
323 * struct iwavl_node index_node;
324 * };
325 *
326 * void print_ints(struct iwavl_node *root)
327 * {
328 * struct int_wrapper *i;
329 *
330 * iwavl_for_each_in_order(i, root, struct int_wrapper, index_node)
331 * printf("%d\n", i->data);
332 * }
333 */
334 #define iwavl_for_each_in_order(child_struct, root, \
335 struct_name, struct_member) \
336 for (struct iwavl_node *_cur = \
337 iwavl_first_in_order(root); \
338 _cur && ((child_struct) = \
339 iwavl_entry(_cur, struct_name, \
340 struct_member), 1); \
341 _cur = iwavl_next_in_order(_cur))
342
343 /*
344 * Like iwavl_for_each_in_order(), but uses the reverse order.
345 */
346 #define iwavl_for_each_in_reverse_order(child_struct, root, \
347 struct_name, struct_member) \
348 for (struct iwavl_node *_cur = \
349 iwavl_last_in_order(root); \
350 _cur && ((child_struct) = \
351 iwavl_entry(_cur, struct_name, \
352 struct_member), 1); \
353 _cur = iwavl_prev_in_order(_cur))
354
355 /*
356 * Like iwavl_for_each_in_order(), but iterates through the nodes in
357 * postorder, so the current node may be deleted or freed.
358 */
359 #define iwavl_for_each_in_postorder(child_struct, root, \
360 struct_name, struct_member) \
361 for ( struct iwavl_node *_cur = \
362 iwavl_first_in_postorder(root), *_parent; \
363 _cur && ((child_struct) = \
364 iwavl_entry(_cur, struct_name, \
365 struct_member), 1) \
366 && (_parent = iwavl_get_parent(_cur), 1); \
367 _cur = iwavl_next_in_postorder(_cur, _parent))
368
369 #endif /* _AVL_TREE_H_ */
370