[
https://issues.apache.org/jira/browse/PROTON-2178?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17068849#comment-17068849
]
ASF GitHub Bot commented on PROTON-2178:
----------------------------------------
gemmellr commented on pull request #36: PROTON-2178 Implement efficient search
of encoded Symbol on ReadableBuffer
URL: https://github.com/apache/qpid-proton-j/pull/36#discussion_r399379661
##########
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;
+ final ReadableBuffer haystack = buffer;
+ final int needleLength = needle.length;
+ for (int i = 0; i < length; i++)
Review comment:
Would initialising i to 'from' rather than 0 simplify things? (Plus other
adjustments accordingly, e.g rename i to index, to rather than length)
----------------------------------------------------------------
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:
[email protected]
> Implement efficient search of encoded Symbol on ReadableBuffer
> --------------------------------------------------------------
>
> Key: PROTON-2178
> URL: https://issues.apache.org/jira/browse/PROTON-2178
> Project: Qpid Proton
> Issue Type: New Feature
> Components: proton-j
> Affects Versions: proton-c-0.30.0
> Reporter: Francesco Nigro
> Priority: Minor
> Labels: perf
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
