lib/gl_avltree_ordered.h

   1 /* Ordered {set,map} data type implemented by a binary tree.
   2    Copyright (C) 2006-2007, 2009-2018 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 /* Ensure 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 static NODE_T
 339 gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
 340 {
 341   /* Create new node.  */
 342   NODE_T new_node =
 343     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 344   bool height_inc;
 345
 346   if (new_node == NULL)
 347     return NULL;
 348
 349   new_node->left = NULL;
 350   new_node->right = NULL;
 351   new_node->balance = 0;
 352   NODE_PAYLOAD_ASSIGN(new_node)
 353
 354   /* Add it to the tree.  */
 355   if (node->left == NULL)
 356     {
 357       node->left = new_node;
 358       node->balance--;
 359       height_inc = (node->right == NULL);
 360     }
 361   else
 362     {
 363       for (node = node->left; node->right != NULL; )
 364         node = node->right;
 365       node->right = new_node;
 366       node->balance++;
 367       height_inc = (node->left == NULL);
 368     }
 369   new_node->parent = node;
 370
 371   /* Rebalance.  */
 372   if (height_inc && node->parent != NULL)
 373     rebalance (container, node, 1, node->parent);
 374
 375   container->count++;
 376   return new_node;
 377 }
 378
 379 static NODE_T
 380 gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
 381 {
 382   /* Create new node.  */
 383   NODE_T new_node =
 384     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 385   bool height_inc;
 386
 387   if (new_node == NULL)
 388     return NULL;
 389
 390   new_node->left = NULL;
 391   new_node->right = NULL;
 392   new_node->balance = 0;
 393   NODE_PAYLOAD_ASSIGN(new_node)
 394
 395   /* Add it to the tree.  */
 396   if (node->right == NULL)
 397     {
 398       node->right = new_node;
 399       node->balance++;
 400       height_inc = (node->left == NULL);
 401     }
 402   else
 403     {
 404       for (node = node->right; node->left != NULL; )
 405         node = node->left;
 406       node->left = new_node;
 407       node->balance--;
 408       height_inc = (node->right == NULL);
 409     }
 410   new_node->parent = node;
 411
 412   /* Rebalance.  */
 413   if (height_inc && node->parent != NULL)
 414     rebalance (container, node, 1, node->parent);
 415
 416   container->count++;
 417   return new_node;
 418 }
 419
 420 static bool
 421 gl_tree_remove_node (CONTAINER_T container, NODE_T node)
 422 {
 423   NODE_T parent = node->parent;
 424
 425   if (node->left == NULL)
 426     {
 427       /* Replace node with node->right.  */
 428       NODE_T child = node->right;
 429
 430       if (child != NULL)
 431         child->parent = parent;
 432       if (parent == NULL)
 433         container->root = child;
 434       else
 435         {
 436           if (parent->left == node)
 437             parent->left = child;
 438           else /* parent->right == node */
 439             parent->right = child;
 440
 441           rebalance (container, child, -1, parent);
 442         }
 443     }
 444   else if (node->right == NULL)
 445     {
 446       /* It is not absolutely necessary to treat this case.  But the more
 447          general case below is more complicated, hence slower.  */
 448       /* Replace node with node->left.  */
 449       NODE_T child = node->left;
 450
 451       child->parent = parent;
 452       if (parent == NULL)
 453         container->root = child;
 454       else
 455         {
 456           if (parent->left == node)
 457             parent->left = child;
 458           else /* parent->right == node */
 459             parent->right = child;
 460
 461           rebalance (container, child, -1, parent);
 462         }
 463     }
 464   else
 465     {
 466       /* Replace node with the rightmost element of the node->left subtree.  */
 467       NODE_T subst;
 468       NODE_T subst_parent;
 469       NODE_T child;
 470
 471       for (subst = node->left; subst->right != NULL; )
 472         subst = subst->right;
 473
 474       subst_parent = subst->parent;
 475
 476       child = subst->left;
 477
 478       /* The case subst_parent == node is special:  If we do nothing special,
 479          we get confusion about node->left, subst->left and child->parent.
 480            subst_parent == node
 481            <==> The 'for' loop above terminated immediately.
 482            <==> subst == subst_parent->left
 483                 [otherwise subst == subst_parent->right]
 484          In this case, we would need to first set
 485            child->parent = node; node->left = child;
 486          and later - when we copy subst into node's position - again
 487            child->parent = subst; subst->left = child;
 488          Altogether a no-op.  */
 489       if (subst_parent != node)
 490         {
 491           if (child != NULL)
 492             child->parent = subst_parent;
 493           subst_parent->right = child;
 494         }
 495
 496       /* Copy subst into node's position.
 497          (This is safer than to copy subst's value into node, keep node in
 498          place, and free subst.)  */
 499       if (subst_parent != node)
 500         {
 501           subst->left = node->left;
 502           subst->left->parent = subst;
 503         }
 504       subst->right = node->right;
 505       subst->right->parent = subst;
 506       subst->balance = node->balance;
 507       subst->parent = parent;
 508       if (parent == NULL)
 509         container->root = subst;
 510       else if (parent->left == node)
 511         parent->left = subst;
 512       else /* parent->right == node */
 513         parent->right = subst;
 514
 515       /* Rebalancing starts at child's parent, that is subst_parent -
 516          except when subst_parent == node.  In this case, we need to use
 517          its replacement, subst.  */
 518       rebalance (container, child, -1, subst_parent != node ? subst_parent : subst);
 519     }
 520
 521   container->count--;
 522   NODE_PAYLOAD_DISPOSE
 523   free (node);
 524   return true;
 525 }
 526
 527 /* For debugging.  */
 528 static unsigned int
 529 check_invariants (NODE_T node, NODE_T parent, size_t *counterp)
 530 {
 531   unsigned int left_height =
 532     (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
 533   unsigned int right_height =
 534     (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
 535   int balance = (int)right_height - (int)left_height;
 536
 537   if (!(node->parent == parent))
 538     abort ();
 539   if (!(balance >= -1 && balance <= 1))
 540     abort ();
 541   if (!(node->balance == balance))
 542     abort ();
 543
 544   (*counterp)++;
 545
 546   return 1 + (left_height > right_height ? left_height : right_height);
 547 }