diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2023-03-22 11:29:46 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-03-22 11:29:46 +0100 |
commit | 39ef03dbfea4665dbe06b187d8d9d19d65e6d660 (patch) | |
tree | 13476d4f80f2b22a506a9bb9a37f96b22c39f03c /vespajlib/src | |
parent | c9d4237920fbfcc644579a2cdf0fcd01bfff2b6c (diff) | |
parent | f217406ad77df0047364e27b607117dcc8953eaf (diff) |
Merge pull request #26518 from vespa-engine/havardpe/decode-index
added DecodeIndex utility class
Diffstat (limited to 'vespajlib/src')
-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 | 85 |
2 files changed, 136 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..223701fa2fd --- /dev/null +++ b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java @@ -0,0 +1,85 @@ +// 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.junit.Assert.assertEquals; + +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); + assertEquals(0, val1); + assertEquals(1, val2); + assertEquals(4, val3); + assertEquals(6, index.size()); + 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++) { + assertEquals(i * 100, index.getByteOffset(i)); + if (i == 0) { + assertEquals(1, index.getFirstChild(i)); + } else if (i == 2) { + assertEquals(4, index.getFirstChild(i)); + } else { + assertEquals(0, index.getFirstChild(i)); + } + if (i < 4) { + assertEquals(i, index.getExtBits(i)); + } else { + assertEquals(0, index.getExtBits(i)); + } + } + } + + @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); + assertEquals(expectOffset, offset); + expectOffset += inner; + for (int j = 0; j < inner; j++) { + index.set(offset + j, (i * j), (i + j), (j & 3)); + } + } + assertEquals(inner * outer, expectOffset); + assertEquals(inner * outer, index.size()); + for (int i = 0; i < outer; i++) { + for (int j = 0; j < inner; j++) { + int offset = i * inner + j; + assertEquals(i * j, index.getByteOffset(offset)); + assertEquals(i + j, index.getFirstChild(offset)); + assertEquals(j & 3, index.getExtBits(offset)); + } + } + } + + @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); + assertEquals(0x7fff_ffff, index.getByteOffset(0)); + assertEquals(0, index.getByteOffset(1)); + assertEquals(0, index.getByteOffset(2)); + assertEquals(0, index.getFirstChild(0)); + assertEquals(0x7fff_ffff, index.getFirstChild(1)); + assertEquals(0, index.getFirstChild(2)); + assertEquals(0, index.getExtBits(0)); + assertEquals(0, index.getExtBits(1)); + assertEquals(3, index.getExtBits(2)); + } +} |