lib/gl_avltree_ordered.h

   1 /* Ordered {set,map} data type implemented by a binary tree.
   2    Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 /* An AVL tree is a binary tree where
  19    1. The height of each node is calculated as
  20         heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
  21    2. The heights of the subtrees of each node differ by at most 1:
  22         | heightof(right) - heightof(left) | <= 1.
  23    3. The index of the elements in the node.left subtree are smaller than
  24       the index of node.
  25       The index of the elements in the node.right subtree are larger than
  26       the index of node.
  27  */
  28
  29 /* Tree node implementation, valid for this file only.  */
  30 struct NODE_IMPL
  31 {
  32   struct NODE_IMPL *left;   /* left branch, or NULL */
  33   struct NODE_IMPL *right;  /* right branch, or NULL */
  34   /* Parent pointer, or NULL. The parent pointer is not needed for most
  35      operations.  It is needed so that a NODE_T can be returned without
  36      memory allocation, on which the functions <container>_remove_node,
  37      <container>_add_before, <container>_add_after can be implemented.  */
  38   struct NODE_IMPL *parent;
  39   int balance;                      /* heightof(right) - heightof(left),
  40                                        always = -1 or 0 or 1 */
  41   NODE_PAYLOAD_FIELDS
  42 };
  43 typedef struct NODE_IMPL * NODE_T;
  44
  45 /* Concrete CONTAINER_IMPL type, valid for this file only.  */
  46 struct CONTAINER_IMPL
  47 {
  48   struct CONTAINER_IMPL_BASE base;
  49   struct NODE_IMPL *root;           /* root node or NULL */
  50   size_t count;                     /* number of nodes */
  51 };
  52
  53 /* An AVL tree of height h has at least F_(h+2) - 1 [Fibonacci number] and at
  54    most 2^h - 1 elements.  So, h <= 84 (because a tree of height h >= 85 would
  55    have at least F_87 - 1 elements, and because even on 64-bit machines,
  56      sizeof (NODE_IMPL) * (F_87 - 1) > 2^64
  57    this would exceed the address space of the machine.  */
  58 #define MAXHEIGHT 83
  59
  60 /* Ensures the tree is balanced, after an insertion or deletion operation.
  61    The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
  62    PARENT = NODE->parent.  (NODE can also be NULL.  But PARENT is non-NULL.)
  63    Rotation operations are performed starting at PARENT (not NODE itself!).  */
  64 static void
  65 rebalance (CONTAINER_T container,
  66            NODE_T node, int height_diff, NODE_T parent)
  67 {
  68   for (;;)
  69     {
  70       NODE_T child;
  71       int previous_balance;
  72       int balance_diff;
  73       NODE_T nodeleft;
  74       NODE_T noderight;
  75
  76       child = node;
  77       node = parent;
  78
  79       previous_balance = node->balance;
  80
  81       /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
  82          branch's height has increased by 1 or the left branch's height has
  83          decreased by 1, -1 if the right branch's height has decreased by 1 or
  84          the left branch's height has increased by 1, 0 if no height change.  */
  85       if (node->left != NULL || node->right != NULL)
  86         balance_diff = (child == node->right ? height_diff : -height_diff);
  87       else
  88         /* Special case where above formula doesn't work, because the caller
  89            didn't tell whether node's left or right branch shrunk from height 1
  90            to NULL.  */
  91         balance_diff = - previous_balance;
  92
  93       node->balance += balance_diff;
  94       if (balance_diff == previous_balance)
  95         {
  96           /* node->balance is outside the range [-1,1].  Must rotate.  */
  97           NODE_T *nodep;
  98
  99           if (node->parent == NULL)
 100             /* node == container->root */
 101             nodep = &container->root;
 102           else if (node->parent->left == node)
 103             nodep = &node->parent->left;
 104           else if (node->parent->right == node)
 105             nodep = &node->parent->right;
 106           else
 107             abort ();
 108
 109           nodeleft = node->left;
 110           noderight = node->right;
 111
 112           if (balance_diff < 0)
 113             {
 114               /* node->balance = -2.  The subtree is heavier on the left side.
 115                  Rotate from left to right:
 116
 117                                   *
 118                                 /   \
 119                              h+2      h
 120                */
 121               NODE_T nodeleftright = nodeleft->right;
 122               if (nodeleft->balance <= 0)
 123                 {
 124                   /*
 125                               *                    h+2|h+3
 126                             /   \                  /    \
 127                          h+2      h      -->      /   h+1|h+2
 128                          / \                      |    /    \
 129                        h+1 h|h+1                 h+1  h|h+1  h
 130                    */
 131                   node->left = nodeleftright;
 132                   nodeleft->right = node;
 133
 134                   nodeleft->parent = node->parent;
 135                   node->parent = nodeleft;
 136                   if (nodeleftright != NULL)
 137                     nodeleftright->parent = node;
 138
 139                   nodeleft->balance += 1;
 140                   node->balance = - nodeleft->balance;
 141
 142                   *nodep = nodeleft;
 143                   height_diff = (height_diff < 0
 144                                  ? /* noderight's height had been decremented from
 145                                       h+1 to h.  The subtree's height changes from
 146                                       h+3 to h+2|h+3.  */
 147                                    nodeleft->balance - 1
 148                                  : /* nodeleft's height had been incremented from
 149                                       h+1 to h+2.  The subtree's height changes from
 150                                       h+2 to h+2|h+3.  */
 151                                    nodeleft->balance);
 152                 }
 153               else
 154                 {
 155                   /*
 156                             *                     h+2
 157                           /   \                 /     \
 158                        h+2      h      -->    h+1     h+1
 159                        / \                    / \     / \
 160                       h  h+1                 h   L   R   h
 161                          / \
 162                         L   R
 163
 164                    */
 165                   NODE_T L = nodeleft->right = nodeleftright->left;
 166                   NODE_T R = node->left = nodeleftright->right;
 167                   nodeleftright->left = nodeleft;
 168                   nodeleftright->right = node;
 169
 170                   nodeleftright->parent = node->parent;
 171                   if (L != NULL)
 172                     L->parent = nodeleft;
 173                   if (R != NULL)
 174                     R->parent = node;
 175                   nodeleft->parent = nodeleftright;
 176                   node->parent = nodeleftright;
 177
 178                   nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
 179                   node->balance = (nodeleftright->balance < 0 ? 1 : 0);
 180                   nodeleftright->balance = 0;
 181
 182                   *nodep = nodeleftright;
 183                   height_diff = (height_diff < 0
 184                                  ? /* noderight's height had been decremented from
 185                                       h+1 to h.  The subtree's height changes from
 186                                       h+3 to h+2.  */
 187                                    -1
 188                                  : /* nodeleft's height had been incremented from
 189                                       h+1 to h+2.  The subtree's height changes from
 190                                       h+2 to h+2.  */
 191                                    0);
 192                 }
 193             }
 194           else
 195             {
 196               /* node->balance = 2.  The subtree is heavier on the right side.
 197                  Rotate from right to left:
 198
 199                                   *
 200                                 /   \
 201                               h      h+2
 202                */
 203               NODE_T noderightleft = noderight->left;
 204               if (noderight->balance >= 0)
 205                 {
 206                   /*
 207                               *                    h+2|h+3
 208                             /   \                   /    \
 209                           h      h+2     -->    h+1|h+2   \
 210                                  / \            /    \    |
 211                              h|h+1 h+1         h   h|h+1 h+1
 212                    */
 213                   node->right = noderightleft;
 214                   noderight->left = node;
 215
 216                   noderight->parent = node->parent;
 217                   node->parent = noderight;
 218                   if (noderightleft != NULL)
 219                     noderightleft->parent = node;
 220
 221                   noderight->balance -= 1;
 222                   node->balance = - noderight->balance;
 223
 224                   *nodep = noderight;
 225                   height_diff = (height_diff < 0
 226                                  ? /* nodeleft's height had been decremented from
 227                                       h+1 to h.  The subtree's height changes from
 228                                       h+3 to h+2|h+3.  */
 229                                    - noderight->balance - 1
 230                                  : /* noderight's height had been incremented from
 231                                       h+1 to h+2.  The subtree's height changes from
 232                                       h+2 to h+2|h+3.  */
 233                                    - noderight->balance);
 234                 }
 235               else
 236                 {
 237                   /*
 238                             *                    h+2
 239                           /   \                /     \
 240                         h      h+2    -->    h+1     h+1
 241                                / \           / \     / \
 242                              h+1  h         h   L   R   h
 243                              / \
 244                             L   R
 245
 246                    */
 247                   NODE_T L = node->right = noderightleft->left;
 248                   NODE_T R = noderight->left = noderightleft->right;
 249                   noderightleft->left = node;
 250                   noderightleft->right = noderight;
 251
 252                   noderightleft->parent = node->parent;
 253                   if (L != NULL)
 254                     L->parent = node;
 255                   if (R != NULL)
 256                     R->parent = noderight;
 257                   node->parent = noderightleft;
 258                   noderight->parent = noderightleft;
 259
 260                   node->balance = (noderightleft->balance > 0 ? -1 : 0);
 261                   noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
 262                   noderightleft->balance = 0;
 263
 264                   *nodep = noderightleft;
 265                   height_diff = (height_diff < 0
 266                                  ? /* nodeleft's height had been decremented from
 267                                       h+1 to h.  The subtree's height changes from
 268                                       h+3 to h+2.  */
 269                                    -1
 270                                  : /* noderight's height had been incremented from
 271                                       h+1 to h+2.  The subtree's height changes from
 272                                       h+2 to h+2.  */
 273                                    0);
 274                 }
 275             }
 276           node = *nodep;
 277         }
 278       else
 279         {
 280           /* No rotation needed.  Only propagation of the height change to the
 281              next higher level.  */
 282           if (height_diff < 0)
 283             height_diff = (previous_balance == 0 ? 0 : -1);
 284           else
 285             height_diff = (node->balance == 0 ? 0 : 1);
 286         }
 287
 288       if (height_diff == 0)
 289         break;
 290
 291       parent = node->parent;
 292       if (parent == NULL)
 293         break;
 294     }
 295 }
 296
 297 static NODE_T
 298 gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS)
 299 {
 300   /* Create new node.  */
 301   NODE_T new_node =
 302     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 303
 304   if (new_node == NULL)
 305     return NULL;
 306
 307   new_node->left = NULL;
 308   new_node->right = NULL;
 309   new_node->balance = 0;
 310   NODE_PAYLOAD_ASSIGN(new_node)
 311
 312   /* Add it to the tree.  */
 313   if (container->root == NULL)
 314     {
 315       container->root = new_node;
 316       new_node->parent = NULL;
 317     }
 318   else
 319     {
 320       NODE_T node;
 321
 322       for (node = container->root; node->left != NULL; )
 323         node = node->left;
 324
 325       node->left = new_node;
 326       new_node->parent = node;
 327       node->balance--;
 328
 329       /* Rebalance.  */
 330       if (node->right == NULL && node->parent != NULL)
 331         rebalance (container, node, 1, node->parent);
 332     }
 333
 334   container->count++;
 335   return new_node;
 336 }
 337
 338 /* Adds the already allocated NEW_NODE to the tree, right before NODE.  */
 339 static void
 340 gl_tree_add_node_before (CONTAINER_T container, NODE_T node, NODE_T new_node)
 341 {
 342   bool height_inc;
 343
 344   new_node->left = NULL;
 345   new_node->right = NULL;
 346   new_node->balance = 0;
 347
 348   /* Add it to the tree.  */
 349   if (node->left == NULL)
 350     {
 351       node->left = new_node;
 352       node->balance--;
 353       height_inc = (node->right == NULL);
 354     }
 355   else
 356     {
 357       for (node = node->left; node->right != NULL; )
 358         node = node->right;
 359       node->right = new_node;
 360       node->balance++;
 361       height_inc = (node->left == NULL);
 362     }
 363   new_node->parent = node;
 364
 365   /* Rebalance.  */
 366   if (height_inc && node->parent != NULL)
 367     rebalance (container, node, 1, node->parent);
 368
 369   container->count++;
 370 }
 371
 372 static NODE_T
 373 gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
 374 {
 375   /* Create new node.  */
 376   NODE_T new_node =
 377     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 378
 379   if (new_node == NULL)
 380     return NULL;
 381
 382   NODE_PAYLOAD_ASSIGN(new_node)
 383
 384   gl_tree_add_node_before (container, node, new_node);
 385   return new_node;
 386 }
 387
 388 /* Adds the already allocated NEW_NODE to the tree, right after NODE.  */
 389 static void
 390 gl_tree_add_node_after (CONTAINER_T container, NODE_T node, NODE_T new_node)
 391 {
 392   bool height_inc;
 393
 394   new_node->left = NULL;
 395   new_node->right = NULL;
 396   new_node->balance = 0;
 397
 398   /* Add it to the tree.  */
 399   if (node->right == NULL)
 400     {
 401       node->right = new_node;
 402       node->balance++;
 403       height_inc = (node->left == NULL);
 404     }
 405   else
 406     {
 407       for (node = node->right; node->left != NULL; )
 408         node = node->left;
 409       node->left = new_node;
 410       node->balance--;
 411       height_inc = (node->right == NULL);
 412     }
 413   new_node->parent = node;
 414
 415   /* Rebalance.  */
 416   if (height_inc && node->parent != NULL)
 417     rebalance (container, node, 1, node->parent);
 418
 419   container->count++;
 420 }
 421
 422 static NODE_T
 423 gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
 424 {
 425   /* Create new node.  */
 426   NODE_T new_node =
 427     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 428
 429   if (new_node == NULL)
 430     return NULL;
 431
 432   NODE_PAYLOAD_ASSIGN(new_node)
 433
 434   gl_tree_add_node_after (container, node, new_node);
 435   return new_node;
 436 }
 437
 438 static void
 439 gl_tree_remove_node_no_free (CONTAINER_T container, NODE_T node)
 440 {
 441   NODE_T parent = node->parent;
 442
 443   if (node->left == NULL)
 444     {
 445       /* Replace node with node->right.  */
 446       NODE_T child = node->right;
 447
 448       if (child != NULL)
 449         child->parent = parent;
 450       if (parent == NULL)
 451         container->root = child;
 452       else
 453         {
 454           if (parent->left == node)
 455             parent->left = child;
 456           else /* parent->right == node */
 457             parent->right = child;
 458
 459           rebalance (container, child, -1, parent);
 460         }
 461     }
 462   else if (node->right == NULL)
 463     {
 464       /* It is not absolutely necessary to treat this case.  But the more
 465          general case below is more complicated, hence slower.  */
 466       /* Replace node with node->left.  */
 467       NODE_T child = node->left;
 468
 469       child->parent = parent;
 470       if (parent == NULL)
 471         container->root = child;
 472       else
 473         {
 474           if (parent->left == node)
 475             parent->left = child;
 476           else /* parent->right == node */
 477             parent->right = child;
 478
 479           rebalance (container, child, -1, parent);
 480         }
 481     }
 482   else
 483     {
 484       /* Replace node with the rightmost element of the node->left subtree.  */
 485       NODE_T subst;
 486       NODE_T subst_parent;
 487       NODE_T child;
 488
 489       for (subst = node->left; subst->right != NULL; )
 490         subst = subst->right;
 491
 492       subst_parent = subst->parent;
 493
 494       child = subst->left;
 495
 496       /* The case subst_parent == node is special:  If we do nothing special,
 497          we get confusion about node->left, subst->left and child->parent.
 498            subst_parent == node
 499            <==> The 'for' loop above terminated immediately.
 500            <==> subst == subst_parent->left
 501                 [otherwise subst == subst_parent->right]
 502          In this case, we would need to first set
 503            child->parent = node; node->left = child;
 504          and later - when we copy subst into node's position - again
 505            child->parent = subst; subst->left = child;
 506          Altogether a no-op.  */
 507       if (subst_parent != node)
 508         {
 509           if (child != NULL)
 510             child->parent = subst_parent;
 511           subst_parent->right = child;
 512         }
 513
 514       /* Copy subst into node's position.
 515          (This is safer than to copy subst's value into node, keep node in
 516          place, and free subst.)  */
 517       if (subst_parent != node)
 518         {
 519           subst->left = node->left;
 520           subst->left->parent = subst;
 521         }
 522       subst->right = node->right;
 523       subst->right->parent = subst;
 524       subst->balance = node->balance;
 525       subst->parent = parent;
 526       if (parent == NULL)
 527         container->root = subst;
 528       else if (parent->left == node)
 529         parent->left = subst;
 530       else /* parent->right == node */
 531         parent->right = subst;
 532
 533       /* Rebalancing starts at child's parent, that is subst_parent -
 534          except when subst_parent == node.  In this case, we need to use
 535          its replacement, subst.  */
 536       rebalance (container, child, -1, subst_parent != node ? subst_parent : subst);
 537     }
 538
 539   container->count--;
 540 }
 541
 542 static bool
 543 gl_tree_remove_node (CONTAINER_T container, NODE_T node)
 544 {
 545   gl_tree_remove_node_no_free (container, node);
 546   NODE_PAYLOAD_DISPOSE (container, node)
 547   free (node);
 548   return true;
 549 }
 550
 551 /* For debugging.  */
 552 static unsigned int
 553 check_invariants (NODE_T node, NODE_T parent, size_t *counterp)
 554 {
 555   unsigned int left_height =
 556     (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
 557   unsigned int right_height =
 558     (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
 559   int balance = (int)right_height - (int)left_height;
 560
 561   if (!(node->parent == parent))
 562     abort ();
 563   if (!(balance >= -1 && balance <= 1))
 564     abort ();
 565   if (!(node->balance == balance))
 566     abort ();
 567
 568   (*counterp)++;
 569
 570   return 1 + (left_height > right_height ? left_height : right_height);
 571 }