| 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 static org.apache.cassandra.utils.TimeUUID.Generator.nextTimeUUID; |
| import static org.junit.Assert.assertEquals; |
| |
| import java.nio.ByteBuffer; |
| import java.util.Iterator; |
| import java.util.Random; |
| import java.util.UUID; |
| |
| import org.junit.Test; |
| |
| import org.junit.Assert; |
| import org.apache.cassandra.transport.ProtocolVersion; |
| import org.apache.cassandra.utils.ByteBufferUtil; |
| import org.apache.cassandra.utils.UUIDGen; |
| import org.slf4j.Logger; |
| import org.slf4j.LoggerFactory; |
| |
| public class UUIDTypeTest |
| { |
| |
| private static final Logger logger = LoggerFactory.getLogger(UUIDTypeTest.class); |
| |
| UUIDType uuidType = new UUIDType(); |
| |
| @Test //CASSANDRA-15896 |
| public void testToJsonEmptyValue() |
| { |
| String res = uuidType.toJSONString(uuidType.fromJSONObject("").bindAndGet(null), ProtocolVersion.CURRENT); |
| assertEquals("\"\"", res); |
| } |
| |
| @Test |
| public void testRandomCompare() |
| { |
| |
| UUID t1 = nextTimeUUID().asUUID(); |
| UUID t2 = nextTimeUUID().asUUID(); |
| |
| testCompare(null, t2, -1); |
| testCompare(t1, null, 1); |
| |
| 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 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 == null) ? "null" : (u1.version() == 1) ? "time-based " : "random "; |
| String tb2 = (u2 == null) ? "null" : (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) |
| { |
| if (uuid == null) |
| return ByteBufferUtil.EMPTY_BYTE_BUFFER; |
| |
| 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 == null) || (u2 == null)) |
| return; |
| 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 != null) && (u1.version() == 1)) && ((u2 != null) && (u2.version() == 1))) |
| assertEquals(c, sign(TimeUUIDType.instance.compare(bytebuffer(u1), bytebuffer(u2)))); |
| |
| logJdkUUIDCompareToVariance(u1, u2, c); |
| } |
| |
| @Test |
| public void testTimeEquality() |
| { |
| UUID a = nextTimeUUID().asUUID(); |
| UUID b = new UUID(a.getMostSignificantBits(), |
| a.getLeastSignificantBits()); |
| |
| assertEquals(0, uuidType.compare(bytebuffer(a), bytebuffer(b))); |
| } |
| |
| @Test |
| public void testTimeSmaller() |
| { |
| UUID a = nextTimeUUID().asUUID(); |
| UUID b = nextTimeUUID().asUUID(); |
| UUID c = nextTimeUUID().asUUID(); |
| |
| 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 = nextTimeUUID().asUUID(); |
| UUID b = nextTimeUUID().asUUID(); |
| UUID c = nextTimeUUID().asUUID(); |
| |
| 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 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) |
| { |
| for (int i = 0 ; i < uuids.length ; i++) |
| { |
| 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)); |
| } |
| } |
| } |
| |
| 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[]>() |
| { |
| 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); |
| } |
| } |