cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From alek...@apache.org
Subject [1/2] cassandra git commit: Fix descending iteration past end of BTreeSearchIterator
Date Fri, 18 Sep 2015 21:12:48 GMT
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 <benedict@apache.org>
Authored: Thu Sep 10 19:53:37 2015 +0100
Committer: Aleksey Yeschenko <aleksey@apache.org>
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));
     }


Mime
View raw message