diff options
author | Håvard Pettersen <havardpe@yahooinc.com> | 2023-03-21 14:01:28 +0000 |
---|---|---|
committer | Håvard Pettersen <havardpe@yahooinc.com> | 2023-03-21 15:05:06 +0000 |
commit | 4c93ec38f843e70ab756f537b158ea5c8e3f7cf8 (patch) | |
tree | 5849666635abea1755fc3a8c7c6966f108e9c75d /vespajlib | |
parent | 3075eced6674caef07fed92b9e311bdda67718a5 (diff) |
added DecodeIndex utility class
Diffstat (limited to 'vespajlib')
-rw-r--r-- | vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java | 51 | ||||
-rw-r--r-- | vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java | 87 |
2 files changed, 138 insertions, 0 deletions
diff --git a/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java b/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java new file mode 100644 index 00000000000..17c7a86730e --- /dev/null +++ b/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java @@ -0,0 +1,51 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.slime; + +/** + * Light-weight index structure describing the layout of a Slime value + * encoded in binary format. + **/ +final class DecodeIndex { + static final int initial_capacity = 16; + private long[] data = new long[initial_capacity]; + private int reserved = 0; + + private int adjustSize(int minSize) { + int capacity = initial_capacity; + while (capacity < minSize) { + capacity = capacity << 1; + } + return capacity; + } + + int reserve(int n) { + int offset = reserved; + if (reserved + n > data.length) { + long[] old = data; + data = new long[adjustSize(reserved + n)]; + System.arraycopy(old, 0, data, 0, reserved); + } + reserved += n; + return offset; + } + + int size() { return reserved; } + + void set(int idx, int byteOffset, int firstChild, int extBits) { + data[idx] = (long)(byteOffset & 0x7fff_ffff) << 33 | + (long)(firstChild & 0x7fff_ffff) << 2 | + extBits & 0x3; + } + + int getByteOffset(int idx) { + return (int)(data[idx] >> 33) & 0x7fff_ffff; + } + + int getFirstChild(int idx) { + return (int)(data[idx] >> 2) & 0x7fff_ffff; + } + + int getExtBits(int idx) { + return (int)data[idx] & 0x3; + } +} diff --git a/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java new file mode 100644 index 00000000000..916eedb75c6 --- /dev/null +++ b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java @@ -0,0 +1,87 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.slime; + +import org.junit.Test; + +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.CoreMatchers.is; + +public class DecodeIndexTest { + + @Test + public void testSimpleUsage() { + DecodeIndex index = new DecodeIndex(); + int val1 = index.reserve(1); + int val2 = index.reserve(3); + int val3 = index.reserve(2); + assertThat(val1, is(0)); + assertThat(val2, is(1)); + assertThat(val3, is(4)); + assertThat(index.size(), is(6)); + index.set(val1 + 0, 0, val2, 0); + index.set(val2 + 0, 100, 0, 1); + index.set(val2 + 1, 200, val3, 2); + index.set(val2 + 2, 300, 0, 3); + index.set(val3 + 0, 400, 0, 0); + index.set(val3 + 1, 500, 0, 0); + for (int i = 0; i < 6; i++) { + assertThat(index.getByteOffset(i), is(i * 100)); + if (i == 0) { + assertThat(index.getFirstChild(i), is(1)); + } else if (i == 2) { + assertThat(index.getFirstChild(i), is(4)); + } else { + assertThat(index.getFirstChild(i), is(0)); + } + if (i < 4) { + assertThat(index.getExtBits(i), is(i)); + } else { + assertThat(index.getExtBits(i), is(0)); + } + } + } + + @Test + public void testManyValues() { + DecodeIndex index = new DecodeIndex(); + int outer = 47; + int inner = 73; + int expectOffset = 0; + for (int i = 0; i < outer; i++) { + int offset = index.reserve(inner); + assertThat(offset, is(expectOffset)); + expectOffset += inner; + for (int j = 0; j < inner; j++) { + index.set(offset + j, (i * j), (i + j), (j & 3)); + } + } + assertThat(expectOffset, is(inner * outer)); + assertThat(index.size(), is(inner * outer)); + for (int i = 0; i < outer; i++) { + for (int j = 0; j < inner; j++) { + int offset = i * inner + j; + assertThat(index.getByteOffset(offset), is(i * j)); + assertThat(index.getFirstChild(offset), is(i + j)); + assertThat(index.getExtBits(offset), is(j & 3)); + } + } + } + + @Test + public void testOverflowNoBleed() { + DecodeIndex index = new DecodeIndex(); + index.reserve(3); + index.set(0, 0xffff_ffff, 0, 0); + index.set(1, 0, 0xffff_ffff, 0); + index.set(2, 0, 0, 0xffff_ffff); + assertThat(index.getByteOffset(0), is(0x7fff_ffff)); + assertThat(index.getByteOffset(1), is(0)); + assertThat(index.getByteOffset(2), is(0)); + assertThat(index.getFirstChild(0), is(0)); + assertThat(index.getFirstChild(1), is(0x7fff_ffff)); + assertThat(index.getFirstChild(2), is(0)); + assertThat(index.getExtBits(0), is(0)); + assertThat(index.getExtBits(1), is(0)); + assertThat(index.getExtBits(2), is(3)); + } +} |