cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bened...@apache.org
Subject cassandra git commit: Optimise (Time)?UUIDType comparisons
Date Tue, 10 Mar 2015 12:44:55 GMT
Repository: cassandra
Updated Branches:
  refs/heads/trunk dce6033d8 -> 6d266253a


Optimise (Time)?UUIDType comparisons

patch by benedict; reviewed by ariel for CASSANDRA-8730


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/6d266253
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/6d266253
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/6d266253

Branch: refs/heads/trunk
Commit: 6d266253a5bdaf3a25eef14e54deb56aba9b2944
Parents: dce6033
Author: Benedict Elliott Smith <benedict@apache.org>
Authored: Tue Mar 10 12:43:52 2015 +0000
Committer: Benedict Elliott Smith <benedict@apache.org>
Committed: Tue Mar 10 12:43:52 2015 +0000

----------------------------------------------------------------------
 CHANGES.txt                                     |   2 +-
 .../cassandra/db/marshal/TimeUUIDType.java      |  72 +++--
 .../apache/cassandra/db/marshal/UUIDType.java   | 113 ++------
 .../cassandra/db/marshal/TimeUUIDTypeTest.java  |  83 ++++--
 .../cassandra/db/marshal/UUIDTypeTest.java      | 267 +++++++++++++++++--
 5 files changed, 388 insertions(+), 149 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/6d266253/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index b9aa8a8..d326313 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
 3.0
+ * Optimise (Time)?UUIDType Comparisons (CASSANDRA-8730)
  * Make CRC32Ex into a separate maven dependency (CASSANDRA-8836)
  * Use preloaded jemalloc w/ Unsafe (CASSANDRA-8714)
  * Add role based access control (CASSANDRA-7653, 8650, 7216, 8760, 8849, 8761)
@@ -60,7 +61,6 @@
  * Select optimal CRC32 implementation at runtime (CASSANDRA-8614)
  * Evaluate MurmurHash of Token once per query (CASSANDRA-7096)
 
-
 2.1.4
  * Add SimpleDate (cql date) and Time (cql time) types (CASSANDRA-7523)
  * Use long for key count in cfstats (CASSANDRA-8913)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/6d266253/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java b/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
index 573b368..17c7abc 100644
--- a/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
+++ b/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java
@@ -37,44 +37,58 @@ public class TimeUUIDType extends AbstractType<UUID>
     {
     } // singleton
 
-    public int compare(ByteBuffer o1, ByteBuffer o2)
+    public int compare(ByteBuffer b1, ByteBuffer b2)
     {
-        if (!o1.hasRemaining() || !o2.hasRemaining())
-            return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0;
+        // Compare for length
+        int s1 = b1.position(), s2 = b2.position();
+        int l1 = b1.limit(), l2 = b2.limit();
 
-        int res = compareTimestampBytes(o1, o2);
-        if (res != 0)
-            return res;
-        return o1.compareTo(o2);
-    }
-
-    private static int compareTimestampBytes(ByteBuffer o1, ByteBuffer o2)
-    {
-        int o1Pos = o1.position();
-        int o2Pos = o2.position();
-
-        int d = (o1.get(o1Pos + 6) & 0xF) - (o2.get(o2Pos + 6) & 0xF);
-        if (d != 0) return d;
+        // should we assert exactly 16 bytes (or 0)? seems prudent
+        boolean p1 = l1 - s1 == 16, p2 = l2 - s2 == 16;
+        if (!(p1 & p2))
+        {
+            assert p1 | (l1 == s1);
+            assert p2 | (l2 == s2);
+            return p1 ? 1 : p2 ? -1 : 0;
+        }
 
-        d = (o1.get(o1Pos + 7) & 0xFF) - (o2.get(o2Pos + 7) & 0xFF);
-        if (d != 0) return d;
+        long msb1 = b1.getLong(s1);
+        long msb2 = b2.getLong(s2);
+        msb1 = reorderTimestampBytes(msb1);
+        msb2 = reorderTimestampBytes(msb2);
 
-        d = (o1.get(o1Pos + 4) & 0xFF) - (o2.get(o2Pos + 4) & 0xFF);
-        if (d != 0) return d;
+        assert (msb1 & topbyte(0xf0L)) == topbyte(0x10L);
+        assert (msb2 & topbyte(0xf0L)) == topbyte(0x10L);
 
-        d = (o1.get(o1Pos + 5) & 0xFF) - (o2.get(o2Pos + 5) & 0xFF);
-        if (d != 0) return d;
+        int c = Long.compare(msb1, msb2);
+        if (c != 0)
+            return c;
 
-        d = (o1.get(o1Pos) & 0xFF) - (o2.get(o2Pos) & 0xFF);
-        if (d != 0) return d;
+        // this has to be a signed per-byte comparison for compatibility
+        // so we transform the bytes so that a simple long comparison is equivalent
+        long lsb1 = signedBytesToNativeLong(b1.getLong(s1 + 8));
+        long lsb2 = signedBytesToNativeLong(b2.getLong(s2 + 8));
+        return Long.compare(lsb1, lsb2);
+    }
 
-        d = (o1.get(o1Pos + 1) & 0xFF) - (o2.get(o2Pos + 1) & 0xFF);
-        if (d != 0) return d;
+    // takes as input 8 signed bytes in native machine order
+    // returns the first byte unchanged, and the following 7 bytes converted to an unsigned
representation
+    // which is the same as a 2's complement long in native format
+    private static long signedBytesToNativeLong(long signedBytes)
+    {
+        return signedBytes ^ 0x0080808080808080L;
+    }
 
-        d = (o1.get(o1Pos + 2) & 0xFF) - (o2.get(o2Pos + 2) & 0xFF);
-        if (d != 0) return d;
+    private static long topbyte(long topbyte)
+    {
+        return topbyte << 56;
+    }
 
-        return (o1.get(o1Pos + 3) & 0xFF) - (o2.get(o2Pos + 3) & 0xFF);
+    protected static long reorderTimestampBytes(long input)
+    {
+        return    (input <<  48)
+                  | ((input <<  16) & 0xFFFF00000000L)
+                  |  (input >>> 32);
     }
 
     public ByteBuffer fromString(String source) throws MarshalException

http://git-wip-us.apache.org/repos/asf/cassandra/blob/6d266253/src/java/org/apache/cassandra/db/marshal/UUIDType.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/marshal/UUIDType.java b/src/java/org/apache/cassandra/db/marshal/UUIDType.java
index 83fa2ba..c925ea0 100644
--- a/src/java/org/apache/cassandra/db/marshal/UUIDType.java
+++ b/src/java/org/apache/cassandra/db/marshal/UUIDType.java
@@ -20,6 +20,8 @@ package org.apache.cassandra.db.marshal;
 import java.nio.ByteBuffer;
 import java.util.UUID;
 
+import com.google.common.primitives.UnsignedLongs;
+
 import org.apache.cassandra.cql3.CQL3Type;
 import org.apache.cassandra.serializers.TypeSerializer;
 import org.apache.cassandra.serializers.MarshalException;
@@ -47,110 +49,47 @@ public class UUIDType extends AbstractType<UUID>
 
     public int compare(ByteBuffer b1, ByteBuffer b2)
     {
-
         // Compare for length
+        int s1 = b1.position(), s2 = b2.position();
+        int l1 = b1.limit(), l2 = b2.limit();
 
-        if ((b1 == null) || (b1.remaining() < 16))
+        // should we assert exactly 16 bytes (or 0)? seems prudent
+        boolean p1 = l1 - s1 == 16, p2 = l2 - s2 == 16;
+        if (!(p1 & p2))
         {
-            return ((b2 == null) || (b2.remaining() < 16)) ? 0 : -1;
+            assert p1 | (l1 == s1);
+            assert p2 | (l2 == s2);
+            return p1 ? 1 : p2 ? -1 : 0;
         }
-        if ((b2 == null) || (b2.remaining() < 16))
-        {
-            return 1;
-        }
-
-        int s1 = b1.position();
-        int s2 = b2.position();
 
         // Compare versions
+        long msb1 = b1.getLong(s1);
+        long msb2 = b2.getLong(s2);
 
-        int v1 = (b1.get(s1 + 6) >> 4) & 0x0f;
-        int v2 = (b2.get(s2 + 6) >> 4) & 0x0f;
+        int version1 = (int) ((msb1 >>> 12) & 0xf);
+        int version2 = (int) ((msb2 >>> 12) & 0xf);
+        if (version1 != version2)
+            return version1 - version2;
 
-        if (v1 != v2)
+        // bytes: version is top 4 bits of byte 6
+        // then: [6.5-8), [4-6), [0-4)
+        if (version1 == 1)
         {
-            return v1 - v2;
-        }
-
-        // Compare timestamps for version 1
-
-        if (v1 == 1)
-        {
-            // if both time-based, compare as timestamps
-            int c = compareTimestampBytes(b1, b2);
+            long reorder1 = TimeUUIDType.reorderTimestampBytes(msb1);
+            long reorder2 = TimeUUIDType.reorderTimestampBytes(msb2);
+            // we know this is >= 0, since the top 3 bits will be 0
+            int c = Long.compare(reorder1, reorder2);
             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++)
+        else
         {
-            int c = ((b1.get(s1 + i)) & 0xFF) - ((b2.get(s2 + i)) & 0xFF);
+            int c = UnsignedLongs.compare(msb1, msb2);
             if (c != 0)
-            {
                 return c;
-            }
-        }
-
-        return 0;
-    }
-
-    private static int compareTimestampBytes(ByteBuffer o1, ByteBuffer o2)
-    {
-        int o1Pos = o1.position();
-        int o2Pos = o2.position();
-
-        int d = (o1.get(o1Pos + 6) & 0xF) - (o2.get(o2Pos + 6) & 0xF);
-        if (d != 0)
-        {
-            return d;
-        }
-
-        d = (o1.get(o1Pos + 7) & 0xFF) - (o2.get(o2Pos + 7) & 0xFF);
-        if (d != 0)
-        {
-            return d;
-        }
-
-        d = (o1.get(o1Pos + 4) & 0xFF) - (o2.get(o2Pos + 4) & 0xFF);
-        if (d != 0)
-        {
-            return d;
-        }
-
-        d = (o1.get(o1Pos + 5) & 0xFF) - (o2.get(o2Pos + 5) & 0xFF);
-        if (d != 0)
-        {
-            return d;
-        }
-
-        d = (o1.get(o1Pos) & 0xFF) - (o2.get(o2Pos) & 0xFF);
-        if (d != 0)
-        {
-            return d;
-        }
-
-        d = (o1.get(o1Pos + 1) & 0xFF) - (o2.get(o2Pos + 1) & 0xFF);
-        if (d != 0)
-        {
-            return d;
-        }
-
-        d = (o1.get(o1Pos + 2) & 0xFF) - (o2.get(o2Pos + 2) & 0xFF);
-        if (d != 0)
-        {
-            return d;
         }
 
-        return (o1.get(o1Pos + 3) & 0xFF) - (o2.get(o2Pos + 3) & 0xFF);
+        return UnsignedLongs.compare(b1.getLong(s1 + 8), b2.getLong(s2 + 8));
     }
 
     @Override

http://git-wip-us.apache.org/repos/asf/cassandra/blob/6d266253/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java b/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
index 4e22df8..0054163 100644
--- a/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
+++ b/test/unit/org/apache/cassandra/db/marshal/TimeUUIDTypeTest.java
@@ -22,7 +22,9 @@ import java.nio.ByteBuffer;
 import java.util.Arrays;
 import java.util.Random;
 import java.util.UUID;
+import java.util.concurrent.ThreadLocalRandom;
 
+import junit.framework.Assert;
 import org.apache.cassandra.serializers.MarshalException;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
@@ -79,25 +81,76 @@ public class TimeUUIDTypeTest
     @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, timeUUIDType);
-        for (int i = 1; i < uuids.length; i++)
+        compareAll(UUIDTypeTest.random(1000, (byte) 0x10));
+        for (ByteBuffer[] permutations : UUIDTypeTest.permutations(100, (byte) 0x10))
+            compareAll(permutations);
+    }
+
+    private void compareAll(ByteBuffer[] uuids)
+    {
+        for (int i = 0 ; i < uuids.length ; i++)
         {
-            long i0 = UUIDGen.getUUID(uuids[i - 1]).timestamp();
-            long i1 = UUIDGen.getUUID(uuids[i]).timestamp();
-            assert i0 <= i1;
+            for (int j = i + 1 ; j < uuids.length ; j++)
+            {
+                ByteBuffer bi = uuids[i];
+                ByteBuffer bj = uuids[j];
+                long i0 = UUIDGen.getUUID(bi).timestamp();
+                long i1 = UUIDGen.getUUID(bj).timestamp();
+                int c = timeUUIDType.compare(bi, bj);
+                if (i0 == i1) Assert.assertTrue(isComparisonEquivalent(bi.compareTo(bj),
c));
+                else Assert.assertTrue(isComparisonEquivalent(Long.compare(i0, i1), c));
+                Assert.assertTrue(isComparisonEquivalent(compareV1(bi, bj), c));
+            }
         }
     }
 
+    private static int compareV1(ByteBuffer o1, ByteBuffer o2)
+    {
+        if (!o1.hasRemaining() || !o2.hasRemaining())
+            return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0;
+
+        int res = compareTimestampBytes(o1, o2);
+        if (res != 0)
+            return res;
+        return o1.compareTo(o2);
+    }
+
+    private static int compareTimestampBytes(ByteBuffer o1, ByteBuffer o2)
+    {
+        int o1Pos = o1.position();
+        int o2Pos = o2.position();
+
+        int d = (o1.get(o1Pos + 6) & 0xF) - (o2.get(o2Pos + 6) & 0xF);
+        if (d != 0) return d;
+
+        d = (o1.get(o1Pos + 7) & 0xFF) - (o2.get(o2Pos + 7) & 0xFF);
+        if (d != 0) return d;
+
+        d = (o1.get(o1Pos + 4) & 0xFF) - (o2.get(o2Pos + 4) & 0xFF);
+        if (d != 0) return d;
+
+        d = (o1.get(o1Pos + 5) & 0xFF) - (o2.get(o2Pos + 5) & 0xFF);
+        if (d != 0) return d;
+
+        d = (o1.get(o1Pos) & 0xFF) - (o2.get(o2Pos) & 0xFF);
+        if (d != 0) return d;
+
+        d = (o1.get(o1Pos + 1) & 0xFF) - (o2.get(o2Pos + 1) & 0xFF);
+        if (d != 0) return d;
+
+        d = (o1.get(o1Pos + 2) & 0xFF) - (o2.get(o2Pos + 2) & 0xFF);
+        if (d != 0) return d;
+
+        return (o1.get(o1Pos + 3) & 0xFF) - (o2.get(o2Pos + 3) & 0xFF);
+    }
+
+    private static boolean isComparisonEquivalent(int c1, int c2)
+    {
+        c1 = c1 < -1 ? -1 : c1 > 1 ? 1 : c1;
+        c2 = c2 < -1 ? -1 : c2 > 1 ? 1 : c2;
+        return c1 == c2;
+    }
+
     @Test
     public void testValidTimeVersion()
     {

http://git-wip-us.apache.org/repos/asf/cassandra/blob/6d266253/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java b/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java
index 1ecacf3..335860c 100644
--- a/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java
+++ b/test/unit/org/apache/cassandra/db/marshal/UUIDTypeTest.java
@@ -24,15 +24,17 @@ package org.apache.cassandra.db.marshal;
 import static org.junit.Assert.assertEquals;
 
 import java.nio.ByteBuffer;
-import java.util.Arrays;
+import java.util.Iterator;
 import java.util.Random;
 import java.util.UUID;
 
+import org.junit.Test;
+
+import junit.framework.Assert;
 import org.apache.cassandra.utils.ByteBufferUtil;
 import org.apache.cassandra.utils.UUIDGen;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
-import org.junit.Test;
 
 public class UUIDTypeTest
 {
@@ -42,7 +44,7 @@ public class UUIDTypeTest
     UUIDType uuidType = new UUIDType();
 
     @Test
-    public void testCompare()
+    public void testRandomCompare()
     {
 
         UUID t1 = UUIDGen.getTimeUUID();
@@ -201,24 +203,255 @@ public class UUIDTypeTest
     }
 
     @Test
-    public void testTimestampComparison()
+    public void testPermutations()
+    {
+        compareAll(random(1000, (byte) 0x00, (byte) 0x10, (byte) 0x20));
+        for (ByteBuffer[] permutations : permutations(10,  (byte) 0x00, (byte) 0x10, (byte)
0x20))
+            compareAll(permutations);
+    }
+
+    private void compareAll(ByteBuffer[] uuids)
     {
-        Random rng = new Random();
-        ByteBuffer[] uuids = new ByteBuffer[100];
-        for (int i = 0; i < uuids.length; i++)
+        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;
+            for (int j = i + 1 ; j < uuids.length ; j++)
+            {
+                ByteBuffer bi = uuids[i];
+                ByteBuffer bj = uuids[j];
+                UUID ui = UUIDGen.getUUID(bi);
+                UUID uj = UUIDGen.getUUID(bj);
+                int c = uuidType.compare(bi, bj);
+                if (ui.version() != uj.version())
+                {
+                    Assert.assertTrue(isComparisonEquivalent(ui.version() - uj.version(),
c));
+                }
+                else if (ui.version() == 1)
+                {
+                    long i0 = ui.timestamp();
+                    long i1 = uj.timestamp();
+                    if (i0 == i1) Assert.assertTrue(isComparisonEquivalent(ByteBufferUtil.compareUnsigned(bi,
bj), c));
+                    else Assert.assertTrue(isComparisonEquivalent(Long.compare(i0, i1), c));
+                }
+                else
+                {
+                    Assert.assertTrue(isComparisonEquivalent(ByteBufferUtil.compareUnsigned(bi,
bj), c));
+                }
+                Assert.assertTrue(isComparisonEquivalent(compareV1(bi, bj), c));
+            }
         }
-        Arrays.sort(uuids, uuidType);
-        for (int i = 1; i < uuids.length; i++)
+    }
+
+    private static boolean isComparisonEquivalent(int c1, int c2)
+    {
+        c1 = c1 < -1 ? -1 : c1 > 1 ? 1 : c1;
+        c2 = c2 < -1 ? -1 : c2 > 1 ? 1 : c2;
+        return c1 == c2;
+    }
+
+    // produce randomCount random byte strings, and permute every possible byte within each
+    // for all provided types, using permute()
+    static Iterable<ByteBuffer[]> permutations(final int randomCount, final byte ...
types)
+    {
+        final Random random = new Random();
+        long seed = random.nextLong();
+        random.setSeed(seed);
+        System.out.println("UUIDTypeTest.permutations.seed=" + seed);
+        return new Iterable<ByteBuffer[]>()
         {
-            long i0 = UUIDGen.getUUID(uuids[i - 1]).timestamp();
-            long i1 = UUIDGen.getUUID(uuids[i]).timestamp();
-            assert i0 <= i1;
+            public Iterator<ByteBuffer[]> iterator()
+            {
+                return new Iterator<ByteBuffer[]>()
+                {
+                    byte[] bytes = new byte[16];
+                    int c = -1, i = 16;
+                    public boolean hasNext()
+                    {
+                        return i < 16 || c < randomCount - 1;
+                    }
+
+                    public ByteBuffer[] next()
+                    {
+                        if (i == 16)
+                        {
+                            random.nextBytes(bytes);
+                            i = 0;
+                            c++;
+                        }
+                        return permute(bytes, i++, types);
+                    }
+                    public void remove()
+                    {
+                    }
+                };
+            }
+        };
+    }
+
+    // for each of the given UUID types provided, produce every possible
+    // permutation of the provided byte[] for the given index
+    static ByteBuffer[] permute(byte[] src, int byteIndex, byte ... types)
+    {
+        assert src.length == 16;
+        assert byteIndex < 16;
+        byte[] bytes = src.clone();
+        ByteBuffer[] permute;
+        if (byteIndex == 6)
+        {
+            permute = new ByteBuffer[16 * types.length];
+            for (int i = 0 ; i < types.length ; i++)
+            {
+                for (int j = 0 ; j < 16 ; j++)
+                {
+                    int k = i * 16 + j;
+                    bytes[6] = (byte)(types[i] | j);
+                    permute[k] = ByteBuffer.wrap(bytes.clone());
+                }
+            }
+        }
+        else
+        {
+            permute = new ByteBuffer[256 * types.length];
+            for (int i = 0 ; i < types.length ; i++)
+            {
+                bytes[6] = types[i];
+                for (int j = 0 ; j < 256 ; j++)
+                {
+                    int k = i * 256 + j;
+                    bytes[byteIndex] = (byte) ((bytes[byteIndex] & 0x0F) | i);
+                    permute[k] = ByteBuffer.wrap(bytes.clone());
+                }
+            }
         }
+        return permute;
+    }
+
+    static ByteBuffer[] random(int count, byte ... types)
+    {
+        Random random = new Random();
+        long seed = random.nextLong();
+        random.setSeed(seed);
+        System.out.println("UUIDTypeTest.random.seed=" + seed);
+        ByteBuffer[] uuids = new ByteBuffer[count * types.length];
+        for (int i = 0 ; i < types.length ; i++)
+        {
+            for (int j = 0; j < count; j++)
+            {
+                int k = (i * count) + j;
+                uuids[k] = ByteBuffer.allocate(16);
+                random.nextBytes(uuids[k].array());
+                // set version to 1
+                uuids[k].array()[6] &= 0x0F;
+                uuids[k].array()[6] |= types[i];
+            }
+        }
+        return uuids;
+    }
+
+    private static int compareV1(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.position();
+        int s2 = b2.position();
+
+        // Compare versions
+
+        int v1 = (b1.get(s1 + 6) >> 4) & 0x0f;
+        int v2 = (b2.get(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(b1, b2);
+            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 = ((b1.get(s1 + i)) & 0xFF) - ((b2.get(s2 + i)) & 0xFF);
+            if (c != 0)
+            {
+                return c;
+            }
+        }
+
+        return 0;
+    }
+
+    private static int compareTimestampBytes(ByteBuffer o1, ByteBuffer o2)
+    {
+        int o1Pos = o1.position();
+        int o2Pos = o2.position();
+
+        int d = (o1.get(o1Pos + 6) & 0xF) - (o2.get(o2Pos + 6) & 0xF);
+        if (d != 0)
+        {
+            return d;
+        }
+
+        d = (o1.get(o1Pos + 7) & 0xFF) - (o2.get(o2Pos + 7) & 0xFF);
+        if (d != 0)
+        {
+            return d;
+        }
+
+        d = (o1.get(o1Pos + 4) & 0xFF) - (o2.get(o2Pos + 4) & 0xFF);
+        if (d != 0)
+        {
+            return d;
+        }
+
+        d = (o1.get(o1Pos + 5) & 0xFF) - (o2.get(o2Pos + 5) & 0xFF);
+        if (d != 0)
+        {
+            return d;
+        }
+
+        d = (o1.get(o1Pos) & 0xFF) - (o2.get(o2Pos) & 0xFF);
+        if (d != 0)
+        {
+            return d;
+        }
+
+        d = (o1.get(o1Pos + 1) & 0xFF) - (o2.get(o2Pos + 1) & 0xFF);
+        if (d != 0)
+        {
+            return d;
+        }
+
+        d = (o1.get(o1Pos + 2) & 0xFF) - (o2.get(o2Pos + 2) & 0xFF);
+        if (d != 0)
+        {
+            return d;
+        }
+
+        return (o1.get(o1Pos + 3) & 0xFF) - (o2.get(o2Pos + 3) & 0xFF);
     }
 }


Mime
View raw message