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 <[email protected]> Authored: Tue Mar 10 12:43:52 2015 +0000 Committer: Benedict Elliott Smith <[email protected]> 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); } }
