Use more comprehensive public domain dedications
[wimlib] / src / avl_tree.c
1 /*
2  * avl_tree.c - intrusive, nonrecursive AVL tree data structure (self-balancing
3  *              binary search tree), implementation 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 #ifdef HAVE_CONFIG_H
23 #  include "config.h"
24 #endif
25
26 #include "wimlib/avl_tree.h"
27
28 /* Starts an in-order traversal of the tree: returns the least-valued node, or
29  * NULL if the tree is empty.  */
30 struct avl_tree_node *
31 avl_tree_first_in_order(const struct avl_tree_node *root)
32 {
33         const struct avl_tree_node *first = root;
34
35         if (first)
36                 while (first->left)
37                         first = first->left;
38         return (struct avl_tree_node *)first;
39 }
40
41 /* Continues an in-order traversal of the tree: returns the next-greatest-valued
42  * node, or NULL if there is none.  */
43 struct avl_tree_node *
44 avl_tree_next_in_order(const struct avl_tree_node *prev)
45 {
46         const struct avl_tree_node *next;
47
48         if (prev->right)
49                 for (next = prev->right;
50                      next->left;
51                      next = next->left)
52                         ;
53         else
54                 for (next = avl_get_parent(prev);
55                      next && prev == next->right;
56                      prev = next, next = avl_get_parent(next))
57                         ;
58         return (struct avl_tree_node *)next;
59 }
60
61 /* Starts a postorder traversal of the tree.  */
62 struct avl_tree_node *
63 avl_tree_first_in_postorder(const struct avl_tree_node *root)
64 {
65         const struct avl_tree_node *first = root;
66
67         if (first)
68                 while (first->left || first->right)
69                         first = first->left ? first->left : first->right;
70
71         return (struct avl_tree_node *)first;
72 }
73
74 /* Continues a postorder traversal of the tree.  @prev will not be deferenced as
75  * it's allowed that its memory has been freed; @prev_parent must be its saved
76  * parent node.  Returns NULL if there are no more nodes (i.e. @prev was the
77  * root of the tree).  */
78 struct avl_tree_node *
79 avl_tree_next_in_postorder(const struct avl_tree_node *prev,
80                            const struct avl_tree_node *prev_parent)
81 {
82         const struct avl_tree_node *next = prev_parent;
83
84         if (next && prev == next->left && next->right)
85                 for (next = next->right;
86                      next->left || next->right;
87                      next = next->left ? next->left : next->right)
88                         ;
89         return (struct avl_tree_node *)next;
90 }
91
92 /* Returns the left child (sign < 0) or the right child (sign > 0) of the
93  * specified AVL tree node.
94  * Note: for all calls of this, 'sign' is constant at compilation time,
95  * so the compiler can remove the conditional.  */
96 static AVL_INLINE struct avl_tree_node *
97 avl_get_child(const struct avl_tree_node *parent, int sign)
98 {
99         if (sign < 0)
100                 return parent->left;
101         else
102                 return parent->right;
103 }
104
105 /* Sets the left child (sign < 0) or the right child (sign > 0) of the
106  * specified AVL tree node.
107  * Note: for all calls of this, 'sign' is constant at compilation time,
108  * so the compiler can remove the conditional.  */
109 static AVL_INLINE void
110 avl_set_child(struct avl_tree_node *parent, int sign,
111               struct avl_tree_node *child)
112 {
113         if (sign < 0)
114                 parent->left = child;
115         else
116                 parent->right = child;
117 }
118
119 /* Sets the parent and balance factor of the specified AVL tree node.  */
120 static AVL_INLINE void
121 avl_set_parent_balance(struct avl_tree_node *node, struct avl_tree_node *parent,
122                        int balance_factor)
123 {
124         node->parent_balance = (uintptr_t)parent | (balance_factor + 1);
125 }
126
127 /* Sets the parent of the specified AVL tree node.  */
128 static AVL_INLINE void
129 avl_set_parent(struct avl_tree_node *node, struct avl_tree_node *parent)
130 {
131         node->parent_balance = (uintptr_t)parent | (node->parent_balance & 3);
132 }
133
134 /* Returns the balance factor of the specified AVL tree node --- that is, the
135  * height of its right subtree minus the height of its left subtree.  */
136 static AVL_INLINE int
137 avl_get_balance_factor(const struct avl_tree_node *node)
138 {
139         return (int)(node->parent_balance & 3) - 1;
140 }
141
142 /* Adds @amount to the balance factor of the specified AVL tree node.
143  * The caller must ensure this still results in a valid balance factor
144  * (-1, 0, or 1).  */
145 static AVL_INLINE void
146 avl_adjust_balance_factor(struct avl_tree_node *node, int amount)
147 {
148         node->parent_balance += amount;
149 }
150
151 static AVL_INLINE void
152 avl_replace_child(struct avl_tree_node **root_ptr,
153                   struct avl_tree_node *parent,
154                   struct avl_tree_node *old_child,
155                   struct avl_tree_node *new_child)
156 {
157         if (parent) {
158                 if (old_child == parent->left)
159                         parent->left = new_child;
160                 else
161                         parent->right = new_child;
162         } else {
163                 *root_ptr = new_child;
164         }
165 }
166
167 /*
168  * Template for performing a single rotation ---
169  *
170  * sign > 0:  Rotate clockwise (right) rooted at A:
171  *
172  *           P?            P?
173  *           |             |
174  *           A             B
175  *          / \           / \
176  *         B   C?  =>    D?  A
177  *        / \               / \
178  *       D?  E?            E?  C?
179  *
180  * (nodes marked with ? may not exist)
181  *
182  * sign < 0:  Rotate counterclockwise (left) rooted at A:
183  *
184  *           P?            P?
185  *           |             |
186  *           A             B
187  *          / \           / \
188  *         C?  B   =>    A   D?
189  *            / \       / \
190  *           E?  D?    C?  E?
191  *
192  * This updates pointers but not balance factors!
193  */
194 static AVL_INLINE void
195 avl_rotate(struct avl_tree_node ** const root_ptr,
196            struct avl_tree_node * const A, const int sign)
197 {
198         struct avl_tree_node * const B = avl_get_child(A, -sign);
199         struct avl_tree_node * const E = avl_get_child(B, +sign);
200         struct avl_tree_node * const P = avl_get_parent(A);
201
202         avl_set_child(A, -sign, E);
203         avl_set_parent(A, B);
204
205         avl_set_child(B, +sign, A);
206         avl_set_parent(B, P);
207
208         if (E)
209                 avl_set_parent(E, A);
210
211         avl_replace_child(root_ptr, P, A, B);
212 }
213
214 /*
215  * Template for performing a double rotation ---
216  *
217  * sign > 0:  Rotate counterclockwise (left) rooted at B, then
218  *                   clockwise (right) rooted at A:
219  *
220  *           P?            P?          P?
221  *           |             |           |
222  *           A             A           E
223  *          / \           / \        /   \
224  *         B   C?  =>    E   C? =>  B     A
225  *        / \           / \        / \   / \
226  *       D?  E         B   G?     D?  F?G?  C?
227  *          / \       / \
228  *         F?  G?    D?  F?
229  *
230  * (nodes marked with ? may not exist)
231  *
232  * sign < 0:  Rotate clockwise (right) rooted at B, then
233  *                   counterclockwise (left) rooted at A:
234  *
235  *         P?          P?              P?
236  *         |           |               |
237  *         A           A               E
238  *        / \         / \            /   \
239  *       C?  B   =>  C?  E    =>    A     B
240  *          / \         / \        / \   / \
241  *         E   D?      G?  B      C?  G?F?  D?
242  *        / \             / \
243  *       G?  F?          F?  D?
244  *
245  * Returns a pointer to E and updates balance factors.  Except for those
246  * two things, this function is equivalent to:
247  *      avl_rotate(root_ptr, B, -sign);
248  *      avl_rotate(root_ptr, A, +sign);
249  *
250  * See comment in avl_handle_subtree_growth() for explanation of balance
251  * factor updates.
252  */
253 static AVL_INLINE struct avl_tree_node *
254 avl_do_double_rotate(struct avl_tree_node ** const root_ptr,
255                      struct avl_tree_node * const B,
256                      struct avl_tree_node * const A, const int sign)
257 {
258         struct avl_tree_node * const E = avl_get_child(B, +sign);
259         struct avl_tree_node * const F = avl_get_child(E, -sign);
260         struct avl_tree_node * const G = avl_get_child(E, +sign);
261         struct avl_tree_node * const P = avl_get_parent(A);
262         const int e = avl_get_balance_factor(E);
263
264         avl_set_child(A, -sign, G);
265         avl_set_parent_balance(A, E, ((sign * e >= 0) ? 0 : -e));
266
267         avl_set_child(B, +sign, F);
268         avl_set_parent_balance(B, E, ((sign * e <= 0) ? 0 : -e));
269
270         avl_set_child(E, +sign, A);
271         avl_set_child(E, -sign, B);
272         avl_set_parent_balance(E, P, 0);
273
274         if (G)
275                 avl_set_parent(G, A);
276
277         if (F)
278                 avl_set_parent(F, B);
279
280         avl_replace_child(root_ptr, P, A, E);
281
282         return E;
283 }
284
285 /*
286  * This function handles the growth of a subtree due to an insertion.
287  *
288  * @root_ptr
289  *      Location of the tree's root pointer.
290  *
291  * @node
292  *      A subtree that has increased in height by 1 due to an insertion.
293  *
294  * @parent
295  *      Parent of @node; must not be NULL.
296  *
297  * @sign
298  *      -1 if @node is the left child of @parent;
299  *      +1 if @node is the right child of @parent.
300  *
301  * This function will adjust @parent's balance factor, then do a (single
302  * or double) rotation if necessary.  The return value will be %true if
303  * the full AVL tree is now adequately balanced, or %false if the subtree
304  * rooted at @parent is now adequately balanced but has increased in
305  * height by 1, so the caller should continue up the tree.
306  *
307  * Note that if %false is returned, no rotation will have been done.
308  * Indeed, a single node insertion cannot require that more than one
309  * (single or double) rotation be done.
310  */
311 static AVL_INLINE bool
312 avl_handle_subtree_growth(struct avl_tree_node ** const root_ptr,
313                           struct avl_tree_node * const node,
314                           struct avl_tree_node * const parent,
315                           const int sign)
316 {
317         int old_balance_factor, new_balance_factor;
318
319         old_balance_factor = avl_get_balance_factor(parent);
320
321         if (old_balance_factor == 0) {
322                 avl_adjust_balance_factor(parent, sign);
323                 /* @parent is still sufficiently balanced (-1 or +1
324                  * balance factor), but must have increased in height.
325                  * Continue up the tree.  */
326                 return false;
327         }
328
329         new_balance_factor = old_balance_factor + sign;
330
331         if (new_balance_factor == 0) {
332                 avl_adjust_balance_factor(parent, sign);
333                 /* @parent is now perfectly balanced (0 balance factor).
334                  * It cannot have increased in height, so there is
335                  * nothing more to do.  */
336                 return true;
337         }
338
339         /* @parent is too left-heavy (new_balance_factor == -2) or
340          * too right-heavy (new_balance_factor == +2).  */
341
342         /* Test whether @node is left-heavy (-1 balance factor) or
343          * right-heavy (+1 balance factor).
344          * Note that it cannot be perfectly balanced (0 balance factor)
345          * because here we are under the invariant that @node has
346          * increased in height due to the insertion.  */
347         if (sign * avl_get_balance_factor(node) > 0) {
348
349                 /* @node (B below) is heavy in the same direction @parent
350                  * (A below) is heavy.
351                  *
352                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
353                  * The comment, diagram, and equations below assume sign < 0.
354                  * The other case is symmetric!
355                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
356                  *
357                  * Do a clockwise rotation rooted at @parent (A below):
358                  *
359                  *           A              B
360                  *          / \           /   \
361                  *         B   C?  =>    D     A
362                  *        / \           / \   / \
363                  *       D   E?        F?  G?E?  C?
364                  *      / \
365                  *     F?  G?
366                  *
367                  * Before the rotation:
368                  *      balance(A) = -2
369                  *      balance(B) = -1
370                  * Let x = height(C).  Then:
371                  *      height(B) = x + 2
372                  *      height(D) = x + 1
373                  *      height(E) = x
374                  *      max(height(F), height(G)) = x.
375                  *
376                  * After the rotation:
377                  *      height(D) = max(height(F), height(G)) + 1
378                  *                = x + 1
379                  *      height(A) = max(height(E), height(C)) + 1
380                  *                = max(x, x) + 1 = x + 1
381                  *      balance(B) = 0
382                  *      balance(A) = 0
383                  */
384                 avl_rotate(root_ptr, parent, -sign);
385
386                 /* Equivalent to setting @parent's balance factor to 0.  */
387                 avl_adjust_balance_factor(parent, -sign); /* A */
388
389                 /* Equivalent to setting @node's balance factor to 0.  */
390                 avl_adjust_balance_factor(node, -sign);   /* B */
391         } else {
392                 /* @node (B below) is heavy in the direction opposite
393                  * from the direction @parent (A below) is heavy.
394                  *
395                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
396                  * The comment, diagram, and equations below assume sign < 0.
397                  * The other case is symmetric!
398                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
399                  *
400                  * Do a counterblockwise rotation rooted at @node (B below),
401                  * then a clockwise rotation rooted at @parent (A below):
402                  *
403                  *           A             A           E
404                  *          / \           / \        /   \
405                  *         B   C?  =>    E   C? =>  B     A
406                  *        / \           / \        / \   / \
407                  *       D?  E         B   G?     D?  F?G?  C?
408                  *          / \       / \
409                  *         F?  G?    D?  F?
410                  *
411                  * Before the rotation:
412                  *      balance(A) = -2
413                  *      balance(B) = +1
414                  * Let x = height(C).  Then:
415                  *      height(B) = x + 2
416                  *      height(E) = x + 1
417                  *      height(D) = x
418                  *      max(height(F), height(G)) = x
419                  *
420                  * After both rotations:
421                  *      height(A) = max(height(G), height(C)) + 1
422                  *                = x + 1
423                  *      balance(A) = balance(E{orig}) >= 0 ? 0 : -balance(E{orig})
424                  *      height(B) = max(height(D), height(F)) + 1
425                  *                = x + 1
426                  *      balance(B) = balance(E{orig} <= 0) ? 0 : -balance(E{orig})
427                  *
428                  *      height(E) = x + 2
429                  *      balance(E) = 0
430                  */
431                 avl_do_double_rotate(root_ptr, node, parent, -sign);
432         }
433
434         /* Height after rotation is unchanged; nothing more to do.  */
435         return true;
436 }
437
438 /* Rebalance the tree after insertion of the specified node.  */
439 void
440 avl_tree_rebalance_after_insert(struct avl_tree_node **root_ptr,
441                                 struct avl_tree_node *inserted)
442 {
443         struct avl_tree_node *node, *parent;
444         bool done;
445
446         inserted->left = NULL;
447         inserted->right = NULL;
448
449         node = inserted;
450
451         /* Adjust balance factor of new node's parent.
452          * No rotation will need to be done at this level.  */
453
454         parent = avl_get_parent(node);
455         if (!parent)
456                 return;
457
458         if (node == parent->left)
459                 avl_adjust_balance_factor(parent, -1);
460         else
461                 avl_adjust_balance_factor(parent, +1);
462
463         if (avl_get_balance_factor(parent) == 0)
464                 /* @parent did not change in height.  Nothing more to do.  */
465                 return;
466
467         /* The subtree rooted at @parent increased in height by 1.  */
468
469         do {
470                 /* Adjust balance factor of next ancestor.  */
471
472                 node = parent;
473                 parent = avl_get_parent(node);
474                 if (!parent)
475                         return;
476
477                 /* The subtree rooted at @node has increased in height by 1.  */
478                 if (node == parent->left)
479                         done = avl_handle_subtree_growth(root_ptr, node,
480                                                          parent, -1);
481                 else
482                         done = avl_handle_subtree_growth(root_ptr, node,
483                                                          parent, +1);
484         } while (!done);
485 }
486
487 /*
488  * This function handles the shrinkage of a subtree due to a deletion.
489  *
490  * @root_ptr
491  *      Location of the tree's root pointer.
492  *
493  * @parent
494  *      A node in the tree, exactly one of whose subtrees has decreased
495  *      in height by 1 due to a deletion.  (This includes the case where
496  *      one of the child pointers has become NULL, since we can consider
497  *      the "NULL" subtree to have a height of 0.)
498  *
499  * @sign
500  *      +1 if the left subtree of @parent has decreased in height by 1;
501  *      -1 if the right subtree of @parent has decreased in height by 1.
502  *
503  * @left_deleted_ret
504  *      If the return value is not NULL, this will be set to %true if the
505  *      left subtree of the returned node has decreased in height by 1,
506  *      or %false if the right subtree of the returned node has decreased
507  *      in height by 1.
508  *
509  * This function will adjust @parent's balance factor, then do a (single
510  * or double) rotation if necessary.  The return value will be NULL if
511  * the full AVL tree is now adequately balanced, or a pointer to the
512  * parent of @parent if @parent is now adequately balanced but has
513  * decreased in height by 1.  Also in the latter case, *left_deleted_ret
514  * will be set.
515  */
516 static AVL_INLINE struct avl_tree_node *
517 avl_handle_subtree_shrink(struct avl_tree_node ** const root_ptr,
518                           struct avl_tree_node *parent,
519                           const int sign,
520                           bool * const left_deleted_ret)
521 {
522         struct avl_tree_node *node;
523         int old_balance_factor, new_balance_factor;
524
525         old_balance_factor = avl_get_balance_factor(parent);
526
527         if (old_balance_factor == 0) {
528                 /* Prior to the deletion, the subtree rooted at
529                  * @parent was perfectly balanced.  It's now
530                  * unbalanced by 1, but that's okay and its height
531                  * hasn't changed.  Nothing more to do.  */
532                 avl_adjust_balance_factor(parent, sign);
533                 return NULL;
534         }
535
536         new_balance_factor = old_balance_factor + sign;
537
538         if (new_balance_factor == 0) {
539                 /* The subtree rooted at @parent is now perfectly
540                  * balanced, whereas before the deletion it was
541                  * unbalanced by 1.  Its height must have decreased
542                  * by 1.  No rotation is needed at this location,
543                  * but continue up the tree.  */
544                 avl_adjust_balance_factor(parent, sign);
545                 node = parent;
546         } else {
547                 /* @parent is too left-heavy (new_balance_factor == -2) or
548                  * too right-heavy (new_balance_factor == +2).  */
549
550                 node = avl_get_child(parent, sign);
551
552                 /* The rotations below are similar to those done during
553                  * insertion (see avl_handle_subtree_growth()), so full
554                  * comments are not provided.  The only new case is the
555                  * one where @node has a balance factor of 0, and that is
556                  * commented.  */
557
558                 if (sign * avl_get_balance_factor(node) >= 0) {
559
560                         avl_rotate(root_ptr, parent, -sign);
561
562                         if (avl_get_balance_factor(node) == 0) {
563                                 /*
564                                  * @node (B below) is perfectly balanced.
565                                  *
566                                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
567                                  * The comment, diagram, and equations
568                                  * below assume sign < 0.  The other case
569                                  * is symmetric!
570                                  * @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
571                                  *
572                                  * Do a clockwise rotation rooted at
573                                  * @parent (A below):
574                                  *
575                                  *           A              B
576                                  *          / \           /   \
577                                  *         B   C?  =>    D     A
578                                  *        / \           / \   / \
579                                  *       D   E         F?  G?E   C?
580                                  *      / \
581                                  *     F?  G?
582                                  *
583                                  * Before the rotation:
584                                  *      balance(A) = -2
585                                  *      balance(B) =  0
586                                  * Let x = height(C).  Then:
587                                  *      height(B) = x + 2
588                                  *      height(D) = x + 1
589                                  *      height(E) = x + 1
590                                  *      max(height(F), height(G)) = x.
591                                  *
592                                  * After the rotation:
593                                  *      height(D) = max(height(F), height(G)) + 1
594                                  *                = x + 1
595                                  *      height(A) = max(height(E), height(C)) + 1
596                                  *                = max(x + 1, x) + 1 = x + 2
597                                  *      balance(A) = -1
598                                  *      balance(B) = +1
599                                  */
600
601                                 /* A: -2 => -1 (sign < 0)
602                                  * or +2 => +1 (sign > 0)
603                                  * No change needed --- that's the same as
604                                  * old_balance_factor.  */
605
606                                 /* B: 0 => +1 (sign < 0)
607                                  * or 0 => -1 (sign > 0)  */
608                                 avl_adjust_balance_factor(node, -sign);
609
610                                 /* Height is unchanged; nothing more to do.  */
611                                 return NULL;
612                         } else {
613                                 avl_adjust_balance_factor(parent, -sign);
614                                 avl_adjust_balance_factor(node, -sign);
615                         }
616                 } else {
617                         node = avl_do_double_rotate(root_ptr, node,
618                                                     parent, -sign);
619                 }
620         }
621         parent = avl_get_parent(node);
622         if (parent)
623                 *left_deleted_ret = (node == parent->left);
624         return parent;
625 }
626
627 /* Swaps node X, which must have 2 children, with its in-order successor, then
628  * unlinks node X.  Returns the parent of X just before unlinking, without its
629  * balance factor having been updated to account for the unlink.  */
630 static AVL_INLINE struct avl_tree_node *
631 avl_tree_swap_with_successor(struct avl_tree_node **root_ptr,
632                              struct avl_tree_node *X,
633                              bool *left_deleted_ret)
634 {
635         struct avl_tree_node *Y, *ret;
636
637         Y = X->right;
638         if (!Y->left) {
639                 /*
640                  *     P?           P?           P?
641                  *     |            |            |
642                  *     X            Y            Y
643                  *    / \          / \          / \
644                  *   A   Y    =>  A   X    =>  A   B?
645                  *      / \          / \
646                  *    (0)  B?      (0)  B?
647                  *
648                  * [ X unlinked, Y returned ]
649                  */
650                 ret = Y;
651                 *left_deleted_ret = false;
652         } else {
653                 struct avl_tree_node *Q;
654
655                 do {
656                         Q = Y;
657                         Y = Y->left;
658                 } while (Y->left);
659
660                 /*
661                  *     P?           P?           P?
662                  *     |            |            |
663                  *     X            Y            Y
664                  *    / \          / \          / \
665                  *   A   ...  =>  A  ...   =>  A  ...
666                  *       |            |            |
667                  *       Q            Q            Q
668                  *      /            /            /
669                  *     Y            X            B?
670                  *    / \          / \
671                  *  (0)  B?      (0)  B?
672                  *
673                  *
674                  * [ X unlinked, Q returned ]
675                  */
676
677                 Q->left = Y->right;
678                 if (Q->left)
679                         avl_set_parent(Q->left, Q);
680                 Y->right = X->right;
681                 avl_set_parent(X->right, Y);
682                 ret = Q;
683                 *left_deleted_ret = true;
684         }
685
686         Y->left = X->left;
687         avl_set_parent(X->left, Y);
688
689         Y->parent_balance = X->parent_balance;
690         avl_replace_child(root_ptr, avl_get_parent(X), X, Y);
691
692         return ret;
693 }
694
695 /*
696  * Removes an item from the specified AVL tree.
697  *
698  * @root_ptr
699  *      Location of the AVL tree's root pointer.  Indirection is needed
700  *      because the root node may change if the tree needed to be rebalanced
701  *      because of the deletion or if @node was the root node.
702  *
703  * @node
704  *      Pointer to the `struct avl_tree_node' embedded in the item to
705  *      remove from the tree.
706  *
707  * Note: This function *only* removes the node and rebalances the tree.
708  * It does not free any memory, nor does it do the equivalent of
709  * avl_tree_node_set_unlinked().
710  */
711 void
712 avl_tree_remove(struct avl_tree_node **root_ptr, struct avl_tree_node *node)
713 {
714         struct avl_tree_node *parent;
715         bool left_deleted = false;
716
717         if (node->left && node->right) {
718                 /* @node is fully internal, with two children.  Swap it
719                  * with its in-order successor (which must exist in the
720                  * right subtree of @node and can have, at most, a right
721                  * child), then unlink @node.  */
722                 parent = avl_tree_swap_with_successor(root_ptr, node,
723                                                       &left_deleted);
724                 /* @parent is now the parent of what was @node's in-order
725                  * successor.  It cannot be NULL, since @node itself was
726                  * an ancestor of its in-order successor.
727                  * @left_deleted has been set to %true if @node's
728                  * in-order successor was the left child of @parent,
729                  * otherwise %false.  */
730         } else {
731                 struct avl_tree_node *child;
732
733                 /* @node is missing at least one child.  Unlink it.  Set
734                  * @parent to @node's parent, and set @left_deleted to
735                  * reflect which child of @parent @node was.  Or, if
736                  * @node was the root node, simply update the root node
737                  * and return.  */
738                 child = node->left ? node->left : node->right;
739                 parent = avl_get_parent(node);
740                 if (parent) {
741                         if (node == parent->left) {
742                                 parent->left = child;
743                                 left_deleted = true;
744                         } else {
745                                 parent->right = child;
746                                 left_deleted = false;
747                         }
748                         if (child)
749                                 avl_set_parent(child, parent);
750                 } else {
751                         if (child)
752                                 avl_set_parent(child, parent);
753                         *root_ptr = child;
754                         return;
755                 }
756         }
757
758         /* Rebalance the tree.  */
759         do {
760                 if (left_deleted)
761                         parent = avl_handle_subtree_shrink(root_ptr, parent,
762                                                            +1, &left_deleted);
763                 else
764                         parent = avl_handle_subtree_shrink(root_ptr, parent,
765                                                            -1, &left_deleted);
766         } while (parent);
767 }