#269 Initial iterator performance enhancements and testing.

lmdbjava · stroomdev66 · Mar 6, 2025 · Mar 6, 2025 · Mar 6, 2025 · Mar 6, 2025
commit d6e0ca1d9f7bb4336c3a2d85c7b3a9d47e007e3d
diff --git a/src/main/java/org/lmdbjava/BufferProxy.java b/src/main/java/org/lmdbjava/BufferProxy.java
@@ -15,15 +15,16 @@
  */
 package org.lmdbjava;
 
+import jnr.ffi.Pointer;
+
+import java.util.Comparator;
+
 import static java.lang.Long.BYTES;
 import static org.lmdbjava.DbiFlags.MDB_INTEGERKEY;
 import static org.lmdbjava.DbiFlags.MDB_UNSIGNEDKEY;
 import static org.lmdbjava.MaskedFlag.isSet;
 import static org.lmdbjava.MaskedFlag.mask;
 
-import java.util.Comparator;
-import jnr.ffi.Pointer;
-
 /**
  * The strategy for mapping memory address to a given buffer type.
  *
@@ -35,17 +36,26 @@
  */
 public abstract class BufferProxy<T> {
 
-  /** Size of a <code>MDB_val</code> pointer in bytes. */
+  /**
+   * Size of a <code>MDB_val</code> pointer in bytes.
+   */
   protected static final int MDB_VAL_STRUCT_SIZE = BYTES * 2;
 
-  /** Offset from a pointer of the <code>MDB_val.mv_data</code> field. */
+  /**
+   * Offset from a pointer of the <code>MDB_val.mv_data</code> field.
+   */
   protected static final int STRUCT_FIELD_OFFSET_DATA = BYTES;
 
-  /** Offset from a pointer of the <code>MDB_val.mv_size</code> field. */
+  /**
+   * Offset from a pointer of the <code>MDB_val.mv_size</code> field.
+   */
   protected static final int STRUCT_FIELD_OFFSET_SIZE = 0;
 
-  /** Explicitly-defined default constructor to avoid warnings. */
-  protected BufferProxy() {}
+  /**
+   * Explicitly-defined default constructor to avoid warnings.
+   */
+  protected BufferProxy() {
+  }
 
   /**
    * Allocate a new buffer suitable for passing to {@link #out(java.lang.Object, jnr.ffi.Pointer)}.
@@ -82,8 +92,8 @@ protected Comparator<T> getComparator(DbiFlags... flags) {
     final int intFlag = mask(flags);
 
     return isSet(intFlag, MDB_INTEGERKEY) || isSet(intFlag, MDB_UNSIGNEDKEY)
-        ? getUnsignedComparator()
-        : getSignedComparator();
+            ? getUnsignedComparator()
+            : getSignedComparator();
   }
 
   /**
@@ -105,7 +115,7 @@ protected Comparator<T> getComparator(DbiFlags... flags) {
    * will have been created by end users, not {@link #allocate()}.
    *
    * @param buffer the buffer to write to <code>MDB_val</code>
-   * @param ptr the pointer to the <code>MDB_val</code>
+   * @param ptr    the pointer to the <code>MDB_val</code>
    * @return a transient pointer that must be kept alive, or null if none
    */
   protected abstract Pointer in(T buffer, Pointer ptr);
@@ -114,8 +124,8 @@ protected Comparator<T> getComparator(DbiFlags... flags) {
    * Called when the <code>MDB_val</code> should be set to reflect the passed buffer.
    *
    * @param buffer the buffer to write to <code>MDB_val</code>
-   * @param size the buffer size to write to <code>MDB_val</code>
-   * @param ptr the pointer to the <code>MDB_val</code>
+   * @param size   the buffer size to write to <code>MDB_val</code>
+   * @param ptr    the pointer to the <code>MDB_val</code>
    * @return a transient pointer that must be kept alive, or null if none
    */
   protected abstract Pointer in(T buffer, int size, Pointer ptr);
@@ -125,7 +135,7 @@ protected Comparator<T> getComparator(DbiFlags... flags) {
    * to reflect the new <code>MDB_val</code>.
    *
    * @param buffer the buffer to write to <code>MDB_val</code>
-   * @param ptr the pointer to the <code>MDB_val</code>
+   * @param ptr    the pointer to the <code>MDB_val</code>
    * @return the buffer for <code>MDB_val</code>
    */
   protected abstract T out(T buffer, Pointer ptr);
@@ -138,4 +148,22 @@ protected Comparator<T> getComparator(DbiFlags... flags) {
   final KeyVal<T> keyVal() {
     return new KeyVal<>(this);
   }
+
+  /**
+   * Test if a supplied buffer contains the supplied prefix buffer.
+   *
+   * @param buffer       The buffer to test.
+   * @param prefixBuffer The prefix to find.
+   * @return True if the key contains the prefix;
+   */
+  abstract boolean containsPrefix(T buffer, T prefixBuffer);
+
+  /**
+   * Make a buffer that is one bit greater than the supplied buffer by incrementing the least significant byte that is
+   * not already 255. This is useful in situations where we want to move past a key range before iterating backward.
+   *
+   * @param buffer The buffer to increment.
+   * @return The incremented buffer or null if the buffer is already at max value.
+   */
+  abstract T incrementLeastSignificantByte(T buffer);
 }
diff --git a/src/main/java/org/lmdbjava/ByteArrayProxy.java b/src/main/java/org/lmdbjava/ByteArrayProxy.java
@@ -15,14 +15,15 @@
  */
 package org.lmdbjava;
 
-import static java.lang.Math.min;
-import static java.util.Objects.requireNonNull;
-import static org.lmdbjava.Library.RUNTIME;
+import jnr.ffi.Pointer;
+import jnr.ffi.provider.MemoryManager;
 
 import java.util.Arrays;
 import java.util.Comparator;
-import jnr.ffi.Pointer;
-import jnr.ffi.provider.MemoryManager;
+
+import static java.lang.Math.min;
+import static java.util.Objects.requireNonNull;
+import static org.lmdbjava.Library.RUNTIME;
 
 /**
  * Byte array proxy.
@@ -31,15 +32,18 @@
  */
 public final class ByteArrayProxy extends BufferProxy<byte[]> {
 
-  /** The byte array proxy. Guaranteed to never be null. */
+  /**
+   * The byte array proxy. Guaranteed to never be null.
+   */
   public static final BufferProxy<byte[]> PROXY_BA = new ByteArrayProxy();
 
   private static final MemoryManager MEM_MGR = RUNTIME.getMemoryManager();
 
   private static final Comparator<byte[]> signedComparator = ByteArrayProxy::compareArraysSigned;
   private static final Comparator<byte[]> unsignedComparator = ByteArrayProxy::compareArrays;
 
-  private ByteArrayProxy() {}
+  private ByteArrayProxy() {
+  }
 
   /**
    * Lexicographically compare two byte arrays.
@@ -68,6 +72,32 @@ public static int compareArrays(final byte[] o1, final byte[] o2) {
     return o1.length - o2.length;
   }
 
+  /**
+   * Lexicographically compare two byte arrays up to a max length.
+   *
+   * @param o1        left operand (required)
+   * @param o2        right operand (required)
+   * @param minLength The length to compare (required)
+   * @return as specified by {@link Comparable} interface
+   */
+  public static int compareArrays(final byte[] o1, final byte[] o2, final int minLength) {
+    requireNonNull(o1);
+    requireNonNull(o2);
+    if (o1 == o2) {
+      return 0;
+    }
+    for (int i = 0; i < minLength; i++) {
+      final int lw = Byte.toUnsignedInt(o1[i]);
+      final int rw = Byte.toUnsignedInt(o2[i]);
+      final int result = Integer.compareUnsigned(lw, rw);
+      if (result != 0) {
+        return result;
+      }
+    }
+
+    return 0;
+  }
+
   /**
    * Compare two byte arrays.
    *
@@ -137,4 +167,38 @@ protected byte[] out(final byte[] buffer, final Pointer ptr) {
     pointer.get(0, bytes, 0, size);
     return bytes;
   }
+
+
+  @Override
+  boolean containsPrefix(final byte[] buffer, final byte[] prefixBuffer) {
+    if (buffer.length < prefixBuffer.length) {
+      return false;
+    }
+
+    // We don't care about signed or unsigned since we are checking for equality.
+    return compareArrays(buffer, prefixBuffer, prefixBuffer.length) == 0;
+  }
+
+  @Override
+  byte[] incrementLeastSignificantByte(final byte[] buffer) {
+    if (buffer == null || buffer.length == 0) {
+      return null;
+    }
+
+    // Start from the least significant byte (closest to limit)
+    for (int i = buffer.length - 1; i >= 0; i--) {
+      final byte b = buffer[i];
+
+      // Check if byte is not at max unsigned value (0xFF = 255 = -1 in signed)
+      if (b != (byte) 0xFF) {
+        final byte[] oneBigger = new byte[buffer.length];
+        System.arraycopy(buffer, 0, oneBigger, 0, buffer.length);
+        oneBigger[i] = (byte) (b + 1);
+        return oneBigger;
+      }
+    }
+
+    // All bytes are at maximum value
+    return null;
+  }
 }
diff --git a/src/main/java/org/lmdbjava/ByteBufProxy.java b/src/main/java/org/lmdbjava/ByteBufProxy.java
@@ -17,12 +17,14 @@
 
 import static io.netty.buffer.PooledByteBufAllocator.DEFAULT;
 import static java.lang.Class.forName;
+import static java.nio.ByteOrder.LITTLE_ENDIAN;
 import static java.util.Objects.requireNonNull;
 import static org.lmdbjava.UnsafeAccess.UNSAFE;
 
 import io.netty.buffer.ByteBuf;
 import io.netty.buffer.PooledByteBufAllocator;
 import java.lang.reflect.Field;
+import java.nio.ByteBuffer;
 import java.util.Comparator;
 import jnr.ffi.Pointer;
 
@@ -163,4 +165,50 @@
     buffer.clear().writerIndex((int) size);
     return buffer;
   }
+
+  @Override
+  boolean containsPrefix(final ByteBuf buffer, final ByteBuf prefixBuffer) {
+    if (buffer.capacity() < prefixBuffer.capacity()) {
+      return false;
+    }
+    return buffer.slice(0, prefixBuffer.capacity()).compareTo(prefixBuffer) == 0;
+  }
+
+  @Override
+  ByteBuf incrementLeastSignificantByte(final ByteBuf buffer) {
+    if (buffer == null || buffer.capacity() == 0) {
+      return null;
+    }
+
+    // TODO : Since endianness isn't a state for Netty ByteBuf we might not be able to do this.
+    if (LITTLE_ENDIAN.equals(buffer.order())) {
+      // Start from the least significant byte (closest to start)
+      for (int i = 0; i < buffer.capacity(); i++) {
+        final byte b = buffer.getByte(i);
+
+        // Check if byte is not at max unsigned value (0xFF = 255 = -1 in signed)
+        if (b != (byte) 0xFF) {
+          final ByteBuf oneBigger = buffer.copy();
+          oneBigger.setByte(i, (byte) (b + 1));
+          return oneBigger;
+        }
+      }
+
+    } else {
+      // Start from the least significant byte (closest to limit)
+      for (int i = buffer.capacity() - 1; i >= 0; i--) {
+        final byte b = buffer.getByte(i);
+
+        // Check if byte is not at max unsigned value (0xFF = 255 = -1 in signed)
+        if (b != (byte) 0xFF) {
+          final ByteBuf oneBigger = buffer.copy();
+          oneBigger.setByte(i, (byte) (b + 1));
+          return oneBigger;
+        }
+      }
+    }
+
+    // All bytes are at maximum value
+    return null;
+  }
 }