ignite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sboi...@apache.org
Subject [26/50] ignite git commit: ignite-db - wip
Date Thu, 28 Apr 2016 08:52:56 GMT
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/892f1f51
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/892f1f51
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/892f1f51

Branch: refs/heads/ignite-db-x-10884
Commit: 892f1f51de8ad8a0051758d14d46624ceac403a6
Parents: 42ac3b3
Author: S.Vladykin <svladykin@gridgain.com>
Authored: Tue Apr 26 07:12:08 2016 +0300
Committer: S.Vladykin <svladykin@gridgain.com>
Committed: Tue Apr 26 07:12:08 2016 +0300

----------------------------------------------------------------------
 .../cache/database/tree/BPlusTree.java          | 130 +++++++++++++------
 .../processors/database/BPlusTreeSelfTest.java  |  16 +--
 2 files changed, 95 insertions(+), 51 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/ignite/blob/892f1f51/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 848d167..f0919d2 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
@@ -340,6 +340,9 @@ public abstract class BPlusTree<L, T extends L> {
             if (r.needReplaceInner == TRUE ||
                 // 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(buf))))
{
+                if (cnt == 1) // It was the last item.
+                    r.needMergeEmptyBranch = TRUE;
+
                 // If we have backId then we've already locked back page, nothing to do here.
                 if (r.fwdId != 0 && r.backId == 0)
                     r.lockForward(0);
@@ -960,6 +963,20 @@ public abstract class BPlusTree<L, T extends L> {
     }
 
     /**
+     * @param leftCnt Left count.
+     * @param rightCnt Right count.
+     * @param cap Capacity.
+     * @param leaf Is leaf pages.
+     * @return {@code true} If can merge these pages.
+     */
+    private boolean canMerge(int leftCnt, int rightCnt, int cap, boolean leaf) {
+        cap -= leftCnt;
+        cap -= rightCnt;
+
+        return cap > 0 || (cap == 0 && (leaf || leftCnt == 0 || rightCnt == 0));
+    }
+
+    /**
      * @param cnt Count.
      * @param cap Capacity.
      * @return {@code true} If may merge.
@@ -1614,6 +1631,9 @@ public abstract class BPlusTree<L, T extends L> {
         /** */
         byte needReplaceInner = FALSE;
 
+        /** */
+        byte needMergeEmptyBranch = FALSE;
+
         /** Removed row. */
         T removed;
 
@@ -1669,32 +1689,32 @@ public abstract class BPlusTree<L, T extends L> {
          * @throws IgniteCheckedException If failed.
          */
         private void mergeEmptyBranch() throws IgniteCheckedException {
+            assert needMergeEmptyBranch == TRUE;
+
             Tail<L> t = tail;
 
             assert t.getCount() > 0;
 
-            boolean leaf = false;
-
             // Find empty branch beginning.
             for (Tail<L> t0 = t.down; t0 != null; t0 = t0.down) {
                 assert t0.type == Tail.EXACT: t0.type;
 
                 if (t0.getCount() != 0)
                     t = t0;
-
-                leaf = t0.lvl == 0;
             }
 
-            if (!leaf) // Can not merge empty branches in the middle of tree.
-                return;
-
             while (t.lvl != 0) { // If we've found empty branch, merge it top down.
-                boolean res = merge(t, true);
+                boolean res = merge(t);
 
                 assert res;
 
+                if (needMergeEmptyBranch == TRUE)
+                    needMergeEmptyBranch = READY; // Need to mark that we've already done
the first iteration.
+
                 t = t.down;
             }
+
+            assert t.lvl == 0: t.lvl;
         }
 
         /**
@@ -1703,10 +1723,15 @@ public abstract class BPlusTree<L, T extends L> {
          * @throws IgniteCheckedException
          */
         private boolean mergeDown(Tail<L> t) throws IgniteCheckedException {
-            if (t.down == null || t.down.sibling == null)
+            assert needMergeEmptyBranch == FALSE || needMergeEmptyBranch == DONE: needMergeEmptyBranch;
+
+            if (t.down == null)
                 return true;
 
-            return mergeDown(t.down) && merge(t, false);
+            if (t.down.sibling == null) // We've merged something there.
+                return false;
+
+            return mergeDown(t.down) && merge(t);
         }
 
         /**
@@ -1719,29 +1744,37 @@ public abstract class BPlusTree<L, T extends L> {
             assert !isFinished();
             assert tail.type == Tail.EXACT;
 
-            // Need to lock more.
-            if (tail.down == null || needReplaceInner == TRUE || tail.getCount() == 0)
+            // Need to lock more to be able to merge.
+            if (needReplaceInner == TRUE ||
+                (needMergeEmptyBranch == TRUE && (tail.down == null || tail.getCount()
== 0)))
                 return false;
 
-            mergeEmptyBranch();
+            // Can merge only if tail is not a routing page.
+            if (tail.getCount() > 0) {
+                if (needMergeEmptyBranch == TRUE) {
+                    mergeEmptyBranch();
 
-            boolean mergeMore = mergeDown(tail);
+                    needMergeEmptyBranch = DONE;
+                }
 
-            if (needReplaceInner == READY) {
-                // Need to replace inner key with new max key for the left subtree.
-                replaceInner();
+                boolean mergeMore = mergeDown(tail);
 
-                needReplaceInner = DONE;
-            }
+                if (needReplaceInner == READY) {
+                    // Need to replace inner key with new max key for the left subtree.
+                    replaceInner(needMergeEmptyBranch == DONE);
 
-            if (tail.getCount() == 0 && tail.lvl != 0 && getRootLevel(meta)
== tail.lvl)
-                freePage(tail.page, tail.buf, tail.io, tail.lvl, false); // Free root.
-            else if (mergeMore) {
-                doReleaseTail(tail.down);
+                    needReplaceInner = DONE;
+                }
 
-                tail.down = null;
+                if (tail.getCount() == 0 && tail.lvl != 0 && getRootLevel(meta)
== tail.lvl)
+                    freePage(tail.page, tail.buf, tail.io, tail.lvl, false); // Free root.
+                else if (mergeMore) {
+                    doReleaseTail(tail.down);
 
-                return false;
+                    tail.down = null;
+
+                    return false;
+                }
             }
 
             releaseTail();
@@ -1868,11 +1901,10 @@ public abstract class BPlusTree<L, T extends L> {
          * @param prnt Parent tail.
          * @param left Left child tail.
          * @param right Right child tail.
-         * @param emptyBranch If we are merging an empty branch.
          * @return {@code true} If merged successfully.
          * @throws IgniteCheckedException If failed.
          */
-        private boolean doMerge(Tail<L> prnt, Tail<L> left, Tail<L> right,
boolean emptyBranch)
+        private boolean doMerge(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();
@@ -1885,6 +1917,8 @@ public abstract class BPlusTree<L, T extends L> {
 
             int newCnt = leftCnt + rightCnt;
 
+            boolean emptyBranch = needMergeEmptyBranch == TRUE || needMergeEmptyBranch ==
READY;
+
             // Need to move down split key in inner pages. For empty branch merge parent
key will be just dropped.
             if (left.lvl != 0 && !emptyBranch)
                 newCnt++;
@@ -1911,15 +1945,14 @@ public abstract class BPlusTree<L, T extends L> {
                 leftCnt++;
             }
 
-            left.io.copyItems(right.buf, left.buf, 0, leftCnt, rightCnt, !emptyBranch ||
rightCnt != 0);
+            left.io.copyItems(right.buf, left.buf, 0, leftCnt, rightCnt, !emptyBranch);
             left.io.setForward(left.buf, right.io.getForward(right.buf));
 
             // Fix index for the right move: remove last item.
-            // For the empty branch we always remove the last item, because we always drop
right child after merge.
             int prntIdx = prnt.idx == prntCnt ? prntCnt - 1 : prnt.idx;
 
-            // Remove split key from parent. Index -1 means that it is not actually our parent
and we should not remove.
-            if (prntIdx != -1)
+            // Remove split key from parent. If we ar emerging empty branch then remove only
on the top iteration.
+            if (needMergeEmptyBranch != READY)
                 doRemove(prnt.io, prnt.buf, prntCnt, prntIdx);
 
             // Forward page is now empty and has no links, can free and release it right
away.
@@ -1972,26 +2005,34 @@ public abstract class BPlusTree<L, T extends L> {
         }
 
         /**
+         * @param emptyBranchMerged If empty branch was merged.
          * @throws IgniteCheckedException If failed.
          */
-        private void replaceInner() throws IgniteCheckedException {
+        private void replaceInner(boolean emptyBranchMerged) throws IgniteCheckedException
{
             assert needReplaceInner == READY: needReplaceInner;
-            assert tail.lvl > 0;
-            assert innerIdx >= 0;
+            assert tail.lvl > 0: "leaf";
+            assert innerIdx >= 0: innerIdx;
 
             Tail<L> leaf = getTail(0);
             Tail<L> inner = tail;
 
             assert inner.type == Tail.EXACT: inner.type;
-            assert innerIdx < inner.getCount();
 
-            int cnt = leaf.getCount();
+            int innerCnt = inner.getCount();
+            int leafCnt = leaf.getCount();
 
-            assert cnt > 0: cnt; // Leaf must be merged at this point already if it was
empty.
+            assert leafCnt > 0: leafCnt; // Leaf must be merged at this point already
if it was empty.
+
+            if (innerIdx == innerCnt) {
+                if (emptyBranchMerged)
+                    return; // Our inner key was dropped.
+
+                throw new IllegalStateException();
+            }
 
             if (innerIdx < inner.getCount()) {
                 // Update inner key with the new biggest key of left subtree.
-                inner.io.store(inner.buf, innerIdx, leaf.io, leaf.buf, cnt - 1);
+                inner.io.store(inner.buf, innerIdx, leaf.io, leaf.buf, leafCnt - 1);
                 leaf.io.setRemoveId(leaf.buf, globalRmvId.get());
             }
             else {
@@ -2003,11 +2044,10 @@ public abstract class BPlusTree<L, T extends L> {
 
         /**
          * @param prnt Parent for merge.
-         * @param emptyBranch If we are merging an empty branch.
          * @return {@code true} If merged, {@code false} if not (because of insufficient
space or empty parent).
          * @throws IgniteCheckedException If failed.
          */
-        private boolean merge(Tail<L> prnt, boolean emptyBranch) throws IgniteCheckedException
{
+        private boolean merge(Tail<L> prnt) throws IgniteCheckedException {
             if (prnt.getCount() == 0)
                 return false; // Parent is an empty routing page, child forward page will
have another parent.
 
@@ -2026,7 +2066,7 @@ public abstract class BPlusTree<L, T extends L> {
 
             assert right.io == left.io: "must always be the same"; // Otherwise can be not
compatible.
 
-            if (!doMerge(prnt, left, right, emptyBranch))
+            if (!doMerge(prnt, left, right))
                 return false;
 
             // left from BACK becomes EXACT.
@@ -2057,6 +2097,12 @@ public abstract class BPlusTree<L, T extends L> {
          * Release pages for all locked levels at the tail.
          */
         private void releaseTail() {
+//            U.dumpStack("releaseTail");
+//            X.println("------>");
+//            for (Tail<L> t = tail; t != null; t = t.down)
+//                X.println("" + t);
+//            X.println("------<");
+
             doReleaseTail(tail);
 
             tail = null;
@@ -2236,7 +2282,7 @@ public abstract class BPlusTree<L, T extends L> {
 
         /** {@inheritDoc} */
         @Override public String toString() {
-            return S.toString(Tail.class, this, "pageId", page.id(), "cnt", getCount());
+            return S.toString(Tail.class, this, "pageId", page.id(), "cnt", getCount(), "lvl",
lvl, "sibling", sibling);
         }
     }
 

http://git-wip-us.apache.org/repos/asf/ignite/blob/892f1f51/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 de2ca10..54accf5 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
@@ -27,16 +27,13 @@ import org.apache.ignite.internal.pagemem.FullPageId;
 import org.apache.ignite.internal.pagemem.PageIdAllocator;
 import org.apache.ignite.internal.pagemem.PageMemory;
 import org.apache.ignite.internal.pagemem.impl.PageMemoryImpl;
-import org.apache.ignite.internal.processors.cache.database.MetaStore;
 import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree;
 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.reuse.ReuseList;
 import org.apache.ignite.internal.util.lang.GridCursor;
-import org.apache.ignite.internal.util.typedef.T2;
 import org.apache.ignite.internal.util.typedef.X;
-import org.apache.ignite.lang.IgniteBiTuple;
 import org.apache.ignite.testframework.junits.common.GridCommonAbstractTest;
 
 /**
@@ -95,12 +92,13 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest {
 
         pageMem.start();
 
-        reuseList = new ReuseList(CACHE_ID, pageMem, 2, new MetaStore() {
-            @Override public IgniteBiTuple<FullPageId,Boolean> getOrAllocateForIndex(int
cacheId, String idxName)
-                throws IgniteCheckedException {
-                return new T2<>(allocatePage(), true);
-            }
-        });
+        reuseList = null;
+//            new ReuseList(CACHE_ID, pageMem, 2, new MetaStore() {
+//            @Override public IgniteBiTuple<FullPageId,Boolean> getOrAllocateForIndex(int
cacheId, String idxName)
+//                throws IgniteCheckedException {
+//                return new T2<>(allocatePage(), true);
+//            }
+//        });
     }
 
     /** {@inheritDoc} */


Mime
View raw message