1 /* Copyright (c) 2003-2006 MySQL AB
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
16 #define DBTUX_TREE_CPP
20 * Add entry. Handle the case when there is room for one more. This
21 * is the common case given slack in nodes.
24 Dbtux::treeAdd(Frag
& frag
, TreePos treePos
, TreeEnt ent
)
26 TreeHead
& tree
= frag
.m_tree
;
27 NodeHandle
node(frag
);
29 if (treePos
.m_loc
!= NullTupLoc
) {
32 selectNode(node
, treePos
.m_loc
);
33 unsigned pos
= treePos
.m_pos
;
34 if (node
.getOccup() < tree
.m_maxOccup
) {
37 nodePushUp(node
, pos
, ent
, RNIL
);
40 treeAddFull(frag
, node
, pos
, ent
);
45 nodePushUp(node
, 0, ent
, RNIL
);
47 tree
.m_root
= node
.m_loc
;
54 * Add entry when node is full. Handle the case when there is g.l.b
55 * node in left subtree with room for one more. It will receive the min
56 * entry of this node. The min entry could be the entry to add.
59 Dbtux::treeAddFull(Frag
& frag
, NodeHandle lubNode
, unsigned pos
, TreeEnt ent
)
61 TreeHead
& tree
= frag
.m_tree
;
62 TupLoc loc
= lubNode
.getLink(0);
63 if (loc
!= NullTupLoc
) {
65 NodeHandle
glbNode(frag
);
68 selectNode(glbNode
, loc
);
69 loc
= glbNode
.getLink(1);
70 } while (loc
!= NullTupLoc
);
71 if (glbNode
.getOccup() < tree
.m_maxOccup
) {
72 // g.l.b node has room
74 Uint32 scanList
= RNIL
;
77 // add the new entry and return min entry
78 nodePushDown(lubNode
, pos
- 1, ent
, scanList
);
80 // g.l.b node receives min entry from l.u.b node
81 nodePushUp(glbNode
, glbNode
.getOccup(), ent
, scanList
);
84 treeAddNode(frag
, lubNode
, pos
, ent
, glbNode
, 1);
87 treeAddNode(frag
, lubNode
, pos
, ent
, lubNode
, 0);
91 * Add entry when there is no g.l.b node in left subtree or the g.l.b
92 * node is full. We must add a new left or right child node which
93 * becomes the new g.l.b node.
96 Dbtux::treeAddNode(Frag
& frag
, NodeHandle lubNode
, unsigned pos
, TreeEnt ent
, NodeHandle parentNode
, unsigned i
)
98 NodeHandle
glbNode(frag
);
100 // connect parent and child
101 parentNode
.setLink(i
, glbNode
.m_loc
);
102 glbNode
.setLink(2, parentNode
.m_loc
);
104 Uint32 scanList
= RNIL
;
107 // add the new entry and return min entry
108 nodePushDown(lubNode
, pos
- 1, ent
, scanList
);
110 // g.l.b node receives min entry from l.u.b node
111 nodePushUp(glbNode
, 0, ent
, scanList
);
112 // re-balance the tree
113 treeAddRebalance(frag
, parentNode
, i
);
117 * Re-balance tree after adding a node. The process starts with the
118 * parent of the added node.
121 Dbtux::treeAddRebalance(Frag
& frag
, NodeHandle node
, unsigned i
)
124 // height of subtree i has increased by 1
125 int j
= (i
== 0 ? -1 : +1);
126 int b
= node
.getBalance();
128 // perfectly balanced
131 // height change propagates up
132 } else if (b
== -j
) {
133 // height of shorter subtree increased
136 // height of tree did not change - done
139 // height of longer subtree increased
141 NodeHandle
childNode(frag
);
142 selectNode(childNode
, node
.getLink(i
));
143 int b2
= childNode
.getBalance();
146 treeRotateSingle(frag
, node
, i
);
147 } else if (b2
== -b
) {
149 treeRotateDouble(frag
, node
, i
);
151 // height of subtree increased so it cannot be perfectly balanced
154 // height of tree did not increase - done
159 TupLoc parentLoc
= node
.getLink(2);
160 if (parentLoc
== NullTupLoc
) {
166 selectNode(node
, parentLoc
);
171 * Remove entry. Optimize for nodes with slack. Handle the case when
172 * there is no underflow i.e. occupancy remains at least minOccup. For
173 * interior nodes this is a requirement. For others it means that we do
174 * not need to consider merge of semi-leaf and leaf.
177 Dbtux::treeRemove(Frag
& frag
, TreePos treePos
)
179 TreeHead
& tree
= frag
.m_tree
;
180 unsigned pos
= treePos
.m_pos
;
181 NodeHandle
node(frag
);
182 selectNode(node
, treePos
.m_loc
);
185 if (node
.getOccup() > tree
.m_minOccup
) {
186 // no underflow in any node type
188 nodePopDown(node
, pos
, ent
, 0);
191 if (node
.getChilds() == 2) {
192 // underflow in interior node
194 treeRemoveInner(frag
, node
, pos
);
197 // remove entry in semi/leaf
198 nodePopDown(node
, pos
, ent
, 0);
199 if (node
.getLink(0) != NullTupLoc
) {
201 treeRemoveSemi(frag
, node
, 0);
204 if (node
.getLink(1) != NullTupLoc
) {
206 treeRemoveSemi(frag
, node
, 1);
209 treeRemoveLeaf(frag
, node
);
212 ndbrequire(tree
.m_entryCount
!= 0);
217 * Remove entry when interior node underflows. There is g.l.b node in
218 * left subtree to borrow an entry from. The max entry of the g.l.b
219 * node becomes the min entry of this node.
222 Dbtux::treeRemoveInner(Frag
& frag
, NodeHandle lubNode
, unsigned pos
)
226 NodeHandle
glbNode(frag
);
227 TupLoc loc
= lubNode
.getLink(0);
230 selectNode(glbNode
, loc
);
231 loc
= glbNode
.getLink(1);
232 } while (loc
!= NullTupLoc
);
233 // borrow max entry from semi/leaf
234 Uint32 scanList
= RNIL
;
235 nodePopDown(glbNode
, glbNode
.getOccup() - 1, ent
, &scanList
);
236 // g.l.b may be empty now
237 // a descending scan may try to enter the empty g.l.b
238 // we prevent this in scanNext
239 nodePopUp(lubNode
, pos
, ent
, scanList
);
240 if (glbNode
.getLink(0) != NullTupLoc
) {
242 treeRemoveSemi(frag
, glbNode
, 0);
245 treeRemoveLeaf(frag
, glbNode
);
249 * Handle semi-leaf after removing an entry. Move entries from leaf to
250 * semi-leaf to bring semi-leaf occupancy above minOccup, if possible.
251 * The leaf may become empty.
254 Dbtux::treeRemoveSemi(Frag
& frag
, NodeHandle semiNode
, unsigned i
)
256 TreeHead
& tree
= frag
.m_tree
;
257 ndbrequire(semiNode
.getChilds() < 2);
258 TupLoc leafLoc
= semiNode
.getLink(i
);
259 NodeHandle
leafNode(frag
);
260 selectNode(leafNode
, leafLoc
);
261 if (semiNode
.getOccup() < tree
.m_minOccup
) {
263 unsigned cnt
= min(leafNode
.getOccup(), tree
.m_minOccup
- semiNode
.getOccup());
264 nodeSlide(semiNode
, leafNode
, cnt
, i
);
265 if (leafNode
.getOccup() == 0) {
268 treeRemoveNode(frag
, leafNode
);
274 * Handle leaf after removing an entry. If parent is semi-leaf, move
275 * entries to it as in the semi-leaf case. If parent is interior node,
279 Dbtux::treeRemoveLeaf(Frag
& frag
, NodeHandle leafNode
)
281 TreeHead
& tree
= frag
.m_tree
;
282 TupLoc parentLoc
= leafNode
.getLink(2);
283 if (parentLoc
!= NullTupLoc
) {
285 NodeHandle
parentNode(frag
);
286 selectNode(parentNode
, parentLoc
);
287 unsigned i
= leafNode
.getSide();
288 if (parentNode
.getLink(1 - i
) == NullTupLoc
) {
289 // parent is semi-leaf
291 if (parentNode
.getOccup() < tree
.m_minOccup
) {
293 unsigned cnt
= min(leafNode
.getOccup(), tree
.m_minOccup
- parentNode
.getOccup());
294 nodeSlide(parentNode
, leafNode
, cnt
, i
);
298 if (leafNode
.getOccup() == 0) {
301 treeRemoveNode(frag
, leafNode
);
309 Dbtux::treeRemoveNode(Frag
& frag
, NodeHandle leafNode
)
311 TreeHead
& tree
= frag
.m_tree
;
312 ndbrequire(leafNode
.getChilds() == 0);
313 TupLoc parentLoc
= leafNode
.getLink(2);
314 unsigned i
= leafNode
.getSide();
315 deleteNode(leafNode
);
316 if (parentLoc
!= NullTupLoc
) {
318 NodeHandle
parentNode(frag
);
319 selectNode(parentNode
, parentLoc
);
320 parentNode
.setLink(i
, NullTupLoc
);
321 // re-balance the tree
322 treeRemoveRebalance(frag
, parentNode
, i
);
326 tree
.m_root
= NullTupLoc
;
330 * Re-balance tree after removing a node. The process starts with the
331 * parent of the removed node.
334 Dbtux::treeRemoveRebalance(Frag
& frag
, NodeHandle node
, unsigned i
)
337 // height of subtree i has decreased by 1
338 int j
= (i
== 0 ? -1 : +1);
339 int b
= node
.getBalance();
341 // perfectly balanced
344 // height of tree did not change - done
347 // height of longer subtree has decreased
350 // height change propagates up
351 } else if (b
== -j
) {
352 // height of shorter subtree has decreased
354 // child on the other side
355 NodeHandle
childNode(frag
);
356 selectNode(childNode
, node
.getLink(1 - i
));
357 int b2
= childNode
.getBalance();
360 treeRotateSingle(frag
, node
, 1 - i
);
361 // height of tree decreased and propagates up
362 } else if (b2
== -b
) {
364 treeRotateDouble(frag
, node
, 1 - i
);
365 // height of tree decreased and propagates up
368 treeRotateSingle(frag
, node
, 1 - i
);
369 // height of tree did not change - done
375 TupLoc parentLoc
= node
.getLink(2);
376 if (parentLoc
== NullTupLoc
) {
382 selectNode(node
, parentLoc
);
387 * Single rotation about node 5. One of LL (i=0) or RR (i=1).
399 * In this change 5,3 and 2 must always be there. 0, 1, 2, 4 and 6 are
400 * all optional. If 4 are there it changes side.
403 Dbtux::treeRotateSingle(Frag
& frag
, NodeHandle
& node
, unsigned i
)
407 5 is the old top node that have been unbalanced due to an insert or
408 delete. The balance is still the old balance before the update.
409 Verify that bal5 is 1 if RR rotate and -1 if LL rotate.
411 NodeHandle node5
= node
;
412 const TupLoc loc5
= node5
.m_loc
;
413 const int bal5
= node5
.getBalance();
414 const int side5
= node5
.getSide();
415 ndbrequire(bal5
+ (1 - i
) == i
);
417 3 is the new root of this part of the tree which is to swap place with
418 node 5. For an insert to cause this it must have the same balance as 5.
419 For deletes it can have the balance 0.
421 TupLoc loc3
= node5
.getLink(i
);
422 NodeHandle
node3(frag
);
423 selectNode(node3
, loc3
);
424 const int bal3
= node3
.getBalance();
426 2 must always be there but is not changed. Thus we mereley check that it
429 ndbrequire(node3
.getLink(i
) != NullTupLoc
);
431 4 is not necessarily there but if it is there it will move from one
432 side of 3 to the other side of 5. For LL it moves from the right side
433 to the left side and for RR it moves from the left side to the right
434 side. This means that it also changes parent from 3 to 5.
436 TupLoc loc4
= node3
.getLink(1 - i
);
437 NodeHandle
node4(frag
);
438 if (loc4
!= NullTupLoc
) {
440 selectNode(node4
, loc4
);
441 ndbrequire(node4
.getSide() == (1 - i
) &&
442 node4
.getLink(2) == loc3
);
444 node4
.setLink(2, loc5
);
448 Retrieve the address of 5's parent before it is destroyed
450 TupLoc loc0
= node5
.getLink(2);
453 The next step is to perform the rotation. 3 will inherit 5's parent
454 and side. 5 will become a child of 3 on the right side for LL and on
455 the left side for RR.
456 5 will get 3 as the parent. It will get 4 as a child and it will be
457 on the right side of 3 for LL and left side of 3 for RR.
458 The final step of the rotate is to check whether 5 originally had any
459 parent. If it had not then 3 is the new root node.
460 We will also verify some preconditions for the change to occur.
461 1. 3 must have had 5 as parent before the change.
462 2. 3's side is left for LL and right for RR before change.
464 ndbrequire(node3
.getLink(2) == loc5
);
465 ndbrequire(node3
.getSide() == i
);
466 node3
.setLink(1 - i
, loc5
);
467 node3
.setLink(2, loc0
);
468 node3
.setSide(side5
);
469 node5
.setLink(i
, loc4
);
470 node5
.setLink(2, loc3
);
471 node5
.setSide(1 - i
);
472 if (loc0
!= NullTupLoc
) {
474 NodeHandle
node0(frag
);
475 selectNode(node0
, loc0
);
476 node0
.setLink(side5
, loc3
);
479 frag
.m_tree
.m_root
= loc3
;
481 /* The final step of the change is to update the balance of 3 and
482 5 that changed places. There are two cases here. The first case is
483 when 3 unbalanced in the same direction by an insert or a delete.
484 In this case the changes will make the tree balanced again for both
486 The second case only occurs at deletes. In this case 3 starts out
487 balanced. In the figure above this could occur if 4 starts out with
488 a right node and the rotate is triggered by a delete of 6's only child.
489 In this case 5 will change balance but still be unbalanced and 3 will
490 be unbalanced in the opposite direction of 5.
496 } else if (bal3
== 0) {
498 node3
.setBalance(-bal5
);
499 node5
.setBalance(bal5
);
504 Set node to 3 as return parameter for enabling caller to continue
511 * Double rotation about node 6. One of LR (i=0) or RL (i=1).
523 * In this change 6, 2 and 4 must be there, all others are optional.
524 * We will start by proving a Lemma.
526 * The height of the sub-trees 1 and 7 and the maximum height of the
527 * threes from 3 and 5 are all the same.
529 * maxheight(3,5) is defined as the maximum height of 3 and 5.
530 * If height(7) > maxheight(3,5) then the AVL condition is ok and we
531 * don't need to perform a rotation.
532 * If height(7) < maxheight(3,5) then the balance of 6 would be at least
533 * -3 which cannot happen in an AVL tree even before a rotation.
534 * Thus we conclude that height(7) == maxheight(3,5)
536 * The next step is to prove that the height of 1 is equal to maxheight(3,5).
537 * If height(1) - 1 > maxheight(3,5) then we would have
538 * balance in 6 equal to -3 at least which cannot happen in an AVL-tree.
539 * If height(1) - 1 = maxheight(3,5) then we should have solved the
540 * unbalance with a single rotate and not with a double rotate.
541 * If height(1) + 1 = maxheight(3,5) then we would be doing a rotate
542 * with node 2 as the root of the rotation.
543 * If height(1) + k = maxheight(3,5) where k >= 2 then the tree could not have
544 * been an AVL-tree before the insert or delete.
545 * Thus we conclude that height(1) = maxheight(3,5)
547 * Thus we conclude that height(1) = maxheight(3,5) = height(7).
550 * The balance of node 4 before the rotation can be any (-1, 0, +1).
552 * The following changes are needed:
554 * 1) Changes parent from 0 -> 4
555 * 2) 1 - i link stays the same
556 * 3) i side link is derived from 1 - i side link from 4
557 * 4) Side is set to 1 - i
559 * If balance(4) == 0 then balance(6) = 0
560 * since height(3) = height(5) = maxheight(3,5) = height(7)
561 * If balance(4) == +1 then balance(6) = 0
562 * since height(5) = maxheight(3,5) = height(7)
563 * If balance(4) == -1 then balance(6) = 1
564 * since height(5) + 1 = maxheight(3,5) = height(7)
567 * 1) Changes parent from 6 -> 4
568 * 2) i side link stays the same
569 * 3) 1 - i side link is derived from i side link of 4
570 * 4) Side is set to i (thus not changed)
572 * If balance(4) == 0 then balance(2) = 0
573 * since height(3) = height(5) = maxheight(3,5) = height(1)
574 * If balance(4) == -1 then balance(2) = 0
575 * since height(3) = maxheight(3,5) = height(1)
576 * If balance(4) == +1 then balance(6) = 1
577 * since height(3) + 1 = maxheight(3,5) = height(1)
580 * 1) Inherits parent from 6
581 * 2) i side link is 2
582 * 3) 1 - i side link is 6
583 * 4) Side is inherited from 6
584 * 5) Balance(4) = 0 independent of previous balance
586 * If height(1) = 0 then only 2, 4 and 6 are involved and then it is
588 * If height(1) >= 1 then we are sure that 1 and 7 exist with the same
589 * height and that if 3 and 5 exist they are of the same height as 1 and
590 * 7 and thus we know that 4 is balanced since newheight(2) = newheight(6).
593 * 1) Change parent from 4 to 2
594 * 2) Change side from i to 1 - i
597 * 1) Change parent from 4 to 6
598 * 2) Change side from 1 - i to i
601 * 1) previous link to 6 is replaced by link to 4 on proper side
603 * Node 1 and 7 needs no changes at all.
605 * Some additional requires are that balance(2) = - balance(6) = -1/+1 since
606 * otherwise we would do a single rotate.
608 * The balance(6) is -1 if i == 0 and 1 if i == 1
612 Dbtux::treeRotateDouble(Frag
& frag
, NodeHandle
& node
, unsigned i
)
614 TreeHead
& tree
= frag
.m_tree
;
617 NodeHandle node6
= node
;
618 const TupLoc loc6
= node6
.m_loc
;
619 // the un-updated balance
620 const int bal6
= node6
.getBalance();
621 const unsigned side6
= node6
.getSide();
624 TupLoc loc2
= node6
.getLink(i
);
625 NodeHandle
node2(frag
);
626 selectNode(node2
, loc2
);
627 const int bal2
= node2
.getBalance();
630 TupLoc loc4
= node2
.getLink(1 - i
);
631 NodeHandle
node4(frag
);
632 selectNode(node4
, loc4
);
633 const int bal4
= node4
.getBalance();
636 ndbrequire(bal6
+ (1 - i
) == i
);
637 ndbrequire(bal2
== -bal6
);
638 ndbrequire(node2
.getLink(2) == loc6
);
639 ndbrequire(node2
.getSide() == i
);
640 ndbrequire(node4
.getLink(2) == loc2
);
643 TupLoc loc3
= node4
.getLink(i
);
644 TupLoc loc5
= node4
.getLink(1 - i
);
646 // fill up leaf before it becomes internal
647 if (loc3
== NullTupLoc
&& loc5
== NullTupLoc
) {
649 if (node4
.getOccup() < tree
.m_minOccup
) {
651 unsigned cnt
= tree
.m_minOccup
- node4
.getOccup();
652 ndbrequire(cnt
< node2
.getOccup());
653 nodeSlide(node4
, node2
, cnt
, i
);
654 ndbrequire(node4
.getOccup() >= tree
.m_minOccup
);
655 ndbrequire(node2
.getOccup() != 0);
658 if (loc3
!= NullTupLoc
) {
660 NodeHandle
node3(frag
);
661 selectNode(node3
, loc3
);
662 node3
.setLink(2, loc2
);
663 node3
.setSide(1 - i
);
665 if (loc5
!= NullTupLoc
) {
667 NodeHandle
node5(frag
);
668 selectNode(node5
, loc5
);
669 node5
.setLink(2, node6
.m_loc
);
674 TupLoc loc0
= node6
.getLink(2);
675 NodeHandle
node0(frag
);
676 // perform the rotation
677 node6
.setLink(i
, loc5
);
678 node6
.setLink(2, loc4
);
679 node6
.setSide(1 - i
);
681 node2
.setLink(1 - i
, loc3
);
682 node2
.setLink(2, loc4
);
684 node4
.setLink(i
, loc2
);
685 node4
.setLink(1 - i
, loc6
);
686 node4
.setLink(2, loc0
);
687 node4
.setSide(side6
);
689 if (loc0
!= NullTupLoc
) {
691 selectNode(node0
, loc0
);
692 node0
.setLink(side6
, loc4
);
695 frag
.m_tree
.m_root
= loc4
;
697 // set balance of changed nodes
703 } else if (bal4
== -bal2
) {
706 node6
.setBalance(bal2
);
707 } else if (bal4
== bal2
) {
709 node2
.setBalance(-bal2
);