DbtuxTree.cpp 18.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
/* Copyright (C) 2003 MySQL AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

#define DBTUX_TREE_CPP
#include "Dbtux.hpp"

/*
 * Add entry.
 */
void
Dbtux::treeAdd(Signal* signal, Frag& frag, TreePos treePos, TreeEnt ent)
{
  TreeHead& tree = frag.m_tree;
  unsigned pos = treePos.m_pos;
28
  NodeHandle node(frag);
29
  // check for empty tree
30
  if (treePos.m_loc == NullTupLoc) {
31
    jam();
32 33 34 35
    insertNode(signal, node, AccPref);
    nodePushUp(signal, node, 0, ent);
    node.setSide(2);
    tree.m_root = node.m_loc;
36 37 38
    return;
  }
  // access full node
39
  selectNode(signal, node, treePos.m_loc, AccFull);
40
  // check if it is bounding node
41
  if (pos != 0 && pos != node.getOccup()) {
42 43
    jam();
    // check if room for one more
44
    if (node.getOccup() < tree.m_maxOccup) {
45
      jam();
46
      nodePushUp(signal, node, pos, ent);
47 48 49
      return;
    }
    // returns min entry
50
    nodePushDown(signal, node, pos - 1, ent);
51
    // find position to add the removed min entry
52
    TupLoc childLoc = node.getLink(0);
53
    if (childLoc == NullTupLoc) {
54 55 56 57 58 59
      jam();
      // left child will be added
      pos = 0;
    } else {
      jam();
      // find glb node
60
      while (childLoc != NullTupLoc) {
61
        jam();
62 63
        selectNode(signal, node, childLoc, AccHead);
        childLoc = node.getLink(1);
64 65
      }
      // access full node again
66 67
      accessNode(signal, node, AccFull);
      pos = node.getOccup();
68 69 70 71 72
    }
    // fall thru to next case
  }
  // adding new min or max
  unsigned i = (pos == 0 ? 0 : 1);
73
  ndbrequire(node.getLink(i) == NullTupLoc);
74
  // check if the half-leaf/leaf has room for one more
75
  if (node.getOccup() < tree.m_maxOccup) {
76
    jam();
77
    nodePushUp(signal, node, pos, ent);
78 79 80
    return;
  }
  // add a new node
81 82 83
  NodeHandle childNode(frag);
  insertNode(signal, childNode, AccPref);
  nodePushUp(signal, childNode, 0, ent);
84
  // connect parent and child
85 86 87
  node.setLink(i, childNode.m_loc);
  childNode.setLink(2, node.m_loc);
  childNode.setSide(i);
88 89 90 91
  // re-balance tree at each node
  while (true) {
    // height of subtree i has increased by 1
    int j = (i == 0 ? -1 : +1);
92
    int b = node.getBalance();
93 94 95
    if (b == 0) {
      // perfectly balanced
      jam();
96
      node.setBalance(j);
97 98 99 100
      // height change propagates up
    } else if (b == -j) {
      // height of shorter subtree increased
      jam();
101
      node.setBalance(0);
102 103 104 105 106
      // height of tree did not change - done
      break;
    } else if (b == j) {
      // height of longer subtree increased
      jam();
107 108 109
      NodeHandle childNode(frag);
      selectNode(signal, childNode, node.getLink(i), AccHead);
      int b2 = childNode.getBalance();
110 111
      if (b2 == b) {
        jam();
112
        treeRotateSingle(signal, frag, node, i);
113 114
      } else if (b2 == -b) {
        jam();
115
        treeRotateDouble(signal, frag, node, i);
116 117 118 119 120 121 122 123 124
      } else {
        // height of subtree increased so it cannot be perfectly balanced
        ndbrequire(false);
      }
      // height of tree did not increase - done
      break;
    } else {
      ndbrequire(false);
    }
125
    TupLoc parentLoc = node.getLink(2);
126
    if (parentLoc == NullTupLoc) {
127 128 129 130
      jam();
      // root node - done
      break;
    }
131 132
    i = node.getSide();
    selectNode(signal, node, parentLoc, AccHead);
133 134 135 136 137 138 139 140 141 142 143
  }
}

/*
 * Remove entry.
 */
void
Dbtux::treeRemove(Signal* signal, Frag& frag, TreePos treePos)
{
  TreeHead& tree = frag.m_tree;
  unsigned pos = treePos.m_pos;
144
  NodeHandle node(frag);
145
  // access full node
146
  selectNode(signal, node, treePos.m_loc, AccFull);
147 148
  TreeEnt ent;
  // check interior node first
149
  if (node.getChilds() == 2) {
150
    jam();
151
    ndbrequire(node.getOccup() >= tree.m_minOccup);
152
    // check if no underflow
153
    if (node.getOccup() > tree.m_minOccup) {
154
      jam();
155
      nodePopDown(signal, node, pos, ent);
156 157 158
      return;
    }
    // save current handle
159
    NodeHandle parentNode = node;
160
    // find glb node
161
    TupLoc childLoc = node.getLink(0);
162
    while (childLoc != NullTupLoc) {
163
      jam();
164 165
      selectNode(signal, node, childLoc, AccHead);
      childLoc = node.getLink(1);
166 167
    }
    // access full node again
168
    accessNode(signal, node, AccFull);
169
    // use glb max as new parent min
170 171
    ent = node.getEnt(node.getOccup() - 1);
    nodePopUp(signal, parentNode, pos, ent);
172
    // set up to remove glb max
173
    pos = node.getOccup() - 1;
174 175 176
    // fall thru to next case
  }
  // remove the element
177 178
  nodePopDown(signal, node, pos, ent);
  ndbrequire(node.getChilds() <= 1);
179 180 181
  // handle half-leaf
  for (unsigned i = 0; i <= 1; i++) {
    jam();
182
    TupLoc childLoc = node.getLink(i);
183
    if (childLoc != NullTupLoc) {
184
      // move to child
185
      selectNode(signal, node, childLoc, AccFull);
186 187 188 189
      // balance of half-leaf parent requires child to be leaf
      break;
    }
  }
190
  ndbrequire(node.getChilds() == 0);
191
  // get parent if any
192 193 194
  TupLoc parentLoc = node.getLink(2);
  NodeHandle parentNode(frag);
  unsigned i = node.getSide();
195
  // move all that fits into parent
196
  if (parentLoc != NullTupLoc) {
197
    jam();
198 199
    selectNode(signal, parentNode, node.getLink(2), AccFull);
    nodeSlide(signal, parentNode, node, i);
200 201 202
    // fall thru to next case
  }
  // non-empty leaf
203
  if (node.getOccup() >= 1) {
204 205 206 207
    jam();
    return;
  }
  // remove empty leaf
208
  deleteNode(signal, node);
209
  if (parentLoc == NullTupLoc) {
210 211
    jam();
    // tree is now empty
212
    tree.m_root = NullTupLoc;
213 214
    return;
  }
215 216
  node = parentNode;
  node.setLink(i, NullTupLoc);
217 218
#ifdef dbtux_min_occup_less_max_occup
  // check if we created a half-leaf
219
  if (node.getBalance() == 0) {
220 221
    jam();
    // move entries from the other child
222 223 224 225 226
    TupLoc childLoc = node.getLink(1 - i);
    NodeHandle childNode(frag);
    selectNode(signal, childNode, childLoc, AccFull);
    nodeSlide(signal, node, childNode, 1 - i);
    if (childNode.getOccup() == 0) {
227
      jam();
228 229
      deleteNode(signal, childNode);
      node.setLink(1 - i, NullTupLoc);
230
      // we are balanced again but our parent balance changes by -1
231
      parentLoc = node.getLink(2);
232
      if (parentLoc == NullTupLoc) {
233 234 235 236
        jam();
        return;
      }
      // fix side and become parent
237 238
      i = node.getSide();
      selectNode(signal, node, parentLoc, AccHead);
239 240 241 242 243 244 245
    }
  }
#endif
  // re-balance tree at each node
  while (true) {
    // height of subtree i has decreased by 1
    int j = (i == 0 ? -1 : +1);
246
    int b = node.getBalance();
247 248 249
    if (b == 0) {
      // perfectly balanced
      jam();
250
      node.setBalance(-j);
251 252 253 254 255
      // height of tree did not change - done
      return;
    } else if (b == j) {
      // height of longer subtree has decreased
      jam();
256
      node.setBalance(0);
257 258 259 260 261
      // height change propagates up
    } else if (b == -j) {
      // height of shorter subtree has decreased
      jam();
      // child on the other side
262 263 264
      NodeHandle childNode(frag);
      selectNode(signal, childNode, node.getLink(1 - i), AccHead);
      int b2 = childNode.getBalance();
265 266
      if (b2 == b) {
        jam();
267
        treeRotateSingle(signal, frag, node, 1 - i);
268 269 270
        // height of tree decreased and propagates up
      } else if (b2 == -b) {
        jam();
271
        treeRotateDouble(signal, frag, node, 1 - i);
272 273 274
        // height of tree decreased and propagates up
      } else {
        jam();
275
        treeRotateSingle(signal, frag, node, 1 - i);
276 277 278 279 280 281
        // height of tree did not change - done
        return;
      }
    } else {
      ndbrequire(false);
    }
282
    TupLoc parentLoc = node.getLink(2);
283
    if (parentLoc == NullTupLoc) {
284 285 286 287
      jam();
      // root node - done
      return;
    }
288 289
    i = node.getSide();
    selectNode(signal, node, parentLoc, AccHead);
290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
  }
}

/*
 * Single rotation about node 5.  One of LL (i=0) or RR (i=1).
 *
 *           0                   0
 *           |                   |
 *           5       ==>         3
 *         /   \               /   \
 *        3     6             2     5
 *       / \                 /     / \
 *      2   4               1     4   6
 *     /
 *    1
 *
 * In this change 5,3 and 2 must always be there. 0, 1, 2, 4 and 6 are
 * all optional. If 4 are there it changes side.
*/
void
Dbtux::treeRotateSingle(Signal* signal,
                        Frag& frag,
312
                        NodeHandle& node,
313 314 315 316 317 318
                        unsigned i)
{
  ndbrequire(i <= 1);
  /*
  5 is the old top node that have been unbalanced due to an insert or
  delete. The balance is still the old balance before the update.
319
  Verify that bal5 is 1 if RR rotate and -1 if LL rotate.
320
  */
321 322 323 324 325
  NodeHandle node5 = node;
  const TupLoc loc5 = node5.m_loc;
  const int bal5 = node5.getBalance();
  const int side5 = node5.getSide();
  ndbrequire(bal5 + (1 - i) == i);
326 327 328 329 330
  /*
  3 is the new root of this part of the tree which is to swap place with
  node 5. For an insert to cause this it must have the same balance as 5.
  For deletes it can have the balance 0.
  */
331 332 333 334
  TupLoc loc3 = node5.getLink(i);
  NodeHandle node3(frag);
  selectNode(signal, node3, loc3, AccHead);
  const int bal3 = node3.getBalance();
335 336 337 338
  /*
  2 must always be there but is not changed. Thus we mereley check that it
  exists.
  */
339
  ndbrequire(node3.getLink(i) != NullTupLoc);
340 341 342 343 344 345
  /*
  4 is not necessarily there but if it is there it will move from one
  side of 3 to the other side of 5. For LL it moves from the right side
  to the left side and for RR it moves from the left side to the right
  side. This means that it also changes parent from 3 to 5.
  */
346 347 348
  TupLoc loc4 = node3.getLink(1 - i);
  NodeHandle node4(frag);
  if (loc4 != NullTupLoc) {
349
    jam();
350 351 352 353 354
    selectNode(signal, node4, loc4, AccHead);
    ndbrequire(node4.getSide() == (1 - i) &&
               node4.getLink(2) == loc3);
    node4.setSide(i);
    node4.setLink(2, loc5);
355 356 357 358 359
  }//if

  /*
  Retrieve the address of 5's parent before it is destroyed
  */
360
  TupLoc loc0 = node5.getLink(2);
361 362 363 364 365 366 367 368 369 370 371 372 373

  /*
  The next step is to perform the rotation. 3 will inherit 5's parent 
  and side. 5 will become a child of 3 on the right side for LL and on
  the left side for RR.
  5 will get 3 as the parent. It will get 4 as a child and it will be
  on the right side of 3 for LL and left side of 3 for RR.
  The final step of the rotate is to check whether 5 originally had any
  parent. If it had not then 3 is the new root node.
  We will also verify some preconditions for the change to occur.
  1. 3 must have had 5 as parent before the change.
  2. 3's side is left for LL and right for RR before change.
  */
374 375 376 377 378 379 380 381 382
  ndbrequire(node3.getLink(2) == loc5);
  ndbrequire(node3.getSide() == i);
  node3.setLink(1 - i, loc5);
  node3.setLink(2, loc0);
  node3.setSide(side5);
  node5.setLink(i, loc4);
  node5.setLink(2, loc3);
  node5.setSide(1 - i);
  if (loc0 != NullTupLoc) {
383
    jam();
384 385 386
    NodeHandle node0(frag);
    selectNode(signal, node0, loc0, AccHead);
    node0.setLink(side5, loc3);
387 388
  } else {
    jam();
389
    frag.m_tree.m_root = loc3;
390 391 392 393 394 395 396 397 398 399 400 401
  }//if
  /* The final step of the change is to update the balance of 3 and
  5 that changed places. There are two cases here. The first case is
  when 3 unbalanced in the same direction by an insert or a delete.
  In this case the changes will make the tree balanced again for both
  3 and 5.
  The second case only occurs at deletes. In this case 3 starts out
  balanced. In the figure above this could occur if 4 starts out with
  a right node and the rotate is triggered by a delete of 6's only child.
  In this case 5 will change balance but still be unbalanced and 3 will
  be unbalanced in the opposite direction of 5.
  */
402
  if (bal3 == bal5) {
403
    jam();
404 405 406
    node3.setBalance(0);
    node5.setBalance(0);
  } else if (bal3 == 0) {
407
    jam();
408 409
    node3.setBalance(-bal5);
    node5.setBalance(bal5);
410 411 412 413
  } else {
    ndbrequire(false);
  }//if
  /*
414
  Set node to 3 as return parameter for enabling caller to continue
415 416
  traversing the tree.
  */
417
  node = node3;
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521
}

/*
 * Double rotation about node 6.  One of LR (i=0) or RL (i=1).
 *
 *        0                  0
 *        |                  |
 *        6      ==>         4
 *       / \               /   \
 *      2   7             2     6
 *     / \               / \   / \
 *    1   4             1   3 5   7
 *       / \
 *      3   5
 *
 * In this change 6, 2 and 4 must be there, all others are optional.
 * We will start by proving a Lemma.
 * Lemma:
 *   The height of the sub-trees 1 and 7 and the maximum height of the
 *   threes from 3 and 5 are all the same.
 * Proof:
 *   maxheight(3,5) is defined as the maximum height of 3 and 5.
 *   If height(7) > maxheight(3,5) then the AVL condition is ok and we
 *   don't need to perform a rotation.
 *   If height(7) < maxheight(3,5) then the balance of 6 would be at least
 *   -3 which cannot happen in an AVL tree even before a rotation.
 *   Thus we conclude that height(7) == maxheight(3,5)
 *
 *   The next step is to prove that the height of 1 is equal to maxheight(3,5).
 *   If height(1) - 1 > maxheight(3,5) then we would have
 *   balance in 6 equal to -3 at least which cannot happen in an AVL-tree.
 *   If height(1) - 1 = maxheight(3,5) then we should have solved the
 *   unbalance with a single rotate and not with a double rotate.
 *   If height(1) + 1 = maxheight(3,5) then we would be doing a rotate
 *   with node 2 as the root of the rotation.
 *   If height(1) + k = maxheight(3,5) where k >= 2 then the tree could not have
 *   been an AVL-tree before the insert or delete.
 *   Thus we conclude that height(1) = maxheight(3,5)
 *
 *   Thus we conclude that height(1) = maxheight(3,5) = height(7).
 *
 * Observation:
 *   The balance of node 4 before the rotation can be any (-1, 0, +1).
 *
 * The following changes are needed:
 * Node 6:
 * 1) Changes parent from 0 -> 4
 * 2) 1 - i link stays the same
 * 3) i side link is derived from 1 - i side link from 4
 * 4) Side is set to 1 - i
 * 5) Balance change:
 *    If balance(4) == 0 then balance(6) = 0
 *      since height(3) = height(5) = maxheight(3,5) = height(7)
 *    If balance(4) == +1 then balance(6) = 0 
 *      since height(5) = maxheight(3,5) = height(7)
 *    If balance(4) == -1 then balance(6) = 1
 *      since height(5) + 1 = maxheight(3,5) = height(7)
 *
 * Node 2:
 * 1) Changes parent from 6 -> 4
 * 2) i side link stays the same
 * 3) 1 - i side link is derived from i side link of 4
 * 4) Side is set to i (thus not changed)
 * 5) Balance change:
 *    If balance(4) == 0 then balance(2) = 0
 *      since height(3) = height(5) = maxheight(3,5) = height(1)
 *    If balance(4) == -1 then balance(2) = 0 
 *      since height(3) = maxheight(3,5) = height(1)
 *    If balance(4) == +1 then balance(6) = 1
 *      since height(3) + 1 = maxheight(3,5) = height(1)
 *
 * Node 4:
 * 1) Inherits parent from 6
 * 2) i side link is 2
 * 3) 1 - i side link is 6
 * 4) Side is inherited from 6
 * 5) Balance(4) = 0 independent of previous balance
 *    Proof:
 *      If height(1) = 0 then only 2, 4 and 6 are involved and then it is
 *      trivially true.
 *      If height(1) >= 1 then we are sure that 1 and 7 exist with the same
 *      height and that if 3 and 5 exist they are of the same height as 1 and
 *      7 and thus we know that 4 is balanced since newheight(2) = newheight(6).
 *
 * If Node 3 exists:
 * 1) Change parent from 4 to 2
 * 2) Change side from i to 1 - i
 *
 * If Node 5 exists:
 * 1) Change parent from 4 to 6
 * 2) Change side from 1 - i to i
 * 
 * If Node 0 exists:
 * 1) previous link to 6 is replaced by link to 4 on proper side
 *
 * Node 1 and 7 needs no changes at all.
 * 
 * Some additional requires are that balance(2) = - balance(6) = -1/+1 since
 * otherwise we would do a single rotate.
 *
 * The balance(6) is -1 if i == 0 and 1 if i == 1
 *
 */
void
522
Dbtux::treeRotateDouble(Signal* signal, Frag& frag, NodeHandle& node, unsigned i)
523 524
{
  // old top node
525 526
  NodeHandle node6 = node;
  const TupLoc loc6 = node6.m_loc;
527
  // the un-updated balance
528 529
  const int bal6 = node6.getBalance();
  const unsigned side6 = node6.getSide();
530 531

  // level 1
532 533 534 535
  TupLoc loc2 = node6.getLink(i);
  NodeHandle node2(frag);
  selectNode(signal, node2, loc2, AccHead);
  const int bal2 = node2.getBalance();
536 537

  // level 2
538 539 540 541
  TupLoc loc4 = node2.getLink(1 - i);
  NodeHandle node4(frag);
  selectNode(signal, node4, loc4, AccHead);
  const int bal4 = node4.getBalance();
542 543

  ndbrequire(i <= 1);
544 545 546 547 548
  ndbrequire(bal6 + (1 - i) == i);
  ndbrequire(bal2 == -bal6);
  ndbrequire(node2.getLink(2) == loc6);
  ndbrequire(node2.getSide() == i);
  ndbrequire(node4.getLink(2) == loc2);
549 550

  // level 3
551 552
  TupLoc loc3 = node4.getLink(i);
  TupLoc loc5 = node4.getLink(1 - i);
553 554

  // fill up leaf before it becomes internal
555
  if (loc3 == NullTupLoc && loc5 == NullTupLoc) {
556 557
    jam();
    TreeHead& tree = frag.m_tree;
558 559 560
    accessNode(signal, node2, AccFull);
    accessNode(signal, node4, AccFull);
    nodeSlide(signal, node4, node2, i);
561
    // implied by rule of merging half-leaves with leaves
562 563
    ndbrequire(node4.getOccup() >= tree.m_minOccup);
    ndbrequire(node2.getOccup() != 0);
564
  } else {
565
    if (loc3 != NullTupLoc) {
566
      jam();
567 568 569 570
      NodeHandle node3(frag);
      selectNode(signal, node3, loc3, AccHead);
      node3.setLink(2, loc2);
      node3.setSide(1 - i);
571
    }
572
    if (loc5 != NullTupLoc) {
573
      jam();
574 575 576 577
      NodeHandle node5(frag);
      selectNode(signal, node5, loc5, AccHead);
      node5.setLink(2, node6.m_loc);
      node5.setSide(i);
578 579 580
    }
  }
  // parent
581 582
  TupLoc loc0 = node6.getLink(2);
  NodeHandle node0(frag);
583
  // perform the rotation
584 585 586
  node6.setLink(i, loc5);
  node6.setLink(2, loc4);
  node6.setSide(1 - i);
587

588 589
  node2.setLink(1 - i, loc3);
  node2.setLink(2, loc4);
590

591 592 593 594
  node4.setLink(i, loc2);
  node4.setLink(1 - i, loc6);
  node4.setLink(2, loc0);
  node4.setSide(side6);
595

596
  if (loc0 != NullTupLoc) {
597
    jam();
598 599
    selectNode(signal, node0, loc0, AccHead);
    node0.setLink(side6, loc4);
600 601
  } else {
    jam();
602
    frag.m_tree.m_root = loc4;
603 604
  }
  // set balance of changed nodes
605 606
  node4.setBalance(0);
  if (bal4 == 0) {
607
    jam();
608 609 610
    node2.setBalance(0);
    node6.setBalance(0);
  } else if (bal4 == -bal2) {
611
    jam();
612 613 614
    node2.setBalance(0);
    node6.setBalance(bal2);
  } else if (bal4 == bal2) {
615
    jam();
616 617
    node2.setBalance(-bal2);
    node6.setBalance(0);
618 619 620 621
  } else {
    ndbrequire(false);
  }
  // new top node
622
  node = node4;
623
}