ignite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sboi...@apache.org
Subject [31/50] [abbrv] ignite git commit: ignite-db - ceiling remove
Date Tue, 19 Apr 2016 12:58:48 GMT
ignite-db - ceiling remove


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

Branch: refs/heads/ignite-db-x-10884
Commit: 08cd76a614103cbd0b331bd17c8b1f9a02cba94e
Parents: b79d594
Author: S.Vladykin <svladykin@gridgain.com>
Authored: Thu Apr 14 01:09:17 2016 +0300
Committer: S.Vladykin <svladykin@gridgain.com>
Committed: Thu Apr 14 01:09:17 2016 +0300

----------------------------------------------------------------------
 .../cache/database/tree/BPlusTree.java          | 76 +++++++++++++++-----
 1 file changed, 60 insertions(+), 16 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/ignite/blob/08cd76a6/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 33547bc..e3dec3d 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
@@ -292,8 +292,17 @@ public abstract class BPlusTree<L, T extends L> {
             int cnt = io.getCount(buf);
             int idx = findInsertionPoint(io, buf, cnt, r.row);
 
-            if (idx < 0)
-                return Remove.RETRY;
+            if (idx < 0) {
+                if (!r.ceil) // We've found exact match on search but now it's gone.
+                    return Remove.RETRY;
+
+                idx = -idx - 1;
+
+                if (idx == cnt) // We can not remove ceiling row here.
+                    return Remove.NOT_FOUND;
+
+                assert idx < cnt;
+            }
 
             r.removed = getRow(io, buf, idx);
 
@@ -798,8 +807,27 @@ public abstract class BPlusTree<L, T extends L> {
      * @return Removed row.
      * @throws IgniteCheckedException If failed.
      */
+    public T removeCeil(L row) throws IgniteCheckedException {
+        return remove(row, true);
+    }
+
+    /**
+     * @param row Lookup row.
+     * @return Removed row.
+     * @throws IgniteCheckedException If failed.
+     */
     public T remove(L row) throws IgniteCheckedException {
-        Remove r = new Remove(row);
+        return remove(row, false);
+    }
+
+    /**
+     * @param row Lookup row.
+     * @param ceil If we can remove ceil row when we can not find exact.
+     * @return Removed row.
+     * @throws IgniteCheckedException If failed.
+     */
+    public T remove(L row, boolean ceil) throws IgniteCheckedException {
+        Remove r = new Remove(row, ceil);
 
         try {
             for (;;) {
@@ -912,6 +940,18 @@ public abstract class BPlusTree<L, T extends L> {
 
                         return res;
 
+                    case Remove.NOT_FOUND:
+                        // We are at the bottom.
+                        assert lvl == 0: lvl;
+
+                        if (!r.ceil) {
+                            r.finish();
+
+                            return res;
+                        }
+
+                        // Intentional fallthrough for ceiling remove.
+
                     case Remove.FOUND:
                         // We must be at the bottom here, just need to remove row from the
current page.
                         assert lvl == 0 : lvl;
@@ -919,17 +959,15 @@ public abstract class BPlusTree<L, T extends L> {
 
                         res = removeFromLeaf(r, page, backId, fwdId);
 
-                        // Finish if we don't need to do any merges.
-                        if (res == Remove.FOUND && r.needReplaceInner == FALSE &&
r.needMerge == FALSE)
-                            r.finish();
-
-                        return res;
-
-                    case Remove.NOT_FOUND:
-                        // We are at the bottom.
-                        assert lvl == 0: lvl;
+                        if (res == Remove.NOT_FOUND) {
+                            assert r.ceil: "must be a retry if not a ceiling remove";
 
-                        r.finish();
+                            r.finish(); // TODO may be try to remove from forward
+                        }
+                        else if (res == Remove.FOUND && r.needReplaceInner == FALSE
&& r.needMerge == FALSE) {
+                            // Finish if we don't need to do any merges.
+                            r.finish();
+                        }
 
                         return res;
 
@@ -1753,6 +1791,9 @@ public abstract class BPlusTree<L, T extends L> {
      * Remove operation.
      */
     private class Remove extends Get {
+        /** */
+        boolean ceil;
+
         /** We may need to lock part of the tree branch from the bottom to up for multiple
levels. */
         Tail<L> tail;
 
@@ -1766,16 +1807,19 @@ public abstract class BPlusTree<L, T extends L> {
         T removed;
 
         /** Current page. */
-        public Page page;
+        Page page;
 
         /** */
-        public short innerIdx = Short.MIN_VALUE;
+        short innerIdx = Short.MIN_VALUE;
 
         /**
          * @param row Row.
+         * @param ceil If we can remove ceil row when we can not find exact.
          */
-        public Remove(L row) {
+        Remove(L row, boolean ceil) {
             super(row);
+
+            this.ceil = ceil;
         }
 
         /** {@inheritDoc} */


Mime
View raw message