svn commit: r1099724 - in /cassandra/branches/cassandra-0.8: CHANGES.txt src/java/org/apache/cassandra/utils/MerkleTree.java

[slebresne]

Author: slebresne
Date: Thu May  5 08:52:16 2011
New Revision: 1099724

URL: http://svn.apache.org/viewvc?rev=1099724&view=rev
Log:
Fix merkle tree splitting exiting early
patch by slebresne; reviewed by stuhood for CASSANDRA-2605

Modified:
    cassandra/branches/cassandra-0.8/CHANGES.txt
    
cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/utils/MerkleTree.java

Modified: cassandra/branches/cassandra-0.8/CHANGES.txt
URL: 
http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.8/CHANGES.txt?rev=1099724&r1=1099723&r2=1099724&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.8/CHANGES.txt (original)
+++ cassandra/branches/cassandra-0.8/CHANGES.txt Thu May  5 08:52:16 2011
@@ -2,6 +2,7 @@
  * faster flushes and compaction from fixing excessively pessimistic 
    rebuffering in BRAF (CASSANDRA-2581)
  * fix returning null column values in the python cql driver (CASSANDRA-2593)
+ * fix merkle tree splitting exiting early (CASSANDRA-2605)
  
 
 0.8.0-beta2

Modified: 
cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/utils/MerkleTree.java
URL: 
http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/utils/MerkleTree.java?rev=1099724&r1=1099723&r2=1099724&view=diff
==============================================================================
--- 
cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/utils/MerkleTree.java
 (original)
+++ 
cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/utils/MerkleTree.java
 Thu May  5 08:52:16 2011
@@ -445,9 +445,15 @@ public class MerkleTree implements Seria
 
         if (hashable instanceof Leaf)
         {
+            Token midpoint = partitioner.midpoint(pleft, pright);
+
+            // We should not create a non-sensical range where start and end 
are the same token (this is non-sensical because range are
+            // start exclusive). Note that we shouldn't hit that unless the 
full range is very small or we are fairly deep
+            if (midpoint.equals(pleft) || midpoint.equals(pright))
+                throw new StopRecursion.TooDeep();
+
             // split
             size++;
-            Token midpoint = partitioner.midpoint(pleft, pright);
             return new Inner(midpoint, new Leaf(), new Leaf());
         }
         // else: node.
@@ -455,12 +461,6 @@ public class MerkleTree implements Seria
         // recurse on the matching child
         Inner node = (Inner)hashable;
 
-        // FIXME: we are not really 'TooDeep', however we cannot say that the
-        // split was successfull otherwise we could have a chance of infinite
-        // loop given how we split.
-        if (t.equals(node.token) || t.equals(pright))
-            throw new StopRecursion.TooDeep();
-
         if (Range.contains(pleft, node.token, t))
             // left child contains token
             node.lchild(splitHelper(node.lchild, pleft, node.token, 
inc(depth), t));