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