added DecodeIndex utility class

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));
+    }
+}