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 <[email protected]> Authored: Mon Nov 21 15:13:21 2016 +0300 Committer: Sergey Sidorov <[email protected]> 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);
