[GitHub] [qpid-proton-j] gemmellr commented on a change in pull request #36: PROTON-2178 Implement efficient search of encoded Symbol on ReadableBuffer

[GitBox <gi...@apache.org>]

gemmellr commented on a change in pull request #36: PROTON-2178 Implement efficient search of encoded Symbol on ReadableBuffer
URL: https://github.com/apache/qpid-proton-j/pull/36#discussion_r379357315
 
 

 ##########
 File path: proton-j/src/main/java/org/apache/qpid/proton/amqp/Symbol.java
 ##########
 @@ -60,6 +66,82 @@ public CharSequence subSequence(int beginIndex, int endIndex)
         return _underlying.subSequence(beginIndex, endIndex);
     }
 
+    /**
+     * https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm jump table
+     */
+    private static int[] createJumpTable(byte[] needle) {
+        final int[] jumpTable = new int[needle.length + 1];
+        int j = 0;
+        for (int i = 1; i < needle.length; i++) {
+            while (j > 0 && needle[j] != needle[i]) {
+                j = jumpTable[j];
+            }
+            if (needle[j] == needle[i]) {
+                j++;
+            }
+            jumpTable[i + 1] = j;
+        }
+        for (int i = 1; i < jumpTable.length; i++) {
+            if (jumpTable[i] != 0) {
+                return jumpTable;
+            }
+        }
+        // optimization over the original algorithm: it would save from accessing any jump table
+        return null;
+    }
+
+    private int[] racyGerOrCreateJumpTable() {
+        int[] jumpTable = this._jumpTable;
+        if (jumpTable == NOT_INITIALIZED_JUMP_TABLE) {
+            jumpTable = createJumpTable(this._underlyingBytes);
+            _jumpTable = jumpTable;
+        }
+        return jumpTable;
+    }
+
+    /**
+     * Returns the index on buffer of the first encoded occurrence of this {@code symbol} within the specified range.<br>
+     * If none is found, then {@code -1} is returned.
+     *
+     * @param buffer the buffer where to search in
+     * @return the index of the first occurrence of this symbol or {@code -1} if it won't occur.
+     * <p>
+     * @throws IllegalArgumentException if any of the indexes of the specified range is negative
+     */
+    public int searchFirst(ReadableBuffer buffer, int from, int to)
+    {
+        Objects.requireNonNull(buffer, "buffer cannot be null");
+        if (from < 0 || to < 0)
+        {
+            throw new IllegalArgumentException("range indexes cannot be negative!");
+        }
+        int j = 0;
+        final int[] jumpTable = racyGerOrCreateJumpTable();
+        final byte[] needle = _underlyingBytes;
+        final long length = to - from;
 
 Review comment:
   Given the other checking above, should it perhaps also validate that to <= from?

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@qpid.apache.org
For additional commands, e-mail: dev-help@qpid.apache.org