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