ignite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From se...@apache.org
Subject [8/9] ignite git commit: ignite-4652 - refactor b+tree for invoke
Date Sun, 05 Feb 2017 19:45:10 GMT
ignite-4652 - refactor b+tree for invoke


Project: http://git-wip-us.apache.org/repos/asf/ignite/repo
Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/057617c2
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/057617c2
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/057617c2

Branch: refs/heads/ignite-4652
Commit: 057617c23e5f235830dc0c14f9609082c54b85b1
Parents: 49787d7
Author: Sergi <sergi.vladykin@gmail.com>
Authored: Sat Feb 4 14:27:06 2017 +0300
Committer: Sergi <sergi.vladykin@gmail.com>
Committed: Sat Feb 4 14:27:06 2017 +0300

----------------------------------------------------------------------
 .../cache/database/tree/BPlusTree.java          | 127 ++++++++++++-------
 .../apache/ignite/internal/util/IgniteTree.java |   2 +-
 .../query/h2/opt/GridH2TreeIndex.java           |   2 +-
 3 files changed, 84 insertions(+), 47 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/ignite/blob/057617c2/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 423acf2..a1860f0 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
@@ -78,6 +78,8 @@ import static org.apache.ignite.internal.processors.cache.database.tree.util.Pag
 import static org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler.isWalDeltaRecordNeeded;
 import static org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler.readPage;
 import static org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler.writePage;
+import static org.apache.ignite.internal.util.IgniteTree.OperationType.REMOVE;
+import static org.apache.ignite.internal.util.IgniteTree.OperationType.UPDATE;
 
 /**
  * Abstract B+Tree.
@@ -224,9 +226,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
             long res = doAskNeighbor(io, pageAddr, back);
 
             if (back) {
-                assert g.getClass() == Remove.class;
+                assert g.getClass() == Invoke.class;
 
-                if (io.getForward(pageAddr) != g.backId) // See how g.backId is setup in
removeDown for this check.
+                if (io.getForward(pageAddr) != g.backId) // See how g.backId is setup in
invokeDown for this check.
                     return RETRY;
 
                 g.backId = res;
@@ -418,14 +420,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
     };
 
     /** */
-    private final GetPageHandler<Remove> rmvFromLeaf = new RemoveFromLeaf();
+    private final GetPageHandler<Invoke> rmvFromLeaf = new RemoveFromLeaf();
 
     /**
      *
      */
-    private class RemoveFromLeaf extends GetPageHandler<Remove> {
+    private class RemoveFromLeaf extends GetPageHandler<Invoke> {
         /** {@inheritDoc} */
-        @Override public Result run0(Page leaf, long pageAddr, BPlusIO<L> io, Remove
r, int lvl)
+        @Override public Result run0(Page leaf, long pageAddr, BPlusIO<L> io, Invoke
r, int lvl)
             throws IgniteCheckedException {
             assert lvl == 0 : lvl; // Leaf.
 
@@ -496,14 +498,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
     };
 
     /** */
-    private final GetPageHandler<Remove> lockBackAndRmvFromLeaf = new LockBackAndRmvFromLeaf();
+    private final GetPageHandler<Invoke> lockBackAndRmvFromLeaf = new LockBackAndRmvFromLeaf();
 
     /**
      *
      */
-    private class LockBackAndRmvFromLeaf extends GetPageHandler<Remove> {
+    private class LockBackAndRmvFromLeaf extends GetPageHandler<Invoke> {
         /** {@inheritDoc} */
-        @Override protected Result run0(Page back, long pageAddr, BPlusIO<L> io, Remove
r, int lvl)
+        @Override protected Result run0(Page back, long pageAddr, BPlusIO<L> io, Invoke
r, int lvl)
             throws IgniteCheckedException {
             // Check that we have consistent view of the world.
             if (io.getForward(pageAddr) != r.pageId)
@@ -521,14 +523,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
     };
 
     /** */
-    private final GetPageHandler<Remove> lockBackAndTail = new LockBackAndTail();
+    private final GetPageHandler<Invoke> lockBackAndTail = new LockBackAndTail();
 
     /**
      *
      */
-    private class LockBackAndTail extends GetPageHandler<Remove> {
+    private class LockBackAndTail extends GetPageHandler<Invoke> {
         /** {@inheritDoc} */
-        @Override public Result run0(Page back, long pageAddr, BPlusIO<L> io, Remove
r, int lvl)
+        @Override public Result run0(Page back, long pageAddr, BPlusIO<L> io, Invoke
r, int lvl)
             throws IgniteCheckedException {
             // Check that we have consistent view of the world.
             if (io.getForward(pageAddr) != r.pageId)
@@ -545,14 +547,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
     };
 
     /** */
-    private final GetPageHandler<Remove> lockTailForward = new LockTailForward();
+    private final GetPageHandler<Invoke> lockTailForward = new LockTailForward();
 
     /**
      *
      */
-    private class LockTailForward extends GetPageHandler<Remove> {
+    private class LockTailForward extends GetPageHandler<Invoke> {
         /** {@inheritDoc} */
-        @Override protected Result run0(Page page, long pageAddr, BPlusIO<L> io, Remove
r, int lvl)
+        @Override protected Result run0(Page page, long pageAddr, BPlusIO<L> io, Invoke
r, int lvl)
             throws IgniteCheckedException {
             r.addTail(page, pageAddr, io, lvl, Tail.FORWARD);
 
@@ -561,14 +563,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
     };
 
     /** */
-    private final GetPageHandler<Remove> lockTail = new LockTail();
+    private final GetPageHandler<Invoke> lockTail = new LockTail();
 
     /**
      *
      */
-    private class LockTail extends GetPageHandler<Remove> {
+    private class LockTail extends GetPageHandler<Invoke> {
         /** {@inheritDoc} */
-        @Override public Result run0(Page page, long pageAddr, BPlusIO<L> io, Remove
r, int lvl)
+        @Override public Result run0(Page page, long pageAddr, BPlusIO<L> io, Invoke
r, int lvl)
             throws IgniteCheckedException {
             assert lvl > 0 : lvl; // We are not at the bottom.
 
@@ -1424,15 +1426,36 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
      * @throws IgniteCheckedException If failed.
      */
     private T doRemove(L row, boolean ceil, boolean needOld) throws IgniteCheckedException
{
+        return doInvoke(row, ceil, needOld, null);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override public void invoke(L key, InvokeClosure<T> c) throws IgniteCheckedException
{
+        assert c != null;
+
+        doInvoke(key, false, false, c);
+    }
+
+    /**
+     * @param row Lookup row.
+     * @param ceil If we can remove ceil row when we can not find exact.
+     * @param needOld {@code True} if need return removed row.
+     * @param c Invoke closure or {@code null} if it is just a plain remove operation.
+     * @return Removed row.
+     * @throws IgniteCheckedException If failed.
+     */
+    private T doInvoke(L row, boolean ceil, boolean needOld, InvokeClosure<T> c) throws
IgniteCheckedException {
         checkDestroyed();
 
-        Remove r = new Remove(row, ceil, needOld);
+        Invoke r = new Invoke(row, ceil, needOld, c);
 
         try {
             for (;;) {
                 r.init();
 
-                switch (removeDown(r, r.rootId, 0L, 0L, r.rootLvl)) {
+                switch (invokeDown(r, r.rootId, 0L, 0L, r.rootLvl)) {
                     case RETRY:
                     case RETRY_ROOT:
                         checkInterrupted();
@@ -1445,11 +1468,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
 
                             // If not found, then the tree grew beyond our call stack ->
retry from the actual root.
                             if (res == RETRY || res == NOT_FOUND) {
-                                int root = getRootLevel();
-
-                                boolean checkRes = r.checkTailLevel(root);
-
-                                assert checkRes : "tail=" + r.tail + ", root=" + root + ",
res=" + res;
+                                assert r.checkTailLevel(getRootLevel()) : "tail=" + r.tail
+ ", res=" + res;
 
                                 checkInterrupted();
 
@@ -1461,7 +1480,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
 
                         assert r.isFinished();
 
-                        return r.rmvd;
+                        return r.oldRow;
                 }
             }
         }
@@ -1490,7 +1509,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
      * @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)
+    private Result invokeDown(final Invoke r, final long pageId, final long backId, final
long fwdId, final int lvl)
         throws IgniteCheckedException {
         assert lvl >= 0 : lvl;
 
@@ -1525,7 +1544,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
 
                         // Intentional fallthrough.
                     case GO_DOWN:
-                        res = removeDown(r, r.pageId, r.backId, r.fwdId, lvl - 1);
+                        res = invokeDown(r, r.pageId, r.backId, r.fwdId, lvl - 1);
 
                         if (res == RETRY) {
                             checkInterrupted();
@@ -1546,7 +1565,10 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
                         // We are at the bottom.
                         assert lvl == 0 : lvl;
 
-                        if (!r.ceil) {
+                        if (r.opType == UPDATE) {
+                            // TODO insert
+                        }
+                        else if (!r.ceil) {
                             r.finish();
 
                             return res;
@@ -1669,13 +1691,6 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
     /**
      * {@inheritDoc}
      */
-    @Override public void invoke(L key, InvokeClosure<L> c) throws IgniteCheckedException
{
-        throw new UnsupportedOperationException();
-    }
-
-    /**
-     * {@inheritDoc}
-     */
     @Override public final T put(T row) throws IgniteCheckedException {
         return put(row, true);
     }
@@ -2466,7 +2481,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
     /**
      * Remove operation.
      */
-    private final class Remove extends Get implements ReuseBag {
+    private final class Invoke extends Get implements ReuseBag {
         /** */
         private boolean ceil;
 
@@ -2479,8 +2494,8 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
         /** */
         Bool needMergeEmptyBranch = FALSE;
 
-        /** Removed row. */
-        private T rmvd;
+        /** Updated or removed row. */
+        private T oldRow;
 
         /** Current page. */
         private Page page;
@@ -2491,28 +2506,39 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
         /** */
         private final boolean needOld;
 
+        /** */
+        private final InvokeClosure<T> c;
+
+        /** */
+        private OperationType opType;
+
         /**
          * @param row Row.
          * @param ceil If we can remove ceil row when we can not find exact.
          * @param needOld {@code True} If need return old value.
+         * @param c Invoke closure or {@code null} if it is just a plain remove operation.
          */
-        private Remove(L row, boolean ceil, boolean needOld) {
+        private Invoke(L row, boolean ceil, boolean needOld, InvokeClosure<T> c) {
             super(row);
 
             this.ceil = ceil;
             this.needOld = needOld;
+            this.c = c;
+
+            if (c == null)
+                opType = REMOVE;
         }
 
         /** {@inheritDoc} */
         @SuppressWarnings("unchecked")
         @Override public long pollFreePage() {
             if (freePages == null)
-                return 0;
+                return 0L;
 
             if (freePages.getClass() == GridLongList.class) {
                 GridLongList list = ((GridLongList)freePages);
 
-                return list.isEmpty() ? 0 : list.remove();
+                return list.isEmpty() ? 0L : list.remove();
             }
 
             long res = (long)freePages;
@@ -2525,7 +2551,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
         /** {@inheritDoc} */
         @SuppressWarnings("unchecked")
         @Override public void addFreePage(long pageId) {
-            assert pageId != 0;
+            assert pageId != 0L;
 
             if (freePages == null)
                 freePages = pageId;
@@ -2546,16 +2572,27 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
         }
 
         /** {@inheritDoc} */
-        @Override boolean notFound(BPlusIO<L> io, long pageAddr, int idx, int lvl)
{
+        @Override boolean notFound(BPlusIO<L> io, long pageAddr, int idx, int lvl)
throws IgniteCheckedException {
             if (lvl == 0) {
                 assert tail == null;
 
+                if (c != null)
+                    opType = c.call(null);
+
                 return true;
             }
 
             return false;
         }
 
+        /** {@inheritDoc} */
+        @Override boolean found(BPlusIO<L> io, long pageAddr, int idx, int lvl) throws
IgniteCheckedException {
+            if (lvl == 0 && c != null)
+                opType = c.call(getRow(io, pageAddr, idx));
+
+            return super.found(io, pageAddr, idx, lvl);
+        }
+
         /**
          * Finish the operation.
          */
@@ -2644,7 +2681,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
          * @return {@code true} If already removed from leaf.
          */
         private boolean isRemoved() {
-            return rmvd != null;
+            return oldRow != null;
         }
 
         /**
@@ -2920,7 +2957,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure
implements
             assert !isRemoved(): "already removed";
 
             // Detach the row.
-            rmvd = needOld ? getRow(io, pageAddr, idx) : (T)Boolean.TRUE;
+            oldRow = needOld ? getRow(io, pageAddr, idx) : (T)Boolean.TRUE;
 
             doRemove(page, io, pageAddr, cnt, idx);
 

http://git-wip-us.apache.org/repos/asf/ignite/blob/057617c2/modules/core/src/main/java/org/apache/ignite/internal/util/IgniteTree.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/IgniteTree.java b/modules/core/src/main/java/org/apache/ignite/internal/util/IgniteTree.java
index faf4034..7968361 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/util/IgniteTree.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/util/IgniteTree.java
@@ -39,7 +39,7 @@ public interface IgniteTree<L, T> {
      * @param c Closure.
      * @throws IgniteCheckedException If failed.
      */
-    public void invoke(L key, InvokeClosure<L> c) throws IgniteCheckedException;
+    public void invoke(L key, InvokeClosure<T> c) throws IgniteCheckedException;
 
     /**
      * Returns the value to which the specified key is mapped, or {@code null} if this tree
contains no mapping for the

http://git-wip-us.apache.org/repos/asf/ignite/blob/057617c2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2TreeIndex.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2TreeIndex.java
b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2TreeIndex.java
index 2b47733..68d3686 100644
--- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2TreeIndex.java
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2TreeIndex.java
@@ -501,7 +501,7 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS
         /**
          * {@inheritDoc}
          */
-        @Override public void invoke(GridSearchRowPointer key, InvokeClosure<GridSearchRowPointer>
c) {
+        @Override public void invoke(GridSearchRowPointer key, InvokeClosure<GridH2Row>
c) {
             throw new UnsupportedOperationException();
         }
 


Mime
View raw message