Return-Path: X-Original-To: archive-asf-public-internal@cust-asf2.ponee.io Delivered-To: archive-asf-public-internal@cust-asf2.ponee.io Received: from cust-asf.ponee.io (cust-asf.ponee.io [163.172.22.183]) by cust-asf2.ponee.io (Postfix) with ESMTP id 184BA200C91 for ; Sun, 11 Jun 2017 22:03:36 +0200 (CEST) Received: by cust-asf.ponee.io (Postfix) id 16F07160BD8; Sun, 11 Jun 2017 20:03:36 +0000 (UTC) Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by cust-asf.ponee.io (Postfix) with SMTP id C3587160C01 for ; Sun, 11 Jun 2017 22:03:31 +0200 (CEST) Received: (qmail 61136 invoked by uid 500); 11 Jun 2017 20:03:30 -0000 Mailing-List: contact commits-help@ignite.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@ignite.apache.org Delivered-To: mailing list commits@ignite.apache.org Received: (qmail 60673 invoked by uid 99); 11 Jun 2017 20:03:30 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 11 Jun 2017 20:03:30 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id DE39CF4A59; Sun, 11 Jun 2017 20:03:28 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: agoncharuk@apache.org To: commits@ignite.apache.org Date: Sun, 11 Jun 2017 20:04:09 -0000 Message-Id: In-Reply-To: References: X-Mailer: ASF-Git Admin Mailer Subject: [43/47] ignite git commit: IGNITE-5267 - Moved ignite-ps module to ignite-core archived-at: Sun, 11 Jun 2017 20:03:36 -0000 http://git-wip-us.apache.org/repos/asf/ignite/blob/6bf5ce46/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 deleted file mode 100644 index 98204eb..0000000 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java +++ /dev/null @@ -1,4808 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.ignite.internal.processors.cache.database.tree; - -import java.io.Externalizable; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collections; -import java.util.Comparator; -import java.util.List; -import java.util.concurrent.atomic.AtomicBoolean; -import java.util.concurrent.atomic.AtomicLong; -import org.apache.ignite.IgniteCheckedException; -import org.apache.ignite.IgniteException; -import org.apache.ignite.internal.IgniteInterruptedCheckedException; -import org.apache.ignite.internal.pagemem.PageIdUtils; -import org.apache.ignite.internal.pagemem.PageMemory; -import org.apache.ignite.internal.pagemem.wal.IgniteWriteAheadLogManager; -import org.apache.ignite.internal.pagemem.wal.record.delta.FixCountRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.FixLeftmostChildRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.FixRemoveId; -import org.apache.ignite.internal.pagemem.wal.record.delta.InsertRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.MetaPageAddRootRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.MetaPageCutRootRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.MetaPageInitRootInlineRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.NewRootInitRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.RemoveRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.ReplaceRecord; -import org.apache.ignite.internal.pagemem.wal.record.delta.SplitExistingPageRecord; -import org.apache.ignite.internal.processors.cache.database.DataStructure; -import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO; -import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusInnerIO; -import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO; -import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusMetaIO; -import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions; -import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO; -import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseBag; -import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseList; -import org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler; -import org.apache.ignite.internal.util.GridArrays; -import org.apache.ignite.internal.util.GridLongList; -import org.apache.ignite.internal.util.IgniteTree; -import org.apache.ignite.internal.util.lang.GridCursor; -import org.apache.ignite.internal.util.lang.GridTreePrinter; -import org.apache.ignite.internal.util.typedef.F; -import org.apache.ignite.internal.util.typedef.internal.S; -import org.apache.ignite.internal.util.typedef.internal.SB; -import org.apache.ignite.internal.util.typedef.internal.U; -import org.apache.ignite.lang.IgniteInClosure; - -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Bool.DONE; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Bool.FALSE; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Bool.READY; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Bool.TRUE; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Result.FOUND; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Result.GO_DOWN; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Result.GO_DOWN_X; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Result.NOT_FOUND; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Result.RETRY; -import static org.apache.ignite.internal.processors.cache.database.tree.BPlusTree.Result.RETRY_ROOT; - -/** - * Abstract B+Tree. - */ -@SuppressWarnings({"RedundantThrowsDeclaration", "ConstantValueVariableUse"}) -public abstract class BPlusTree extends DataStructure implements IgniteTree { - /** */ - private static final Object[] EMPTY = {}; - - /** */ - private static volatile boolean interrupted; - - /** */ - private final AtomicBoolean destroyed = new AtomicBoolean(false); - - /** */ - private final String name; - - /** */ - private final float minFill; - - /** */ - private final float maxFill; - - /** */ - protected final long metaPageId; - - /** */ - private boolean canGetRowFromInner; - - /** */ - private IOVersions> innerIos; - - /** */ - private IOVersions> leafIos; - - /** */ - private final AtomicLong globalRmvId; - - /** */ - private volatile TreeMetaData treeMeta; - - /** */ - private final GridTreePrinter treePrinter = new GridTreePrinter() { - /** */ - private boolean keys = true; - - @Override protected List getChildren(final Long pageId) { - if (pageId == null || pageId == 0L) - return null; - - try { - long page = acquirePage(pageId); - - try { - long pageAddr = readLock(pageId, page); // No correctness guaranties. - - try { - BPlusIO io = io(pageAddr); - - if (io.isLeaf()) - return null; - - int cnt = io.getCount(pageAddr); - - assert cnt >= 0 : cnt; - - List res; - - if (cnt > 0) { - res = new ArrayList<>(cnt + 1); - - for (int i = 0; i < cnt; i++) - res.add(inner(io).getLeft(pageAddr, i)); - - res.add(inner(io).getRight(pageAddr, cnt - 1)); - } - else { - long left = inner(io).getLeft(pageAddr, 0); - - res = left == 0 ? Collections.emptyList() : Collections.singletonList(left); - } - - return res; - } - finally { - readUnlock(pageId, page, pageAddr); - } - } - finally { - releasePage(pageId, page); - } - } - catch (IgniteCheckedException ignored) { - throw new AssertionError("Can not acquire page."); - } - } - - @Override protected String formatTreeNode(final Long pageId) { - if (pageId == null) - return ">NPE<"; - - if (pageId == 0L) - return ""; - - try { - long page = acquirePage(pageId); - try { - long pageAddr = readLock(pageId, page); // No correctness guaranties. - try { - BPlusIO io = io(pageAddr); - - return printPage(io, pageAddr, keys); - } - finally { - readUnlock(pageId, page, pageAddr); - } - } - finally { - releasePage(pageId, page); - } - } - catch (IgniteCheckedException e) { - throw new IllegalStateException(e); - } - } - }; - - /** */ - private final GetPageHandler askNeighbor = new AskNeighbor(); - - /** - * - */ - private class AskNeighbor extends GetPageHandler { - /** {@inheritDoc} */ - @Override public Result run0(long pageId, long page, long pageAddr, BPlusIO io, Get g, int isBack) { - assert !io.isLeaf(); // Inner page. - - boolean back = isBack == TRUE.ordinal(); - - long res = doAskNeighbor(io, pageAddr, back); - - if (back) { - if (io.getForward(pageAddr) != g.backId) // See how g.backId is setup in removeDown for this check. - return RETRY; - - g.backId(res); - } - else { - assert isBack == FALSE.ordinal() : isBack; - - g.fwdId(res); - } - - return FOUND; - } - } - - /** */ - private final GetPageHandler search = new Search(); - - /** - * - */ - private class Search extends GetPageHandler { - /** {@inheritDoc} */ - @Override public Result run0(long pageId, long page, long pageAddr, BPlusIO io, Get g, int lvl) - throws IgniteCheckedException { - // Check the triangle invariant. - if (io.getForward(pageAddr) != g.fwdId) - return RETRY; - - boolean needBackIfRouting = g.backId != 0; - - g.backId(0L); // Usually we'll go left down and don't need it. - - 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 - else - idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, g.row, g.shift); - - boolean found = idx >= 0; - - if (found) { // Found exact match. - assert g.getClass() != GetCursor.class; - - if (g.found(io, pageAddr, idx, lvl)) - return FOUND; - - // Else we need to reach leaf page, go left down. - } - else { - idx = fix(idx); - - if (g.notFound(io, pageAddr, idx, lvl)) // No way down, stop here. - return NOT_FOUND; - } - - assert !io.isLeaf() : io; - - // If idx == cnt then we go right down, else left down: getLeft(cnt) == getRight(cnt - 1). - g.pageId(inner(io).getLeft(pageAddr, idx)); - - // If we see the tree in consistent state, then our right down page must be forward for our left down page, - // we need to setup fwdId and/or backId to be able to check this invariant on lower level. - if (idx < cnt) { - // Go left down here. - g.fwdId(inner(io).getRight(pageAddr, idx)); - } - else { - // Go right down here or it is an empty branch. - assert idx == cnt; - - // Here child's forward is unknown to us (we either go right or it is an empty "routing" page), - // need to ask our forward about the child's forward (it must be leftmost child of our forward page). - // This is ok from the locking standpoint because we take all locks in the forward direction. - long fwdId = io.getForward(pageAddr); - - // Setup fwdId. - if (fwdId == 0) - g.fwdId(0L); - else { - // We can do askNeighbor on forward page here because we always take locks in forward direction. - Result res = askNeighbor(fwdId, g, false); - - if (res != FOUND) - return res; // Retry. - } - - // Setup backId. - 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(pageAddr, cnt - 1)); - else if (needBackIfRouting) { - // Can't get backId here because of possible deadlock and it is only needed for remove operation. - return GO_DOWN_X; - } - } - - return GO_DOWN; - } - } - - /** */ - private final GetPageHandler replace = new Replace(); - - /** - * - */ - private class Replace extends GetPageHandler { - /** {@inheritDoc} */ - @SuppressWarnings("unchecked") - @Override public Result run0(long pageId, long page, long pageAddr, BPlusIO io, Put p, int lvl) - throws IgniteCheckedException { - // Check the triangle invariant. - if (io.getForward(pageAddr) != p.fwdId) - return RETRY; - - assert p.btmLvl == 0 : "split is impossible with replace"; - - final int cnt = io.getCount(pageAddr); - final int idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, p.row, 0); - - if (idx < 0) // Not found, split or merge happened. - return RETRY; - - // Replace link at idx with new one. - // Need to read link here because `p.finish()` will clear row. - L newRow = p.row; - - // Detach the old row if we are on a leaf page. - if (lvl == 0) { - assert p.oldRow == null; // The old row must be set only once. - - // Inner replace state must be consistent by the end of the operation. - assert p.needReplaceInner == FALSE || p.needReplaceInner == DONE : p.needReplaceInner; - - // Need to replace inner key if now we are replacing the rightmost row and have a forward page. - if (canGetRowFromInner && idx + 1 == cnt && p.fwdId != 0L && p.needReplaceInner == FALSE) { - // Can happen only for invoke, otherwise inner key must be replaced on the way down. - assert p.invoke != null; - - // We need to restart the operation from root to perform inner replace. - // On the second pass we will not get here (will avoid infinite loop) because - // needReplaceInner will be DONE or our key will not be the rightmost anymore. - return RETRY_ROOT; - } - - // Get old row in leaf page to reduce contention at upper level. - p.oldRow = p.needOld ? getRow(io, pageAddr, idx) : (T)Boolean.TRUE; - - p.finish(); - } - - boolean needWal = needWalDeltaRecord(pageId, page, null); - - byte[] newRowBytes = io.store(pageAddr, idx, newRow, null, needWal); - - if (needWal) - wal.log(new ReplaceRecord<>(cacheId, pageId, io, newRowBytes, idx)); - - return FOUND; - } - } - - /** */ - private final GetPageHandler insert = new Insert(); - - /** - * - */ - private class Insert extends GetPageHandler { - /** {@inheritDoc} */ - @Override public Result run0(long pageId, long page, long pageAddr, BPlusIO io, Put p, int lvl) - throws IgniteCheckedException { - assert p.btmLvl == lvl : "we must always insert at the bottom level: " + p.btmLvl + " " + lvl; - - // Check triangle invariant. - if (io.getForward(pageAddr) != p.fwdId) - return RETRY; - - int cnt = io.getCount(pageAddr); - 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."); - - idx = fix(idx); - - // Do insert. - L moveUpRow = p.insert(pageId, page, pageAddr, io, idx, lvl); - - // Check if split happened. - if (moveUpRow != null) { - p.btmLvl++; // Get high. - p.row = moveUpRow; - - if (p.invoke != null) - p.invoke.row = moveUpRow; - - // Here forward page can't be concurrently removed because we keep write lock on tail which is the only - // page who knows about the forward page, because it was just produced by split. - p.rightId = io.getForward(pageAddr); - p.tail(pageId, page, pageAddr); - - assert p.rightId != 0; - } - else - p.finish(); - - return FOUND; - } - } - - /** */ - private final GetPageHandler rmvFromLeaf = new RemoveFromLeaf(); - - /** - * - */ - private class RemoveFromLeaf extends GetPageHandler { - /** {@inheritDoc} */ - @Override public Result run0(long leafId, long leafPage, long leafAddr, BPlusIO io, Remove r, int lvl) - throws IgniteCheckedException { - assert lvl == 0 : lvl; // Leaf. - - // Check the triangle invariant. - if (io.getForward(leafAddr) != r.fwdId) - return RETRY; - - final int cnt = io.getCount(leafAddr); - - assert cnt <= Short.MAX_VALUE: cnt; - - 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. - - assert idx >= 0 && idx < cnt: idx; - - // Need to do inner replace when we remove the rightmost element and the leaf have no forward page, - // i.e. it is not the rightmost leaf of the tree. - boolean needReplaceInner = canGetRowFromInner && idx == cnt - 1 && io.getForward(leafAddr) != 0; - - // !!! Before modifying state we have to make sure that we will not go for retry. - - // We may need to replace inner key or want to merge this leaf with sibling after the remove -> keep lock. - if (needReplaceInner || - // We need to make sure that we have back or forward to be able to merge. - ((r.fwdId != 0 || r.backId != 0) && mayMerge(cnt - 1, io.getMaxCount(leafAddr, pageSize())))) { - // If we have backId then we've already locked back page, nothing to do here. - if (r.fwdId != 0 && r.backId == 0) { - Result res = r.lockForward(0); - - if (res != FOUND) { - assert r.tail == null; - - return res; // Retry. - } - - assert r.tail != null; // We've just locked forward page. - } - - // Retry must reset these fields when we release the whole branch without remove. - assert r.needReplaceInner == FALSE: "needReplaceInner"; - assert r.needMergeEmptyBranch == FALSE: "needMergeEmptyBranch"; - - if (cnt == 1) // It was the last element on the leaf. - r.needMergeEmptyBranch = TRUE; - - if (needReplaceInner) - r.needReplaceInner = TRUE; - - Tail t = r.addTail(leafId, leafPage, leafAddr, io, 0, Tail.EXACT); - - t.idx = (short)idx; - - // We will do the actual remove only when we made sure that - // we've locked the whole needed branch correctly. - return FOUND; - } - - r.removeDataRowFromLeaf(leafId, leafPage, leafAddr, null, io, cnt, idx); - - return FOUND; - } - } - - /** */ - private final GetPageHandler lockBackAndRmvFromLeaf = new LockBackAndRmvFromLeaf(); - - /** - * - */ - private class LockBackAndRmvFromLeaf extends GetPageHandler { - /** {@inheritDoc} */ - @Override protected Result run0(long backId, long backPage, long backAddr, BPlusIO io, Remove r, int lvl) - throws IgniteCheckedException { - // Check that we have consistent view of the world. - if (io.getForward(backAddr) != r.pageId) - return RETRY; - - // Correct locking order: from back to forward. - Result res = r.doRemoveFromLeaf(); - - // Keep locks on back and leaf pages for subsequent merges. - if (res == FOUND && r.tail != null) - r.addTail(backId, backPage, backAddr, io, lvl, Tail.BACK); - - return res; - } - } - - /** */ - private final GetPageHandler lockBackAndTail = new LockBackAndTail(); - - /** - * - */ - private class LockBackAndTail extends GetPageHandler { - /** {@inheritDoc} */ - @Override public Result run0(long backId, long backPage, long backAddr, BPlusIO io, Remove r, int lvl) - throws IgniteCheckedException { - // Check that we have consistent view of the world. - if (io.getForward(backAddr) != r.pageId) - return RETRY; - - // Correct locking order: from back to forward. - Result res = r.doLockTail(lvl); - - if (res == FOUND) - r.addTail(backId, backPage, backAddr, io, lvl, Tail.BACK); - - return res; - } - } - - /** */ - private final GetPageHandler lockTailForward = new LockTailForward(); - - /** - * - */ - private class LockTailForward extends GetPageHandler { - /** {@inheritDoc} */ - @Override protected Result run0(long pageId, long page, long pageAddr, BPlusIO io, Remove r, int lvl) - throws IgniteCheckedException { - r.addTail(pageId, page, pageAddr, io, lvl, Tail.FORWARD); - - return FOUND; - } - } - - /** */ - private final GetPageHandler lockTail = new LockTail(); - - /** - * - */ - private class LockTail extends GetPageHandler { - /** {@inheritDoc} */ - @Override public Result run0(long pageId, long page, long pageAddr, BPlusIO io, Remove r, int lvl) - throws IgniteCheckedException { - assert lvl > 0 : lvl; // We are not at the bottom. - - // Check that we have a correct view of the world. - if (io.getForward(pageAddr) != r.fwdId) - return RETRY; - - // We don't have a back page, need to lock our forward and become a back for it. - if (r.fwdId != 0 && r.backId == 0) { - Result res = r.lockForward(lvl); - - if (res != FOUND) - return res; // Retry. - } - - r.addTail(pageId, page, pageAddr, io, lvl, Tail.EXACT); - - return FOUND; - } - } - - /** */ - private final PageHandler cutRoot = new CutRoot(); - - /** - * - */ - private class CutRoot extends PageHandler { - /** {@inheritDoc} */ - @Override public Bool run(int cacheId, long metaId, long metaPage, long metaAddr, PageIO iox, Boolean walPlc, Void ignore, int lvl) - throws IgniteCheckedException { - // Safe cast because we should never recycle meta page until the tree is destroyed. - BPlusMetaIO io = (BPlusMetaIO)iox; - - assert lvl == io.getRootLevel(metaAddr); // Can drop only root. - - io.cutRoot(metaAddr, pageSize()); - - if (needWalDeltaRecord(metaId, metaPage, walPlc)) - wal.log(new MetaPageCutRootRecord(cacheId, metaId)); - - int newLvl = lvl - 1; - - assert io.getRootLevel(metaAddr) == newLvl; - - treeMeta = new TreeMetaData(newLvl, io.getFirstPageId(metaAddr, newLvl)); - - return TRUE; - } - } - - /** */ - private final PageHandler addRoot = new AddRoot(); - - /** - * - */ - private class AddRoot extends PageHandler { - /** {@inheritDoc} */ - @Override public Bool run(int cacheId, long metaId, long metaPage, long pageAddr, PageIO iox, Boolean walPlc, Long rootPageId, int lvl) - throws IgniteCheckedException { - assert rootPageId != null; - - // Safe cast because we should never recycle meta page until the tree is destroyed. - BPlusMetaIO io = (BPlusMetaIO)iox; - - assert lvl == io.getLevelsCount(pageAddr); - - io.addRoot(pageAddr, rootPageId, pageSize()); - - if (needWalDeltaRecord(metaId, metaPage, walPlc)) - wal.log(new MetaPageAddRootRecord(cacheId, metaId, rootPageId)); - - assert io.getRootLevel(pageAddr) == lvl; - assert io.getFirstPageId(pageAddr, lvl) == rootPageId; - - treeMeta = new TreeMetaData(lvl, rootPageId); - - return TRUE; - } - } - - /** */ - private final PageHandler initRoot = new InitRoot(); - - /** - * - */ - private class InitRoot extends PageHandler { - /** {@inheritDoc} */ - @Override public Bool run(int cacheId, long metaId, long metaPage, long pageAddr, PageIO iox, Boolean walPlc, Long rootId, int inlineSize) - throws IgniteCheckedException { - assert rootId != null; - - // Safe cast because we should never recycle meta page until the tree is destroyed. - BPlusMetaIO io = (BPlusMetaIO)iox; - - io.initRoot(pageAddr, rootId, pageSize()); - io.setInlineSize(pageAddr, inlineSize); - - if (needWalDeltaRecord(metaId, metaPage, walPlc)) - wal.log(new MetaPageInitRootInlineRecord(cacheId, metaId, rootId, inlineSize)); - - assert io.getRootLevel(pageAddr) == 0; - assert io.getFirstPageId(pageAddr, 0) == rootId; - - treeMeta = new TreeMetaData(0, rootId); - - return TRUE; - } - } - - /** - * @param name Tree name. - * @param cacheId Cache ID. - * @param pageMem Page memory. - * @param wal Write ahead log manager. - * @param globalRmvId Remove ID. - * @param metaPageId Meta page ID. - * @param reuseList Reuse list. - * @param innerIos Inner IO versions. - * @param leafIos Leaf IO versions. - * @throws IgniteCheckedException If failed. - */ - protected BPlusTree( - String name, - int cacheId, - PageMemory pageMem, - IgniteWriteAheadLogManager wal, - AtomicLong globalRmvId, - long metaPageId, - ReuseList reuseList, - IOVersions> innerIos, - IOVersions> leafIos - ) throws IgniteCheckedException { - this(name, cacheId, pageMem, wal, globalRmvId, metaPageId, reuseList); - setIos(innerIos, leafIos); - } - - /** - * @param name Tree name. - * @param cacheId Cache ID. - * @param pageMem Page memory. - * @param wal Write ahead log manager. - * @param globalRmvId Remove ID. - * @param metaPageId Meta page ID. - * @param reuseList Reuse list. - * @throws IgniteCheckedException If failed. - */ - protected BPlusTree( - String name, - int cacheId, - PageMemory pageMem, - IgniteWriteAheadLogManager wal, - AtomicLong globalRmvId, - long metaPageId, - ReuseList reuseList - ) throws IgniteCheckedException { - super(cacheId, pageMem, wal); - - assert !F.isEmpty(name); - - // TODO make configurable: 0 <= minFill <= maxFill <= 1 - minFill = 0f; // Testing worst case when merge happens only on empty page. - maxFill = 0f; // Avoiding random effects on testing. - - assert metaPageId != 0L; - - this.metaPageId = metaPageId; - this.name = name; - this.reuseList = reuseList; - this.globalRmvId = globalRmvId; - } - - /** - * @param innerIos Inner IO versions. - * @param leafIos Leaf IO versions. - */ - protected void setIos(IOVersions> innerIos, - IOVersions> leafIos) { - assert innerIos != null; - assert leafIos != null; - - this.canGetRowFromInner = innerIos.latest().canGetRow(); // TODO refactor - this.innerIos = innerIos; - this.leafIos = leafIos; - } - - /** - * @return Tree name. - */ - public final String getName() { - return name; - } - - /** - * Initialize new tree. - * - * @param initNew {@code True} if new tree should be created. - * @throws IgniteCheckedException If failed. - */ - protected final void initTree(boolean initNew) throws IgniteCheckedException { - initTree(initNew, 0); - } - - /** - * Initialize new tree. - * - * @param initNew {@code True} if new tree should be created. - * @param inlineSize Inline size. - * @throws IgniteCheckedException If failed. - */ - protected final void initTree(boolean initNew, int inlineSize) throws IgniteCheckedException { - if (initNew) { - // Allocate the first leaf page, it will be our root. - long rootId = allocatePage(null); - - init(rootId, latestLeafIO()); - - // Initialize meta page with new root page. - Bool res = write(metaPageId, initRoot, BPlusMetaIO.VERSIONS.latest(), rootId, inlineSize, FALSE); - - assert res == TRUE: res; - - assert treeMeta != null; - } - } - - /** - * @return Tree meta data. - * @throws IgniteCheckedException If failed. - */ - private TreeMetaData treeMeta() throws IgniteCheckedException { - TreeMetaData meta0 = treeMeta; - - if (meta0 != null) - return meta0; - - final long metaPage = acquirePage(metaPageId); - try { - long pageAddr = readLock(metaPageId, metaPage); // Meta can't be removed. - - assert pageAddr != 0 : "Failed to read lock meta page [metaPageId=" + - U.hexLong(metaPageId) + ']'; - - try { - BPlusMetaIO io = BPlusMetaIO.VERSIONS.forPage(pageAddr); - - int rootLvl = io.getRootLevel(pageAddr); - long rootId = io.getFirstPageId(pageAddr, rootLvl); - - treeMeta = meta0 = new TreeMetaData(rootLvl, rootId); - } - finally { - readUnlock(metaPageId, metaPage, pageAddr); - } - } - finally { - releasePage(metaPageId, metaPage); - } - - return meta0; - } - - /** - * @return Root level. - * @throws IgniteCheckedException If failed. - */ - private int getRootLevel() throws IgniteCheckedException { - TreeMetaData meta0 = treeMeta(); - - assert meta0 != null; - - return meta0.rootLvl; - } - - /** - * @param metaId Meta page ID. - * @param metaPage Meta page pointer. - * @param lvl Level, if {@code 0} then it is a bottom level, if negative then root. - * @return Page ID. - */ - private long getFirstPageId(long metaId, long metaPage, int lvl) { - long pageAddr = readLock(metaId, metaPage); // Meta can't be removed. - - try { - BPlusMetaIO io = BPlusMetaIO.VERSIONS.forPage(pageAddr); - - if (lvl < 0) - lvl = io.getRootLevel(pageAddr); - - if (lvl >= io.getLevelsCount(pageAddr)) - return 0; - - return io.getFirstPageId(pageAddr, lvl); - } - finally { - readUnlock(metaId, metaPage, pageAddr); - } - } - - /** - * @param upper Upper bound. - * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row. - * @return Cursor. - * @throws IgniteCheckedException If failed. - */ - private GridCursor findLowerUnbounded(L upper, Object x) throws IgniteCheckedException { - ForwardCursor cursor = new ForwardCursor(null, upper, x); - - long firstPageId; - - long metaPage = acquirePage(metaPageId); - try { - firstPageId = getFirstPageId(metaPageId, metaPage, 0); // Level 0 is always at the bottom. - } - finally { - releasePage(metaPageId, metaPage); - } - - long firstPage = acquirePage(firstPageId); - - try { - long pageAddr = readLock(firstPageId, firstPage); // We always merge pages backwards, the first page is never removed. - - try { - cursor.init(pageAddr, io(pageAddr), 0); - } - finally { - readUnlock(firstPageId, firstPage, pageAddr); - } - } - finally { - releasePage(firstPageId, firstPage); - } - - return cursor; - } - - /** - * Check if the tree is getting destroyed. - */ - private void checkDestroyed() { - if (destroyed.get()) - throw new IllegalStateException("Tree is being concurrently destroyed: " + getName()); - } - - /** - * @param lower Lower bound inclusive or {@code null} if unbounded. - * @param upper Upper bound inclusive or {@code null} if unbounded. - * @return Cursor. - * @throws IgniteCheckedException If failed. - */ - @Override public GridCursor find(L lower, L upper) throws IgniteCheckedException { - return find(lower, upper, null); - } - - /** - * @param lower Lower bound inclusive or {@code null} if unbounded. - * @param upper Upper bound inclusive or {@code null} if unbounded. - * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row. - * @return Cursor. - * @throws IgniteCheckedException If failed. - */ - public final GridCursor find(L lower, L upper, Object x) throws IgniteCheckedException { - checkDestroyed(); - - try { - if (lower == null) - return findLowerUnbounded(upper, x); - - ForwardCursor cursor = new ForwardCursor(lower, upper, x); - - cursor.find(); - - return cursor; - } - catch (IgniteCheckedException e) { - throw new IgniteCheckedException("Runtime failure on bounds: [lower=" + lower + ", upper=" + upper + "]", e); - } - catch (RuntimeException e) { - throw new IgniteException("Runtime failure on bounds: [lower=" + lower + ", upper=" + upper + "]", e); - } - catch (AssertionError e) { - throw new AssertionError("Assertion error on bounds: [lower=" + lower + ", upper=" + upper + "]", e); - } - finally { - checkDestroyed(); - } - } - - /** {@inheritDoc} */ - @Override public T findFirst() throws IgniteCheckedException { - checkDestroyed(); - - try { - long firstPageId; - - long metaPage = acquirePage(metaPageId); - try { - firstPageId = getFirstPageId(metaPageId, metaPage, 0); - } - finally { - releasePage(metaPageId, metaPage); - } - - long page = acquirePage(firstPageId); - - try { - long pageAddr = readLock(firstPageId, page); - - try { - BPlusIO io = io(pageAddr); - - int cnt = io.getCount(pageAddr); - - if (cnt == 0) - return null; - - return getRow(io, pageAddr, 0); - } - finally { - readUnlock(firstPageId, page, pageAddr); - } - } - finally { - releasePage(firstPageId, page); - } - } - catch (IgniteCheckedException e) { - throw new IgniteCheckedException("Runtime failure on first row lookup", e); - } - catch (RuntimeException e) { - throw new IgniteException("Runtime failure on first row lookup", e); - } - catch (AssertionError e) { - throw new AssertionError("Assertion error on first row lookup", e); - } - finally { - checkDestroyed(); - } - } - - /** {@inheritDoc} */ - @SuppressWarnings("unchecked") - @Override public T findLast() throws IgniteCheckedException { - checkDestroyed(); - - try { - GetOne g = new GetOne(null, null, true); - doFind(g); - - return (T)g.row; - } - catch (IgniteCheckedException e) { - throw new IgniteCheckedException("Runtime failure on last row lookup", e); - } - catch (RuntimeException e) { - throw new IgniteException("Runtime failure on last row lookup", e); - } - catch (AssertionError e) { - throw new AssertionError("Assertion error on last row lookup", e); - } - finally { - checkDestroyed(); - } - } - - /** - * @param row Lookup row for exact match. - * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row. - * @return Found result or {@code null}. - * @throws IgniteCheckedException If failed. - */ - @SuppressWarnings("unchecked") - public final R findOne(L row, Object x) throws IgniteCheckedException { - checkDestroyed(); - - try { - GetOne g = new GetOne(row, x, false); - - doFind(g); - - return (R)g.row; - } - catch (IgniteCheckedException e) { - throw new IgniteCheckedException("Runtime failure on lookup row: " + row, e); - } - catch (RuntimeException e) { - throw new IgniteException("Runtime failure on lookup row: " + row, e); - } - catch (AssertionError e) { - throw new AssertionError("Assertion error on lookup row: " + row, e); - } - finally { - checkDestroyed(); - } - } - - /** - * @param row Lookup row for exact match. - * @return Found row. - * @throws IgniteCheckedException If failed. - */ - @SuppressWarnings("unchecked") - @Override public final T findOne(L row) throws IgniteCheckedException { - return findOne(row, null); - } - - /** - * @param g Get. - * @throws IgniteCheckedException If failed. - */ - private void doFind(Get g) throws IgniteCheckedException { - for (;;) { // Go down with retries. - g.init(); - - switch (findDown(g, g.rootId, 0L, g.rootLvl)) { - case RETRY: - case RETRY_ROOT: - checkInterrupted(); - - continue; - - default: - return; - } - } - } - - /** - * @param g Get. - * @param pageId Page ID. - * @param fwdId Expected forward page ID. - * @param lvl Level. - * @return Result code. - * @throws IgniteCheckedException If failed. - */ - private Result findDown(final Get g, final long pageId, final long fwdId, final int lvl) - throws IgniteCheckedException { - long page = acquirePage(pageId); - - try { - for (;;) { - // Init args. - g.pageId = pageId; - g.fwdId = fwdId; - - Result res = read(pageId, page, search, g, lvl, RETRY); - - switch (res) { - case GO_DOWN: - case GO_DOWN_X: - assert g.pageId != pageId; - assert g.fwdId != fwdId || fwdId == 0; - - // Go down recursively. - res = findDown(g, g.pageId, g.fwdId, lvl - 1); - - switch (res) { - case RETRY: - checkInterrupted(); - - continue; // The child page got split, need to reread our page. - - default: - return res; - } - - case NOT_FOUND: - assert lvl == 0 : lvl; - - g.row = null; // Mark not found result. - - return res; - - default: - return res; - } - } - } - finally { - if (g.canRelease(pageId, lvl)) - releasePage(pageId, page); - } - } - - /** - * @param instance Instance name. - * @param type Tree type. - * @return Tree name. - */ - public static String treeName(String instance, String type) { - return instance + "##" + type; - } - - /** - * For debug. - * - * @return Tree as {@link String}. - * @throws IgniteCheckedException If failed. - */ - @SuppressWarnings("unused") - public final String printTree() throws IgniteCheckedException { - long rootPageId; - - long metaPage = acquirePage(metaPageId); - try { - rootPageId = getFirstPageId(metaPageId, metaPage, -1); - } - finally { - releasePage(metaPageId, metaPage); - } - - return treePrinter.print(rootPageId); - } - - /** - * @throws IgniteCheckedException If failed. - */ - public final void validateTree() throws IgniteCheckedException { - long rootPageId; - int rootLvl; - - long metaPage = acquirePage(metaPageId); - try { - rootLvl = getRootLevel(); - - if (rootLvl < 0) - fail("Root level: " + rootLvl); - - validateFirstPages(metaPageId, metaPage, rootLvl); - - rootPageId = getFirstPageId(metaPageId, metaPage, rootLvl); - - validateDownPages(rootPageId, 0L, rootLvl); - - validateDownKeys(rootPageId, null, rootLvl); - } - finally { - releasePage(metaPageId, metaPage); - } - } - - /** - * @param pageId Page ID. - * @param minRow Minimum row. - * @throws IgniteCheckedException If failed. - */ - private void validateDownKeys(long pageId, L minRow, int lvl) throws IgniteCheckedException { - long page = acquirePage(pageId); - try { - long pageAddr = readLock(pageId, page); // No correctness guaranties. - - try { - BPlusIO io = io(pageAddr); - - int cnt = io.getCount(pageAddr); - - if (cnt < 0) - fail("Negative count: " + cnt); - - if (io.isLeaf()) { - for (int i = 0; i < cnt; i++) { - 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); - } - - return; - } - - // To find our inner key we have to go left and then always go to the right. - for (int i = 0; i < cnt; i++) { - L row = io.getLookupRow(this, pageAddr, i); - - 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(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, lvl - 1); - - minRow = row; - } - - // 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, lvl - 1); - } - finally { - readUnlock(pageId, page, pageAddr); - } - } - finally { - releasePage(pageId, page); - } - } - - /** - * @param pageId Page ID. - * @return Search row. - * @throws IgniteCheckedException If failed. - */ - private L getGreatestRowInSubTree(long pageId) throws IgniteCheckedException { - long page = acquirePage(pageId); - try { - long pageAddr = readLock(pageId, page); // No correctness guaranties. - - try { - BPlusIO io = io(pageAddr); - - int cnt = io.getCount(pageAddr); - - if (io.isLeaf()) { - if (cnt <= 0) // This code is called only if the tree is not empty, so we can't see empty leaf. - fail("Invalid leaf count: " + cnt + " " + U.hexLong(pageId)); - - return io.getLookupRow(this, pageAddr, cnt - 1); - } - - long rightId = inner(io).getLeft(pageAddr, cnt);// The same as getRight(cnt - 1), but good for routing pages. - - return getGreatestRowInSubTree(rightId); - } - finally { - readUnlock(pageId, page, pageAddr); - } - } - finally { - releasePage(pageId, page); - } - } - - /** - * @param metaId Meta page ID. - * @param metaPage Meta page pointer. - * @param rootLvl Root level. - * @throws IgniteCheckedException If failed. - */ - private void validateFirstPages(long metaId, long metaPage, int rootLvl) throws IgniteCheckedException { - for (int lvl = rootLvl; lvl > 0; lvl--) - validateFirstPage(metaId, metaPage, lvl); - } - - /** - * @param msg Message. - */ - private static void fail(Object msg) { - throw new AssertionError(msg); - } - - /** - * @param metaId Meta page ID. - * @param metaPage Meta page pointer. - * @param lvl Level. - * @throws IgniteCheckedException If failed. - */ - private void validateFirstPage(long metaId, long metaPage, int lvl) throws IgniteCheckedException { - if (lvl == 0) - fail("Leaf level: " + lvl); - - long pageId = getFirstPageId(metaId, metaPage, lvl); - - long leftmostChildId; - - long page = acquirePage(pageId); - try { - long pageAddr = readLock(pageId, page); // No correctness guaranties. - - try { - BPlusIO io = io(pageAddr); - - if (io.isLeaf()) - fail("Leaf."); - - leftmostChildId = inner(io).getLeft(pageAddr, 0); - } - finally { - readUnlock(pageId, page, pageAddr); - } - } - finally { - releasePage(pageId, page); - } - - long firstDownPageId = getFirstPageId(metaId, metaPage, lvl - 1); - - if (firstDownPageId != leftmostChildId) - fail(new SB("First: meta ").appendHex(firstDownPageId).a(", child ").appendHex(leftmostChildId)); - } - - /** - * @param pageId Page ID. - * @param fwdId Forward ID. - * @param lvl Level. - * @throws IgniteCheckedException If failed. - */ - private void validateDownPages(long pageId, long fwdId, int lvl) throws IgniteCheckedException { - long page = acquirePage(pageId); - try { - long pageAddr = readLock(pageId, page); // No correctness guaranties. - - try { - long realPageId = BPlusIO.getPageId(pageAddr); - - if (realPageId != pageId) - fail(new SB("ABA on page ID: ref ").appendHex(pageId).a(", buf ").appendHex(realPageId)); - - BPlusIO io = io(pageAddr); - - if (io.isLeaf() != (lvl == 0)) // Leaf pages only at the level 0. - fail("Leaf level mismatch: " + lvl); - - long actualFwdId = io.getForward(pageAddr); - - if (actualFwdId != fwdId) - fail(new SB("Triangle: expected fwd ").appendHex(fwdId).a(", actual fwd ").appendHex(actualFwdId)); - - int cnt = io.getCount(pageAddr); - - if (cnt < 0) - fail("Negative count: " + cnt); - - if (io.isLeaf()) { - if (cnt == 0 && getRootLevel() != 0) - fail("Empty leaf page."); - } - else { - // Recursively go down if we are on inner level. - for (int i = 0; i < cnt; i++) - validateDownPages(inner(io).getLeft(pageAddr, i), inner(io).getRight(pageAddr, i), lvl - 1); - - if (fwdId != 0) { - // For the rightmost child ask neighbor. - long fwdId0 = fwdId; - long fwdPage = acquirePage(fwdId0); - try { - long fwdPageAddr = readLock(fwdId0, fwdPage); // No correctness guaranties. - - try { - if (io(fwdPageAddr) != io) - fail("IO on the same level must be the same"); - - fwdId = inner(io).getLeft(fwdPageAddr, 0); - } - finally { - readUnlock(fwdId0, fwdPage, fwdPageAddr); - } - } - finally { - releasePage(fwdId0, fwdPage); - } - } - - long leftId = inner(io).getLeft(pageAddr, cnt); // The same as io.getRight(cnt - 1) but works for routing pages. - - validateDownPages(leftId, fwdId, lvl - 1); - } - } - finally { - readUnlock(pageId, page, pageAddr); - } - } - finally { - releasePage(pageId, page); - } - } - - /** - * @param io IO. - * @param pageAddr Page address. - * @param keys Keys. - * @return String. - * @throws IgniteCheckedException If failed. - */ - private String printPage(BPlusIO io, long pageAddr, boolean keys) throws IgniteCheckedException { - StringBuilder b = new StringBuilder(); - - b.append(formatPageId(PageIO.getPageId(pageAddr))); - - b.append(" [ "); - b.append(io.isLeaf() ? "L " : "I "); - - int cnt = io.getCount(pageAddr); - long fwdId = io.getForward(pageAddr); - - b.append("cnt=").append(cnt).append(' '); - b.append("fwd=").append(formatPageId(fwdId)).append(' '); - - if (!io.isLeaf()) { - b.append("lm=").append(formatPageId(inner(io).getLeft(pageAddr, 0))).append(' '); - - if (cnt > 0) - b.append("rm=").append(formatPageId(inner(io).getRight(pageAddr, cnt - 1))).append(' '); - } - - if (keys) - b.append("keys=").append(printPageKeys(io, pageAddr)).append(' '); - - b.append(']'); - - return b.toString(); - } - - /** - * @param io IO. - * @param pageAddr Page address. - * @return Keys as String. - * @throws IgniteCheckedException If failed. - */ - private String printPageKeys(BPlusIO io, long pageAddr) throws IgniteCheckedException { - int cnt = io.getCount(pageAddr); - - StringBuilder b = new StringBuilder(); - - b.append('['); - - for (int i = 0; i < cnt; i++) { - if (i != 0) - b.append(','); - - b.append(io.isLeaf() || canGetRowFromInner ? getRow(io, pageAddr, i) : io.getLookupRow(this, pageAddr, i)); - } - - b.append(']'); - - return b.toString(); - } - - /** - * @param x Long. - * @return String. - */ - private static String formatPageId(long x) { - return U.hexLong(x); - } - - /** - * @param idx Index after binary search, which can be negative. - * @return Always positive index. - */ - private static int fix(int idx) { - assert checkIndex(idx): idx; - - if (idx < 0) - idx = -idx - 1; - - return idx; - } - - /** - * @param idx Index. - * @return {@code true} If correct. - */ - private static boolean checkIndex(int idx) { - return idx > -Short.MAX_VALUE && idx < Short.MAX_VALUE; - } - - /** - * Check if interrupted. - * @throws IgniteInterruptedCheckedException If interrupted. - */ - private static void checkInterrupted() throws IgniteInterruptedCheckedException { - // We should not interrupt operations in the middle, because otherwise we'll end up in inconsistent state. - // Because of that we do not check for Thread.interrupted() - if (interrupted) - throw new IgniteInterruptedCheckedException("Interrupted."); - } - - /** - * Interrupt all operations on all threads and all indexes. - */ - @SuppressWarnings("unused") - public static void interruptAll() { - interrupted = true; - } - - /** - * @param row Lookup row. - * @return Removed row. - * @throws IgniteCheckedException If failed. - */ - @Override public final T remove(L row) throws IgniteCheckedException { - return doRemove(row, true); - } - - /** - * @param row Lookup row. - * @throws IgniteCheckedException If failed. - * @return {@code True} if removed row. - */ - public final boolean removex(L row) throws IgniteCheckedException { - Boolean res = (Boolean)doRemove(row, false); - - return res != null ? res : false; - } - - /** {@inheritDoc} */ - @Override public void invoke(L row, Object z, InvokeClosure c) throws IgniteCheckedException { - checkDestroyed(); - - Invoke x = new Invoke(row, z, c); - - try { - for (;;) { - x.init(); - - Result res = invokeDown(x, x.rootId, 0L, 0L, x.rootLvl); - - switch (res) { - case RETRY: - case RETRY_ROOT: - checkInterrupted(); - - continue; - - default: - if (!x.isFinished()) { - res = x.tryFinish(); - - if (res == RETRY || res == RETRY_ROOT) { - checkInterrupted(); - - continue; - } - - assert x.isFinished(): res; - } - - return; - } - } - } - catch (IgniteCheckedException e) { - throw new IgniteCheckedException("Runtime failure on search row: " + row, e); - } - catch (RuntimeException e) { - throw new IgniteException("Runtime failure on search row: " + row, e); - } - catch (AssertionError e) { - throw new AssertionError("Assertion error on search row: " + row, e); - } - finally { - x.releaseAll(); - checkDestroyed(); - } - } - - /** - * @param x Invoke operation. - * @param pageId Page ID. - * @param backId Expected backward page ID if we are going to the right. - * @param fwdId Expected forward page ID. - * @param lvl Level. - * @return Result code. - * @throws IgniteCheckedException If failed. - */ - private Result invokeDown(final Invoke x, final long pageId, final long backId, final long fwdId, final int lvl) - throws IgniteCheckedException { - assert lvl >= 0 : lvl; - - if (x.isTail(pageId, lvl)) - return FOUND; // We've already locked this page, so return that we are ok. - - long page = acquirePage(pageId); - - try { - for (;;) { - // Init args. - x.pageId(pageId); - x.fwdId(fwdId); - x.backId(backId); - - Result res = read(pageId, page, search, x, lvl, RETRY); - - switch (res) { - case GO_DOWN_X: - assert backId != 0; - assert x.backId == 0; // We did not setup it yet. - - x.backId(pageId); // Dirty hack to setup a check inside of askNeighbor. - - // We need to get backId here for our child page, it must be the last child of our back. - res = askNeighbor(backId, x, true); - - if (res != FOUND) - return res; // Retry. - - assert x.backId != pageId; // It must be updated in askNeighbor. - - // Intentional fallthrough. - case GO_DOWN: - res = x.tryReplaceInner(pageId, page, fwdId, lvl); - - if (res != RETRY) - res = invokeDown(x, x.pageId, x.backId, x.fwdId, lvl - 1); - - if (res == RETRY_ROOT || x.isFinished()) - return res; - - if (res == RETRY) { - checkInterrupted(); - - continue; - } - - // Unfinished Put does insertion on the same level. - if (x.isPut()) - continue; - - assert x.isRemove(); // Guarded by isFinished. - - res = x.finishOrLockTail(pageId, page, backId, fwdId, lvl); - - return res; - - case NOT_FOUND: - if (lvl == 0) - x.invokeClosure(); - - return x.onNotFound(pageId, page, fwdId, lvl); - - case FOUND: - if (lvl == 0) - x.invokeClosure(); - - return x.onFound(pageId, page, backId, fwdId, lvl); - - default: - return res; - } - } - } - finally { - x.levelExit(); - - if (x.canRelease(pageId, lvl)) - releasePage(pageId, page); - } - } - - - /** - * @param row Lookup row. - * @param needOld {@code True} if need return removed row. - * @return Removed row. - * @throws IgniteCheckedException If failed. - */ - private T doRemove(L row, boolean needOld) throws IgniteCheckedException { - checkDestroyed(); - - Remove r = new Remove(row, needOld); - - try { - for (;;) { - r.init(); - - Result res = removeDown(r, r.rootId, 0L, 0L, r.rootLvl); - - switch (res) { - case RETRY: - case RETRY_ROOT: - checkInterrupted(); - - continue; - - default: - if (!r.isFinished()) { - res = r.finishTail(); - - // If not found, then the tree grew beyond our call stack -> retry from the actual root. - if (res == RETRY || res == NOT_FOUND) { - assert r.checkTailLevel(getRootLevel()) : "tail=" + r.tail + ", res=" + res; - - checkInterrupted(); - - continue; - } - - assert res == FOUND: res; - } - - assert r.isFinished(); - - return r.rmvd; - } - } - } - catch (IgniteCheckedException e) { - throw new IgniteCheckedException("Runtime failure on search row: " + row, e); - } - catch (RuntimeException e) { - throw new IgniteException("Runtime failure on search row: " + row, e); - } - catch (AssertionError e) { - throw new AssertionError("Assertion error on search row: " + row, e); - } - finally { - r.releaseAll(); - checkDestroyed(); - } - } - - /** - * @param r Remove operation. - * @param pageId Page ID. - * @param backId Expected backward page ID if we are going to the right. - * @param fwdId Expected forward page ID. - * @param lvl Level. - * @return Result code. - * @throws IgniteCheckedException If failed. - */ - private Result removeDown(final Remove r, final long pageId, final long backId, final long fwdId, final int lvl) - throws IgniteCheckedException { - assert lvl >= 0 : lvl; - - if (r.isTail(pageId, lvl)) - return FOUND; // We've already locked this page, so return that we are ok. - - long page = acquirePage(pageId); - - try { - for (;;) { - // Init args. - r.pageId = pageId; - r.fwdId = fwdId; - r.backId = backId; - - Result res = read(pageId, page, search, r, lvl, RETRY); - - switch (res) { - case GO_DOWN_X: - assert backId != 0; - assert r.backId == 0; // We did not setup it yet. - - r.backId = pageId; // Dirty hack to setup a check inside of askNeighbor. - - // We need to get backId here for our child page, it must be the last child of our back. - res = askNeighbor(backId, r, true); - - if (res != FOUND) - return res; // Retry. - - assert r.backId != pageId; // It must be updated in askNeighbor. - - // Intentional fallthrough. - case GO_DOWN: - res = removeDown(r, r.pageId, r.backId, r.fwdId, lvl - 1); - - if (res == RETRY) { - checkInterrupted(); - - continue; - } - - if (res == RETRY_ROOT || r.isFinished()) - return res; - - res = r.finishOrLockTail(pageId, page, backId, fwdId, lvl); - - return res; - - case NOT_FOUND: - // We are at the bottom. - assert lvl == 0 : lvl; - - r.finish(); - - return res; - - case FOUND: - return r.tryRemoveFromLeaf(pageId, page, backId, fwdId, lvl); - - default: - return res; - } - } - } - finally { - r.page = 0L; - - if (r.canRelease(pageId, lvl)) - releasePage(pageId, page); - } - } - - /** - * @param cnt Count. - * @param cap Capacity. - * @return {@code true} If may merge. - */ - private boolean mayMerge(int cnt, int cap) { - int minCnt = (int)(minFill * cap); - - if (cnt <= minCnt) { - assert cnt == 0; // TODO remove - - return true; - } - - assert cnt > 0; - - int maxCnt = (int)(maxFill * cap); - - if (cnt > maxCnt) - return false; - - assert false; // TODO remove - - // Randomization is for smoothing worst case scenarios. Probability of merge attempt - // is proportional to free space in our page (discounted on fill factor). - return randomInt(maxCnt - minCnt) >= cnt - minCnt; - } - - /** - * @return Root level. - * @throws IgniteCheckedException If failed. - */ - public final int rootLevel() throws IgniteCheckedException { - checkDestroyed(); - - return getRootLevel(); - } - - /** - * !!! For debug only! May produce wrong results on concurrent access. - * - * @return Size. - * @throws IgniteCheckedException If failed. - */ - @Override public final long size() throws IgniteCheckedException { - checkDestroyed(); - - long pageId; - - long metaPage = acquirePage(metaPageId); - try { - pageId = getFirstPageId(metaPageId, metaPage, 0); // Level 0 is always at the bottom. - } - finally { - releasePage(metaPageId, metaPage); - } - - BPlusIO io = null; - - long cnt = 0; - - while (pageId != 0) { - long curId = pageId; - long curPage = acquirePage(curId); - try { - long curAddr = readLock(curId, curPage); // No correctness guaranties. - - try { - if (io == null) { - io = io(curAddr); - - assert io.isLeaf(); - } - - cnt += io.getCount(curAddr); - - pageId = io.getForward(curAddr); - } - finally { - readUnlock(curId, curPage, curAddr); - } - } - finally { - releasePage(curId, curPage); - } - } - - checkDestroyed(); - - return cnt; - } - - /** - * {@inheritDoc} - */ - @Override public final T put(T row) throws IgniteCheckedException { - return doPut(row, true); - } - - /** - * @param row New value. - * @throws IgniteCheckedException If failed. - * @return {@code True} if replaced existing row. - */ - public boolean putx(T row) throws IgniteCheckedException { - Boolean res = (Boolean)doPut(row, false); - - return res != null ? res : false; - } - - /** - * @param row New value. - * @param needOld {@code True} If need return old value. - * @return Old row. - * @throws IgniteCheckedException If failed. - */ - private T doPut(T row, boolean needOld) throws IgniteCheckedException { - checkDestroyed(); - - Put p = new Put(row, needOld); - - try { - for (;;) { // Go down with retries. - p.init(); - - Result res = putDown(p, p.rootId, 0L, p.rootLvl); - - switch (res) { - case RETRY: - case RETRY_ROOT: - checkInterrupted(); - - continue; - - case FOUND: - // We may need to insert split key into upper level here. - if (!p.isFinished()) { - // It must be impossible to have an insert higher than the current root, - // because we are making decision about creating new root while keeping - // write lock on current root, so it can't concurrently change. - assert p.btmLvl <= getRootLevel(); - - checkInterrupted(); - - continue; - } - - return p.oldRow; - - default: - throw new IllegalStateException("Result: " + res); - } - } - } - catch (IgniteCheckedException e) { - throw new IgniteCheckedException("Runtime failure on row: " + row, e); - } - catch (RuntimeException e) { - throw new IgniteException("Runtime failure on row: " + row, e); - } - catch (AssertionError e) { - throw new AssertionError("Assertion error on row: " + row, e); - } - finally { - checkDestroyed(); - } - } - - /** - * Destroys tree. This method is allowed to be invoked only when the tree is out of use (no concurrent operations - * are trying to read or update the tree after destroy beginning). - * - * @return Number of pages recycled from this tree. If the tree was destroyed by someone else concurrently returns - * {@code 0}, otherwise it should return at least {@code 2} (for meta page and root page), unless this tree is - * used as metadata storage, or {@code -1} if we don't have a reuse list and did not do recycling at all. - * @throws IgniteCheckedException If failed. - */ - public final long destroy() throws IgniteCheckedException { - return destroy(null); - } - - /** - * Destroys tree. This method is allowed to be invoked only when the tree is out of use (no concurrent operations - * are trying to read or update the tree after destroy beginning). - * - * @param c Visitor closure. Visits only leaf pages. - * @return Number of pages recycled from this tree. If the tree was destroyed by someone else concurrently returns - * {@code 0}, otherwise it should return at least {@code 2} (for meta page and root page), unless this tree is - * used as metadata storage, or {@code -1} if we don't have a reuse list and did not do recycling at all. - * @throws IgniteCheckedException If failed. - */ - public final long destroy(IgniteInClosure c) throws IgniteCheckedException { - if (!markDestroyed()) - return 0; - - if (reuseList == null) - return -1; - - DestroyBag bag = new DestroyBag(); - - long pagesCnt = 0; - - long metaPage = acquirePage(metaPageId); - try { - long metaPageAddr = writeLock(metaPageId, metaPage); // No checks, we must be out of use. - - assert metaPageAddr != 0L; - - try { - for (long pageId : getFirstPageIds(metaPageAddr)) { - assert pageId != 0; - - do { - final long pId = pageId; - - long page = acquirePage(pId); - - try { - long pageAddr = writeLock(pId, page); // No checks, we must be out of use. - - try { - BPlusIO io = io(pageAddr); - - if (c != null && io.isLeaf()) - io.visit(pageAddr, c); - - long fwdPageId = io.getForward(pageAddr); - - bag.addFreePage(recyclePage(pageId, page, pageAddr, null)); - pagesCnt++; - - pageId = fwdPageId; - } - finally { - writeUnlock(pId, page, pageAddr, true); - } - } - finally { - releasePage(pId, page); - } - - if (bag.size() == 128) { - reuseList.addForRecycle(bag); - - assert bag.isEmpty() : bag.size(); - } - } - while (pageId != 0); - } - - bag.addFreePage(recyclePage(metaPageId, metaPage, metaPageAddr, null)); - pagesCnt++; - } - finally { - writeUnlock(metaPageId, metaPage, metaPageAddr, true); - } - } - finally { - releasePage(metaPageId, metaPage); - } - - reuseList.addForRecycle(bag); - - assert bag.size() == 0 : bag.size(); - - return pagesCnt; - } - - /** - * @return {@code True} if state was changed. - */ - private boolean markDestroyed() { - return destroyed.compareAndSet(false, true); - } - - /** - * @param pageAddr Meta page address. - * @return First page IDs. - */ - protected Iterable getFirstPageIds(long pageAddr) { - List res = new ArrayList<>(); - - BPlusMetaIO mio = BPlusMetaIO.VERSIONS.forPage(pageAddr); - - for (int lvl = mio.getRootLevel(pageAddr); lvl >= 0; lvl--) - res.add(mio.getFirstPageId(pageAddr, lvl)); - - return res; - } - - /** - * @param pageId Page ID. - * @param page Page pointer. - * @param pageAddr Page address - * @param io IO. - * @param fwdId Forward page ID. - * @param fwdBuf Forward buffer. - * @param idx Insertion index. - * @return {@code true} The middle index was shifted to the right. - * @throws IgniteCheckedException If failed. - */ - private boolean splitPage( - long pageId, long page, long pageAddr, BPlusIO io, long fwdId, long fwdBuf, int idx - ) throws IgniteCheckedException { - int cnt = io.getCount(pageAddr); - int mid = cnt >>> 1; - - boolean res = false; - - if (idx > mid) { // If insertion is going to be to the forward page, keep more in the back page. - mid++; - - res = true; - } - - // Update forward page. - io.splitForwardPage(pageAddr, fwdId, fwdBuf, mid, cnt, pageSize()); - - // Update existing page. - io.splitExistingPage(pageAddr, mid, fwdId); - - if (needWalDeltaRecord(pageId, page, null)) - wal.log(new SplitExistingPageRecord(cacheId, pageId, mid, fwdId)); - - return res; - } - - /** - * @param pageId Page ID. - * @param page Page pointer. - * @param pageAddr Page address - * @param walPlc Full page WAL record policy. - */ - private void writeUnlockAndClose(long pageId, long page, long pageAddr, Boolean walPlc) { - try { - writeUnlock(pageId, page, pageAddr, walPlc, true); - } - finally { - releasePage(pageId, page); - } - } - - /** - * @param pageId Inner page ID. - * @param g Get. - * @param back Get back (if {@code true}) or forward page (if {@code false}). - * @return Operation result. - * @throws IgniteCheckedException If failed. - */ - private Result askNeighbor(long pageId, Get g, boolean back) throws IgniteCheckedException { - return read(pageId, askNeighbor, g, back ? TRUE.ordinal() : FALSE.ordinal(), RETRY); - } - - /** - * @param p Put. - * @param pageId Page ID. - * @param fwdId Expected forward page ID. - * @param lvl Level. - * @return Result code. - * @throws IgniteCheckedException If failed. - */ - private Result putDown(final Put p, final long pageId, final long fwdId, final int lvl) - throws IgniteCheckedException { - assert lvl >= 0 : lvl; - - final long page = acquirePage(pageId); - - try { - for (;;) { - // Init args. - p.pageId = pageId; - p.fwdId = fwdId; - - Result res = read(pageId, page, search, p, lvl, RETRY); - - switch (res) { - case GO_DOWN: - case GO_DOWN_X: - assert lvl > 0 : lvl; - assert p.pageId != pageId; - assert p.fwdId != fwdId || fwdId == 0; - - res = p.tryReplaceInner(pageId, page, fwdId, lvl); - - if (res != RETRY) // Go down recursively. - res = putDown(p, p.pageId, p.fwdId, lvl - 1); - - if (res == RETRY_ROOT || p.isFinished()) - return res; - - if (res == RETRY) - checkInterrupted(); - - continue; // We have to insert split row to this level or it is a retry. - - case FOUND: // Do replace. - assert lvl == 0 : "This replace can happen only at the bottom level."; - - return p.tryReplace(pageId, page, fwdId, lvl); - - case NOT_FOUND: // Do insert. - assert lvl == p.btmLvl : "must insert at the bottom level"; - assert p.needReplaceInner == FALSE : p.needReplaceInner + " " + lvl; - - return p.tryInsert(pageId, page, fwdId, lvl); - - default: - return res; - } - } - } - finally { - if (p.canRelease(pageId, lvl)) - releasePage(pageId, page); - } - } - - /** - * @param io IO. - * @param pageAddr Page address. - * @param back Backward page. - * @return Page ID. - */ - private long doAskNeighbor(BPlusIO io, long pageAddr, boolean back) { - long res; - - if (back) { - // Count can be 0 here if it is a routing page, in this case we have a single child. - int cnt = io.getCount(pageAddr); - - // We need to do get the rightmost child: io.getRight(cnt - 1), - // here io.getLeft(cnt) is the same, but handles negative index if count is 0. - res = inner(io).getLeft(pageAddr, cnt); - } - else // Leftmost child. - res = inner(io).getLeft(pageAddr, 0); - - assert res != 0 : "inner page with no route down: " + U.hexLong(PageIO.getPageId(pageAddr)); - - return res; - } - - /** {@inheritDoc} */ - @Override public String toString() { - return S.toString(BPlusTree.class, this); - } - - /** - * Get operation. - */ - private abstract class Get { - /** */ - long rmvId; - - /** Starting point root level. May be outdated. Must be modified only in {@link Get#init()}. */ - int rootLvl; - - /** Starting point root ID. May be outdated. Must be modified only in {@link Get#init()}. */ - long rootId; - - /** */ - L row; - - /** In/Out parameter: Page ID. */ - long pageId; - - /** In/Out parameter: expected forward page ID. */ - long fwdId; - - /** In/Out parameter: in case of right turn this field will contain backward page ID for the child. */ - long backId; - - /** */ - int shift; - - /** If this operation is a part of invoke. */ - Invoke invoke; - - /** Ignore row passed, find last row */ - boolean findLast; - - /** - * @param row Row. - * @param findLast find last row. - */ - Get(L row, boolean findLast) { - assert findLast ^ row != null; - - this.row = row; - this.findLast = findLast; - } - - /** - * @param g Other operation to copy from. - */ - final void copyFrom(Get g) { - rmvId = g.rmvId; - rootLvl = g.rootLvl; - pageId = g.pageId; - fwdId = g.fwdId; - backId = g.backId; - shift = g.shift; - findLast = g.findLast; - } - - /** - * Initialize operation. - * - * @throws IgniteCheckedException If failed. - */ - final void init() throws IgniteCheckedException { - TreeMetaData meta0 = treeMeta(); - - assert meta0 != null; - - restartFromRoot(meta0.rootId, meta0.rootLvl, globalRmvId.get()); - } - - /** - * @param rootId Root page ID. - * @param rootLvl Root level. - * @param rmvId Remove ID to be afraid of. - */ - void restartFromRoot(long rootId, int rootLvl, long rmvId) { - this.rootId = rootId; - this.rootLvl = rootLvl; - this.rmvId = rmvId; - } - - /** - * @param io IO. - * @param pageAddr Page address. - * @param idx Index of found entry. - * @param lvl Level. - * @return {@code true} If we need to stop. - * @throws IgniteCheckedException If failed. - */ - boolean found(BPlusIO io, long pageAddr, int idx, int lvl) throws IgniteCheckedException { - assert lvl >= 0; - - return lvl == 0; // Stop if we are at the bottom. - } - - /** - * @param io IO. - * @param pageAddr Page address. - * @param idx Insertion point. - * @param lvl Level. - * @return {@code true} If we need to stop. - * @throws IgniteCheckedException If failed. - */ - boolean notFound(BPlusIO io, long pageAddr, int idx, int lvl) throws IgniteCheckedException { - assert lvl >= 0; - - return lvl == 0; // Stop if we are at the bottom. - } - - /** - * @param pageId Page. - * @param lvl Level. - * @return {@code true} If we can release the given page. - */ - boolean canRelease(long pageId, int lvl) { - return pageId != 0L; - } - - /** - * @param backId Back page ID. - */ - void backId(long backId) { - this.backId = backId; - } - - /** - * @param pageId Page ID. - */ - void pageId(long pageId) { - this.pageId = pageId; - } - - /** - * @param fwdId Forward page ID. - */ - void fwdId(long fwdId) { - this.fwdId = fwdId; - } - - /** - * @return {@code true} If the operation is finished. - */ - boolean isFinished() { - throw new IllegalStateException(); - } - } - - /** - * Get a single entry. - */ - private final class GetOne extends Get { - /** */ - Object x; - - /** - * @param row Row. - * @param x Implementation specific argument. - * @param findLast Ignore row passed, find last row - */ - private GetOne(L row, Object x, boolean findLast) { - super(row, findLast); - - this.x = x; - } - - /** {@inheritDoc} */ - @SuppressWarnings("unchecked") - @Override boolean found(BPlusIO io, long pageAddr, int idx, int lvl) throws IgniteCheckedException { - // Check if we are on an inner page and can't get row from it. - if (lvl != 0 && !canGetRowFromInner) - return false; - - row = getRow(io, pageAddr, idx, x); - - return true; - } - } - - /** - * Get a cursor for range. - */ - private final class GetCursor extends Get { - /** */ - ForwardCursor cursor; - - /** - * @param lower Lower bound. - * @param shift Shift. - * @param cursor Cursor. - */ - GetCursor(L lower, int shift, ForwardCursor cursor) { - super(lower, false); - - assert shift != 0; // Either handle range of equal rows or find a greater row after concurrent merge. - - this.shift = shift; - this.cursor = cursor; - } - - /** {@inheritDoc} */ - @Override boolean found(BPlusIO io, long pageAddr, int idx, int lvl) throws IgniteCheckedException { - throw new IllegalStateException(); // Must never be called because we always have a shift. - } - - /** {@inheritDoc} */ - @Override boolean notFound(BPlusIO io, long pageAddr, int idx, int lvl) throws IgniteCheckedException { - if (lvl != 0) - return false; - - cursor.init(pageAddr, io, idx); - - return true; - } - } - - /** - * Put operation. - */ - private final class Put extends Get { - /** Right child page ID for split row. */ - long rightId; - - /** Replaced row if any. */ - T oldRow; - - /** - * This page is kept locked after split until insert to the upper level will not be finished. - * It is needed because split row will be "in flight" and if we'll release tail, remove on - * split row may fail. - */ - long tailId; - - /** */ - long tailPage; - - /** */ - long tailAddr; - - /** - * Bottom level for insertion (insert can't go deeper). Will be incremented on split on each level. - */ - short btmLvl; - - /** */ - Bool needReplaceInner = FALSE; - - /** */ - final boolean needOld; - - /** - * @param row Row. - * @param needOld {@code True} If need return old value. - */ - private Put(T row, boolean needOld) { - super(row, false); - - this.needOld = needOld; - } - - /** {@inheritDoc} */ - @Override boolean found(BPlusIO io, long pageAddr, int idx, int lvl) { - if (lvl == 0) // Leaf: need to stop. - return true; - - assert btmLvl == 0; // It can not be insert. - - // If we can get full row from the inner page, we have to replace it with the new one. On the way down - // we can not miss inner key even in presence of concurrent operations because of `triangle` invariant + - // concurrent inner replace handling by retrying from root. - if (canGetRowFromInner && needReplaceInner == FALSE) - needReplaceInner = TRUE; - - return false; - } - - /** {@inheritDoc} */ - @Override boolean notFound(BPlusIO io, long pageAddr, int idx, int lvl) { - assert btmLvl >= 0 : btmLvl; - assert lvl >= btmLvl : lvl; - - return lvl == btmLvl; - } - - /** - * @param tailId Tail page ID. - * @param tailPage Tail page pointer. - * @param tailPageAddr Tail page address - */ - private void tail(long tailId, long tailPage, long tailPageAddr) { - assert (tailId == 0L) == (tailPage == 0L); - assert (tailPage == 0L) == (tailPageAddr == 0L); - - if (this.tailPage != 0L) - writeUnlockAndClose(this.tailId, this.tailPage, this.tailAddr, null); - - this.tailId = tailId; - this.tailPage = tailPage; - this.tailAddr = tailPageAddr; - } - - /** {@inheritDoc} */ - @Override boolean canRelease(long pageId, int lvl) { - return pageId != 0L && tailId != pageId; - } - - /** - * Finish put. - */ - private void finish() { - row = null; - rightId = 0; - - tail(0L, 0L, 0L); - } - - /** {@inheritDoc} */ - @Override boolean isFinished() { - return row == null; - } - - /** - * @param pageId Page ID. - * @param page Page pointer. - * @param pageAddr Page address. - * @param io IO. - * @param idx Index. - * @param lvl Level. - * @return Move up row. - * @throws IgniteCheckedException If failed. - */ - private L insert(long pageId, long page, long pageAddr, BPlusIO io, int idx, int lvl) - throws IgniteCheckedException { - int maxCnt = io.getMaxCount(pageAddr, pageSize()); -