Repository: ignite Updated Branches: refs/heads/ignite-3477 3443c4e49 -> 79a546a97
GG-11414 Get rid of NavigableMap dependency for distributed joins Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/ef015d38 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/ef015d38 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/ef015d38 Branch: refs/heads/ignite-3477 Commit: ef015d3893026dc2e0516b65b3caf7df9eec72f1 Parents: 9d6288f Author: Sergey Sidorov <[email protected]> Authored: Mon Oct 31 19:02:13 2016 +0300 Committer: Sergey Sidorov <[email protected]> Committed: Mon Oct 31 19:02:13 2016 +0300 ---------------------------------------------------------------------- .../apache/ignite/internal/util/IgniteTree.java | 105 +++++++++++++++++++ .../offheap/unsafe/GridOffHeapSnapTreeMap.java | 50 ++++++++- .../internal/util/snaptree/SnapTreeMap.java | 49 ++++++++- .../query/h2/opt/GridH2IndexBase.java | 92 ++++++++++++---- .../query/h2/opt/GridH2TreeIndex.java | 32 +++--- 5 files changed, 290 insertions(+), 38 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/ef015d38/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 new file mode 100644 index 0000000..2c1e1af --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/util/IgniteTree.java @@ -0,0 +1,105 @@ +/* + * 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.util; + +import java.util.*; + +/** + * Interface for ignite internal tree. + */ +public interface IgniteTree<K, V> { + /** + * Associates the specified value with the specified key in this tree. + * + * @param key key with which the specified value is to be associated + * @param value value to be associated with the specified key + * @return the previous value associated with key + */ + V put(K key, V value); + + /** + * Returns the value to which the specified key is mapped, or {@code null} if this tree contains no mapping for the + * key. + * + * @param key the key whose associated value is to be returned + * @return the value to which the specified key is mapped, or {@code null} if this tree contains no mapping for the + * key + */ + V get(Object key); + + /** + * Removes the mapping for a key from this tree if it is present. + * + * @param key key whose mapping is to be removed from the tree + * @return the previous value associated with key, or null if there was no mapping for key. + */ + V remove(Object key); + + /** + * Returns the number of elements in this tree. + * + * @return the number of elements in this tree + */ + int size(); + + /** + * Returns a {@link Collection} view of the values contained in this tree. + * + * @return a collection view of the values contained in this map + */ + Collection<V> values(); + + /** + * Returns a view of the portion of this tree whose keys are less than (or equal to, if {@code inclusive} is true) + * {@code toKey}. The returned tree is backed by this tree, so changes in the returned tree are reflected in this + * tree, and vice-versa. The returned tree supports all optional tree operations that this tree supports. + * + * @param toKey high endpoint of the keys in the returned tree + * @param inclusive {@code true} if the high endpoint is to be included in the returned view + * @return a view of the portion of this tree whose keys are less than (or equal to, if {@code inclusive} is true) + * {@code toKey} + */ + IgniteTree<K, V> headTree(K toKey, boolean inclusive); + + /** + * Returns a view of the portion of this tree whose keys are greater than (or equal to, if {@code inclusive} is + * true) {@code fromKey}. The returned tree is backed by this tree, so changes in the returned tree are reflected + * in this tree, and vice-versa. The returned tree supports all optional tree operations that this tree supports. + * + * @param fromKey low endpoint of the keys in the returned tree + * @param inclusive {@code true} if the low endpoint is to be included in the returned view + * @return a view of the portion of this tree whose keys are greater than (or equal to, if {@code inclusive} is + * true) {@code fromKey} + */ + IgniteTree<K, V> tailTree(K fromKey, boolean inclusive); + + /** + * Returns a view of the portion of this tree whose keys range from {@code fromKey} to {@code toKey}. If {@code + * fromKey} and {@code toKey} are equal, the returned tree is empty unless {@code fromInclusive} and {@code + * toInclusive} are both true. The returned tree is backed by this tree, so changes in the returned tree are + * reflected in this tree, and vice-versa. The returned tree supports all optional tree operations that this tree + * supports. + * + * @param fromKey low endpoint of the keys in the returned tree + * @param fromInclusive {@code true} if the low endpoint is to be included in the returned view + * @param toKey high endpoint of the keys in the returned tree + * @param toInclusive {@code true} if the high endpoint is to be included in the returned view + * @return a view of the portion of this tree whose keys range from {@code fromKey} to {@code toKey} + */ + IgniteTree<K, V> subTree(final K fromKey, final boolean fromInclusive, final K toKey, final boolean toInclusive); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ef015d38/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 7bde651..681394f 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 @@ -55,6 +55,7 @@ import java.util.concurrent.atomic.AtomicLong; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantReadWriteLock; import org.apache.ignite.internal.processors.cache.distributed.dht.GridReservable; +import org.apache.ignite.internal.util.*; import org.apache.ignite.internal.util.typedef.internal.SB; import org.jetbrains.annotations.Nullable; import org.jsr166.ConcurrentHashMap8; @@ -106,8 +107,9 @@ import org.jsr166.ConcurrentHashMap8; * @author Nathan Bronson */ @SuppressWarnings("ALL") -public class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer,V extends GridOffHeapSmartPointer> - extends AbstractMap<K,V> implements ConcurrentNavigableMap<K, V>, Cloneable, AutoCloseable, GridReservable { +public class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer, V extends GridOffHeapSmartPointer> + extends AbstractMap<K, V> + implements ConcurrentNavigableMap<K, V>, Cloneable, AutoCloseable, GridReservable, IgniteTree<K, V> { /** This is a special value that indicates that an optimistic read failed. */ private static final GridOffHeapSmartPointer SpecialRetry = new GridOffHeapSmartPointer() { @Override public long pointer() { @@ -3820,10 +3822,32 @@ public class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer,V extends return new SubMap(this, null, null, false, null, null, false, true); } + //////////////// IgniteTree + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> headTree(final K toKey, final boolean inclusive) { + return new SubMap(this, null, null, false, toKey, comparable(toKey), inclusive, false); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> tailTree(final K fromKey, final boolean inclusive) { + return new SubMap(this, fromKey, comparable(fromKey), inclusive, null, null, false, false); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> subTree(final K fromKey, final boolean fromInclusive, final K toKey, + final boolean toInclusive) { + final Comparable<? super K> fromCmp = comparable(fromKey); + if (fromCmp.compareTo(toKey) > 0) { + throw new IllegalArgumentException(); + } + return new SubMap(this, fromKey, fromCmp, fromInclusive, toKey, comparable(toKey), toInclusive, false); + } + /** * Submap. */ - private class SubMap extends AbstractMap<K,V> implements ConcurrentNavigableMap<K,V> { + private class SubMap extends AbstractMap<K,V> implements ConcurrentNavigableMap<K,V>, IgniteTree<K, V> { /** */ private final GridOffHeapSnapTreeMap<K,V> m; @@ -4429,6 +4453,26 @@ public class GridOffHeapSnapTreeMap<K extends GridOffHeapSmartPointer,V extends @Override public NavigableSet<K> descendingKeySet() { return descendingMap().navigableKeySet(); } + + /////////// IgniteTree + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> headTree(K toKey, boolean inclusive) { + return headMap(toKey, inclusive); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> tailTree(K fromKey, boolean inclusive) { + return tailMap(fromKey, inclusive); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> subTree(final K fromKey, + final boolean fromInclusive, + final K toKey, + final boolean toInclusive) { + return subMap(fromKey, fromInclusive, toKey, toInclusive); + } } /** http://git-wip-us.apache.org/repos/asf/ignite/blob/ef015d38/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 b5c6545..064e7b0 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 @@ -35,6 +35,8 @@ package org.apache.ignite.internal.util.snaptree; +import org.apache.ignite.internal.util.*; + import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; @@ -102,7 +104,9 @@ import java.util.concurrent.ConcurrentNavigableMap; * @author Nathan Bronson */ @SuppressWarnings("ALL") -public class SnapTreeMap<K,V> extends AbstractMap<K,V> implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable { +public class SnapTreeMap<K, V> extends AbstractMap<K, V> implements ConcurrentNavigableMap<K, V>, Cloneable, + Serializable, IgniteTree<K, V> { + /** */ private static final long serialVersionUID = 0L; @@ -2341,7 +2345,30 @@ public class SnapTreeMap<K,V> extends AbstractMap<K,V> implements ConcurrentNavi return new SubMap(this, null, null, false, null, null, false, true); } - private static class SubMap<K,V> extends AbstractMap<K,V> implements ConcurrentNavigableMap<K,V>, Serializable { + //////////////// IgniteTree + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> headTree(final K toKey, final boolean inclusive) { + return new SubMap<K,V>(this, null, null, false, toKey, comparable(toKey), inclusive, false); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> tailTree(final K fromKey, final boolean inclusive) { + return new SubMap<K,V>(this, fromKey, comparable(fromKey), inclusive, null, null, false, false); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> subTree(final K fromKey, final boolean fromInclusive, final K toKey, + final boolean toInclusive) { + final Comparable<? super K> fromCmp = comparable(fromKey); + if (fromCmp.compareTo(toKey) > 0) { + throw new IllegalArgumentException(); + } + return new SubMap<K,V>(this, fromKey, fromCmp, fromInclusive, toKey, comparable(toKey), toInclusive, false); + } + + private static class SubMap<K, V> extends AbstractMap<K, V> implements ConcurrentNavigableMap<K, V>, Serializable, + IgniteTree<K, V> { /** */ private static final long serialVersionUID = 0L; @@ -2863,6 +2890,24 @@ public class SnapTreeMap<K,V> extends AbstractMap<K,V> implements ConcurrentNavi minCmp = minKey == null ? null : m.comparable(minKey); maxCmp = maxKey == null ? null : m.comparable(maxKey); } + + /////// IgniteTree + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> headTree(final K toKey, final boolean inclusive) { + return headMap(toKey, inclusive); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> tailTree(final K fromKey, final boolean inclusive) { + return tailMap(fromKey, inclusive); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<K, V> subTree(final K fromKey, final boolean fromInclusive, final K toKey, + final boolean toInclusive) { + return subMap(fromKey, fromInclusive, toKey, toInclusive); + } } //////// Serialization http://git-wip-us.apache.org/repos/asf/ignite/blob/ef015d38/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2IndexBase.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2IndexBase.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2IndexBase.java index 858dca1..032b548 100644 --- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2IndexBase.java +++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/opt/GridH2IndexBase.java @@ -17,16 +17,7 @@ package org.apache.ignite.internal.processors.query.h2.opt; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collection; -import java.util.Collections; -import java.util.Comparator; -import java.util.HashMap; -import java.util.Iterator; -import java.util.List; -import java.util.Map; -import java.util.UUID; +import java.util.*; import java.util.concurrent.BlockingQueue; import java.util.concurrent.ConcurrentNavigableMap; import java.util.concurrent.Future; @@ -52,7 +43,7 @@ import org.apache.ignite.internal.processors.query.h2.twostep.msg.GridH2RowRange import org.apache.ignite.internal.processors.query.h2.twostep.msg.GridH2RowRangeBounds; import org.apache.ignite.internal.processors.query.h2.twostep.msg.GridH2ValueMessage; import org.apache.ignite.internal.processors.query.h2.twostep.msg.GridH2ValueMessageFactory; -import org.apache.ignite.internal.util.GridSpinBusyLock; +import org.apache.ignite.internal.util.*; import org.apache.ignite.internal.util.lang.GridFilteredIterator; import org.apache.ignite.internal.util.typedef.CIX2; import org.apache.ignite.internal.util.typedef.F; @@ -465,11 +456,19 @@ public abstract class GridH2IndexBase extends BaseIndex { if (msg.bounds() != null) { // This is the first request containing all the search rows. - ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> snapshot0 = qctx.getSnapshot(idxId); + Object snapshot0 = qctx.getSnapshot(idxId); assert !msg.bounds().isEmpty() : "empty bounds"; - src = new RangeSource(msg.bounds(), snapshot0, qctx.filter()); + IgniteTree snapshotTree; + + if (snapshot0 instanceof IgniteTree) + snapshotTree = (IgniteTree)snapshot0; + else + snapshotTree = new IgniteNavigableMapTree( + (NavigableMap<GridSearchRowPointer, GridH2Row>) snapshot0); + + src = new RangeSource(msg.bounds(), snapshotTree, qctx.filter()); } else { // This is request to fetch next portion of data. @@ -1371,7 +1370,7 @@ public abstract class GridH2IndexBase extends BaseIndex { Iterator<GridH2Row> curRange = emptyIterator(); /** */ - final ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> tree; + final IgniteTree tree; /** */ final IndexingQueryFilter filter; @@ -1383,7 +1382,7 @@ public abstract class GridH2IndexBase extends BaseIndex { */ RangeSource( Iterable<GridH2RowRangeBounds> bounds, - ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> tree, + IgniteTree tree, IndexingQueryFilter filter ) { this.filter = filter; @@ -1443,7 +1442,7 @@ public abstract class GridH2IndexBase extends BaseIndex { SearchRow first = toSearchRow(bounds.first()); SearchRow last = toSearchRow(bounds.last()); - ConcurrentNavigableMap<GridSearchRowPointer,GridH2Row> t = tree != null ? tree : treeForRead(); + IgniteTree t = tree != null ? tree : treeForRead(); curRange = doFind0(t, first, true, last, filter); @@ -1462,7 +1461,7 @@ public abstract class GridH2IndexBase extends BaseIndex { /** * @return Snapshot for current thread if there is one. */ - protected ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> treeForRead() { + protected IgniteTree treeForRead() { throw new UnsupportedOperationException(); } @@ -1474,7 +1473,7 @@ public abstract class GridH2IndexBase extends BaseIndex { * @param filter Filter. * @return Iterator over rows in given range. */ - protected Iterator<GridH2Row> doFind0(ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> t, + protected Iterator<GridH2Row> doFind0(IgniteTree t, @Nullable SearchRow first, boolean includeFirst, @Nullable SearchRow last, @@ -1541,4 +1540,61 @@ public abstract class GridH2IndexBase extends BaseIndex { return fltr.apply(key, val); } } + + /** + * Adapter from {@link NavigableMap} to {@link IgniteTree}. + */ + protected static class IgniteNavigableMapTree implements IgniteTree<GridSearchRowPointer, GridH2Row> { + private NavigableMap<GridSearchRowPointer, GridH2Row> tree; + + /** + * @param map the {@link NavigableMap} which should be adapted. + */ + public IgniteNavigableMapTree(final NavigableMap<GridSearchRowPointer, GridH2Row> map) { + this.tree = map; + } + + /** {@inheritDoc} */ + @Override public GridH2Row put(final GridSearchRowPointer key, final GridH2Row value) { + return tree.put(key, value); + } + + /** {@inheritDoc} */ + @Override public GridH2Row get(final Object key) { + return tree.get(key); + } + + /** {@inheritDoc} */ + @Override public GridH2Row remove(final Object key) { + return tree.remove(key); + } + + /** {@inheritDoc} */ + @Override public int size() { + return tree.size(); + } + + /** {@inheritDoc} */ + @Override public Collection<GridH2Row> values() { + return tree.values(); + } + + /** {@inheritDoc} */ + @Override + public IgniteTree<GridSearchRowPointer, GridH2Row> headTree(GridSearchRowPointer toKey, boolean inclusive) { + return new IgniteNavigableMapTree(tree.headMap(toKey, inclusive)); + } + + /** {@inheritDoc} */ + @Override + public IgniteTree<GridSearchRowPointer, GridH2Row> tailTree(GridSearchRowPointer fromKey, boolean inclusive) { + return new IgniteNavigableMapTree(tree.tailMap(fromKey, inclusive)); + } + + /** {@inheritDoc} */ + @Override public IgniteTree<GridSearchRowPointer, GridH2Row> subTree(GridSearchRowPointer fromKey, + boolean fromInclusive, GridSearchRowPointer toKey, boolean toInclusive) { + return new IgniteNavigableMapTree(tree.subMap(fromKey, fromInclusive, toKey, toInclusive)); + } + } } \ No newline at end of file http://git-wip-us.apache.org/repos/asf/ignite/blob/ef015d38/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 c56fb94..b4cd76f 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 @@ -23,7 +23,8 @@ import java.util.List; import java.util.NavigableMap; import java.util.concurrent.ConcurrentNavigableMap; import java.util.concurrent.ConcurrentSkipListMap; -import org.apache.ignite.internal.util.GridEmptyIterator; + +import org.apache.ignite.internal.util.*; import org.apache.ignite.internal.util.offheap.unsafe.GridOffHeapSnapTreeMap; import org.apache.ignite.internal.util.offheap.unsafe.GridUnsafeGuard; import org.apache.ignite.internal.util.snaptree.SnapTreeMap; @@ -48,7 +49,7 @@ import org.jetbrains.annotations.Nullable; @SuppressWarnings("ComparatorNotSerializable") public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridSearchRowPointer> { /** */ - private final ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> tree; + private final IgniteTree<GridSearchRowPointer, GridH2Row> tree; /** */ private final boolean snapshotEnabled; @@ -91,7 +92,8 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS }; } else { - tree = new ConcurrentSkipListMap<>( + tree = new IgniteNavigableMapTree( + new ConcurrentSkipListMap<>( new Comparator<GridSearchRowPointer>() { @Override public int compare(GridSearchRowPointer o1, GridSearchRowPointer o2) { if (o1 instanceof ComparableRow) @@ -103,7 +105,7 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS return compareRows(o1, o2); } } - ); + )); } } else { @@ -148,11 +150,11 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS } /** {@inheritDoc} */ - protected final ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> treeForRead() { + protected final IgniteTree treeForRead() { if (!snapshotEnabled) return tree; - ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> res = threadLocalSnapshot(); + IgniteTree res = threadLocalSnapshot(); if (res == null) res = tree; @@ -268,14 +270,14 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS */ @SuppressWarnings("unchecked") private Iterator<GridH2Row> doFind(@Nullable SearchRow first, boolean includeFirst, @Nullable SearchRow last) { - ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> t = treeForRead(); + IgniteTree t = treeForRead(); return doFind0(t, first, includeFirst, last, threadLocalFilter()); } /** {@inheritDoc} */ @Override protected final Iterator<GridH2Row> doFind0( - ConcurrentNavigableMap<GridSearchRowPointer, GridH2Row> t, + IgniteTree t, @Nullable SearchRow first, boolean includeFirst, @Nullable SearchRow last, @@ -283,7 +285,7 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS ) { includeFirst &= first != null; - NavigableMap<GridSearchRowPointer, GridH2Row> range = subTree(t, comparable(first, includeFirst ? -1 : 1), + IgniteTree<GridSearchRowPointer, GridH2Row> range = subTree(t, comparable(first, includeFirst ? -1 : 1), comparable(last, 1)); if (range == null) @@ -310,30 +312,30 @@ public class GridH2TreeIndex extends GridH2IndexBase implements Comparator<GridS /** * Takes sup-map from given one. * - * @param map Map. + * @param tree Tree. * @param first Lower bound. * @param last Upper bound. * @return Sub-map. */ @SuppressWarnings({"IfMayBeConditional", "TypeMayBeWeakened"}) - private NavigableMap<GridSearchRowPointer, GridH2Row> subTree(NavigableMap<GridSearchRowPointer, GridH2Row> map, + private IgniteTree subTree(IgniteTree tree, @Nullable GridSearchRowPointer first, @Nullable GridSearchRowPointer last) { // We take exclusive bounds because it is possible that one search row will be equal to multiple key rows // in tree and we must return them all. if (first == null) { if (last == null) - return map; + return tree; else - return map.headMap(last, false); + return tree.headTree(last, false); } else { if (last == null) - return map.tailMap(first, false); + return tree.tailTree(first, false); else { if (compare(first, last) > 0) return null; - return map.subMap(first, false, last, false); + return tree.subTree(first, false, last, false); } } }
