lib/gl_avltree_oset.c

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