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 2011/04/10 01:46:28 UTC
svn commit: r1090711 - in /cassandra/trunk:
src/java/org/apache/cassandra/db/marshal/UUIDType.java
test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java
Author: jbellis
Date: Sat Apr 9 23:46:28 2011
New Revision: 1090711
URL: http://svn.apache.org/viewvc?rev=1090711&view=rev
Log:
Add unified UUIDType
patch by Ed Anuff; reviewed by jbellis for CASSANDRA-2233
Added:
cassandra/trunk/src/java/org/apache/cassandra/db/marshal/UUIDType.java
cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java
Added: cassandra/trunk/src/java/org/apache/cassandra/db/marshal/UUIDType.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/db/marshal/UUIDType.java?rev=1090711&view=auto
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/db/marshal/UUIDType.java (added)
+++ cassandra/trunk/src/java/org/apache/cassandra/db/marshal/UUIDType.java Sat Apr 9 23:46:28 2011
@@ -0,0 +1,205 @@
+package org.apache.cassandra.db.marshal;
+
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+import java.nio.ByteBuffer;
+import java.util.UUID;
+
+/**
+ * Compares UUIDs using the following criteria:<br>
+ * - if count of supplied bytes is less than 16, compare counts<br>
+ * - compare UUID version fields<br>
+ * - nil UUID is always lesser<br>
+ * - compare timestamps if both are time-based<br>
+ * - compare lexically, unsigned msb-to-lsb comparison<br>
+ *
+ * @author edanuff
+ * @see "com.fasterxml.uuid.UUIDComparator"
+ *
+ */
+public class UUIDType extends AbstractType<UUID>
+{
+ public static final UUIDType instance = new UUIDType();
+
+ UUIDType()
+ {
+ }
+
+ public int compare(ByteBuffer b1, ByteBuffer b2)
+ {
+
+ // Compare for length
+
+ if ((b1 == null) || (b1.remaining() < 16))
+ {
+ return ((b2 == null) || (b2.remaining() < 16)) ? 0 : -1;
+ }
+ if ((b2 == null) || (b2.remaining() < 16))
+ {
+ return 1;
+ }
+
+ int s1 = b1.arrayOffset() + b1.position();
+ byte[] o1 = b1.array();
+
+ int s2 = b2.arrayOffset() + b2.position();
+ byte[] o2 = b2.array();
+
+ if (o1.length == s1)
+ {
+ return o2.length == s2 ? 0 : -1;
+ }
+ if (o2.length == s2)
+ {
+ return 1;
+ }
+
+ // Compare versions
+
+ int v1 = (o1[s1 + 6] >> 4) & 0x0f;
+ int v2 = (o2[s2 + 6] >> 4) & 0x0f;
+
+ if (v1 != v2)
+ {
+ return v1 - v2;
+ }
+
+ // Compare timestamps for version 1
+
+ if (v1 == 1)
+ {
+ // if both time-based, compare as timestamps
+ int c = compareTimestampBytes(s1, o1, s2, o2);
+ if (c != 0)
+ {
+ return c;
+ }
+ }
+
+ // Compare the two byte arrays starting from the first
+ // byte in the sequence until an inequality is
+ // found. This should provide equivalent results
+ // to the comparison performed by the RFC 4122
+ // Appendix A - Sample Implementation.
+ // Note: java.util.UUID.compareTo is not a lexical
+ // comparison
+
+ for (int i = 0; i < 16; i++)
+ {
+ int c = ((o1[s1 + i]) & 0xFF) - ((o2[s2 + i]) & 0xFF);
+ if (c != 0)
+ {
+ return c;
+ }
+ }
+
+ return 0;
+ }
+
+ private static int compareTimestampBytes(int s1, byte[] o1, int s2,
+ byte[] o2)
+ {
+ int d = (o1[s1 + 6] & 0xF) - (o2[s2 + 6] & 0xF);
+ if (d != 0)
+ {
+ return d;
+ }
+ d = (o1[s1 + 7] & 0xFF) - (o2[s2 + 7] & 0xFF);
+ if (d != 0)
+ {
+ return d;
+ }
+ d = (o1[s1 + 4] & 0xFF) - (o2[s2 + 4] & 0xFF);
+ if (d != 0)
+ {
+ return d;
+ }
+ d = (o1[s1 + 5] & 0xFF) - (o2[s2 + 5] & 0xFF);
+ if (d != 0)
+ {
+ return d;
+ }
+ d = (o1[s1 + 0] & 0xFF) - (o2[s2 + 0] & 0xFF);
+ if (d != 0)
+ {
+ return d;
+ }
+ d = (o1[s1 + 1] & 0xFF) - (o2[s2 + 1] & 0xFF);
+ if (d != 0)
+ {
+ return d;
+ }
+ d = (o1[s1 + 2] & 0xFF) - (o2[s2 + 2] & 0xFF);
+ if (d != 0)
+ {
+ return d;
+ }
+ return (o1[s1 + 3] & 0xFF) - (o2[s2 + 3] & 0xFF);
+ }
+
+ public UUID compose(ByteBuffer bytes)
+ {
+
+ bytes = bytes.slice();
+ if (bytes.remaining() < 16)
+ return new UUID(0, 0);
+ return new UUID(bytes.getLong(), bytes.getLong());
+ }
+
+ public String toString(UUID uuid)
+ {
+ return uuid.toString();
+ }
+
+ public Class<UUID> getType()
+ {
+ return UUID.class;
+ }
+
+ public void validate(ByteBuffer bytes)
+ {
+ if ((bytes.remaining() != 0) && (bytes.remaining() != 16))
+ {
+ throw new MarshalException("UUIDs must be exactly 16 bytes");
+ }
+ }
+
+ public String getString(ByteBuffer bytes)
+ {
+ if (bytes.remaining() == 0)
+ {
+ return "";
+ }
+ if (bytes.remaining() != 16)
+ {
+ throw new MarshalException("UUIDs must be exactly 16 bytes");
+ }
+ UUID uuid = compose(bytes);
+ return uuid.toString();
+ }
+
+ @Override
+ public ByteBuffer fromString(String source) throws MarshalException
+ {
+ return LexicalUUIDType.instance.fromString(source);
+ }
+}
Added: cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java?rev=1090711&view=auto
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java (added)
+++ cassandra/trunk/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java Sat Apr 9 23:46:28 2011
@@ -0,0 +1,214 @@
+package org.apache.cassandra.db.marshal;
+
+import static org.junit.Assert.assertEquals;
+
+import java.net.InetAddress;
+import java.net.UnknownHostException;
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import java.util.Random;
+import java.util.UUID;
+
+import org.apache.cassandra.utils.UUIDGen;
+import org.apache.log4j.Logger;
+import org.junit.Test;
+
+public class UUIDTypeTest
+{
+
+ private static final Logger logger = Logger.getLogger(UUIDTypeTest.class);
+
+ UUIDType uuidType = new UUIDType();
+
+ @Test
+ public void testCompare()
+ {
+
+ UUID t1 = newTimeBasedUUID();
+ UUID t2 = newTimeBasedUUID();
+
+ testCompare(t1, t2, -1);
+ testCompare(t1, t1, 0);
+ testCompare(t2, t2, 0);
+
+ UUID nullId = new UUID(0, 0);
+
+ testCompare(nullId, t1, -1);
+ testCompare(t2, nullId, 1);
+ testCompare(nullId, nullId, 0);
+
+ for (int test = 1; test < 32; test++)
+ {
+ UUID r1 = UUID.randomUUID();
+ UUID r2 = UUID.randomUUID();
+
+ testCompare(r1, r2, compareUUID(r1, r2));
+ testCompare(r1, r1, 0);
+ testCompare(r2, r2, 0);
+
+ testCompare(t1, r1, -1);
+ testCompare(r2, t2, 1);
+ }
+ }
+
+ public UUID newTimeBasedUUID()
+ {
+ try
+ {
+ return UUIDGen.makeType1UUIDFromHost(InetAddress.getLocalHost());
+ } catch (UnknownHostException e)
+ {
+ throw new RuntimeException(e);
+ }
+ }
+
+ public static int compareUnsigned(long n1, long n2)
+ {
+ if (n1 == n2)
+ {
+ return 0;
+ }
+ if ((n1 < n2) ^ ((n1 < 0) != (n2 < 0)))
+ {
+ return -1;
+ }
+ return 1;
+ }
+
+ public static int compareUUID(UUID u1, UUID u2)
+ {
+ int c = compareUnsigned(u1.getMostSignificantBits(),
+ u2.getMostSignificantBits());
+ if (c != 0)
+ {
+ return c;
+ }
+ return compareUnsigned(u1.getLeastSignificantBits(),
+ u2.getLeastSignificantBits());
+ }
+
+ public String describeCompare(UUID u1, UUID u2, int c)
+ {
+ String tb1 = (u1.version() == 1) ? "time-based " : "random ";
+ String tb2 = (u2.version() == 1) ? "time-based " : "random ";
+ String comp = (c < 0) ? " < " : ((c == 0) ? " = " : " > ");
+ return tb1 + u1 + comp + tb2 + u2;
+ }
+
+ public int sign(int i)
+ {
+ if (i < 0)
+ {
+ return -1;
+ }
+ if (i > 0)
+ {
+ return 1;
+ }
+ return 0;
+ }
+
+ public static ByteBuffer bytebuffer(UUID uuid)
+ {
+ long msb = uuid.getMostSignificantBits();
+ long lsb = uuid.getLeastSignificantBits();
+ byte[] bytes = new byte[16];
+
+ for (int i = 0; i < 8; i++)
+ {
+ bytes[i] = (byte) (msb >>> 8 * (7 - i));
+ }
+ for (int i = 8; i < 16; i++)
+ {
+ bytes[i] = (byte) (lsb >>> 8 * (7 - i));
+ }
+
+ return ByteBuffer.wrap(bytes);
+ }
+
+ public void logJdkUUIDCompareToVariance(UUID u1, UUID u2, int expC)
+ {
+ if (u1.version() != u2.version())
+ {
+ return;
+ }
+ if (u1.version() == 1)
+ {
+ return;
+ }
+ if (u1.compareTo(u2) != expC)
+ {
+ logger.info("*** Note: java.util.UUID.compareTo() would have compared this differently");
+ }
+
+ }
+
+ public void testCompare(UUID u1, UUID u2, int expC)
+ {
+ int c = sign(uuidType.compare(bytebuffer(u1), bytebuffer(u2)));
+ expC = sign(expC);
+ assertEquals("Expected " + describeCompare(u1, u2, expC) + ", got "
+ + describeCompare(u1, u2, c), expC, c);
+
+ if (u1.version() == 1)
+ assertEquals(c, sign(TimeUUIDType.instance.compare(bytebuffer(u1), bytebuffer(u2))));
+
+ logJdkUUIDCompareToVariance(u1, u2, c);
+ }
+
+ @Test
+ public void testTimeEquality()
+ {
+ UUID a = newTimeBasedUUID();
+ UUID b = new UUID(a.getMostSignificantBits(),
+ a.getLeastSignificantBits());
+
+ assertEquals(0, uuidType.compare(bytebuffer(a), bytebuffer(b)));
+ }
+
+ @Test
+ public void testTimeSmaller()
+ {
+ UUID a = newTimeBasedUUID();
+ UUID b = newTimeBasedUUID();
+ UUID c = newTimeBasedUUID();
+
+ assert uuidType.compare(bytebuffer(a), bytebuffer(b)) < 0;
+ assert uuidType.compare(bytebuffer(b), bytebuffer(c)) < 0;
+ assert uuidType.compare(bytebuffer(a), bytebuffer(c)) < 0;
+ }
+
+ @Test
+ public void testTimeBigger()
+ {
+ UUID a = newTimeBasedUUID();
+ UUID b = newTimeBasedUUID();
+ UUID c = newTimeBasedUUID();
+
+ assert uuidType.compare(bytebuffer(c), bytebuffer(b)) > 0;
+ assert uuidType.compare(bytebuffer(b), bytebuffer(a)) > 0;
+ assert uuidType.compare(bytebuffer(c), bytebuffer(a)) > 0;
+ }
+
+ @Test
+ public void testTimestampComparison()
+ {
+ Random rng = new Random();
+ ByteBuffer[] uuids = new ByteBuffer[100];
+ for (int i = 0; i < uuids.length; i++)
+ {
+ uuids[i] = ByteBuffer.allocate(16);
+ rng.nextBytes(uuids[i].array());
+ // set version to 1
+ uuids[i].array()[6] &= 0x0F;
+ uuids[i].array()[6] |= 0x10;
+ }
+ Arrays.sort(uuids, uuidType);
+ for (int i = 1; i < uuids.length; i++)
+ {
+ long i0 = UUIDGen.getUUID(uuids[i - 1]).timestamp();
+ long i1 = UUIDGen.getUUID(uuids[i]).timestamp();
+ assert i0 <= i1;
+ }
+ }
+}