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