use value density to estimate needed decode index size

- inline index array into BinaryView to avoid indirection
- let DecodeIndex sanity check requested size against max size
- grow with 25% (factor 1.25) if estimate is close to buffer size

4 files changed, 277 insertions, 94 deletions

diff --git a/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java b/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java
index 0e111d42061..c54c9e7930e 100644
--- a/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java
+++ b/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java
@@ -14,15 +14,24 @@ public final class BinaryView implements Inspector {
 
     private final byte[] data;
     private final SymbolTable names;
-    private final DecodeIndex index;
+    private final long[] index;
     private final int self;
 
-    private BinaryView(byte[] data, SymbolTable names, DecodeIndex index, int self) {
+    private BinaryView(byte[] data, SymbolTable names, long[] index, int self) {
         this.data = data;
         this.names = names;
         this.index = index;
         this.self = self;
     }
+    private int byte_offset(int idx) {
+        return (int)(index[idx] >> 33) & 0x7fff_ffff;
+    }
+    private int first_child(int idx) {
+        return (int)(index[idx] >> 2) & 0x7fff_ffff;
+    }
+    private int ext_bits(int idx) {
+        return (int)index[idx] & 0x3;
+    }
     private int peek_cmpr_int(int idx) {
         long next = data[idx++];
         long value = (next & 0x7f);
@@ -92,8 +101,8 @@ public final class BinaryView implements Inspector {
     }
     private Inspector find_field(int pos, int len, int sym) {
         for (int i = 0; i < len; ++i) {
-            int idx = index.getByteOffset(pos + i);
-            if (peek_cmpr_int(idx - (index.getExtBits(pos + i) + 1)) == sym) {
+            int idx = byte_offset(pos + i);
+            if (peek_cmpr_int(idx - (ext_bits(pos + i) + 1)) == sym) {
                 return new BinaryView(data, names, index, pos + i);
             }
         }
@@ -102,110 +111,110 @@ public final class BinaryView implements Inspector {
 
     @Override public boolean valid() { return true; }
     @Override public void ifValid(Consumer<Inspector> consumer) { consumer.accept(this); }
-    @Override public Type type() { return decode_type(data[index.getByteOffset(self)]); }
+    @Override public Type type() { return decode_type(data[byte_offset(self)]); }
     @Override public int children() {
         return switch (type()) {
-            case OBJECT, ARRAY -> extract_children(index.getByteOffset(self));
+            case OBJECT, ARRAY -> extract_children(byte_offset(self));
             default -> 0;
         };
     }
     @Override public int entries() {
         return switch (type()) {
-            case ARRAY -> extract_children(index.getByteOffset(self));
+            case ARRAY -> extract_children(byte_offset(self));
             default -> 0;
         };
     }
     @Override public int fields() {
         return switch (type()) {
-            case OBJECT -> extract_children(index.getByteOffset(self));
+            case OBJECT -> extract_children(byte_offset(self));
             default -> 0;
         };
     }
     @Override public boolean asBool() {
         return switch (type()) {
-            case BOOL -> (decode_meta(data[index.getByteOffset(self)]) != 0);
+            case BOOL -> (decode_meta(data[byte_offset(self)]) != 0);
             default -> false;
         };
     }
     @Override public long asLong() {
         return switch (type()) {
-            case LONG -> extract_long(index.getByteOffset(self));
-            case DOUBLE -> (long)extract_double(index.getByteOffset(self));
+            case LONG -> extract_long(byte_offset(self));
+            case DOUBLE -> (long)extract_double(byte_offset(self));
             default -> 0;
         };
     }
     @Override public double asDouble() {
         return switch (type()) {
-            case LONG -> extract_long(index.getByteOffset(self));
-            case DOUBLE -> extract_double(index.getByteOffset(self));
+            case LONG -> extract_long(byte_offset(self));
+            case DOUBLE -> extract_double(byte_offset(self));
             default -> 0.0;
         };
     }
     @Override public String asString() {
         return switch (type()) {
-            case STRING -> extract_string(index.getByteOffset(self));
+            case STRING -> extract_string(byte_offset(self));
             default -> Value.emptyString;
         };
     }
     @Override public byte[] asUtf8() {
         return switch (type()) {
-            case STRING -> extract_bytes(index.getByteOffset(self));
+            case STRING -> extract_bytes(byte_offset(self));
             default -> Value.emptyData;
         };
     }
     @Override public byte[] asData() {
         return switch (type()) {
-            case DATA -> extract_bytes(index.getByteOffset(self));
+            case DATA -> extract_bytes(byte_offset(self));
             default -> Value.emptyData;
         };
     }
     @Override public void accept(Visitor v) {
         switch (type()) {
             case NIX:    v.visitNix(); break;
-            case BOOL:   v.visitBool(decode_meta(data[index.getByteOffset(self)]) != 0); break;
-            case LONG:   v.visitLong(extract_long(index.getByteOffset(self))); break;
-            case DOUBLE: v.visitDouble(extract_double(index.getByteOffset(self))); break;
-            case STRING: v.visitString(extract_bytes(index.getByteOffset(self))); break;
-            case DATA:   v.visitData(extract_bytes(index.getByteOffset(self))); break;
+            case BOOL:   v.visitBool(decode_meta(data[byte_offset(self)]) != 0); break;
+            case LONG:   v.visitLong(extract_long(byte_offset(self))); break;
+            case DOUBLE: v.visitDouble(extract_double(byte_offset(self))); break;
+            case STRING: v.visitString(extract_bytes(byte_offset(self))); break;
+            case DATA:   v.visitData(extract_bytes(byte_offset(self))); break;
             case ARRAY:  v.visitArray(this); break;
             case OBJECT: v.visitObject(this); break;
             default: throw new RuntimeException("should not be reached");
         }
     }
     @Override public void traverse(ArrayTraverser at) {
-        int pos = index.getFirstChild(self);
+        int pos = first_child(self);
         int len = entries();
         for (int i = 0; i < len; ++i) {
             at.entry(i, new BinaryView(data, names, index, pos + i));
         }
     }
     @Override public void traverse(ObjectSymbolTraverser ot) {
-        int pos = index.getFirstChild(self);
+        int pos = first_child(self);
         int len = fields();
         for (int i = 0; i < len; ++i) {
-            int sym = peek_cmpr_int(index.getByteOffset(pos + i) - (index.getExtBits(pos + i) + 1));
+            int sym = peek_cmpr_int(byte_offset(pos + i) - (ext_bits(pos + i) + 1));
             ot.field(sym, new BinaryView(data, names, index, pos + i));
         }
     }
     @Override public void traverse(ObjectTraverser ot) {
-        int pos = index.getFirstChild(self);
+        int pos = first_child(self);
         int len = fields();
         for (int i = 0; i < len; ++i) {
-            int sym = peek_cmpr_int(index.getByteOffset(pos + i) - (index.getExtBits(pos + i) + 1));
+            int sym = peek_cmpr_int(byte_offset(pos + i) - (ext_bits(pos + i) + 1));
             ot.field(names.inspect(sym), new BinaryView(data, names, index, pos + i));
         }
     }
     @Override public Inspector entry(int idx) {
         int limit = entries();
         if (idx >= 0 && idx < limit) {
-            return new BinaryView(data, names, index, index.getFirstChild(self) + idx);
+            return new BinaryView(data, names, index, first_child(self) + idx);
         }
         return NixValue.invalid();
     }
     @Override public Inspector field(int sym) {
         int limit = fields();
         if (limit > 0 && sym != SymbolTable.INVALID) {
-            return find_field(index.getFirstChild(self), limit, sym);
+            return find_field(first_child(self), limit, sym);
         }
         return NixValue.invalid();
     }
@@ -214,7 +223,7 @@ public final class BinaryView implements Inspector {
         if (limit > 0) {
             int sym = names.lookup(name);
             if (sym != SymbolTable.INVALID) {
-                return find_field(index.getFirstChild(self), limit, sym);
+                return find_field(first_child(self), limit, sym);
             }
         }
         return NixValue.invalid();
@@ -243,11 +252,11 @@ public final class BinaryView implements Inspector {
                 break; }
             case ARRAY: {
                 int size = input.read_size(meta);
-                if (size > input.getBacking().length - index.size()) {
+                int firstChild = index.tryReserveChildren(size, self + 1, input.getPosition());
+                if (firstChild < 0) {
                     input.fail("decode index too big");
                     return;
                 }
-                int firstChild = index.reserve(size);
                 index.set(self, pos, firstChild, extBits);
                 for (int i = 0; i < size; ++i) {
                     buildIndex(input, index, firstChild + i, 0);
@@ -255,11 +264,11 @@ public final class BinaryView implements Inspector {
                 break; }
             case OBJECT: {
                 int size = input.read_size(meta);
-                if (size > input.getBacking().length - index.size()) {
+                int firstChild = index.tryReserveChildren(size, self + 1, input.getPosition());
+                if (firstChild < 0) {
                     input.fail("decode index too big");
                     return;
                 }
-                int firstChild = index.reserve(size);
                 index.set(self, pos, firstChild, extBits);
                 for (int i = 0; i < size; ++i) {
                     int childExtBits = input.skip_cmpr_int();
@@ -276,13 +285,13 @@ public final class BinaryView implements Inspector {
 
     static Inspector inspectImpl(BufferedInput input) {
         var names = new SymbolTable();
-        var index = new DecodeIndex();
         BinaryDecoder.decodeSymbolTable(input, names);
-        buildIndex(input, index, index.reserve(1), 0);
+        var index = new DecodeIndex(input.getBacking().length, input.getPosition());
+        buildIndex(input, index, 0, 0);
         if (input.failed()) {
             return NixValue.invalid();
         }
-        return new BinaryView(input.getBacking(), names, index, 0);
+        return new BinaryView(input.getBacking(), names, index.getBacking(), 0);
     }
 
     public static Inspector inspect(byte[] data) {
@@ -304,4 +313,13 @@ public final class BinaryView implements Inspector {
     static double extract_double_for_testing(byte[] data, int idx) {
         return new BinaryView(data, null, null, -1).extract_double(idx);
     }
+    static int byte_offset_for_testing(DecodeIndex index, int idx) {
+        return new BinaryView(null, null, index.getBacking(), -1).byte_offset(idx);
+    }
+    static int first_child_for_testing(DecodeIndex index, int idx) {
+        return new BinaryView(null, null, index.getBacking(), -1).first_child(idx);
+    }
+    static int ext_bits_for_testing(DecodeIndex index, int idx) {
+        return new BinaryView(null, null, index.getBacking(), -1).ext_bits(idx);
+    }
 }
diff --git a/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java b/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java
index 17c7a86730e..5df24154a08 100644
--- a/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java
+++ b/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java
@@ -6,23 +6,46 @@ package com.yahoo.slime;
  * 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;
+    private long[] data;
+    private int reserved;
+    private final int totalSize;
+    private final int rootOffset;
+
+    private int binarySize() { return totalSize - rootOffset; }
+
+    private int adjustSize(int minSize, int maxSize, int cnt, int byteOffset) {
+        double density = (double)cnt / (double)(byteOffset - rootOffset);
+        double estSize = 1.1 * density * binarySize();
+        double expSize = 1.25 * data.length;
+        double wantedSize = (estSize > expSize) ? estSize : expSize;
+        if (wantedSize < minSize) {
+            return minSize;
         }
-        return capacity;
+        if (wantedSize > maxSize) {
+            return maxSize;
+        }
+        return (int)wantedSize;
+    }
+
+    DecodeIndex(int totalSize, int rootOffset) {
+        this.totalSize = totalSize;
+        this.rootOffset = rootOffset;
+        int initialCapacity = Math.max(16, binarySize() / 24);
+        data = new long[initialCapacity];
+        reserved = 1;
     }
 
-    int reserve(int n) {
+    long[] getBacking() { return data; }
+
+    int tryReserveChildren(int n, int cnt, int byteOffset) {
         int offset = reserved;
-        if (reserved + n > data.length) {
+        if (n > data.length - reserved) {
+            final int maxSize = (totalSize - byteOffset) + cnt;
+            if (n > maxSize - reserved) {
+                return -1; // error; too much space requested
+            }
             long[] old = data;
-            data = new long[adjustSize(reserved + n)];
+            data = new long[adjustSize(reserved + n, maxSize, cnt, byteOffset)];
             System.arraycopy(old, 0, data, 0, reserved);
         }
         reserved += n;
@@ -30,22 +53,11 @@ final class DecodeIndex {
     }
 
     int size() { return reserved; }
+    int capacity() { return data.length; }
 
     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/BinaryViewTest.java b/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java
index 920a25b96c9..c45d7a9c59e 100644
--- a/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java
+++ b/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java
@@ -343,7 +343,7 @@ public class BinaryViewTest {
     }
 
     @Test public void testDecodeIndexOverflowArray() {
-        byte[] data = { 0, encode_type_and_meta(Type.ARRAY.ID, 4) };
+        byte[] data = { 0, encode_type_and_meta(Type.ARRAY.ID, 20) };
         var input = new BufferedInput(data);
         var view = BinaryView.inspectImpl(input);
         assertFalse(view.valid());
@@ -352,7 +352,7 @@ public class BinaryViewTest {
     }
 
     @Test public void testDecodeIndexOverflowObject() {
-        byte[] data = { 0, encode_type_and_meta(Type.OBJECT.ID, 4) };
+        byte[] data = { 0, encode_type_and_meta(Type.OBJECT.ID, 20) };
         var input = new BufferedInput(data);
         var view = BinaryView.inspectImpl(input);
         assertFalse(view.valid());
diff --git a/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java
index 223701fa2fd..c34a718d2bb 100644
--- a/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java
+++ b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java
@@ -3,83 +3,236 @@ package com.yahoo.slime;
 
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+import static com.yahoo.slime.BinaryView.byte_offset_for_testing;
+import static com.yahoo.slime.BinaryView.first_child_for_testing;
+import static com.yahoo.slime.BinaryView.ext_bits_for_testing;
 
 public class DecodeIndexTest {
 
+    int checkCapacity(DecodeIndex index, int oldCapacity) {
+        int capacity = index.capacity();
+        if (oldCapacity == -1) {
+            System.out.println("DecodeIndex initial capacity " + capacity);
+        } else if (capacity != oldCapacity) {
+            System.out.println("DecodeIndex capacity increased to " + capacity);
+        }
+        return capacity;
+    }
+
     @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);
+        DecodeIndex index = new DecodeIndex(100, 10);
+        assertEquals(1, index.size());
+        int capacity = checkCapacity(index, -1);
+        int root = 0;
+        capacity = checkCapacity(index, capacity);
+        int val2 = index.tryReserveChildren(3, 1, 15);
+        capacity = checkCapacity(index, capacity);
+        int val3 = index.tryReserveChildren(2, 2, 20);
+        capacity = checkCapacity(index, capacity);
         assertEquals(1, val2);
         assertEquals(4, val3);
         assertEquals(6, index.size());
-        index.set(val1 + 0,    0, val2, 0);
+        index.set(root,        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));
+            assertEquals(i * 100, byte_offset_for_testing(index, i));
             if (i == 0) {
-                assertEquals(1, index.getFirstChild(i));
+                assertEquals(1, first_child_for_testing(index, i));
             } else if (i == 2) {
-                assertEquals(4, index.getFirstChild(i));
+                assertEquals(4, first_child_for_testing(index, i));
             } else {
-                assertEquals(0, index.getFirstChild(i));
+                assertEquals(0, first_child_for_testing(index, i));
             }
             if (i < 4) {
-                assertEquals(i, index.getExtBits(i));
+                assertEquals(i, ext_bits_for_testing(index, i));
             } else {
-                assertEquals(0, index.getExtBits(i));
+                assertEquals(0, ext_bits_for_testing(index, i));
             }
         }
     }
 
     @Test
     public void testManyValues() {
-        DecodeIndex index = new DecodeIndex();
         int outer = 47;
         int inner = 73;
-        int expectOffset = 0;
+        int symSize = 128;
+        int bytesPerValue = 5;
+        DecodeIndex index = new DecodeIndex(symSize + inner * outer * bytesPerValue, symSize);
+        int capacity = checkCapacity(index, -1);
+        int indexOffset = 1;
+        int binaryOffset = symSize + bytesPerValue;
+        int expectOffset = 1;
         for (int i = 0; i < outer; i++) {
-            int offset = index.reserve(inner);
+            int offset = index.tryReserveChildren(inner, indexOffset, binaryOffset);
+            capacity = checkCapacity(index, capacity);
             assertEquals(expectOffset, offset);
             expectOffset += inner;
             for (int j = 0; j < inner; j++) {
                 index.set(offset + j, (i * j), (i + j), (j & 3));
+                ++indexOffset;
+                binaryOffset += bytesPerValue;
             }
         }
-        assertEquals(inner * outer, expectOffset);
-        assertEquals(inner * outer, index.size());
+        assertEquals(1 + inner * outer, expectOffset);
+        assertEquals(1 + 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));
+                int offset = 1 + i * inner + j;
+                assertEquals(i * j, byte_offset_for_testing(index, offset));
+                assertEquals(i + j, first_child_for_testing(index, offset));
+                assertEquals(j & 3, ext_bits_for_testing(index, offset));
             }
         }
     }
 
     @Test
     public void testOverflowNoBleed() {
-        DecodeIndex index = new DecodeIndex();
-        index.reserve(3);
+        DecodeIndex index = new DecodeIndex(100, 10);
+        index.tryReserveChildren(2, 1, 20);
+        assertEquals(3, index.size());
         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));
+        assertEquals(0x7fff_ffff, byte_offset_for_testing(index, 0));
+        assertEquals(0, byte_offset_for_testing(index, 1));
+        assertEquals(0, byte_offset_for_testing(index, 2));
+        assertEquals(0, first_child_for_testing(index, 0));
+        assertEquals(0x7fff_ffff, first_child_for_testing(index, 1));
+        assertEquals(0, first_child_for_testing(index, 2));
+        assertEquals(0, ext_bits_for_testing(index, 0));
+        assertEquals(0, ext_bits_for_testing(index, 1));
+        assertEquals(3, ext_bits_for_testing(index, 2));
+    }
+
+    @Test
+    public void testMinimalInitialCapacity() {
+        DecodeIndex index = new DecodeIndex(2, 1);
+        assertEquals(16, index.capacity());
+    }
+
+    @Test
+    public void testInitialCapacityEstimate() {
+        DecodeIndex index = new DecodeIndex((33 * 24) + 167, 167);
+        assertEquals(33, index.capacity());
+    }
+
+    void assertWithinRange(int low, int high, int actual) {
+        if (actual >= low && actual <= high) {
+            System.out.println("value " + actual + " in range [" + low + "," + high + "]");
+        } else {
+            fail("value " + actual + " not in range [" + low + "," + high + "]");
+        }
+    }
+
+    void assertGreater(int limit, int actual) {
+        if (actual > limit) {
+            System.out.println("value " + actual + " is greater than " + limit);
+        } else {
+            fail("value " + actual + " is not greater than " + limit);
+        }
+    }
+
+    void assertLess(int limit, int actual) {
+        if (actual < limit) {
+            System.out.println("value " + actual + " is less than " + limit);
+        } else {
+            fail("value " + actual + " is not less than " + limit);
+        }
+    }
+
+    DecodeIndex prepareIndex(int symSize, int numValues) {
+        DecodeIndex index = new DecodeIndex((numValues * 24) + symSize, symSize);
+        assertEquals(1, index.tryReserveChildren(numValues - 1, 1, symSize + 24));
+        assertEquals(numValues, index.size());
+        assertEquals(numValues, index.capacity());
+        return index;
+    }
+
+    @Test
+    public void testDensityBasedCapacityEstimate() {
+        var index = prepareIndex(167, 33);
+        double exp = 1.25 * index.capacity();
+        assertEquals(33, index.tryReserveChildren(10, 20, 167 + (20 * 4)));
+        int doneCnt = 20;
+        double bytesPerObject = 4.0;
+        int pendingData = (33 * 24) - (20 * 4);
+        double est = (doneCnt + pendingData / bytesPerObject);
+        int maxSize = doneCnt + pendingData;
+        assertGreater((int)(exp * 1.05), index.capacity());
+        assertWithinRange((int)(1.05 * est), (int)(1.15 * est), index.capacity());
+        assertLess(maxSize, index.capacity());
+    }
+
+    @Test
+    public void testExpCapacityGrowth() {
+        var index = prepareIndex(167, 33);
+        double exp = 1.25 * index.capacity();
+        assertEquals(33, index.tryReserveChildren(1, 20, 167 + (20 * 32)));
+        int doneCnt = 20;
+        double bytesPerObject = 32.0;
+        int pendingData = (33 * 24) - (20 * 32);
+        double est = (doneCnt + pendingData / bytesPerObject);
+        int maxSize = doneCnt + pendingData;
+        assertWithinRange((int)(0.95 * exp), (int)(1.05 * exp), index.capacity());
+        assertGreater((int)(est * 1.15), index.capacity());
+        assertLess(maxSize, index.capacity());
+    }
+
+    @Test
+    public void testMinCapacityGrowth() {
+        var index = prepareIndex(167, 33);
+        double exp = 1.25 * index.capacity();
+        assertEquals(33, index.tryReserveChildren(20, 20, 167 + (20 * 32)));
+        int doneCnt = 20;
+        double bytesPerObject = 32.0;
+        int pendingData = (33 * 24) - (20 * 32);
+        double est = (doneCnt + pendingData / bytesPerObject);
+        int maxSize = doneCnt + pendingData;
+        assertGreater((int)(exp * 1.05), index.capacity());
+        assertGreater((int)(est * 1.15), index.capacity());
+        assertEquals(33 + 20, index.capacity());
+        assertLess(maxSize, index.capacity());
+    }
+
+    @Test
+    public void testMaxCapacityGrowth() {
+        var index = prepareIndex(167, 33);
+        double exp = 1.25 * index.capacity();
+        assertEquals(33, index.tryReserveChildren(1, 32, 167 + (33 * 24) - 3));
+        int minSize = 33 + 1;
+        int maxSize = 32 + 3;
+        assertLess((int)(exp * 0.95), index.capacity());
+        assertGreater(minSize, index.capacity());
+        assertEquals(maxSize, index.capacity());
+    }
+
+    @Test
+    public void testMinMaxCapacityGrowth() {
+        var index = prepareIndex(167, 33);
+        assertEquals(-1, index.tryReserveChildren(5, 32, 167 + (33 * 24) - 3));
+        assertEquals(33, index.capacity());
+    }
+
+    @Test
+    public void testExpNanCapacityGrowth() {
+        var index = prepareIndex(167, 33);
+        double exp = 1.25 * index.capacity();
+        assertEquals(33, index.tryReserveChildren(1, 0, 167));
+        assertWithinRange((int)(0.95 * exp), (int)(1.05 * exp), index.capacity());
+    }
+
+    @Test
+    public void testMaxInfCapacityGrowth() {
+        var index = prepareIndex(167, 17);
+        double exp = 1.25 * index.capacity();
+        assertEquals(17, index.tryReserveChildren(1, 10, 167));
+        int maxSize = 10 + (17 * 24);
+        assertEquals(maxSize, index.capacity());
     }
 }