You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ag...@apache.org on 2017/01/11 17:27:33 UTC
[04/22] ignite git commit: GG-11414
GG-11414
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo
Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/37eb93b2
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/37eb93b2
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/37eb93b2
Branch: refs/heads/ignite-3477
Commit: 37eb93b2d01e7199b858a5d1e006501936d54625
Parents: df7b4f6
Author: Sergey Sidorov <ss...@gridgain.com>
Authored: Mon Nov 21 15:13:21 2016 +0300
Committer: Sergey Sidorov <ss...@gridgain.com>
Committed: Mon Nov 21 15:13:21 2016 +0300
----------------------------------------------------------------------
.../cache/IgniteCacheOffheapManagerImpl.java | 2 +-
.../cache/database/tree/BPlusTree.java | 23 +++++++++---
.../offheap/unsafe/GridOffHeapSnapTreeMap.java | 4 +++
.../internal/util/snaptree/SnapTreeMap.java | 33 ++++++-----------
.../processors/database/BPlusTreeSelfTest.java | 37 ++++++++++++++++++++
.../internal/processors/query/h2/H2Cursor.java | 17 +++++++++
.../query/h2/opt/GridH2TreeIndex.java | 2 ++
7 files changed, 91 insertions(+), 27 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/ignite/blob/37eb93b2/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java
index 66896d2..861bb11 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java
@@ -897,7 +897,7 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple
/** {@inheritDoc} */
@Override public GridCursor<? extends CacheDataRow> cursor() throws IgniteCheckedException {
- return dataTree.find(null, null);
+ return dataTree.findAll();
}
/** {@inheritDoc} */
http://git-wip-us.apache.org/repos/asf/ignite/blob/37eb93b2/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 f761975..d60246e 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
@@ -753,8 +753,20 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
public GridCursor<T> find(L lower, boolean lowerInclusive,
L upper, boolean upperInclusive) throws IgniteCheckedException {
- // TODO inclusive / exclusive logic should be implemented
- return find(lower, upper);
+ if (lower == null || upper == null)
+ throw new NullPointerException();
+
+ ForwardCursor cursor = new ForwardCursor(lower, upper);
+
+ if (!lowerInclusive)
+ cursor.lowerShift = 1;
+
+ if (!upperInclusive)
+ cursor.upperShift = -1;
+
+ cursor.find();
+
+ return cursor;
}
public GridCursor<T> findAll() throws IgniteCheckedException {
@@ -3464,6 +3476,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/** */
private final L upperBound;
+ /** */
+ private int upperShift = 1; // Initially it is -1 to handle multiple equal rows.
+
/**
* @param lowerBound Lower bound.
* @param upperBound Upper bound.
@@ -3535,8 +3550,8 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Compare with the last row on the page.
int cmp = compare(io, buf, cnt - 1, upperBound);
- if (cmp > 0) {
- int idx = findInsertionPoint(io, buf, low, cnt, upperBound, 1);
+ if (cmp > 0 || (cmp == 0 && upperShift == -1)) {
+ int idx = findInsertionPoint(io, buf, low, cnt, upperBound, upperShift);
assert idx < 0;
http://git-wip-us.apache.org/repos/asf/ignite/blob/37eb93b2/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java b/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java
index eb09af5..ab175de 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java
@@ -3845,6 +3845,8 @@ public class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer, V extends
@Override public GridCursor<V> find(K lower, boolean lowerInclusive, K upper, boolean upperInclusive)
throws IgniteCheckedException {
+ if (lower == null || upper == null)
+ throw new NullPointerException();
final Comparable<? super K> fromCmp = comparable(lower);
@@ -4495,6 +4497,8 @@ public class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer, V extends
@Override public GridCursor<V> find(K lower, boolean lowerInclusive, K upper, boolean upperInclusive)
throws IgniteCheckedException {
+ if (lower == null || upper == null)
+ throw new NullPointerException();
SubMap subMap = subMap(lower, lowerInclusive, upper, upperInclusive);
http://git-wip-us.apache.org/repos/asf/ignite/blob/37eb93b2/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java b/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java
index 8bd5f59..79c110d 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/util/snaptree/SnapTreeMap.java
@@ -2350,18 +2350,12 @@ public class SnapTreeMap<K, V> extends AbstractMap<K, V> implements ConcurrentNa
//////////////// IgniteTree
@Override public GridCursor<V> find(K lower, boolean lowerInclusive,
- K upper, boolean upperInclusive) throws IgniteCheckedException {
- if (lower == null)
- if (upper == null) // all
- return new GridCursorIteratorWrapper<>(values().iterator());
- else // head
- return new GridCursorIteratorWrapper<>(headMap(upper, upperInclusive).values().iterator());
- else
- if (upper == null) // tail
- return new GridCursorIteratorWrapper<>(tailMap(lower, lowerInclusive).values().iterator());
- else // interval
- return new GridCursorIteratorWrapper<>(subMap(lower, lowerInclusive, upper, upperInclusive)
- .values().iterator());
+ K upper, boolean upperInclusive) throws IgniteCheckedException {
+ if (lower == null || upper == null)
+ throw new NullPointerException();
+
+ return new GridCursorIteratorWrapper<>(subMap(lower, lowerInclusive, upper, upperInclusive)
+ .values().iterator());
}
public GridCursor<V> find(K lower, K upper) throws IgniteCheckedException {
@@ -2921,16 +2915,11 @@ public class SnapTreeMap<K, V> extends AbstractMap<K, V> implements ConcurrentNa
@Override public GridCursor<V> find(K lower, boolean lowerInclusive,
K upper, boolean upperInclusive) throws IgniteCheckedException {
- if (lower == null)
- if (upper == null) // all
- return new GridCursorIteratorWrapper<>(values().iterator());
- else // head
- return new GridCursorIteratorWrapper<>(headMap(upper, upperInclusive).values().iterator());
- else
- if (upper == null) // tail
- return new GridCursorIteratorWrapper<>(tailMap(lower, lowerInclusive).values().iterator());
- else // interval
- return new GridCursorIteratorWrapper<>(subMap(lower, lowerInclusive, upper, upperInclusive).values().iterator());
+ if (lower == null || upper == null)
+ throw new NullPointerException();
+
+ return new GridCursorIteratorWrapper<>(subMap(lower, lowerInclusive, upper, upperInclusive)
+ .values().iterator());
}
public GridCursor<V> find(K lower, K upper) throws IgniteCheckedException {
http://git-wip-us.apache.org/repos/asf/ignite/blob/37eb93b2/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java
----------------------------------------------------------------------
diff --git a/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java b/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java
index 4bc39ea..88edaf1 100644
--- a/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java
+++ b/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java
@@ -173,6 +173,43 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest {
/**
* @throws IgniteCheckedException If failed.
*/
+ public void testFind() throws IgniteCheckedException {
+ TestTree tree = createTestTree(true);
+ TreeMap<Long, Long> map = new TreeMap<>();
+
+ long size = CNT * CNT;
+
+ for (long i = 1; i <= size; i++) {
+ tree.put(i);
+ map.put(i, i);
+ }
+
+ checkCursor(tree.findAll(), map.values().iterator());
+ checkCursor(tree.find(10L, 70L), map.subMap(10L, true, 70L, true).values().iterator());
+ checkCursor(tree.find(10L, true, 50L, false), map.subMap(10L, true, 50L, false).values().iterator());
+ checkCursor(tree.find(10L, false, 50L, true), map.subMap(10L, false, 50L, true).values().iterator());
+ checkCursor(tree.find(10L, false, 50L, false), map.subMap(10L, false, 50L, false).values().iterator());
+ checkCursor(tree.find(10L, true, 50L, true), map.subMap(10L, true, 50L, true).values().iterator());
+ }
+
+ /**
+ * @param cursor cursor to check.
+ * @param iterator iterator with expected result.
+ * @throws IgniteCheckedException If failed
+ */
+ private void checkCursor(GridCursor<Long> cursor, Iterator<Long> iterator) throws IgniteCheckedException {
+ while (cursor.next()) {
+ assertTrue(iterator.hasNext());
+
+ assertEquals(iterator.next(), cursor.get());
+ }
+
+ assertFalse(iterator.hasNext());
+ }
+
+ /**
+ * @throws IgniteCheckedException If failed.
+ */
public void testPutRemove_1_20_mm_1() throws IgniteCheckedException {
MAX_PER_PAGE = 1;
CNT = 20;
http://git-wip-us.apache.org/repos/asf/ignite/blob/37eb93b2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/H2Cursor.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/H2Cursor.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/H2Cursor.java
index d3b6265..95114a2 100644
--- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/H2Cursor.java
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/H2Cursor.java
@@ -1,3 +1,20 @@
+/*
+ * 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.query.h2;
import org.apache.ignite.*;
http://git-wip-us.apache.org/repos/asf/ignite/blob/37eb93b2/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 e03c1a1..f442e4e 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
@@ -527,6 +527,8 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS
@Override public GridCursor<GridH2Row> find(GridSearchRowPointer lower, boolean lowerInclusive,
GridSearchRowPointer upper, boolean upperInclusive)
throws IgniteCheckedException {
+ if (lower == null || upper == null)
+ throw new NullPointerException();
NavigableMap<GridSearchRowPointer, GridH2Row> subMap =
tree.subMap(lower, lowerInclusive, upper, upperInclusive);