lib/gl_avltree_oset.c

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