You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by sb...@apache.org on 2017/05/26 14:06:10 UTC
[10/39] ignite git commit: master - BPlusTree: compare with lvl
master - BPlusTree: compare with lvl
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo
Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/ff813891
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/ff813891
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/ff813891
Branch: refs/heads/ignite-5075-cc-debug
Commit: ff813891dffb24021f4f7b744cf30d58d919dc42
Parents: 33cb5e8
Author: Sergi Vladykin <se...@gmail.com>
Authored: Wed May 24 08:52:24 2017 +0300
Committer: Sergi Vladykin <se...@gmail.com>
Committed: Wed May 24 08:52:24 2017 +0300
----------------------------------------------------------------------
.../cache/database/tree/BPlusTree.java | 64 +++++++++++++-------
1 file changed, 41 insertions(+), 23 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/ignite/blob/ff813891/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java
index a4c09d5..4d2110c 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java
@@ -253,11 +253,12 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
int cnt = io.getCount(pageAddr);
int idx;
+
if (g.findLast)
- idx = io.isLeaf()? cnt - 1: -cnt - 1; //(-cnt - 1) mimics not_found result of findInsertionPoint
- //in case of cnt = 0 we end up in 'not found' branch below with idx being 0 after fix() adjustment
+ idx = io.isLeaf() ? cnt - 1 : -cnt - 1; // (-cnt - 1) mimics not_found result of findInsertionPoint
+ // in case of cnt = 0 we end up in 'not found' branch below with idx being 0 after fix() adjustment
else
- idx = findInsertionPoint(io, pageAddr, 0, cnt, g.row, g.shift);
+ idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, g.row, g.shift);
boolean found = idx >= 0;
@@ -338,7 +339,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert p.btmLvl == 0 : "split is impossible with replace";
final int cnt = io.getCount(pageAddr);
- final int idx = findInsertionPoint(io, pageAddr, 0, cnt, p.row, 0);
+ final int idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, p.row, 0);
if (idx < 0) // Not found, split or merge happened.
return RETRY;
@@ -399,7 +400,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
return RETRY;
int cnt = io.getCount(pageAddr);
- int idx = findInsertionPoint(io, pageAddr, 0, cnt, p.row, 0);
+ int idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, p.row, 0);
if (idx >= 0) // We do not support concurrent put of the same key.
throw new IllegalStateException("Duplicate row in index.");
@@ -451,7 +452,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert cnt <= Short.MAX_VALUE: cnt;
- int idx = findInsertionPoint(io, leafAddr, 0, cnt, r.row, 0);
+ int idx = findInsertionPoint(lvl, io, leafAddr, 0, cnt, r.row, 0);
if (idx < 0)
return RETRY; // We've found exact match on search but now it's gone.
@@ -1205,7 +1206,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
validateDownPages(rootPageId, 0L, rootLvl);
- validateDownKeys(rootPageId, null);
+ validateDownKeys(rootPageId, null, rootLvl);
}
finally {
releasePage(metaPageId, metaPage);
@@ -1217,7 +1218,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @param minRow Minimum row.
* @throws IgniteCheckedException If failed.
*/
- private void validateDownKeys(long pageId, L minRow) throws IgniteCheckedException {
+ private void validateDownKeys(long pageId, L minRow, int lvl) throws IgniteCheckedException {
long page = acquirePage(pageId);
try {
long pageAddr = readLock(pageId, page); // No correctness guaranties.
@@ -1232,7 +1233,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (io.isLeaf()) {
for (int i = 0; i < cnt; i++) {
- if (minRow != null && compare(io, pageAddr, i, minRow) <= 0)
+ if (minRow != null && compare(lvl, io, pageAddr, i, minRow) <= 0)
fail("Wrong sort order: " + U.hexLong(pageId) + " , at " + i + " , minRow: " + minRow);
minRow = io.getLookupRow(this, pageAddr, i);
@@ -1245,20 +1246,20 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
for (int i = 0; i < cnt; i++) {
L row = io.getLookupRow(this, pageAddr, i);
- if (minRow != null && compare(io, pageAddr, i, minRow) <= 0)
+ if (minRow != null && compare(lvl, io, pageAddr, i, minRow) <= 0)
fail("Min row violated: " + row + " , minRow: " + minRow);
long leftId = inner(io).getLeft(pageAddr, i);
L leafRow = getGreatestRowInSubTree(leftId);
- int cmp = compare(io, pageAddr, i, leafRow);
+ int cmp = compare(lvl, io, pageAddr, i, leafRow);
if (cmp < 0 || (cmp != 0 && canGetRowFromInner))
fail("Wrong inner row: " + U.hexLong(pageId) + " , at: " + i + " , leaf: " + leafRow +
" , inner: " + row);
- validateDownKeys(leftId, minRow);
+ validateDownKeys(leftId, minRow, lvl - 1);
minRow = row;
}
@@ -1266,7 +1267,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Need to handle the rightmost child subtree separately or handle empty routing page.
long rightId = inner(io).getLeft(pageAddr, cnt); // The same as getRight(cnt - 1)
- validateDownKeys(rightId, minRow);
+ validateDownKeys(rightId, minRow, lvl - 1);
}
finally {
readUnlock(pageId, page, pageAddr);
@@ -2694,7 +2695,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert fwdPageAddr != 0L;
// TODO GG-11640 log a correct forward page record.
- Boolean fwdPageWalPlc = Boolean.TRUE;
+ final Boolean fwdPageWalPlc = Boolean.TRUE;
try {
boolean midShift = splitPage(pageId, page, pageAddr, io, fwdId, fwdPageAddr, idx);
@@ -2742,7 +2743,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert newRootAddr != 0L;
// Never write full new root page, because it is known to be new.
- Boolean newRootPageWalPlc = Boolean.FALSE;
+ final Boolean newRootPageWalPlc = Boolean.FALSE;
try {
boolean needWal = needWalDeltaRecord(newRootId, newRootPage, newRootPageWalPlc);
@@ -3650,7 +3651,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert tail.type == Tail.EXACT: tail.type;
if (tail.idx == Short.MIN_VALUE) {
- int idx = findInsertionPoint(tail.io, tail.buf, 0, tail.getCount(), row, 0);
+ int idx = findInsertionPoint(tail.lvl, tail.io, tail.buf, 0, tail.getCount(), row, 0);
assert checkIndex(idx): idx;
@@ -4173,7 +4174,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
private byte type;
/** */
- private final byte lvl;
+ private final int lvl;
/** */
private short idx = Short.MIN_VALUE;
@@ -4249,7 +4250,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return Insertion point as in {@link Arrays#binarySearch(Object[], Object, Comparator)}.
* @throws IgniteCheckedException If failed.
*/
- private int findInsertionPoint(BPlusIO<L> io, long buf, int low, int cnt, L row, int shift)
+ private int findInsertionPoint(int lvl, BPlusIO<L> io, long buf, int low, int cnt, L row, int shift)
throws IgniteCheckedException {
assert row != null;
@@ -4258,7 +4259,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
while (low <= high) {
int mid = (low + high) >>> 1;
- int cmp = compare(io, buf, mid, row);
+ int cmp = compare(lvl, io, buf, mid, row);
if (cmp == 0)
cmp = -shift; // We need to fix the case when search row matches multiple data rows.
@@ -4329,6 +4330,19 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
protected abstract int compare(BPlusIO<L> io, long pageAddr, int idx, L row) throws IgniteCheckedException;
/**
+ * @param lvl Level.
+ * @param io IO.
+ * @param pageAddr Page address.
+ * @param idx Index of row in the given buffer.
+ * @param row Lookup row.
+ * @return Comparison result as in {@link Comparator#compare(Object, Object)}.
+ * @throws IgniteCheckedException If failed.
+ */
+ protected int compare(int lvl, BPlusIO<L> io, long pageAddr, int idx, L row) throws IgniteCheckedException {
+ return compare(io, pageAddr, idx, row);
+ }
+
+ /**
* Get a full detached data row.
*
* @param io IO.
@@ -4421,11 +4435,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @throws IgniteCheckedException If failed.
*/
private int findLowerBound(long pageAddr, BPlusIO<L> io, int cnt) throws IgniteCheckedException {
+ assert io.isLeaf();
+
// Compare with the first row on the page.
- int cmp = compare(io, pageAddr, 0, lowerBound);
+ int cmp = compare(0, io, pageAddr, 0, lowerBound);
if (cmp < 0 || (cmp == 0 && lowerShift == 1)) {
- int idx = findInsertionPoint(io, pageAddr, 0, cnt, lowerBound, lowerShift);
+ int idx = findInsertionPoint(0, io, pageAddr, 0, cnt, lowerBound, lowerShift);
assert idx < 0;
@@ -4444,11 +4460,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @throws IgniteCheckedException If failed.
*/
private int findUpperBound(long pageAddr, BPlusIO<L> io, int low, int cnt) throws IgniteCheckedException {
+ assert io.isLeaf();
+
// Compare with the last row on the page.
- int cmp = compare(io, pageAddr, cnt - 1, upperBound);
+ int cmp = compare(0, io, pageAddr, cnt - 1, upperBound);
if (cmp > 0) {
- int idx = findInsertionPoint(io, pageAddr, low, cnt, upperBound, 1);
+ int idx = findInsertionPoint(0, io, pageAddr, low, cnt, upperBound, 1);
assert idx < 0;