DbtuxTree.cpp 22.4 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 28 29 30 31 32
/* 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"

/*
 * Search for entry.
 *
 * Search key is index attribute data and tree entry value.  Start from
 * root node and compare the key to min/max of each node.  Use linear
 * search on the final (bounding) node.  Initial attributes which are
 * same in min/max need not be checked.
 */
void
Dbtux::treeSearch(Signal* signal, Frag& frag, SearchPar searchPar, TreePos& treePos)
{
  const TreeHead& tree = frag.m_tree;
  const unsigned numAttrs = frag.m_numAttrs;
33 34
  treePos.m_loc = tree.m_root;
  if (treePos.m_loc == NullTupLoc) {
35 36 37 38 39 40
    // empty tree
    jam();
    treePos.m_pos = 0;
    treePos.m_match = false;
    return;
  }
unknown's avatar
unknown committed
41
  NodeHandle node(frag);
42 43
loop: {
    jam();
unknown's avatar
unknown committed
44 45
    selectNode(signal, node, treePos.m_loc, AccPref);
    const unsigned occup = node.getOccup();
46 47 48 49 50 51 52 53
    ndbrequire(occup != 0);
    // number of equal initial attributes in bounding node
    unsigned numEq = ZNIL;
    for (unsigned i = 0; i <= 1; i++) {
      jam();
      // compare prefix
      CmpPar cmpPar;
      cmpPar.m_data1 = searchPar.m_data;
unknown's avatar
unknown committed
54
      cmpPar.m_data2 = node.getPref(i);
55 56 57 58 59 60 61 62
      cmpPar.m_len2 = tree.m_prefSize;
      cmpPar.m_first = 0;
      cmpPar.m_numEq = 0;
      int ret = cmpTreeAttrs(frag, cmpPar);
      if (ret == NdbSqlUtil::CmpUnknown) {
        jam();
        // read full value
        ReadPar readPar;
unknown's avatar
unknown committed
63
        readPar.m_ent = node.getMinMax(i);
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
        ndbrequire(cmpPar.m_numEq < numAttrs);
        readPar.m_first = cmpPar.m_numEq;
        readPar.m_count = numAttrs - cmpPar.m_numEq;
        readPar.m_data = 0;     // leave in signal data
        tupReadAttrs(signal, frag, readPar);
        // compare full value
        cmpPar.m_data2 = readPar.m_data;
        cmpPar.m_len2 = ZNIL;   // big
        cmpPar.m_first = readPar.m_first;
        ret = cmpTreeAttrs(frag, cmpPar);
        ndbrequire(ret != NdbSqlUtil::CmpUnknown);
      }
      if (numEq > cmpPar.m_numEq)
        numEq = cmpPar.m_numEq;
      if (ret == 0) {
        jam();
        // keys are equal, compare entry values
unknown's avatar
unknown committed
81
        ret = searchPar.m_ent.cmp(node.getMinMax(i));
82 83 84
      }
      if (i == 0 ? (ret < 0) : (ret > 0)) {
        jam();
unknown's avatar
unknown committed
85
        const TupLoc loc = node.getLink(i);
86
        if (loc != NullTupLoc) {
87 88
          jam();
          // continue to left/right subtree
89
          treePos.m_loc = loc;
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
          goto loop;
        }
        // position is immediately before/after this node
        treePos.m_pos = (i == 0 ? 0 : occup);
        treePos.m_match = false;
        return;
      }
      if (ret == 0) {
        jam();
        // position is at first/last entry
        treePos.m_pos = (i == 0 ? 0 : occup - 1);
        treePos.m_match = true;
        return;
      }
    }
unknown's avatar
unknown committed
105 106
    // access rest of the bounding node
    accessNode(signal, node, AccFull);
107 108 109 110 111 112 113 114 115 116
    // position is strictly within the node
    ndbrequire(occup >= 2);
    const unsigned numWithin = occup - 2;
    for (unsigned j = 1; j <= numWithin; j++) {
      jam();
      int ret = 0;
      // compare remaining attributes
      if (numEq < numAttrs) {
        jam();
        ReadPar readPar;
unknown's avatar
unknown committed
117
        readPar.m_ent = node.getEnt(j);
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
        readPar.m_first = numEq;
        readPar.m_count = numAttrs - numEq;
        readPar.m_data = 0;     // leave in signal data
        tupReadAttrs(signal, frag, readPar);
        // compare
        CmpPar cmpPar;
        cmpPar.m_data1 = searchPar.m_data;
        cmpPar.m_data2 = readPar.m_data;
        cmpPar.m_len2 = ZNIL;  // big
        cmpPar.m_first = readPar.m_first;
        ret = cmpTreeAttrs(frag, cmpPar);
        ndbrequire(ret != NdbSqlUtil::CmpUnknown);
      }
      if (ret == 0) {
        jam();
        // keys are equal, compare entry values
unknown's avatar
unknown committed
134
        ret = searchPar.m_ent.cmp(node.getEnt(j));
135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
      }
      if (ret <= 0) {
        jam();
        // position is before or at this entry
        treePos.m_pos = j;
        treePos.m_match = (ret == 0);
        return;
      }
    }
    // position is before last entry
    treePos.m_pos = occup - 1;
    treePos.m_match = false;
    return;
  }
}

/*
 * Add entry.
 */
void
Dbtux::treeAdd(Signal* signal, Frag& frag, TreePos treePos, TreeEnt ent)
{
  TreeHead& tree = frag.m_tree;
  unsigned pos = treePos.m_pos;
unknown's avatar
unknown committed
159
  NodeHandle node(frag);
160
  // check for empty tree
161
  if (treePos.m_loc == NullTupLoc) {
162
    jam();
unknown's avatar
unknown committed
163 164 165 166
    insertNode(signal, node, AccPref);
    nodePushUp(signal, node, 0, ent);
    node.setSide(2);
    tree.m_root = node.m_loc;
167 168 169
    return;
  }
  // access full node
unknown's avatar
unknown committed
170
  selectNode(signal, node, treePos.m_loc, AccFull);
171
  // check if it is bounding node
unknown's avatar
unknown committed
172
  if (pos != 0 && pos != node.getOccup()) {
173 174
    jam();
    // check if room for one more
unknown's avatar
unknown committed
175
    if (node.getOccup() < tree.m_maxOccup) {
176
      jam();
unknown's avatar
unknown committed
177
      nodePushUp(signal, node, pos, ent);
178 179 180
      return;
    }
    // returns min entry
unknown's avatar
unknown committed
181
    nodePushDown(signal, node, pos - 1, ent);
182
    // find position to add the removed min entry
unknown's avatar
unknown committed
183
    TupLoc childLoc = node.getLink(0);
184
    if (childLoc == NullTupLoc) {
185 186 187 188 189 190
      jam();
      // left child will be added
      pos = 0;
    } else {
      jam();
      // find glb node
191
      while (childLoc != NullTupLoc) {
192
        jam();
unknown's avatar
unknown committed
193 194
        selectNode(signal, node, childLoc, AccHead);
        childLoc = node.getLink(1);
195 196
      }
      // access full node again
unknown's avatar
unknown committed
197 198
      accessNode(signal, node, AccFull);
      pos = node.getOccup();
199 200 201 202 203
    }
    // fall thru to next case
  }
  // adding new min or max
  unsigned i = (pos == 0 ? 0 : 1);
unknown's avatar
unknown committed
204
  ndbrequire(node.getLink(i) == NullTupLoc);
205
  // check if the half-leaf/leaf has room for one more
unknown's avatar
unknown committed
206
  if (node.getOccup() < tree.m_maxOccup) {
207
    jam();
unknown's avatar
unknown committed
208
    nodePushUp(signal, node, pos, ent);
209 210 211
    return;
  }
  // add a new node
unknown's avatar
unknown committed
212 213 214
  NodeHandle childNode(frag);
  insertNode(signal, childNode, AccPref);
  nodePushUp(signal, childNode, 0, ent);
215
  // connect parent and child
unknown's avatar
unknown committed
216 217 218
  node.setLink(i, childNode.m_loc);
  childNode.setLink(2, node.m_loc);
  childNode.setSide(i);
219 220 221 222
  // re-balance tree at each node
  while (true) {
    // height of subtree i has increased by 1
    int j = (i == 0 ? -1 : +1);
unknown's avatar
unknown committed
223
    int b = node.getBalance();
224 225 226
    if (b == 0) {
      // perfectly balanced
      jam();
unknown's avatar
unknown committed
227
      node.setBalance(j);
228 229 230 231
      // height change propagates up
    } else if (b == -j) {
      // height of shorter subtree increased
      jam();
unknown's avatar
unknown committed
232
      node.setBalance(0);
233 234 235 236 237
      // height of tree did not change - done
      break;
    } else if (b == j) {
      // height of longer subtree increased
      jam();
unknown's avatar
unknown committed
238 239 240
      NodeHandle childNode(frag);
      selectNode(signal, childNode, node.getLink(i), AccHead);
      int b2 = childNode.getBalance();
241 242
      if (b2 == b) {
        jam();
unknown's avatar
unknown committed
243
        treeRotateSingle(signal, frag, node, i);
244 245
      } else if (b2 == -b) {
        jam();
unknown's avatar
unknown committed
246
        treeRotateDouble(signal, frag, node, i);
247 248 249 250 251 252 253 254 255
      } else {
        // height of subtree increased so it cannot be perfectly balanced
        ndbrequire(false);
      }
      // height of tree did not increase - done
      break;
    } else {
      ndbrequire(false);
    }
unknown's avatar
unknown committed
256
    TupLoc parentLoc = node.getLink(2);
257
    if (parentLoc == NullTupLoc) {
258 259 260 261
      jam();
      // root node - done
      break;
    }
unknown's avatar
unknown committed
262 263
    i = node.getSide();
    selectNode(signal, node, parentLoc, AccHead);
264 265 266 267 268 269 270 271 272 273 274
  }
}

/*
 * Remove entry.
 */
void
Dbtux::treeRemove(Signal* signal, Frag& frag, TreePos treePos)
{
  TreeHead& tree = frag.m_tree;
  unsigned pos = treePos.m_pos;
unknown's avatar
unknown committed
275
  NodeHandle node(frag);
276
  // access full node
unknown's avatar
unknown committed
277
  selectNode(signal, node, treePos.m_loc, AccFull);
278 279
  TreeEnt ent;
  // check interior node first
unknown's avatar
unknown committed
280
  if (node.getChilds() == 2) {
281
    jam();
unknown's avatar
unknown committed
282
    ndbrequire(node.getOccup() >= tree.m_minOccup);
283
    // check if no underflow
unknown's avatar
unknown committed
284
    if (node.getOccup() > tree.m_minOccup) {
285
      jam();
unknown's avatar
unknown committed
286
      nodePopDown(signal, node, pos, ent);
287 288 289
      return;
    }
    // save current handle
unknown's avatar
unknown committed
290
    NodeHandle parentNode = node;
291
    // find glb node
unknown's avatar
unknown committed
292
    TupLoc childLoc = node.getLink(0);
293
    while (childLoc != NullTupLoc) {
294
      jam();
unknown's avatar
unknown committed
295 296
      selectNode(signal, node, childLoc, AccHead);
      childLoc = node.getLink(1);
297 298
    }
    // access full node again
unknown's avatar
unknown committed
299
    accessNode(signal, node, AccFull);
300
    // use glb max as new parent min
unknown's avatar
unknown committed
301 302
    ent = node.getEnt(node.getOccup() - 1);
    nodePopUp(signal, parentNode, pos, ent);
303
    // set up to remove glb max
unknown's avatar
unknown committed
304
    pos = node.getOccup() - 1;
305 306 307
    // fall thru to next case
  }
  // remove the element
unknown's avatar
unknown committed
308 309
  nodePopDown(signal, node, pos, ent);
  ndbrequire(node.getChilds() <= 1);
310 311 312
  // handle half-leaf
  for (unsigned i = 0; i <= 1; i++) {
    jam();
unknown's avatar
unknown committed
313
    TupLoc childLoc = node.getLink(i);
314
    if (childLoc != NullTupLoc) {
315
      // move to child
unknown's avatar
unknown committed
316
      selectNode(signal, node, childLoc, AccFull);
317 318 319 320
      // balance of half-leaf parent requires child to be leaf
      break;
    }
  }
unknown's avatar
unknown committed
321
  ndbrequire(node.getChilds() == 0);
322
  // get parent if any
unknown's avatar
unknown committed
323 324 325
  TupLoc parentLoc = node.getLink(2);
  NodeHandle parentNode(frag);
  unsigned i = node.getSide();
326
  // move all that fits into parent
327
  if (parentLoc != NullTupLoc) {
328
    jam();
unknown's avatar
unknown committed
329 330
    selectNode(signal, parentNode, node.getLink(2), AccFull);
    nodeSlide(signal, parentNode, node, i);
331 332 333
    // fall thru to next case
  }
  // non-empty leaf
unknown's avatar
unknown committed
334
  if (node.getOccup() >= 1) {
335 336 337 338
    jam();
    return;
  }
  // remove empty leaf
unknown's avatar
unknown committed
339
  deleteNode(signal, node);
340
  if (parentLoc == NullTupLoc) {
341 342
    jam();
    // tree is now empty
343
    tree.m_root = NullTupLoc;
344 345
    return;
  }
unknown's avatar
unknown committed
346 347
  node = parentNode;
  node.setLink(i, NullTupLoc);
348 349
#ifdef dbtux_min_occup_less_max_occup
  // check if we created a half-leaf
unknown's avatar
unknown committed
350
  if (node.getBalance() == 0) {
351 352
    jam();
    // move entries from the other child
unknown's avatar
unknown committed
353 354 355 356 357
    TupLoc childLoc = node.getLink(1 - i);
    NodeHandle childNode(frag);
    selectNode(signal, childNode, childLoc, AccFull);
    nodeSlide(signal, node, childNode, 1 - i);
    if (childNode.getOccup() == 0) {
358
      jam();
unknown's avatar
unknown committed
359 360
      deleteNode(signal, childNode);
      node.setLink(1 - i, NullTupLoc);
361
      // we are balanced again but our parent balance changes by -1
unknown's avatar
unknown committed
362
      parentLoc = node.getLink(2);
363
      if (parentLoc == NullTupLoc) {
364 365 366 367
        jam();
        return;
      }
      // fix side and become parent
unknown's avatar
unknown committed
368 369
      i = node.getSide();
      selectNode(signal, node, parentLoc, AccHead);
370 371 372 373 374 375 376
    }
  }
#endif
  // re-balance tree at each node
  while (true) {
    // height of subtree i has decreased by 1
    int j = (i == 0 ? -1 : +1);
unknown's avatar
unknown committed
377
    int b = node.getBalance();
378 379 380
    if (b == 0) {
      // perfectly balanced
      jam();
unknown's avatar
unknown committed
381
      node.setBalance(-j);
382 383 384 385 386
      // height of tree did not change - done
      return;
    } else if (b == j) {
      // height of longer subtree has decreased
      jam();
unknown's avatar
unknown committed
387
      node.setBalance(0);
388 389 390 391 392
      // height change propagates up
    } else if (b == -j) {
      // height of shorter subtree has decreased
      jam();
      // child on the other side
unknown's avatar
unknown committed
393 394 395
      NodeHandle childNode(frag);
      selectNode(signal, childNode, node.getLink(1 - i), AccHead);
      int b2 = childNode.getBalance();
396 397
      if (b2 == b) {
        jam();
unknown's avatar
unknown committed
398
        treeRotateSingle(signal, frag, node, 1 - i);
399 400 401
        // height of tree decreased and propagates up
      } else if (b2 == -b) {
        jam();
unknown's avatar
unknown committed
402
        treeRotateDouble(signal, frag, node, 1 - i);
403 404 405
        // height of tree decreased and propagates up
      } else {
        jam();
unknown's avatar
unknown committed
406
        treeRotateSingle(signal, frag, node, 1 - i);
407 408 409 410 411 412
        // height of tree did not change - done
        return;
      }
    } else {
      ndbrequire(false);
    }
unknown's avatar
unknown committed
413
    TupLoc parentLoc = node.getLink(2);
414
    if (parentLoc == NullTupLoc) {
415 416 417 418
      jam();
      // root node - done
      return;
    }
unknown's avatar
unknown committed
419 420
    i = node.getSide();
    selectNode(signal, node, parentLoc, AccHead);
421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442
  }
}

/*
 * 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,
unknown's avatar
unknown committed
443
                        NodeHandle& node,
444 445 446 447 448 449
                        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.
unknown's avatar
unknown committed
450
  Verify that bal5 is 1 if RR rotate and -1 if LL rotate.
451
  */
unknown's avatar
unknown committed
452 453 454 455 456
  NodeHandle node5 = node;
  const TupLoc loc5 = node5.m_loc;
  const int bal5 = node5.getBalance();
  const int side5 = node5.getSide();
  ndbrequire(bal5 + (1 - i) == i);
457 458 459 460 461
  /*
  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.
  */
unknown's avatar
unknown committed
462 463 464 465
  TupLoc loc3 = node5.getLink(i);
  NodeHandle node3(frag);
  selectNode(signal, node3, loc3, AccHead);
  const int bal3 = node3.getBalance();
466 467 468 469
  /*
  2 must always be there but is not changed. Thus we mereley check that it
  exists.
  */
unknown's avatar
unknown committed
470
  ndbrequire(node3.getLink(i) != NullTupLoc);
471 472 473 474 475 476
  /*
  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.
  */
unknown's avatar
unknown committed
477 478 479
  TupLoc loc4 = node3.getLink(1 - i);
  NodeHandle node4(frag);
  if (loc4 != NullTupLoc) {
480
    jam();
unknown's avatar
unknown committed
481 482 483 484 485
    selectNode(signal, node4, loc4, AccHead);
    ndbrequire(node4.getSide() == (1 - i) &&
               node4.getLink(2) == loc3);
    node4.setSide(i);
    node4.setLink(2, loc5);
486 487 488 489 490
  }//if

  /*
  Retrieve the address of 5's parent before it is destroyed
  */
unknown's avatar
unknown committed
491
  TupLoc loc0 = node5.getLink(2);
492 493 494 495 496 497 498 499 500 501 502 503 504

  /*
  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.
  */
unknown's avatar
unknown committed
505 506 507 508 509 510 511 512 513
  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) {
514
    jam();
unknown's avatar
unknown committed
515 516 517
    NodeHandle node0(frag);
    selectNode(signal, node0, loc0, AccHead);
    node0.setLink(side5, loc3);
518 519
  } else {
    jam();
unknown's avatar
unknown committed
520
    frag.m_tree.m_root = loc3;
521 522 523 524 525 526 527 528 529 530 531 532
  }//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.
  */
unknown's avatar
unknown committed
533
  if (bal3 == bal5) {
534
    jam();
unknown's avatar
unknown committed
535 536 537
    node3.setBalance(0);
    node5.setBalance(0);
  } else if (bal3 == 0) {
538
    jam();
unknown's avatar
unknown committed
539 540
    node3.setBalance(-bal5);
    node5.setBalance(bal5);
541 542 543 544
  } else {
    ndbrequire(false);
  }//if
  /*
unknown's avatar
unknown committed
545
  Set node to 3 as return parameter for enabling caller to continue
546 547
  traversing the tree.
  */
unknown's avatar
unknown committed
548
  node = node3;
549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652
}

/*
 * 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
unknown's avatar
unknown committed
653
Dbtux::treeRotateDouble(Signal* signal, Frag& frag, NodeHandle& node, unsigned i)
654 655
{
  // old top node
unknown's avatar
unknown committed
656 657
  NodeHandle node6 = node;
  const TupLoc loc6 = node6.m_loc;
658
  // the un-updated balance
unknown's avatar
unknown committed
659 660
  const int bal6 = node6.getBalance();
  const unsigned side6 = node6.getSide();
661 662

  // level 1
unknown's avatar
unknown committed
663 664 665 666
  TupLoc loc2 = node6.getLink(i);
  NodeHandle node2(frag);
  selectNode(signal, node2, loc2, AccHead);
  const int bal2 = node2.getBalance();
667 668

  // level 2
unknown's avatar
unknown committed
669 670 671 672
  TupLoc loc4 = node2.getLink(1 - i);
  NodeHandle node4(frag);
  selectNode(signal, node4, loc4, AccHead);
  const int bal4 = node4.getBalance();
673 674

  ndbrequire(i <= 1);
unknown's avatar
unknown committed
675 676 677 678 679
  ndbrequire(bal6 + (1 - i) == i);
  ndbrequire(bal2 == -bal6);
  ndbrequire(node2.getLink(2) == loc6);
  ndbrequire(node2.getSide() == i);
  ndbrequire(node4.getLink(2) == loc2);
680 681

  // level 3
unknown's avatar
unknown committed
682 683
  TupLoc loc3 = node4.getLink(i);
  TupLoc loc5 = node4.getLink(1 - i);
684 685

  // fill up leaf before it becomes internal
unknown's avatar
unknown committed
686
  if (loc3 == NullTupLoc && loc5 == NullTupLoc) {
687 688
    jam();
    TreeHead& tree = frag.m_tree;
unknown's avatar
unknown committed
689 690 691
    accessNode(signal, node2, AccFull);
    accessNode(signal, node4, AccFull);
    nodeSlide(signal, node4, node2, i);
692
    // implied by rule of merging half-leaves with leaves
unknown's avatar
unknown committed
693 694
    ndbrequire(node4.getOccup() >= tree.m_minOccup);
    ndbrequire(node2.getOccup() != 0);
695
  } else {
unknown's avatar
unknown committed
696
    if (loc3 != NullTupLoc) {
697
      jam();
unknown's avatar
unknown committed
698 699 700 701
      NodeHandle node3(frag);
      selectNode(signal, node3, loc3, AccHead);
      node3.setLink(2, loc2);
      node3.setSide(1 - i);
702
    }
unknown's avatar
unknown committed
703
    if (loc5 != NullTupLoc) {
704
      jam();
unknown's avatar
unknown committed
705 706 707 708
      NodeHandle node5(frag);
      selectNode(signal, node5, loc5, AccHead);
      node5.setLink(2, node6.m_loc);
      node5.setSide(i);
709 710 711
    }
  }
  // parent
unknown's avatar
unknown committed
712 713
  TupLoc loc0 = node6.getLink(2);
  NodeHandle node0(frag);
714
  // perform the rotation
unknown's avatar
unknown committed
715 716 717
  node6.setLink(i, loc5);
  node6.setLink(2, loc4);
  node6.setSide(1 - i);
718

unknown's avatar
unknown committed
719 720
  node2.setLink(1 - i, loc3);
  node2.setLink(2, loc4);
721

unknown's avatar
unknown committed
722 723 724 725
  node4.setLink(i, loc2);
  node4.setLink(1 - i, loc6);
  node4.setLink(2, loc0);
  node4.setSide(side6);
726

unknown's avatar
unknown committed
727
  if (loc0 != NullTupLoc) {
728
    jam();
unknown's avatar
unknown committed
729 730
    selectNode(signal, node0, loc0, AccHead);
    node0.setLink(side6, loc4);
731 732
  } else {
    jam();
unknown's avatar
unknown committed
733
    frag.m_tree.m_root = loc4;
734 735
  }
  // set balance of changed nodes
unknown's avatar
unknown committed
736 737
  node4.setBalance(0);
  if (bal4 == 0) {
738
    jam();
unknown's avatar
unknown committed
739 740 741
    node2.setBalance(0);
    node6.setBalance(0);
  } else if (bal4 == -bal2) {
742
    jam();
unknown's avatar
unknown committed
743 744 745
    node2.setBalance(0);
    node6.setBalance(bal2);
  } else if (bal4 == bal2) {
746
    jam();
unknown's avatar
unknown committed
747 748
    node2.setBalance(-bal2);
    node6.setBalance(0);
749 750 751 752
  } else {
    ndbrequire(false);
  }
  // new top node
unknown's avatar
unknown committed
753
  node = node4;
754
}