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