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