This is an automated email from the ASF dual-hosted git repository. raminqaf pushed a commit to branch release-2.4 in repository https://gitbox.apache.org/repos/asf/flink.git
commit 0ccdfc56b91285eb44c9b04957bedf238ed3215b Author: Ramin Gharib <[email protected]> AuthorDate: Mon Oct 26 09:47:29 2026 +0100 [FLINK-41180][core] Sort VARIANT object fields by UTF-8 bytes The variant spec orders the fields of an object by the unsigned UTF-8 bytes of their names. The builder sorted them with String.compareTo, which is UTF-16 order, and getField binary-searched objects of 32 or more fields in the same order. The two orders differ when, at the first differing character, one name has a code point from U+E000 to U+FFFF and the other one from U+10000 up. In a spec-ordered object of 32 fields with the keys U+FF61 and U+1F600, getField(U+1F600) returned null. The builder now sorts fields by their stored key bytes, and getField binary-searches in the same order. Objects written in UTF-16 order stay readable: after a miss for a key with a code point from U+E000 up, getField scans the fields linearly. For any other key both orders agree, so the miss stands. Keys that differ as Strings but are stored as the same bytes, such as "a\uD800" and "a?", are now duplicates. Such an object held two fields with the same name before. getField("a\uD800") now finds the field in objects of any size. Objects with keys from U+E000 up can have a different field order now, which shows in getFieldNames and in CAST to STRING. A Flink version without this change can miss such keys in objects of 32 or more fields. Such an object stored before the upgrade is not byte-equal to the same object built after it. Generated-by: Claude Code 2.1.310 (Claude Opus 5.5) (cherry picked from commit dab40d31eba000411f919fe9b77afc6d77bfa1a7) --- docs/content.zh/docs/sql/reference/data-types.md | 4 +- docs/content/docs/sql/reference/data-types.md | 4 +- .../apache/flink/types/variant/BinaryVariant.java | 82 ++++++++------ .../flink/types/variant/BinaryVariantBuilder.java | 4 +- .../variant/BinaryVariantInternalBuilder.java | 32 +++--- .../flink/types/variant/BinaryVariantUtil.java | 29 ++++- .../variant/BinaryVariantInternalBuilderTest.java | 2 +- .../flink/types/variant/BinaryVariantTest.java | 123 ++++++++++++++++++--- 8 files changed, 208 insertions(+), 72 deletions(-) diff --git a/docs/content.zh/docs/sql/reference/data-types.md b/docs/content.zh/docs/sql/reference/data-types.md index 5bd96e1a6a9..703185f11de 100644 --- a/docs/content.zh/docs/sql/reference/data-types.md +++ b/docs/content.zh/docs/sql/reference/data-types.md @@ -1732,8 +1732,8 @@ leaf is stored by the rules above, so the cast is supported only when every leaf - A `ROW` or `STRUCTURED` value is keyed by its field names. - A `MAP` needs a character string key, which becomes the object key. A `NULL` key fails the cast. If a key appears twice, the last value is kept. -- A variant object sorts its keys, so neither the field order of a `ROW` nor the entry order of a - `MAP` is kept. +- A variant object sorts its keys by their UTF-8 bytes, so neither the field order of a `ROW` nor + the entry order of a `MAP` is kept. - A `NULL` element, field, or map value becomes a variant null, so an array keeps its length and an object keeps its keys. A cast element by element differs here: `ARRAY<INT>` to `ARRAY<VARIANT>` keeps a SQL `NULL`, while `ARRAY<INT>` to `VARIANT` turns it into a variant null. diff --git a/docs/content/docs/sql/reference/data-types.md b/docs/content/docs/sql/reference/data-types.md index f3235b83f5b..1ac289a0402 100644 --- a/docs/content/docs/sql/reference/data-types.md +++ b/docs/content/docs/sql/reference/data-types.md @@ -1740,8 +1740,8 @@ leaf is stored by the rules above, so the cast is supported only when every leaf - A `ROW` or `STRUCTURED` value is keyed by its field names. - A `MAP` needs a character string key, which becomes the object key. A `NULL` key fails the cast. If a key appears twice, the last value is kept. -- A variant object sorts its keys, so neither the field order of a `ROW` nor the entry order of a - `MAP` is kept. +- A variant object sorts its keys by their UTF-8 bytes, so neither the field order of a `ROW` nor + the entry order of a `MAP` is kept. - A `NULL` element, field, or map value becomes a variant null, so an array keeps its length and an object keeps its keys. A cast element by element differs here: `ARRAY<INT>` to `ARRAY<VARIANT>` keeps a SQL `NULL`, while `ARRAY<INT>` to `VARIANT` turns it into a variant null. diff --git a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariant.java b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariant.java index 90e61c159df..25427486205 100644 --- a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariant.java +++ b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariant.java @@ -37,10 +37,12 @@ import static org.apache.flink.types.variant.BinaryVariantUtil.SIZE_LIMIT; import static org.apache.flink.types.variant.BinaryVariantUtil.VERSION; import static org.apache.flink.types.variant.BinaryVariantUtil.VERSION_MASK; import static org.apache.flink.types.variant.BinaryVariantUtil.checkIndex; +import static org.apache.flink.types.variant.BinaryVariantUtil.compareMetadataKey; import static org.apache.flink.types.variant.BinaryVariantUtil.encodeKey; import static org.apache.flink.types.variant.BinaryVariantUtil.getMetadataKey; import static org.apache.flink.types.variant.BinaryVariantUtil.handleArray; import static org.apache.flink.types.variant.BinaryVariantUtil.handleObject; +import static org.apache.flink.types.variant.BinaryVariantUtil.hasCodePointFromE000; import static org.apache.flink.types.variant.BinaryVariantUtil.malformedVariant; import static org.apache.flink.types.variant.BinaryVariantUtil.metadataKeyEquals; import static org.apache.flink.types.variant.BinaryVariantUtil.microsToInstant; @@ -339,51 +341,67 @@ public final class BinaryVariant implements Variant { // Find the field value whose key is equal to `key`. Return null if the key is not found. // It is only legal to call it when `getType()` is `Type.OBJECT`. private BinaryVariant getFieldByKey(String key) { + byte[] keyBytes = encodeKey(key); return handleObject( value, pos, (size, idSize, offsetSize, idStart, offsetStart, dataStart) -> { + int index; // Use linear search for a short list. Switch to binary search when the length // reaches `BINARY_SEARCH_THRESHOLD`. if (size < BINARY_SEARCH_THRESHOLD) { - byte[] keyBytes = encodeKey(key); - for (int i = 0; i < size; ++i) { - int id = readUnsigned(value, idStart + idSize * i, idSize); - if (metadataKeyEquals(metadata, id, keyBytes)) { - int offset = - readUnsigned( - value, offsetStart + offsetSize * i, offsetSize); - return new BinaryVariant(value, metadata, dataStart + offset); - } - } + index = findFieldLinear(keyBytes, size, idSize, idStart); } else { - int low = 0; - int high = size - 1; - while (low <= high) { - // Use unsigned right shift to compute the middle of `low` and `high`. - // This is not only a performance optimization, because it can properly - // handle the case where `low + high` overflows int. - int mid = (low + high) >>> 1; - int id = readUnsigned(value, idStart + idSize * mid, idSize); - // Compare decoded Strings here. The builder sorts fields by - // String.compareTo, which is not UTF-8 byte order. - int cmp = getMetadataKey(metadata, id).compareTo(key); - if (cmp < 0) { - low = mid + 1; - } else if (cmp > 0) { - high = mid - 1; - } else { - int offset = - readUnsigned( - value, offsetStart + offsetSize * mid, offsetSize); - return new BinaryVariant(value, metadata, dataStart + offset); - } + index = findFieldBinary(keyBytes, size, idSize, idStart); + // Objects that earlier Flink versions wrote are sorted in UTF-16 order + // instead. Only a miss for a key with a code point from U+E000 up can be + // wrong there, see `hasCodePointFromE000`. Such a miss scans all fields, + // because an object does not record which order it uses. + if (index < 0 && hasCodePointFromE000(keyBytes)) { + index = findFieldLinear(keyBytes, size, idSize, idStart); } } - return null; + if (index < 0) { + return null; + } + int offset = readUnsigned(value, offsetStart + offsetSize * index, offsetSize); + return new BinaryVariant(value, metadata, dataStart + offset); }); } + // Return the index of the field whose key has the UTF-8 bytes `key`, or -1 if there is none. + private int findFieldLinear(byte[] key, int size, int idSize, int idStart) { + for (int i = 0; i < size; ++i) { + int id = readUnsigned(value, idStart + idSize * i, idSize); + if (metadataKeyEquals(metadata, id, key)) { + return i; + } + } + return -1; + } + + // Like `findFieldLinear`, for fields sorted by the unsigned UTF-8 bytes of their keys. + private int findFieldBinary(byte[] key, int size, int idSize, int idStart) { + int low = 0; + int high = size - 1; + while (low <= high) { + // Use unsigned right shift to compute the middle of `low` and `high`. This is not only + // a performance optimization, because it can properly handle the case where + // `low + high` overflows int. + int mid = (low + high) >>> 1; + int id = readUnsigned(value, idStart + idSize * mid, idSize); + int cmp = compareMetadataKey(metadata, id, key); + if (cmp < 0) { + low = mid + 1; + } else if (cmp > 0) { + high = mid - 1; + } else { + return mid; + } + } + return -1; + } + // Get the array element at the `index` slot. Return null if `index` is out of the bound of // `[0, arraySize())`. // It is only legal to call it when `getType()` is `Type.ARRAY`. diff --git a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantBuilder.java b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantBuilder.java index 4de45e319fc..9a96c283e60 100644 --- a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantBuilder.java +++ b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantBuilder.java @@ -186,9 +186,7 @@ public class BinaryVariantBuilder implements VariantBuilder { @Override public VariantObjectBuilder add(String key, Variant value) { - int id = builder.addKey(key); - entries.add( - new BinaryVariantInternalBuilder.FieldEntry(key, id, builder.getWritePos())); + builder.addField(entries, 0, key); builder.appendVariant((BinaryVariant) value); return this; } diff --git a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantInternalBuilder.java b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantInternalBuilder.java index 4ac26cb2b46..e922a2bdec8 100644 --- a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantInternalBuilder.java +++ b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantInternalBuilder.java @@ -33,7 +33,6 @@ import java.math.BigInteger; import java.nio.charset.StandardCharsets; import java.util.ArrayList; import java.util.Arrays; -import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.UUID; @@ -492,7 +491,7 @@ public class BinaryVariantInternalBuilder { // Add a field to the object that starts at `start`. Call it right before writing the value, // since the field records the current write position as its offset. public void addField(ArrayList<FieldEntry> fields, int start, String key) { - fields.add(new FieldEntry(key, addKey(key), writePos - start)); + fields.add(new FieldEntry(addKey(key), writePos - start)); } // Finish writing a variant object after all of its fields have already been written. The @@ -505,20 +504,21 @@ public class BinaryVariantInternalBuilder { // record the offset of the field. The offset is computed as `getWritePos() - start`. // 3. The caller calls `finishWritingObject` to finish writing a variant object. // - // This function is responsible to sort the fields by key. If there are duplicate field keys: + // This function is responsible to sort the fields by the unsigned UTF-8 bytes of their keys, + // as the variant spec requires. Fields whose keys have the same bytes are duplicates: // - when `allowDuplicateKeys` is true, the field with the greatest offset value (the last // appended one) is kept. // - otherwise, throw an exception. public void finishWritingObject(int start, ArrayList<FieldEntry> fields) { int size = fields.size(); - Collections.sort(fields); + fields.sort(keyOrder); int maxId = size == 0 ? 0 : fields.get(0).id; if (allowDuplicateKeys) { int distinctPos = 0; // Maintain a list of distinct keys in-place. for (int i = 1; i < size; ++i) { maxId = Math.max(maxId, fields.get(i).id); - if (fields.get(i).id == fields.get(i - 1).id) { + if (keyOrder.compare(fields.get(i - 1), fields.get(i)) == 0) { // Found a duplicate key. Keep the field with a greater offset. if (fields.get(distinctPos).offset < fields.get(i).offset) { fields.set( @@ -554,13 +554,12 @@ public class BinaryVariantInternalBuilder { } writePos = start + currentOffset; // Change back to the sort order by field keys to meet the variant spec. - Collections.sort(fields); + fields.sort(keyOrder); } } else { for (int i = 1; i < size; ++i) { maxId = Math.max(maxId, fields.get(i).id); - String key = fields.get(i).key; - if (key.equals(fields.get(i - 1).key)) { + if (keyOrder.compare(fields.get(i - 1), fields.get(i)) == 0) { throw VARIANT_DUPLICATE_KEY_EXCEPTION; } } @@ -698,24 +697,17 @@ public class BinaryVariantInternalBuilder { // Temporarily store the information of a field. We need to collect all fields in an JSON // object, // sort them by their keys, and build the variant object in sorted order. - public static final class FieldEntry implements Comparable<FieldEntry> { - final String key; + public static final class FieldEntry { final int id; final int offset; - public FieldEntry(String key, int id, int offset) { - this.key = key; + FieldEntry(int id, int offset) { this.id = id; this.offset = offset; } FieldEntry withNewOffset(int newOffset) { - return new FieldEntry(key, id, newOffset); - } - - @Override - public int compareTo(FieldEntry other) { - return key.compareTo(other.key); + return new FieldEntry(id, newOffset); } } @@ -835,5 +827,9 @@ public class BinaryVariantInternalBuilder { private final HashMap<String, Integer> dictionary = new HashMap<>(); // Store all keys in `dictionary` in the order of id. private final ArrayList<byte[]> dictionaryKeys = new ArrayList<>(); + // Order fields by the stored UTF-8 bytes of their keys. Keys that differ as Strings but are + // stored as the same bytes, such as an unpaired surrogate and '?', compare as equal. + private final Comparator<FieldEntry> keyOrder = + (a, b) -> Arrays.compareUnsigned(dictionaryKeys.get(a.id), dictionaryKeys.get(b.id)); private final boolean allowDuplicateKeys; } diff --git a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantUtil.java b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantUtil.java index c0812989fa6..23cdf8c6779 100644 --- a/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantUtil.java +++ b/flink-core/src/main/java/org/apache/flink/types/variant/BinaryVariantUtil.java @@ -86,7 +86,7 @@ public class BinaryVariantUtil { * Object value. The content contains a size, a list of field ids, a list of field offsets, and * the actual field data. The length of the id list is {@code size}, while the length of the * offset list is {@code size + 1}, where the last offset represent the total size of the field - * data. The fields in an object must be sorted by the field name in alphabetical order. + * data. The fields in an object must be sorted by the unsigned UTF-8 bytes of their names. * Duplicate field names in one object are not allowed. * * <p>We use 5 bits in the type info to specify the integer type of the object header: it should @@ -868,6 +868,33 @@ public class BinaryVariantUtil { && Arrays.equals(metadata, start, start + length, key, 0, length); } + /** + * Compares the key at {@code id} in the variant metadata with the UTF-8 encoded {@code key} by + * their unsigned bytes, the order of object fields in the variant spec. + */ + static int compareMetadataKey(byte[] metadata, int id, byte[] key) { + long range = metadataKeyRange(metadata, id); + int start = keyStart(range); + return Arrays.compareUnsigned( + metadata, start, start + keyLength(range), key, 0, key.length); + } + + /** + * Whether the UTF-8 encoded {@code key} has a code point from U+E000 up, which encodes to a + * lead byte of 0xEE or above. UTF-16 order differs from UTF-8 byte order only between a code + * point from U+E000 to U+FFFF and one from U+10000 up, whose UTF-16 surrogates sort below + * U+E000. So a binary search for a key without such a code point finds the same field in either + * order, and a miss is final. + */ + static boolean hasCodePointFromE000(byte[] key) { + for (byte b : key) { + if ((b & 0xFF) >= 0xEE) { + return true; + } + } + return false; + } + /** * Locates the key at {@code id} in the variant metadata. The range is packed into a long so * that a lookup allocates nothing. diff --git a/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantInternalBuilderTest.java b/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantInternalBuilderTest.java index 2043381dc76..a6b5d153a64 100644 --- a/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantInternalBuilderTest.java +++ b/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantInternalBuilderTest.java @@ -219,7 +219,7 @@ class BinaryVariantInternalBuilderTest { final ArrayList<BinaryVariantInternalBuilder.FieldEntry> fields = new ArrayList<>( Collections.singletonList( - new BinaryVariantInternalBuilder.FieldEntry("a", id, 0))); + new BinaryVariantInternalBuilder.FieldEntry(id, 0))); assertThatThrownBy(() -> objectBuilder.finishWritingObject(0, fields)) .isSameAs(BinaryVariantInternalBuilder.VARIANT_SIZE_LIMIT_EXCEPTION); } diff --git a/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantTest.java b/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantTest.java index 4dd84d1d0db..8729209bbf4 100644 --- a/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantTest.java +++ b/flink-core/src/test/java/org/apache/flink/types/variant/BinaryVariantTest.java @@ -23,7 +23,9 @@ import org.apache.flink.core.testutils.CommonTestUtils; import org.junit.jupiter.api.BeforeEach; import org.junit.jupiter.api.Test; import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.Arguments; import org.junit.jupiter.params.provider.CsvSource; +import org.junit.jupiter.params.provider.MethodSource; import org.junit.jupiter.params.provider.ValueSource; import java.math.BigDecimal; @@ -35,13 +37,22 @@ import java.time.LocalTime; import java.time.ZoneOffset; import java.time.temporal.ChronoUnit; import java.util.Collections; +import java.util.List; import java.util.UUID; +import java.util.stream.Stream; +import static org.apache.flink.types.variant.BinaryVariantUtil.BINARY_SEARCH_THRESHOLD; +import static org.apache.flink.types.variant.BinaryVariantUtil.handleObject; import static org.assertj.core.api.Assertions.assertThat; import static org.assertj.core.api.Assertions.assertThatThrownBy; class BinaryVariantTest { + // U+E000 is EE 80 80 in UTF-8 and U+1F600 is F0 9F 98 80, so UTF-8 byte order puts U+E000 + // first. UTF-16 order compares E000 with the surrogate D83D and puts U+1F600 first. + private static final String BMP_KEY = "\uE000"; + private static final String SUPPLEMENTARY_KEY = "\uD83D\uDE00"; + private BinaryVariantBuilder builder; @BeforeEach @@ -315,28 +326,52 @@ class BinaryVariantTest { } } - @Test - void testDuplicatedKeyObjectVariant() { + @ParameterizedTest(name = "{0}") + @MethodSource("duplicateKeys") + void testDuplicatedKeyObjectVariant( + final String description, + final String key, + final String duplicate, + final List<String> fieldNames) { assertThatThrownBy( () -> builder.object(false) - .add("k", builder.of((byte) 10)) - .add("k", builder.of("hello")) + .add(key, builder.of((byte) 10)) + .add(duplicate, builder.of("hello")) .build()) .isInstanceOf(RuntimeException.class) .hasMessage("VARIANT_DUPLICATE_KEY"); Variant variant = builder.object(true) - .add("k", builder.of((byte) 10)) - .add("k", builder.of("hello")) + .add(key, builder.of((byte) 10)) + .add(duplicate, builder.of("hello")) .add("k1", builder.of(10)) .build(); - assertThat(variant.getField("k").getString()).isEqualTo("hello"); + assertThat(variant.getFieldNames()).containsExactlyElementsOf(fieldNames); + assertThat(variant.getField(key).getString()).isEqualTo("hello"); assertThat(variant.getField("k1").getInt()).isEqualTo(10); } + private static Stream<Arguments> duplicateKeys() { + return Stream.of( + Arguments.of("same key", "k", "k", List.of("k", "k1")), + // UTF-8 has no unpaired surrogates, so the builder stores both keys as "k?". + Arguments.of("same UTF-8 bytes", "k?", "k\uD800", List.of("k1", "k?"))); + } + + @Test + void testObjectFieldsAreSortedByUtf8Bytes() { + final Variant object = + builder.object() + .add(SUPPLEMENTARY_KEY, builder.of(1)) + .add(BMP_KEY, builder.of(2)) + .build(); + + assertThat(object.getFieldNames()).containsExactly(BMP_KEY, SUPPLEMENTARY_KEY); + } + @Test void testToJsonScalar() { Instant instant = Instant.EPOCH; @@ -488,15 +523,44 @@ class BinaryVariantTest { + "\"}}"); } - @Test - void testGetFieldWithUnpairedSurrogate() { + @ParameterizedTest(name = "{0} fields") + @ValueSource(ints = {1, BINARY_SEARCH_THRESHOLD}) + void testGetFieldWithUnpairedSurrogate(final int size) { // UTF-8 has no unpaired surrogates. The builder writes one as '?', and a lookup encodes its // key the same way. - final Variant object = builder.object().add("a\uD800", builder.of(1)).build(); + final Variant object = + objectWithFillerFields(builder, size - 1).add("a\uD800", builder.of(100)).build(); + + assertThat(object.getFieldNames()).contains("a?"); + assertThat(object.getField("a\uD800").getInt()).isEqualTo(100); + assertThat(object.getField("a?").getInt()).isEqualTo(100); + } - assertThat(object.getFieldNames()).containsExactly("a?"); - assertThat(object.getField("a\uD800").getInt()).isEqualTo(1); - assertThat(object.getField("a?").getInt()).isEqualTo(1); + @ParameterizedTest(name = "{0}") + @MethodSource("objectsInBothKeyOrders") + void testGetFieldWithBinarySearch(final String keyOrder, final Variant object) { + assertThat(object.getField("é").getInt()).isEqualTo(100); + assertThat(object.getField("中").getInt()).isEqualTo(200); + assertThat(object.getField(BMP_KEY).getInt()).isEqualTo(300); + assertThat(object.getField(SUPPLEMENTARY_KEY).getInt()).isEqualTo(400); + assertThat(object.getField("\uE001")).isNull(); + } + + private static Stream<Arguments> objectsInBothKeyOrders() { + final BinaryVariantBuilder builder = new BinaryVariantBuilder(); + final BinaryVariant object = + (BinaryVariant) + objectWithFillerFields(builder, BINARY_SEARCH_THRESHOLD - 4) + .add("é", builder.of(100)) + .add("中", builder.of(200)) + .add(BMP_KEY, builder.of(300)) + .add(SUPPLEMENTARY_KEY, builder.of(400)) + .build(); + // The other keys sort before the last two in both orders, so swapping the last two fields + // turns UTF-8 byte order into UTF-16 order. + return Stream.of( + Arguments.of("UTF-8 byte order", object), + Arguments.of("UTF-16 order", swapLastTwoFields(object))); } @Test @@ -589,4 +653,37 @@ class BinaryVariantTest { assertThat(((BinaryVariant) subVariant).getPos()).isGreaterThan(0); assertThat(CommonTestUtils.createCopySerializable(subVariant)).isEqualTo(subVariant); } + + /** Starts an object with {@code count} fields named k00, k01, and so on. */ + private static BinaryVariantBuilder.VariantObjectBuilder objectWithFillerFields( + final BinaryVariantBuilder builder, final int count) { + final BinaryVariantBuilder.VariantObjectBuilder object = builder.object(); + for (int i = 0; i < count; i++) { + object.add(String.format("k%02d", i), builder.of(i)); + } + return object; + } + + /** Swaps the ids and offsets of the last two fields, which keeps each value with its key. */ + private static BinaryVariant swapLastTwoFields(final BinaryVariant object) { + final byte[] value = object.getValue().clone(); + handleObject( + value, + 0, + (size, idSize, offsetSize, idStart, offsetStart, dataStart) -> { + swapBytes(value, idStart + idSize * (size - 2), idSize); + swapBytes(value, offsetStart + offsetSize * (size - 2), offsetSize); + return null; + }); + return new BinaryVariant(value, object.getMetadata()); + } + + /** Swaps the {@code length} bytes at {@code start} with the {@code length} bytes after them. */ + private static void swapBytes(final byte[] bytes, final int start, final int length) { + for (int i = start; i < start + length; i++) { + final byte b = bytes[i]; + bytes[i] = bytes[i + length]; + bytes[i + length] = b; + } + } }
