cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject svn commit: r888140 - in /incubator/cassandra/trunk: src/java/org/apache/cassandra/dht/ src/java/org/apache/cassandra/utils/ test/unit/org/apache/cassandra/dht/
Date Mon, 07 Dec 2009 21:20:55 GMT
Author: jbellis
Date: Mon Dec  7 21:20:25 2009
New Revision: 888140

URL: http://svn.apache.org/viewvc?rev=888140&view=rev
Log:
support wrapping ranges in IPartitioner.midpoint.  patch by Stu Hood; reviewed by jbellis
for CASSANDRA-519

Modified:
    incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java
    incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java
    incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java
    incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java
    incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java
    incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/BootStrapperTest.java
    incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/CollatingOrderPreservingPartitionerTest.java
    incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/OrderPreservingPartitionerTest.java
    incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java
    incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RandomPartitionerTest.java

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java
(original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java
Mon Dec  7 21:20:25 2009
@@ -18,6 +18,7 @@
 
 package org.apache.cassandra.dht;
 
+import java.math.BigInteger;
 import java.text.Collator;
 import java.util.Arrays;
 import java.util.Comparator;
@@ -26,12 +27,15 @@
 
 import org.apache.cassandra.db.DecoratedKey;
 import org.apache.cassandra.utils.FBUtilities;
+import org.apache.cassandra.utils.Pair;
 
 public class CollatingOrderPreservingPartitioner implements IPartitioner<BytesToken>
 {
     static final Collator collator = Collator.getInstance(new Locale("en", "US"));
 
     public static final BytesToken MINIMUM = new BytesToken(new byte[0]);
+    
+    public static final BigInteger BYTE_MASK = new BigInteger("255");
 
     /**
      * Comparators for decorated keys.
@@ -63,82 +67,51 @@
         return comparator;
     }
 
+    public BytesToken midpoint(BytesToken ltoken, BytesToken rtoken)
+    {
+        int sigbytes = Math.max(ltoken.token.length, rtoken.token.length);
+        BigInteger left = bigForBytes(ltoken.token, sigbytes);
+        BigInteger right = bigForBytes(rtoken.token, sigbytes);
+
+        Pair<BigInteger,Boolean> midpair = FBUtilities.midpoint(left, right, 8*sigbytes);
+        return new BytesToken(bytesForBig(midpair.left, sigbytes, midpair.right));
+    }
+
     /**
-     * @return A new byte array that will compare (via compareByteArrays)
-     * approximately halfway between the parameters.
+     * Convert a byte array containing the most significant of 'sigbytes' bytes
+     * representing a big-endian magnitude into a BigInteger.
      */
-    private static byte[] midpoint(byte[] lbytes, byte[] rbytes)
+    private BigInteger bigForBytes(byte[] bytes, int sigbytes)
     {
-        // pad the arrays to equal length, for convenience
-        int inlength;
-        int comparison = FBUtilities.compareByteArrays(lbytes, rbytes);
-        if (comparison < 0)
+        if (bytes.length != sigbytes)
         {
-            inlength = Math.max(lbytes.length, rbytes.length);
-            if (lbytes.length < inlength)
-                lbytes = Arrays.copyOf(lbytes, inlength);
-            else if (rbytes.length < inlength)
-                rbytes = Arrays.copyOf(rbytes, inlength);
+            // append zeros
+            bytes = Arrays.copyOf(bytes, sigbytes);
         }
-        else
-        {
-            // wrapping range must involve the minimum token
-            assert Arrays.equals(MINIMUM.token, rbytes);
-
-            inlength = Math.max(lbytes.length, 1);
-            if (lbytes.length < inlength)
-                lbytes = Arrays.copyOf(lbytes, inlength);
-            rbytes = new byte[inlength];
-            Arrays.fill(rbytes, (byte)0xFF);
-        }
-
-        // if the lsbits of the two inputs are not equal we have to extend
-        // the result array to make room for a carried bit during the right shift
-        int outlength = (((int)lbytes[inlength-1] & 0x01) == ((int)rbytes[inlength-1]
& 0x01))
-                        ? inlength
-                        : inlength+1;
-        byte[] result = new byte[outlength];
-        boolean carrying = false;
+        return new BigInteger(1, bytes);
+    }
 
-        // perform the addition
-        for (int i = inlength-1; i >= 0; i--)
+    /**
+     * Convert a (positive) BigInteger into a byte array representing its magnitude.
+     * If remainder is true, an additional byte with the high order bit enabled
+     * will be added to the end of the array
+     */
+    private byte[] bytesForBig(BigInteger big, int sigbytes, boolean remainder)
+    {
+        byte[] bytes = new byte[sigbytes + (remainder ? 1 : 0)];
+        if (remainder)
         {
-            // initialize the lsbit if we're carrying
-            int sum = carrying ? 1 : 0;
-
-            // remove the sign bit, and sum left and right
-            sum += (lbytes[i] & 0xFF) + (rbytes[i] & 0xFF);
-            
-            // see if we'll need to carry
-            carrying = sum > 0xFF;
-
-            // set to the sum (truncating the msbit)
-            result[i] = (byte)sum;
+            // remaining bit is the most significant in the last byte
+            bytes[sigbytes] |= 0x80;
         }
-        // the carried bit from addition will be shifted in as the msbit
-
-        // perform the division (as a right shift)
-        for (int i = 0; i < inlength; i++)
+        // bitmask for a single byte
+        for (int i = 0; i < sigbytes; i++)
         {
-            // initialize the msbit if we're carrying
-            byte shifted = (byte)(carrying ? 0x80 : 0x00);
-
-            // check the lsbit to see if we'll need to continue carrying
-            carrying = (result[i] & 0x01) == 0x01;
-
-            // OR the right shifted value into the result byte
-            result[i] = (byte)(shifted | ((result[i] & 0xFF) >>> 1));
+            int maskpos = 8 * (sigbytes - (i + 1));
+            // apply bitmask and get byte value
+            bytes[i] = (byte)(big.and(BYTE_MASK.shiftLeft(maskpos)).shiftRight(maskpos).intValue()
& 0xFF);
         }
-
-        if (carrying)
-            // the last byte in the result array
-            result[inlength] |= 0x80;
-        return result;
-    }
-
-    public BytesToken midpoint(BytesToken ltoken, BytesToken rtoken)
-    {
-        return new BytesToken(midpoint(ltoken.token, rtoken.token));
+        return bytes;
     }
 
     public BytesToken getMinimumToken()

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java Mon Dec
 7 21:20:25 2009
@@ -56,10 +56,6 @@
     /**
      * Calculate a Token representing the approximate "middle" of the given
      * range.
-	 *
-	 * The Tokens must have been generated by previous calls to midpoint,
-	 * or be equal to this.getMinimumToken(). The range may not wrap unless it
-	 * involves this.getMinimumToken().
      *
      * @return The approximate midpoint between left and right.
      */

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java
(original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java
Mon Dec  7 21:20:25 2009
@@ -19,17 +19,22 @@
 package org.apache.cassandra.dht;
 
 import java.io.UnsupportedEncodingException;
+import java.math.BigInteger;
 import java.util.Arrays;
 import java.util.Comparator;
 import java.util.Random;
 
 import org.apache.cassandra.config.DatabaseDescriptor;
 import org.apache.cassandra.db.DecoratedKey;
+import org.apache.cassandra.utils.FBUtilities;
+import org.apache.cassandra.utils.Pair;
 
 public class OrderPreservingPartitioner implements IPartitioner<StringToken>
 {
     public static final StringToken MINIMUM = new StringToken("");
 
+    public static final BigInteger CHAR_MASK = new BigInteger("65535");
+
     /**
      * Comparators for decorated keys.
      */
@@ -61,102 +66,53 @@
         return comparator;
     }
 
-    /**
-     * Copies the given string into a char array, padding the end
-     * with empty chars up to length.
-     */
-    private static char[] getChars(String str, int length)
+    public StringToken midpoint(StringToken ltoken, StringToken rtoken)
     {
-        char[] chars;
-        if (str.length() < length)
-        {
-            chars = new char[length];
-            str.getChars(0, str.length(), chars, 0);
-        }
-        else if (str.length() == length)
-        {
-            chars = str.toCharArray();
-        }
-        else
-            throw new RuntimeException("Cannot truncate string of length " + str.length()
+ " to length " + length);
-        return chars;
+        int sigchars = Math.max(ltoken.token.length(), rtoken.token.length());
+        BigInteger left = bigForString(ltoken.token, sigchars);
+        BigInteger right = bigForString(rtoken.token, sigchars);
+
+        Pair<BigInteger,Boolean> midpair = FBUtilities.midpoint(left, right, 16*sigchars);
+        return new StringToken(stringForBig(midpair.left, sigchars, midpair.right));
     }
 
     /**
-     * @return A new String array that will compare
-     * approximately halfway between the parameters.
+     * Copies the characters of the given string into a BigInteger.
+     *
+     * TODO: Does not acknowledge any codepoints above 0xFFFF... problem?
      */
-    private static String midpoint(String left, String right)
+    private static BigInteger bigForString(String str, int sigchars)
     {
-        int inlength;
-        char[] lchars;
-        char[] rchars;
-        int comparison = left.compareTo(right);
-        if (comparison < 0)
-        {
-            inlength = Math.max(left.length(), right.length());
-            lchars = getChars(left, inlength);
-            rchars = getChars(right, inlength);
-        }
-        else
-        {
-            // wrapping range must involve the minimum token
-            assert MINIMUM.token.equals(right);
-            
-            inlength = Math.max(left.length(), 1);
-            lchars = getChars(left, inlength);
-            rchars = new char[inlength];
-            Arrays.fill(rchars, (char)0xFFFF);
-        }
-
+        assert str.length() <= sigchars;
 
-        // if the lsbits of the two inputs are not equal we have to extend
-        // the result array to make room for a carried bit during the right shift
-        int outlength = (((int)lchars[inlength-1] & 0x0001) == ((int)rchars[inlength-1]
& 0x0001))
-                        ? inlength
-                        : inlength+1;
-        char[] result = new char[outlength];
-        boolean carrying = false;
-
-        // perform the addition
-        for (int i = inlength-1; i >= 0; i--)
+        BigInteger big = BigInteger.ZERO;
+        for (int i = 0; i < str.length(); i++)
         {
-            // initialize the lsbit if we're carrying
-            int sum = carrying ? 0x0001 : 0x0000;
-
-            // remove the sign bit, and sum left and right
-            sum += (lchars[i] & 0xFFFF) + (rchars[i] & 0xFFFF);
-            
-            // see if we'll need to carry
-            carrying = sum > 0xFFFF;
-
-            // set to the sum (truncating the msbit)
-            result[i] = (char)sum;
+            int charpos = 16 * (sigchars - (i + 1));
+            BigInteger charbig = BigInteger.valueOf(str.charAt(i) & 0xFFFF);
+            big = big.or(charbig.shiftLeft(charpos));
         }
-        // the carried bit from addition will be shifted in as the msbit
-
-        // perform the division (as a right shift)
-        for (int i = 0; i < inlength; i++)
-        {
-            // initialize the msbit if we're carrying
-            char shifted = (char)(carrying ? 0x8000 : 0x0000);
-
-            // check the lsbit to see if we'll need to continue carrying
-            carrying = (result[i] & 0x0001) == 0x0001;
-
-            // OR the right shifted value into the result char
-            result[i] = (char)(shifted | ((result[i] & 0xFFFF) >>> 1));
-        }
-
-        if (carrying)
-            // the last char in the result array
-            result[inlength] |= 0x8000;
-        return new String(result);
+        return big;
     }
 
-    public StringToken midpoint(StringToken ltoken, StringToken rtoken)
+    /**
+     * Convert a (positive) BigInteger into a String.
+     * If remainder is true, an additional char with the high order bit enabled
+     * will be added to the end of the String.
+     */
+    private String stringForBig(BigInteger big, int sigchars, boolean remainder)
     {
-        return new StringToken(midpoint(ltoken.token, rtoken.token));
+        char[] chars = new char[sigchars + (remainder ? 1 : 0)];
+        if (remainder)
+            // remaining bit is the most significant in the last char
+            chars[sigchars] |= 0x8000;
+        for (int i = 0; i < sigchars; i++)
+        {
+            int maskpos = 16 * (sigchars - (i + 1));
+            // apply bitmask and get char value
+            chars[i] = (char)(big.and(CHAR_MASK.shiftLeft(maskpos)).shiftRight(maskpos).intValue()
& 0xFFFF);
+        }
+        return new String(chars);
     }
 
     public StringToken getMinimumToken()

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java Mon
Dec  7 21:20:25 2009
@@ -26,6 +26,7 @@
 import org.apache.cassandra.db.DecoratedKey;
 import org.apache.cassandra.utils.FBUtilities;
 import org.apache.cassandra.utils.GuidGenerator;
+import org.apache.cassandra.utils.Pair;
 
 /**
  * This class generates a BigIntegerToken using MD5 hash.
@@ -33,7 +34,6 @@
 public class RandomPartitioner implements IPartitioner<BigIntegerToken>
 {
     public static final BigInteger TWO = new BigInteger("2");
-    public static final BigInteger MD5_MAX = TWO.pow(127);
 
     public static final BigIntegerToken MINIMUM = new BigIntegerToken("0");
 
@@ -80,22 +80,9 @@
 
     public BigIntegerToken midpoint(BigIntegerToken ltoken, BigIntegerToken rtoken)
     {
-        BigInteger left = ltoken.token;
-        BigInteger right = rtoken.token;
-
-        BigInteger midpoint;
-        if (left.compareTo(right) < 0)
-        {
-            midpoint = left.add(right).divide(TWO);
-        }
-        else
-        {
-            // wrapping case
-            BigInteger distance = MD5_MAX.add(right).subtract(left);
-            BigInteger unchecked = distance.divide(TWO).add(left);
-            midpoint = (unchecked.compareTo(MD5_MAX) > 0) ? unchecked.subtract(MD5_MAX)
: unchecked;
-        }
-        return new BigIntegerToken(midpoint);
+        Pair<BigInteger,Boolean> midpair = FBUtilities.midpoint(ltoken.token, rtoken.token,
127);
+        // discard the remainder
+        return new BigIntegerToken(midpair.left);
     }
 
 	public BigIntegerToken getMinimumToken()

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/FBUtilities.java Mon Dec
 7 21:20:25 2009
@@ -36,6 +36,8 @@
 {
     private static Logger logger_ = Logger.getLogger(FBUtilities.class);
 
+    public static final BigInteger TWO = new BigInteger("2");
+
     private static InetAddress localInetAddress_;
 
     public static String[] strip(String string, String token)
@@ -64,7 +66,38 @@
             }
         return localInetAddress_;
     }
-    
+
+    /**
+     * Given two bit arrays represented as BigIntegers, containing the given
+     * number of significant bits, calculate a midpoint.
+     *
+     * @param left The left point.
+     * @param right The right point.
+     * @param sigbits The number of bits in the points that are significant.
+     * @return A midpoint that will compare bitwise halfway between the params, and
+     * a boolean representing whether a non-zero lsbit remainder was generated.
+     */
+    public static Pair<BigInteger,Boolean> midpoint(BigInteger left, BigInteger right,
int sigbits)
+    {
+        BigInteger midpoint;
+        boolean remainder;
+        if (left.compareTo(right) < 0)
+        {
+            BigInteger sum = left.add(right);
+            remainder = sum.testBit(0);
+            midpoint = sum.shiftRight(1);
+        }
+        else
+        {
+            BigInteger max = TWO.pow(sigbits);
+            // wrapping case
+            BigInteger distance = max.add(right).subtract(left);
+            remainder = distance.testBit(0);
+            midpoint = distance.shiftRight(1).add(left).mod(max);
+        }
+        return new Pair(midpoint, remainder);
+    }
+
     public static byte[] toByteArray(int i)
     {
         byte[] bytes = new byte[4];
@@ -141,8 +174,7 @@
     	}
     	catch (Exception e)
         {
-    		if (logger_.isDebugEnabled())
-                logger_.debug(LogUtil.throwableToString(e));
+            throw new RuntimeException(e);
     	}
     	return result;
 	}
@@ -168,7 +200,6 @@
         }
     }
 
-
     public static byte[] decompress(byte[] compressedData, int off, int len) throws IOException,
DataFormatException
     {
     	 // Create the decompressor and give it the data to compress
@@ -208,7 +239,7 @@
         return bytes;
     }
 
-    public static String bytesToHex(byte[] bytes)
+    public static String bytesToHex(byte... bytes)
     {
         StringBuilder sb = new StringBuilder();
         for (byte b : bytes)

Modified: incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/BootStrapperTest.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/BootStrapperTest.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/BootStrapperTest.java (original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/BootStrapperTest.java Mon
Dec  7 21:20:25 2009
@@ -124,9 +124,7 @@
         for (int i = 1; i <= numOldNodes; i++)
         {
             // leave .1 for myEndpoint
-            // TODO use this when #519 is fixed
-            // tmd.update(p.getRandomToken(), InetAddress.getByName("127.0.0." + (i + 1)));
-            tmd.update(p.getToken(FBUtilities.bytesToHex(FBUtilities.toByteArray(i * 13))),
InetAddress.getByName("127.0.0." + (i + 1)));
+            tmd.update(p.getRandomToken(), InetAddress.getByName("127.0.0." + (i + 1)));
         }
     }
 }
\ No newline at end of file

Modified: incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/CollatingOrderPreservingPartitionerTest.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/CollatingOrderPreservingPartitionerTest.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/CollatingOrderPreservingPartitionerTest.java
(original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/CollatingOrderPreservingPartitionerTest.java
Mon Dec  7 21:20:25 2009
@@ -24,29 +24,9 @@
 
 public class CollatingOrderPreservingPartitionerTest extends PartitionerTestCase<BytesToken>
{
     @Override
-    public IPartitioner<BytesToken> getPartitioner()
+    public void initPartitioner()
     {
-        return new CollatingOrderPreservingPartitioner();
-    }
-
-    @Override
-    public BytesToken tok(String string)
-    {
-        // we just need some kind of byte array
-        try
-        {
-            return new BytesToken(string.getBytes("US-ASCII"));
-        }
-        catch(Exception e)
-        {
-            throw new RuntimeException(e);
-        }
-    }
-
-    @Override
-    public String tos(BytesToken token)
-    {
-        return FBUtilities.bytesToHex(token.token);
+        partitioner = new CollatingOrderPreservingPartitioner();
     }
 
     /**
@@ -59,4 +39,16 @@
         BytesToken tok = new BytesToken((byte)0xFF, (byte)0xFF);
         assert tok.compareTo(factory.fromString(factory.toString(tok))) == 0;
     }
+
+    @Test
+    public void testCompare()
+    {
+        assert tok("").compareTo(tok("asdf")) < 0;
+        assert tok("asdf").compareTo(tok("")) > 0;
+        assert tok("").compareTo(tok("")) == 0;
+        assert tok("z").compareTo(tok("a")) > 0;
+        assert tok("a").compareTo(tok("z")) < 0;
+        assert tok("asdf").compareTo(tok("asdf")) == 0;
+        assert tok("asdz").compareTo(tok("asdf")) > 0;
+    }
 }

Modified: incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/OrderPreservingPartitionerTest.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/OrderPreservingPartitionerTest.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/OrderPreservingPartitionerTest.java
(original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/OrderPreservingPartitionerTest.java
Mon Dec  7 21:20:25 2009
@@ -27,20 +27,20 @@
 
 public class OrderPreservingPartitionerTest extends PartitionerTestCase<StringToken>
{
     @Override
-    public IPartitioner<StringToken> getPartitioner()
+    public void initPartitioner()
     {
-        return new OrderPreservingPartitioner();
+        partitioner = new OrderPreservingPartitioner();
     }
 
-    @Override
-    public StringToken tok(String string)
-    {
-        return new StringToken(string);
-    }
-
-    @Override
-    public String tos(StringToken token)
+    @Test
+    public void testCompare()
     {
-        return FBUtilities.bytesToHex(token.token.getBytes());
+        assert tok("").compareTo(tok("asdf")) < 0;
+        assert tok("asdf").compareTo(tok("")) > 0;
+        assert tok("").compareTo(tok("")) == 0;
+        assert tok("z").compareTo(tok("a")) > 0;
+        assert tok("a").compareTo(tok("z")) < 0;
+        assert tok("asdf").compareTo(tok("asdf")) == 0;
+        assert tok("asdz").compareTo(tok("asdf")) > 0;
     }
 }

Modified: incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java
(original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java
Mon Dec  7 21:20:25 2009
@@ -18,6 +18,8 @@
 */
 package org.apache.cassandra.dht;
 
+import java.util.Random;
+
 import static org.junit.Assert.assertEquals;
 
 import org.junit.Before;
@@ -28,37 +30,43 @@
 public abstract class PartitionerTestCase<T extends Token> {
     protected IPartitioner<T> partitioner;
 
-    public abstract IPartitioner<T> getPartitioner();
-    public abstract T tok(String string);
-    public abstract String tos(T token);
+    public abstract void initPartitioner();
 
     @Before
     public void clean()
     {
-        this.partitioner = this.getPartitioner();
+        initPartitioner();
     }
 
-    @Test
-    public void testCompare()
+    public T tok(String string)
     {
-        assert tok("").compareTo(tok("asdf")) < 0;
-        assert tok("asdf").compareTo(tok("")) > 0;
-        assert tok("").compareTo(tok("")) == 0;
-        assert tok("z").compareTo(tok("a")) > 0;
-        assert tok("a").compareTo(tok("z")) < 0;
-        assert tok("asdf").compareTo(tok("asdf")) == 0;
-        assert tok("asdz").compareTo(tok("asdf")) > 0;
+        return partitioner.getToken(string);
     }
 
+    /**
+     * Recurses randomly to the given depth a few times.
+     */
     public void assertMidpoint(T left, T right, int depth)
     {
-        T mid = this.partitioner.midpoint(left, right);
+        Random rand = new Random();
+        for (int i = 0; i < 1000; i++)
+        {
+            assertMidpoint(left, right, rand, depth);
+        }
+    }
+
+    private void assertMidpoint(T left, T right, Random rand, int depth)
+    {
+        T mid = partitioner.midpoint(left, right);
         assert new Range(left, right).contains(mid)
-                : "For " + tos(left) + "," + tos(right) + ": range did not contain mid:"
+ tos(mid);
-        if (depth > 0)
-            assertMidpoint(left, mid, depth-1);
-        if (depth > 0)
-            assertMidpoint(mid, right, depth-1);
+                : "For " + left + "," + right + ": range did not contain mid:" + mid;
+        if (depth < 1)
+            return;
+
+        if (rand.nextBoolean())
+            assertMidpoint(left, mid, rand, depth-1);
+        else
+            assertMidpoint(mid, right, rand, depth-1);
     }
 
     @Test
@@ -71,15 +79,19 @@
     @Test
     public void testMidpointMinimum()
     {
-        assertMidpoint(tok(""), tok("a"), 16);
-        assertMidpoint(tok(""), tok("aaa"), 16);
+        T mintoken = partitioner.getMinimumToken(); 
+        assert mintoken.compareTo(partitioner.midpoint(mintoken, mintoken)) != 0;
+        assertMidpoint(mintoken, tok("a"), 16);
+        assertMidpoint(mintoken, tok("aaa"), 16);
+        assertMidpoint(mintoken, mintoken, 126);
+        assertMidpoint(tok("a"), mintoken, 16);
     }
 
     @Test
     public void testMidpointWrapping()
     {
-        assertMidpoint(tok(""), tok(""), 16);
-        assertMidpoint(tok("a"), tok(""), 16);
+        assertMidpoint(tok("b"), tok("a"), 16);
+        assertMidpoint(tok("bbb"), tok("a"), 16);
     }
     
     @Test
@@ -94,14 +106,14 @@
     @Test
     public void testTokenFactoryBytes()
     {
-        Token.TokenFactory factory = this.partitioner.getTokenFactory();
+        Token.TokenFactory factory = partitioner.getTokenFactory();
         assert tok("a").compareTo(factory.fromByteArray(factory.toByteArray(tok("a")))) ==
0;
     }
     
     @Test
     public void testTokenFactoryStrings()
     {
-        Token.TokenFactory factory = this.partitioner.getTokenFactory();
+        Token.TokenFactory factory = partitioner.getTokenFactory();
         assert tok("a").compareTo(factory.fromString(factory.toString(tok("a")))) == 0;
     }
 }

Modified: incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RandomPartitionerTest.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RandomPartitionerTest.java?rev=888140&r1=888139&r2=888140&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RandomPartitionerTest.java
(original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RandomPartitionerTest.java
Mon Dec  7 21:20:25 2009
@@ -26,16 +26,10 @@
 import org.apache.cassandra.db.DecoratedKey;
 import org.junit.Test;
 
-public class RandomPartitionerTest
+public class RandomPartitionerTest extends PartitionerTestCase<BigIntegerToken>
 {
-
-    @Test
-    public void testDiskFormat()
+    public void initPartitioner()
     {
-        RandomPartitioner part = new RandomPartitioner();
-        String key = "key";
-        DecoratedKey decKey = part.decorateKey(key);
-        DecoratedKey result = part.convertFromDiskFormat(part.convertToDiskFormat(decKey));
-        assertEquals(decKey, result);
+        partitioner = new RandomPartitioner();
     }
 }



Mime
View raw message