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