ignite-db - wip
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/74dfb8f9 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/74dfb8f9 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/74dfb8f9 Branch: refs/heads/ignite-db-x-10884 Commit: 74dfb8f971cd44a1b10d8fdab6a8bb19c98dd7a7 Parents: 3df530a Author: S.Vladykin <[email protected]> Authored: Mon Apr 25 19:58:51 2016 +0300 Committer: S.Vladykin <[email protected]> Committed: Mon Apr 25 19:58:51 2016 +0300 ---------------------------------------------------------------------- .../cache/database/tree/BPlusTree.java | 325 +++++++------------ .../processors/database/BPlusTreeSelfTest.java | 89 ++++- 2 files changed, 202 insertions(+), 212 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/74dfb8f9/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 61e612a..a24c38a 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 @@ -210,8 +210,10 @@ public abstract class BPlusTree<L, T extends L> { if (cnt != 0) // It is not a routing page and we are going to the right, can get backId here. g.backId = inner(io).getLeft(buf, cnt - 1); - else if (needBackIfRouting && g.getClass() == Remove.class) - return Remove.GO_DOWN_X; // Can't get backId here because of possible deadlock. + else if (needBackIfRouting) { + // Can't get backId here because of possible deadlock and it is only needed for remove operation. + return Remove.GO_DOWN_X; + } } return Get.GO_DOWN; @@ -322,7 +324,16 @@ public abstract class BPlusTree<L, T extends L> { r.removed = getRow(io, buf, idx); - r.doRemove(io, leaf, buf, cnt, idx, 0, false); + r.doRemove(io, buf, cnt, idx); + + if (r.needReplaceInner == TRUE) { + // We increment remove ID in write lock on leaf page, thus it is guaranteed that + // any successor will get greater value than he had read at the beginning of the operation. + // Thus he is guaranteed to do a retry from root. Since inner replace takes locks on the whole branch + // and releases the locks only when the inner key is updated and the successor saw the updated removeId, + // then after retry from root, he will see updated inner key. + io.setRemoveId(buf, globalRmvId.incrementAndGet()); + } // We may need to replace inner key or want to merge this leaf with sibling after the remove -> keep lock. if (r.needReplaceInner == TRUE || @@ -332,10 +343,7 @@ public abstract class BPlusTree<L, T extends L> { if (r.fwdId != 0 && r.backId == 0) r.lockForward(0); - r.addTail(leaf, buf, io, 0, Tail.EXACT, Integer.MIN_VALUE); - - if (r.needReplaceInner == FALSE) - r.needMerge = TRUE; + r.addTail(leaf, buf, io, 0, Tail.EXACT, -1); } return Remove.FOUND; @@ -353,12 +361,9 @@ public abstract class BPlusTree<L, T extends L> { // Correct locking order: from back to forward. int res = r.doRemoveFromLeaf(); - // If we need to do more tricks, then we have to keep locks on back and leaf pages. - if (res == Remove.FOUND && (r.needMerge == TRUE || r.needReplaceInner == TRUE)) { - assert r.needMerge == TRUE ^ r.needReplaceInner == TRUE: "we can do only one thing at once"; - - r.addTail(back, buf, io, lvl, Tail.BACK, Integer.MIN_VALUE); - } + // Keep locks on back and leaf pages for subsequent merges. + if (res == Remove.FOUND && r.tail != null) + r.addTail(back, buf, io, lvl, Tail.BACK, -1); return res; } @@ -376,7 +381,7 @@ public abstract class BPlusTree<L, T extends L> { int res = r.doLockTail(lvl); if (res == Remove.FOUND) - r.addTail(back, buf, io, lvl, Tail.BACK, Integer.MIN_VALUE); + r.addTail(back, buf, io, lvl, Tail.BACK, -1); return res; } @@ -387,7 +392,7 @@ public abstract class BPlusTree<L, T extends L> { @Override protected int run0(Page page, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) throws IgniteCheckedException { - r.addTail(page, buf, io, lvl, Tail.FORWARD, Integer.MIN_VALUE); + r.addTail(page, buf, io, lvl, Tail.FORWARD, -1); return Remove.FOUND; } @@ -435,13 +440,6 @@ public abstract class BPlusTree<L, T extends L> { r.addTail(page, buf, io, lvl, Tail.EXACT, idx); - if (r.needMerge == TRUE) { - assert r.needReplaceInner == FALSE; - assert r.tail.down.type == Tail.EXACT; - - r.needMerge = READY; - } - return Remove.FOUND; } }; @@ -547,7 +545,7 @@ public abstract class BPlusTree<L, T extends L> { /** * @param meta Meta page. - * @param lvl Level, if {@code 0} then it is a bottom level, if {@link Integer#MIN_VALUE}, then root. + * @param lvl Level, if {@code 0} then it is a bottom level, if negative then root. * @return Page ID. */ private long getFirstPageId(Page meta, int lvl) { @@ -556,7 +554,7 @@ public abstract class BPlusTree<L, T extends L> { try { BPlusMetaIO io = BPlusMetaIO.VERSIONS.forPage(buf); - if (lvl == Integer.MIN_VALUE) + if (lvl < 0) lvl = io.getRootLevel(buf); if (lvl >= io.getLevelsCount(buf)) @@ -673,6 +671,7 @@ public abstract class BPlusTree<L, T extends L> { switch (res) { case Get.GO_DOWN: + case Get.GO_DOWN_X: assert g.pageId != pageId; assert g.fwdId != fwdId || fwdId == 0; @@ -717,7 +716,7 @@ public abstract class BPlusTree<L, T extends L> { long rootPageId; try (Page meta = page(metaPageId)) { - rootPageId = getFirstPageId(meta, Integer.MIN_VALUE); + rootPageId = getFirstPageId(meta, -1); } catch (IgniteCheckedException e) { throw new IllegalStateException(e); @@ -848,7 +847,7 @@ public abstract class BPlusTree<L, T extends L> { default: if (!r.isFinished()) - r.finishTail(true); + r.finishTail(); assert r.isFinished(); @@ -910,7 +909,7 @@ public abstract class BPlusTree<L, T extends L> { return res; } - if (!r.isFinished() && !r.finishTail(false)) + if (!r.isFinished() && !r.finishTail()) return r.lockTail(page, backId, fwdId, lvl); return res; @@ -939,7 +938,7 @@ public abstract class BPlusTree<L, T extends L> { r.finish(); } - else if (res == Remove.FOUND && r.needReplaceInner == FALSE && r.needMerge == FALSE) { + else if (res == Remove.FOUND && r.tail == null) { // Finish if we don't need to do any merges. r.finish(); } @@ -996,25 +995,6 @@ public abstract class BPlusTree<L, T extends L> { } /** - * @param cur Current tail element. - * @param fwdCnt Count in forward page. - * @return Count after merge or {@code -1} if merge is impossible. - */ - private int countAfterMerge(Tail cur, int fwdCnt) { - int cnt = cur.io.getCount(cur.buf); - - int newCnt = cnt + fwdCnt; - - if (cur.lvl != 0) - newCnt++; // We have to move down split key in inner pages. - - if (newCnt <= cur.io.getMaxCount(cur.buf)) - return newCnt; - - return -1; - } - - /** * @param row Row. * @return Old row. * @throws IgniteCheckedException If failed. @@ -1269,19 +1249,21 @@ public abstract class BPlusTree<L, T extends L> { switch (res) { case Put.GO_DOWN: + case Put.GO_DOWN_X: assert lvl > 0 : lvl; assert p.pageId != pageId; assert p.fwdId != fwdId || fwdId == 0; - if (p.foundInner == TRUE) { // Need to replace ref in inner page. - p.foundInner = FALSE; // Protect from retries. + // TODO race on go down? + if (p.needReplaceInner == TRUE) { // Need to replace ref in inner page. + p.needReplaceInner = FALSE; // Protect from retries. res = writePage(page, replace, p, lvl, Put.RETRY); if (res != Put.FOUND) return res; // Need to retry. - p.foundInner = DONE; // We can have only single matching inner key. + p.needReplaceInner = DONE; // We can have only single matching inner key. } // Go down recursively. @@ -1306,7 +1288,7 @@ public abstract class BPlusTree<L, T extends L> { case Put.NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; - assert p.foundInner == FALSE: p.foundInner; + assert p.needReplaceInner == FALSE: p.needReplaceInner; // Init args. p.pageId = pageId; @@ -1554,7 +1536,7 @@ public abstract class BPlusTree<L, T extends L> { short btmLvl; /** */ - byte foundInner = FALSE; + byte needReplaceInner = FALSE; /** * @param row Row. @@ -1569,8 +1551,8 @@ public abstract class BPlusTree<L, T extends L> { return true; // If we can get full row from the inner page, we must do inner replace to update full row info here. - if (io.canGetRow() && foundInner == FALSE) - foundInner = TRUE; + if (io.canGetRow() && needReplaceInner == FALSE) + needReplaceInner = TRUE; return false; } @@ -1631,9 +1613,6 @@ public abstract class BPlusTree<L, T extends L> { /** */ byte needReplaceInner = FALSE; - /** */ - byte needMerge = FALSE; - /** Removed row. */ T removed; @@ -1688,49 +1667,33 @@ public abstract class BPlusTree<L, T extends L> { /** * Process tail and finish. * - * @param ignoreMergeMore Ignore the attempt to merge more pages up. * @return {@code false} If failed to finish and we need to lock more pages up. * @throws IgniteCheckedException If failed. */ - private boolean finishTail(boolean ignoreMergeMore) throws IgniteCheckedException { + private boolean finishTail() throws IgniteCheckedException { assert !isFinished(); - assert needMerge != FALSE || needReplaceInner != FALSE; - assert tail != null; + assert tail.type == Tail.EXACT; - if (needReplaceInner == TRUE) - return false; // Need to find inner page. + // Need to lock more. + if (tail.down == null || needReplaceInner == TRUE || tail.io.getCount(tail.buf) == 0) + return false; - if (needReplaceInner == READY) { - assert needMerge == FALSE: needMerge; - - // We increment remove ID in write lock on leaf page, thus it is guaranteed that - // any successor will get greater value than he had read at the beginning of the operation. - // Thus he is guaranteed to do a retry from root. Since inner replace takes locks on the whole branch - // and releases the locks only when the inner key is updated and the successor saw the updated removeId, - // then after retry from root, he will see updated inner key. - globalRmvId.incrementAndGet(); + // Merge from the top to the bottom. + for (Tail<L> t = tail; t.down != null; t = t.down) + merge(t); + if (needReplaceInner == READY) { // Need to replace inner key with new max key for the left subtree. - doReplaceInner(); + replaceInner(); needReplaceInner = DONE; } - else if (needMerge == READY) { - assert needReplaceInner == FALSE: needReplaceInner; - assert tail.down != null; - - boolean needMergeMore = merge(tail.lvl - 1, true); - if (needMergeMore && !ignoreMergeMore) { - needMerge = TRUE; +// if (cnt == 0 && lvl != 0 && getRootLevel(meta) == lvl) TODO +// freePage(page, buf, io, lvl); // Free root. - return false; - } - - needMerge = DONE; - } - else - return false; +// if (needMergeMore) +// return false; releaseTail(); finish(); @@ -1798,7 +1761,7 @@ public abstract class BPlusTree<L, T extends L> { * @throws IgniteCheckedException If failed. */ private int lockTail(Page page, long backId, long fwdId, int lvl) throws IgniteCheckedException { - assert needMerge == TRUE ^ needReplaceInner == TRUE: "we can do only one thing at once"; + assert tail != null; // Init parameters for the handlers. this.pageId = page.id(); @@ -1839,53 +1802,49 @@ public abstract class BPlusTree<L, T extends L> { * @param buf Buffer. * @param cnt Count. * @param idx Index to remove. - * @param lvl Level. - * @param kickLeftChild If we are dropping left child instead of the right one. * @throws IgniteCheckedException If failed. */ - private void doRemove(BPlusIO io, Page page, ByteBuffer buf, int cnt, int idx, int lvl, boolean kickLeftChild) + private void doRemove(BPlusIO io, ByteBuffer buf, int cnt, int idx) throws IgniteCheckedException { - assert cnt > 0; - assert idx >= 0; - assert idx < cnt; // TODO check why is the code below exists - -// if (idx == cnt) { -// idx--; // This may happen in case of right turn, we need to remove the rightmost ref and link. -// -// assert !kickLeftChild: "right child must be dropped here"; -// } + assert cnt > 0: cnt; + assert idx >= 0 && idx < cnt: idx + " " + cnt; cnt--; - io.copyItems(buf, buf, idx + 1, idx, cnt - idx, kickLeftChild); + io.copyItems(buf, buf, idx + 1, idx, cnt - idx, false); io.setCount(buf, cnt); - - if (cnt == 0 && lvl != 0 && getRootLevel(meta) == lvl) - freePage(page, buf, io, lvl); // Free root. } /** * @param prnt Parent tail. - * @param cur Current tail. - * @param fwd Forward tail. + * @param left Left child tail. + * @param right Right child tail. + * @return {@code true} If merged successfully. * @throws IgniteCheckedException If failed. */ - private boolean mergePages(Tail<L> prnt, Tail<L> cur, Tail<L> fwd) throws IgniteCheckedException { - assert fwd.io == cur.io; // Otherwise incompatible. + private boolean mergePages(Tail<L> prnt, Tail<L> left, Tail<L> right) throws IgniteCheckedException { + assert right.io == left.io; // Otherwise incompatible. + assert left.io.getForward(left.buf) == right.page.id(); - int cnt = cur.io.getCount(cur.buf); - int fwdCnt = fwd.io.getCount(fwd.buf); - int newCnt = countAfterMerge(cur, fwdCnt); + int prntCnt = prnt.io.getCount(prnt.buf); + int backCnt = left.io.getCount(left.buf); + int curCnt = right.io.getCount(right.buf); - if (newCnt == -1) // Not enough space. - return false; + assert prntCnt > 0: prntCnt; - cur.io.setCount(cur.buf, newCnt); + int newCnt = backCnt + curCnt; - int prntCnt = prnt.io.getCount(prnt.buf); + // Need to move down split key in inner pages, but for the last key it will be a special case merge. + if (left.lvl != 0 && false) // TODO + newCnt++; + + if (newCnt > left.io.getMaxCount(left.buf)) + return false; + + left.io.setCount(left.buf, newCnt); // Move down split key in inner pages. - if (cur.lvl != 0) { + if (left.lvl != 0) { int prntIdx = prnt.idx; if (prntIdx == prntCnt) // It was a right turn. @@ -1893,21 +1852,22 @@ public abstract class BPlusTree<L, T extends L> { // We can be sure that we have enough free space to store split key here, // because we've done remove already and did not release child locks. - inner(cur.io).store(cur.buf, cnt, prnt.io, prnt.buf, prntIdx); + left.io.store(left.buf, backCnt, prnt.io, prnt.buf, prntIdx); - cnt++; + backCnt++; } - cur.io.copyItems(fwd.buf, cur.buf, 0, cnt, fwdCnt, true); - cur.io.setForward(cur.buf, fwd.io.getForward(fwd.buf)); + left.io.copyItems(right.buf, left.buf, 0, backCnt, curCnt, true); + left.io.setForward(left.buf, right.io.getForward(right.buf)); - assert prntCnt > 0: prntCnt; + // Fix index for the right move: remove last item. + int prntIdx = prnt.idx == prntCnt ? prntCnt - 1 : prnt.idx; - // Remove split key from parent. If parent is root and becomes empty, it will be freed by doRemove. - doRemove(prnt.io, prnt.page, prnt.buf, prntCnt, prnt.idx, prnt.lvl, false); + // Remove split key from parent. + doRemove(prnt.io, prnt.buf, prntCnt, prntIdx); // Forward page is now empty and has no links. - freePage(fwd.page, fwd.buf, fwd.io, fwd.lvl); + freePage(right.page, right.buf, right.io, right.lvl); return true; } @@ -1939,6 +1899,8 @@ public abstract class BPlusTree<L, T extends L> { emptyPages = new ArrayList<>(4); emptyPages.add(page.fullId()); + + writeUnlockAndClose(page); } /** @@ -1952,38 +1914,9 @@ public abstract class BPlusTree<L, T extends L> { } /** - * @param inner Inner replace page. * @throws IgniteCheckedException If failed. */ - private void dropEmptyBranch(Tail inner) throws IgniteCheckedException { - int cnt = inner.io.getCount(inner.buf); - - assert cnt > 0: cnt; - - // We need to check if the branch we are going to drop goes to the left or to the right. - boolean kickLeft = inner.down.page.id() == inner(inner.io).getLeft(inner.buf, inner.idx); - - assert kickLeft || inner.down.page.id() == inner(inner.io).getRight(inner.buf, inner.idx); - - // Remove found inner key from inner page. - doRemove(inner.io, inner.page, inner.buf, cnt, inner.idx, inner.lvl, kickLeft); - - // If inner page was root and became empty, it was handled in doRemove. - // Otherwise we can be sure that inner page was not freed, at lead it must become - // an empty routing page. Thus always starting from inner.down here. - for (Tail t = inner.down; t != null; t = t.down) { - // TODO merge branch but not just free it - - assert t.io.getCount(t.buf) == 0: row; - - freePage(t.page, t.buf, t.io, t.lvl); - } - } - - /** - * @throws IgniteCheckedException If failed. - */ - private void doReplaceInner() throws IgniteCheckedException { + private void replaceInner() throws IgniteCheckedException { assert needReplaceInner == READY: needReplaceInner; assert tail.lvl > 0; assert innerIdx >= 0; @@ -1996,89 +1929,59 @@ public abstract class BPlusTree<L, T extends L> { int cnt = leaf.io.getCount(leaf.buf); - if (cnt == 0) { // Merge empty leaf page. - if (!merge(0, false)) { - // For leaf pages this can happen only when parent is empty -> drop the whole branch. - dropEmptyBranch(inner); - - return; - } - - // Need to handle possible tail restructuring after merge. - leaf = getTail(0); - - cnt = leaf.io.getCount(leaf.buf); + assert cnt > 0: cnt; // Leaf must be merged at this point already if it was empty. - // If any leaf becomes empty we have to either merge it or drop the whole empty branch. - assert cnt > 0: "leaf can't be empty after successful merge"; - } - - // If after leaf merge parent have lost inner key, we don't need to update it anymore. if (innerIdx < inner.io.getCount(inner.buf)) { - inner(inner.io).store(inner.buf, innerIdx, leaf.io, leaf.buf, cnt - 1); + // Update inner key with the new biggest key of left subtree. + inner.io.store(inner.buf, innerIdx, leaf.io, leaf.buf, cnt - 1); leaf.io.setRemoveId(leaf.buf, globalRmvId.get()); } else { + // If after leaf merge parent have lost inner key, we don't need to update it anymore. assert innerIdx == inner.io.getCount(inner.buf); assert inner(inner.io).getLeft(inner.buf, innerIdx) == leaf.page.id(); } - - // We can't merge the whole branch up here because of locking rules. - // Here we've already locked the whole branch from the bottom to the top. } /** - * @param lvl Level. - * @return {@code true} If merged, {@code false} if not (because of insufficient space). + * @param prnt Parent for merge. + * @return {@code true} If merged, {@code false} if not (because of insufficient space or empty parent). * @throws IgniteCheckedException If failed. */ - private boolean merge(int lvl, boolean releaseMerged) throws IgniteCheckedException { - assert tail.lvl > lvl; - - Tail<L> prnt = getTail(lvl + 1); - + private boolean merge(Tail<L> prnt) throws IgniteCheckedException { if (prnt.io.getCount(prnt.buf) == 0) return false; // Parent is an empty routing page, child forward page will have another parent. - Tail<L> cur = getTail(lvl); - Tail<L> back = cur.sibling; + Tail<L> right = prnt.down; + Tail<L> left = right.sibling; - assert prnt.down == cur : prnt.down; - assert back != null: "we must have a partner to merge with"; + assert right.type == Tail.EXACT; + assert left != null: "we must have a partner to merge with"; - if (back.type != Tail.BACK) { // Flip if it was actually FORWARD but not BACK. - assert back.type == Tail.FORWARD: back.type; + if (left.type != Tail.BACK) { // Flip if it was actually FORWARD but not BACK. + assert left.type == Tail.FORWARD: left.type; - back = cur; // Current goes back. - cur = cur.sibling; // Forward becomes current. + left = right; + right = right.sibling; } - assert cur.io == back.io: "must always be the same"; // Otherwise can be not compatible. + assert right.io == left.io: "must always be the same"; // Otherwise can be not compatible. - if (!mergePages(prnt, back, cur)) + if (!mergePages(prnt, left, right)) return false; - // BACK becomes EXACT. - if (back.type == Tail.BACK) { - assert back.sibling == null; - - back.down = cur.down; - back.type = Tail.EXACT; - prnt.down = back; - } - else { // back is already EXACT - assert back.type == Tail.EXACT: back.type; + // left from BACK becomes EXACT. + if (left.type == Tail.BACK) { + assert left.sibling == null; - back.sibling = null; + left.down = right.down; + left.type = Tail.EXACT; + prnt.down = left; } + else { // left is already EXACT. + assert left.type == Tail.EXACT: left.type; - // Always unlock and release current because we made it invisible for further code. - writeUnlockAndClose(cur.page); - - if (releaseMerged) { - prnt.down = null; - - writeUnlockAndClose(back.page); + left.sibling = null; } return true; @@ -2248,7 +2151,7 @@ public abstract class BPlusTree<L, T extends L> { */ private Tail(Page page, ByteBuffer buf, BPlusIO<L> io, byte type, int lvl, int idx) { assert type == BACK || type == EXACT || type == FORWARD: type; - assert idx == Integer.MIN_VALUE || (idx >= 0 && idx <= Short.MAX_VALUE): idx ; + assert idx == -1 || (idx >= 0 && idx <= Short.MAX_VALUE): idx ; assert lvl >= 0 && lvl <= Byte.MAX_VALUE: lvl; assert page != null; http://git-wip-us.apache.org/repos/asf/ignite/blob/74dfb8f9/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java index e3919f1..6dcb237 100644 --- a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java +++ b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java @@ -61,6 +61,15 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { private static final int CACHE_ID = 100500; /** */ + private static int MAX_COUNT = 0; + + /** */ + private static int PUT_INC = 1; + + /** */ + private static int RMV_INC = 1; + + /** */ private PageMemory pageMem; /** */ @@ -87,8 +96,62 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { } /** {@inheritDoc} */ - @Override protected void afterTestsStopped() throws Exception { + @Override protected void afterTest() throws Exception { pageMem.stop(); + + MAX_COUNT = 0; + PUT_INC = 1; + RMV_INC = -1; + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testSingle1() throws IgniteCheckedException { + MAX_COUNT = 1; + PUT_INC = -1; + RMV_INC = -1; + + doTestPutRemoveForwardBackward(true); + } + + /** + * @param canGetRow Can get row from inner page. + * @throws IgniteCheckedException If failed. + */ + private void doTestPutRemoveForwardBackward(boolean canGetRow) throws IgniteCheckedException { + TestTree tree = createTestTree(canGetRow); + + long cnt = 10; + + for (long x = PUT_INC > 0 ? 0 : cnt - 1; x >= 0 && x < cnt; x += PUT_INC) { + assertNull(tree.findOne(x)); + + tree.put(x); + + assertEquals(x, tree.findOne(x).longValue()); + } + + X.println(tree.printTree()); + + assertNull(tree.findOne(-1L)); + + for (long x = 0; x < cnt; x++) + assertEquals(x, tree.findOne(x).longValue()); + + assertNull(tree.findOne(cnt)); + + for (long x = RMV_INC > 0 ? 0 : cnt - 1; x >= 0 && x < cnt; x += RMV_INC) { + X.println(" -- " + x); + + assertEquals(x, tree.remove(x).longValue()); + + assertNull(tree.findOne(x)); + + X.println(tree.printTree()); + } + + assertFalse(tree.find(null, null).next()); } /** @@ -438,6 +501,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { } /** + * TODO refactor to use integer in inner page * Long inner. */ private static final class LongInnerIO extends BPlusInnerIO<Long> { @@ -454,6 +518,14 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { } /** {@inheritDoc} */ + @Override public int getMaxCount(ByteBuffer buf) { + if (MAX_COUNT != 0) + return MAX_COUNT; + + return super.getMaxCount(buf); + } + + /** {@inheritDoc} */ @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<Long> srcIo, ByteBuffer src, int srcIdx) throws IgniteCheckedException { store(dst, dstIdx, srcIo.getLookupRow(null, src, srcIdx)); @@ -485,11 +557,26 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { } /** {@inheritDoc} */ + @Override public int getMaxCount(ByteBuffer buf) { + if (MAX_COUNT != 0) + return MAX_COUNT; + + return super.getMaxCount(buf); + } + + /** {@inheritDoc} */ @Override public void store(ByteBuffer buf, int idx, Long row) { buf.putLong(offset(idx), row); } /** {@inheritDoc} */ + @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<Long> srcIo, ByteBuffer src, int srcIdx) { + assert srcIo == this; + + dst.putLong(offset(dstIdx), src.getLong(offset(srcIdx))); + } + + /** {@inheritDoc} */ @Override public Long getLookupRow(BPlusTree<Long,?> tree, ByteBuffer buf, int idx) throws IgniteCheckedException { return buf.getLong(offset(idx));
