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 #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 =
 314     (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
 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_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 *) xmalloc (sizeof (struct gl_oset_node_impl));
 353   bool height_inc;
 354
 355   new_node->left = NULL;
 356   new_node->right = NULL;
 357   new_node->balance = 0;
 358   new_node->value = elt;
 359
 360   /* Add it to the tree.  */
 361   if (node->left == NULL)
 362     {
 363       node->left = new_node;
 364       node->balance--;
 365       height_inc = (node->right == NULL);
 366     }
 367   else
 368     {
 369       for (node = node->left; node->right != NULL; )
 370         node = node->right;
 371       node->right = new_node;
 372       node->balance++;
 373       height_inc = (node->left == NULL);
 374     }
 375   new_node->parent = node;
 376
 377   /* Rebalance.  */
 378   if (height_inc && node->parent != NULL)
 379     rebalance (set, node, 1, node->parent);
 380
 381   set->count++;
 382   return new_node;
 383 }
 384
 385 static gl_oset_node_t
 386 gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
 387 {
 388   /* Create new node.  */
 389   gl_oset_node_t new_node =
 390     (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
 391   bool height_inc;
 392
 393   new_node->left = NULL;
 394   new_node->right = NULL;
 395   new_node->balance = 0;
 396   new_node->value = elt;
 397
 398   /* Add it to the tree.  */
 399   if (node->right == NULL)
 400     {
 401       node->right = new_node;
 402       node->balance++;
 403       height_inc = (node->left == NULL);
 404     }
 405   else
 406     {
 407       for (node = node->right; node->left != NULL; )
 408         node = node->left;
 409       node->left = new_node;
 410       node->balance--;
 411       height_inc = (node->right == NULL);
 412     }
 413   new_node->parent = node;
 414
 415   /* Rebalance.  */
 416   if (height_inc && node->parent != NULL)
 417     rebalance (set, node, 1, node->parent);
 418
 419   set->count++;
 420   return new_node;
 421 }
 422
 423 static bool
 424 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
 425 {
 426   gl_oset_node_t parent = node->parent;
 427
 428   if (node->left == NULL)
 429     {
 430       /* Replace node with node->right.  */
 431       gl_oset_node_t child = node->right;
 432
 433       if (child != NULL)
 434         child->parent = parent;
 435       if (parent == NULL)
 436         set->root = child;
 437       else
 438         {
 439           if (parent->left == node)
 440             parent->left = child;
 441           else /* parent->right == node */
 442             parent->right = child;
 443
 444           rebalance (set, child, -1, parent);
 445         }
 446     }
 447   else if (node->right == NULL)
 448     {
 449       /* It is not absolutely necessary to treat this case.  But the more
 450          general case below is more complicated, hence slower.  */
 451       /* Replace node with node->left.  */
 452       gl_oset_node_t child = node->left;
 453
 454       child->parent = parent;
 455       if (parent == NULL)
 456         set->root = child;
 457       else
 458         {
 459           if (parent->left == node)
 460             parent->left = child;
 461           else /* parent->right == node */
 462             parent->right = child;
 463
 464           rebalance (set, child, -1, parent);
 465         }
 466     }
 467   else
 468     {
 469       /* Replace node with the rightmost element of the node->left subtree.  */
 470       gl_oset_node_t subst;
 471       gl_oset_node_t subst_parent;
 472       gl_oset_node_t child;
 473
 474       for (subst = node->left; subst->right != NULL; )
 475         subst = subst->right;
 476
 477       subst_parent = subst->parent;
 478
 479       child = subst->left;
 480
 481       /* The case subst_parent == node is special:  If we do nothing special,
 482          we get confusion about node->left, subst->left and child->parent.
 483            subst_parent == node
 484            <==> The 'for' loop above terminated immediately.
 485            <==> subst == subst_parent->left
 486                 [otherwise subst == subst_parent->right]
 487          In this case, we would need to first set
 488            child->parent = node; node->left = child;
 489          and later - when we copy subst into node's position - again
 490            child->parent = subst; subst->left = child;
 491          Altogether a no-op.  */
 492       if (subst_parent != node)
 493         {
 494           if (child != NULL)
 495             child->parent = subst_parent;
 496           subst_parent->right = child;
 497         }
 498
 499       /* Copy subst into node's position.
 500          (This is safer than to copy subst's value into node, keep node in
 501          place, and free subst.)  */
 502       if (subst_parent != node)
 503         {
 504           subst->left = node->left;
 505           subst->left->parent = subst;
 506         }
 507       subst->right = node->right;
 508       subst->right->parent = subst;
 509       subst->balance = node->balance;
 510       subst->parent = parent;
 511       if (parent == NULL)
 512         set->root = subst;
 513       else if (parent->left == node)
 514         parent->left = subst;
 515       else /* parent->right == node */
 516         parent->right = subst;
 517
 518       /* Rebalancing starts at child's parent, that is subst_parent -
 519          except when subst_parent == node.  In this case, we need to use
 520          its replacement, subst.  */
 521       rebalance (set, child, -1, subst_parent != node ? subst_parent : subst);
 522     }
 523
 524   set->count--;
 525   free (node);
 526   return true;
 527 }
 528
 529 /* Generic binary tree code.  */
 530 #include "gl_anytree_oset.h"
 531
 532 /* For debugging.  */
 533 static unsigned int
 534 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
 535 {
 536   unsigned int left_height =
 537     (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
 538   unsigned int right_height =
 539     (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
 540   int balance = (int)right_height - (int)left_height;
 541
 542   if (!(node->parent == parent))
 543     abort ();
 544   if (!(balance >= -1 && balance <= 1))
 545     abort ();
 546   if (!(node->balance == balance))
 547     abort ();
 548
 549   (*counterp)++;
 550
 551   return 1 + (left_height > right_height ? left_height : right_height);
 552 }
 553 void
 554 gl_avltree_oset_check_invariants (gl_oset_t set)
 555 {
 556   size_t counter = 0;
 557   if (set->root != NULL)
 558     check_invariants (set->root, NULL, &counter);
 559   if (!(set->count == counter))
 560     abort ();
 561 }
 562
 563 const struct gl_oset_implementation gl_avltree_oset_implementation =
 564   {
 565     gl_tree_create_empty,
 566     gl_tree_size,
 567     gl_tree_search,
 568     gl_tree_search_atleast,
 569     gl_tree_add,
 570     gl_tree_remove,
 571     gl_tree_oset_free,
 572     gl_tree_iterator,
 573     gl_tree_iterator_next,
 574     gl_tree_iterator_free
 575   };