Repository: cassandra Updated Branches: refs/heads/trunk 375465d1c -> be8b9f299
Fix descending iteration past end of BTreeSearchIterator patch by benedict; reviewed by branimir for CASSANDRA-10301 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/aef71696 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/aef71696 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/aef71696 Branch: refs/heads/trunk Commit: aef71696e6f19d2569d310206b287f919da32b4f Parents: 959b96e Author: Benedict Elliott Smith <[email protected]> Authored: Thu Sep 10 19:53:37 2015 +0100 Committer: Aleksey Yeschenko <[email protected]> Committed: Fri Sep 18 21:47:28 2015 +0100 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../cassandra/utils/btree/BTreeSearchIterator.java | 5 ++--- .../apache/cassandra/utils/btree/TreeCursor.java | 16 +++++++--------- .../org/apache/cassandra/utils/LongBTreeTest.java | 9 ++++++--- 4 files changed, 16 insertions(+), 15 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/aef71696/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index d95d833..2c0cde2 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 3.0.0-rc1 + * Fix descending iteration past end of BTreeSearchIterator (CASSANDRA-10301) * Transfer hints to a different node on decommission (CASSANDRA-10198) * Check partition keys for CAS operations during stmt validation (CASSANDRA-10338) * Add custom query expressions to SELECT (CASSANDRA-10217) http://git-wip-us.apache.org/repos/asf/cassandra/blob/aef71696/src/java/org/apache/cassandra/utils/btree/BTreeSearchIterator.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/BTreeSearchIterator.java b/src/java/org/apache/cassandra/utils/btree/BTreeSearchIterator.java index 6d023d2..ec16a8e 100644 --- a/src/java/org/apache/cassandra/utils/btree/BTreeSearchIterator.java +++ b/src/java/org/apache/cassandra/utils/btree/BTreeSearchIterator.java @@ -102,9 +102,8 @@ public class BTreeSearchIterator<K, V> extends TreeCursor<K> implements IndexedS return null; int state = this.state; - int index = seekTo(target, forwards, (state & (ON_ITEM | BEFORE_FIRST)) != 0); - boolean found = index >= 0; - if (!found) index = -1 -index; + boolean found = seekTo(target, forwards, (state & (ON_ITEM | BEFORE_FIRST)) != 0); + int index = cur.globalIndex(); V next = null; if (state == BEFORE_FIRST && compareToFirst(index) < 0) http://git-wip-us.apache.org/repos/asf/cassandra/blob/aef71696/src/java/org/apache/cassandra/utils/btree/TreeCursor.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/TreeCursor.java b/src/java/org/apache/cassandra/utils/btree/TreeCursor.java index 164b83f..5e55698 100644 --- a/src/java/org/apache/cassandra/utils/btree/TreeCursor.java +++ b/src/java/org/apache/cassandra/utils/btree/TreeCursor.java @@ -93,9 +93,9 @@ class TreeCursor<K> extends NodeCursor<K> /** * seeks from the current position, forwards or backwards, for the provided key * while the direction could be inferred (or ignored), it is required so that (e.g.) we do not infinitely loop on bad inputs - * if there is no such key, it moves to the key that would naturally proceed it (i.e. it behaves as ceil when ascending; floor when descending) + * if there is no such key, it moves to the key that would naturally follow/succeed it (i.e. it behaves as ceil when ascending; floor when descending) */ - int seekTo(K key, boolean forwards, boolean skipOne) + boolean seekTo(K key, boolean forwards, boolean skipOne) { NodeCursor<K> cur = this.cur; @@ -114,7 +114,7 @@ class TreeCursor<K> extends NodeCursor<K> { // we moved out of the tree; return out-of-bounds this.cur = root(); - return forwards ? -1 - size(rootNode()) : -1; + return false; } if (tryOne) @@ -128,9 +128,8 @@ class TreeCursor<K> extends NodeCursor<K> if (forwards ? cmp >= 0 : cmp <= 0) { // we've either matched, or excluded the value from being present - int index = cur.globalIndex(); this.cur = cur; - return cmp == 0 ? index : -1 -index; + return cmp == 0; } } @@ -151,7 +150,7 @@ class TreeCursor<K> extends NodeCursor<K> if (cmpbound == 0) // it was an exact match, so terminate here { this.cur = cur; - return cur.globalBranchIndex(); + return true; } } @@ -168,8 +167,7 @@ class TreeCursor<K> extends NodeCursor<K> this.cur = cur; assert !cur.inChild; - int index = cur.globalIndex(); - return match ? index : -1 -index; + return match; } /** @@ -189,7 +187,7 @@ class TreeCursor<K> extends NodeCursor<K> /** * move out of a leaf node that is currently out of (its own) bounds - * @return null if we're now out-of-bounds of the whole true + * @return null if we're now out-of-bounds of the whole tree */ private <K> NodeCursor<K> moveOutOfLeaf(boolean forwards, NodeCursor<K> cur, NodeCursor<K> ifFail) { http://git-wip-us.apache.org/repos/asf/cassandra/blob/aef71696/test/burn/org/apache/cassandra/utils/LongBTreeTest.java ---------------------------------------------------------------------- diff --git a/test/burn/org/apache/cassandra/utils/LongBTreeTest.java b/test/burn/org/apache/cassandra/utils/LongBTreeTest.java index 0e8c467..5044290 100644 --- a/test/burn/org/apache/cassandra/utils/LongBTreeTest.java +++ b/test/burn/org/apache/cassandra/utils/LongBTreeTest.java @@ -569,12 +569,12 @@ public class LongBTreeTest boolean useFake = mixInNotPresentItems && rnd.nextBoolean(); final float fakeRatio = rnd.nextFloat(); List<Integer> results = new ArrayList<>(); - Long fakeLb = null, fakeUb = null; + Long fakeLb = (long) Integer.MIN_VALUE, fakeUb = null; + Integer max = null; for (Integer v : canonical) { if ( !useFake - || fakeLb == null - || (fakeUb == null ? v - 1 : fakeUb) <= fakeLb + 1 + || (fakeUb == null ? v - 1 : fakeUb) <= fakeLb + 1 || rnd.nextFloat() < fakeRatio) { // if we cannot safely construct a fake value, or our randomizer says not to, we emit the next real value @@ -593,7 +593,10 @@ public class LongBTreeTest results.add((int) mid); fakeLb = mid; } + max = v; } + if (useFake && max != null && max < Integer.MAX_VALUE) + results.add(max + 1); final float useChance = rnd.nextFloat(); return Lists.newArrayList(filter(results, (x) -> rnd.nextFloat() < useChance)); }
