You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2009/12/07 22:20:55 UTC
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/
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();
}
}