lib/gl_avltree_oset.c

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