This is an automated email from the ASF dual-hosted git repository.
fanningpj pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/pekko.git
The following commit(s) were added to refs/heads/main by this push:
new 6f3de3b50a ByteString lastIndexOfSlice (#2855)
6f3de3b50a is described below
commit 6f3de3b50af01d525d0f04397fd3c2480b9fcf7c
Author: PJ Fanning <[email protected]>
AuthorDate: Mon Apr 13 13:02:10 2026 +0200
ByteString lastIndexOfSlice (#2855)
* Add lastIndexOfSlice to ByteString
Agent-Logs-Url:
https://github.com/pjfanning/incubator-pekko/sessions/5bb99eb9-ef1a-4d68-a4f1-1d556423f93e
Co-authored-by: pjfanning <[email protected]>
Address code review: use length-1 default end, clarify unrolledLastIndexOf
comment
Agent-Logs-Url:
https://github.com/pjfanning/incubator-pekko/sessions/5bb99eb9-ef1a-4d68-a4f1-1d556423f93e
Co-authored-by: pjfanning <[email protected]>
merge issue
* Update ByteStringSpec.scala
* Create ByteString_lastIndexOfSlice_Benchmark.scala
* reorder code
* scalafmt
Update ByteString.scala
* add extra tests and fix issues in indexOfSlice
* Add edge case tests for indexOfSlice/lastIndexOfSlice; fix empty-slice
boundary bugs
Agent-Logs-Url:
https://github.com/pjfanning/incubator-pekko/sessions/8d88160e-6241-4825-a6e9-0c7ad0e5ac56
Co-authored-by: pjfanning <[email protected]>
* scalafmt
---------
Co-authored-by: copilot-swe-agent[bot]
<[email protected]>
Co-authored-by: pjfanning <[email protected]>
---
.../org/apache/pekko/util/ByteStringSpec.scala | 215 +++++++++++++++++++++
.../scala/org/apache/pekko/util/ByteString.scala | 147 +++++++++++---
.../ByteString_lastIndexOfSlice_Benchmark.scala | 39 ++++
3 files changed, 379 insertions(+), 22 deletions(-)
diff --git
a/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
b/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
index 1601b581f1..0891437a14 100644
--- a/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
+++ b/actor-tests/src/test/scala/org/apache/pekko/util/ByteStringSpec.scala
@@ -830,6 +830,12 @@ class ByteStringSpec extends AnyWordSpec with Matchers
with Checkers {
val concat0 = ByteStrings(ByteString1.fromString("ab"),
ByteString1.fromString("dd"))
concat0.lastIndexOf('d'.toByte, 2) should ===(2)
concat0.lastIndexOf('d'.toByte, 3) should ===(3)
+
+ // end larger than length - 1 should be clamped to the last valid index
+ val bs5 = ByteString1.fromString("abcde")
+ bs5.lastIndexOf('e', 100) should ===(4)
+ bs5.lastIndexOf('a', 100) should ===(0)
+ bs5.lastIndexOf('z', 100) should ===(-1)
}
"lastIndexOf (specialized)" in {
ByteString.empty.lastIndexOf(5.toByte, -1) should ===(-1)
@@ -894,6 +900,50 @@ class ByteStringSpec extends AnyWordSpec with Matchers
with Checkers {
concat0.lastIndexOf(0xFF.toByte, 18) should ===(18)
concat0.lastIndexOf(0xFF.toByte, 17) should ===(0)
concat0.lastIndexOf(0xFE.toByte) should ===(-1)
+
+ // Single-byte ByteString
+ val single = ByteString1(Array[Byte]('x'))
+ single.lastIndexOf('x'.toByte) should ===(0)
+ single.lastIndexOf('y'.toByte) should ===(-1)
+
+ // SWAR boundary: exactly 7 bytes (only tail, no full chunk)
+ val len7 = ByteString1.fromString("abcdefg")
+ len7.lastIndexOf('g'.toByte) should ===(6)
+ len7.lastIndexOf('a'.toByte) should ===(0)
+ len7.lastIndexOf('d'.toByte) should ===(3)
+ len7.lastIndexOf('z'.toByte) should ===(-1)
+
+ // SWAR boundary: exactly 8 bytes (one full chunk, no tail)
+ val len8 = ByteString1.fromString("abcdefgh")
+ len8.lastIndexOf('h'.toByte) should ===(7)
+ len8.lastIndexOf('a'.toByte) should ===(0)
+ len8.lastIndexOf('d'.toByte) should ===(3)
+ len8.lastIndexOf('z'.toByte) should ===(-1)
+
+ // SWAR boundary: exactly 9 bytes (1-byte tail + 1 full chunk)
+ val len9 = ByteString1.fromString("abcdefghi")
+ len9.lastIndexOf('i'.toByte) should ===(8) // found in tail
+ len9.lastIndexOf('a'.toByte) should ===(0) // found in chunk
+ len9.lastIndexOf('h'.toByte) should ===(7) // last byte of chunk
+ len9.lastIndexOf('z'.toByte) should ===(-1)
+
+ // SWAR boundary: exactly 16 bytes (2 full chunks, no tail)
+ val len16 = ByteString1.fromString("abcdefghijklmnop")
+ len16.lastIndexOf('p'.toByte) should ===(15) // last byte of rightmost
chunk
+ len16.lastIndexOf('a'.toByte) should ===(0) // first byte of leftmost
chunk
+ len16.lastIndexOf('h'.toByte) should ===(7) // last byte of leftmost
chunk
+ len16.lastIndexOf('i'.toByte) should ===(8) // first byte of rightmost
chunk
+
+ // All-same-byte array longer than 8: last index is the highest
+ val allSame = ByteString(Array[Byte](7, 7, 7, 7, 7, 7, 7, 7, 7)) // 9
bytes
+ allSame.lastIndexOf(7.toByte) should ===(8)
+ allSame.lastIndexOf(7.toByte, 5) should ===(5)
+ allSame.lastIndexOf(7.toByte, 0) should ===(0)
+
+ // ByteString1 with startIndex offset: find a byte residing in the SWAR
chunk
+ val slicedLong = ByteString1.fromString("xxabcdefghijk").drop(2) //
"abcdefghijk", 11 bytes
+ slicedLong.lastIndexOf('a'.toByte) should ===(0) // first byte, found
via chunk scan
+ slicedLong.lastIndexOf('h'.toByte) should ===(7) // last byte of chunk
}
"indexOf (specialized)" in {
ByteString.empty.indexOf(5.toByte) should ===(-1)
@@ -1140,7 +1190,34 @@ class ByteStringSpec extends AnyWordSpec with Matchers
with Checkers {
val byteStringXxyz = ByteString1.fromString("xxyz")
byteStringXxyz.indexOfSlice(slice0) should ===(1)
+ byteStringXxyz.indexOfSlice(slice0, -1) should ===(1)
byteStringXxyz.indexOfSlice(slice0, 2) should ===(-1)
+ byteStringXxyz.indexOfSlice(Seq.empty) should ===(0)
+ byteStringXxyz.indexOfSlice(Seq.empty, -1) should ===(0)
+ byteStringXxyz.indexOfSlice(Seq.empty, 1) should ===(1)
+
+ // empty slice at from == length: should return length (consistent with
Scala standard library)
+ byteStringXxyz.indexOfSlice(Seq.empty, 4) should ===(4)
+ // empty slice at from > length: should return -1
+ byteStringXxyz.indexOfSlice(Seq.empty, 5) should ===(-1)
+
+ // Empty source
+ ByteString.empty.indexOfSlice(Seq.empty) should ===(0)
+ ByteString.empty.indexOfSlice(ByteString1.fromString("a")) should ===(-1)
+
+ // Slice equals entire source
+
ByteString1.fromString("abc").indexOfSlice(ByteString1.fromString("abc"))
should ===(0)
+
+ // Slice longer than source
+ ByteString1.fromString("ab").indexOfSlice(ByteString1.fromString("abc"))
should ===(-1)
+
+ // Cross-segment match in ByteStrings: "bc" spans segment boundary of
("ab" ++ "cd")
+ ByteStrings(ByteString1.fromString("ab"), ByteString1.fromString("cd"))
+ .indexOfSlice(ByteString1.fromString("bc")) should ===(1)
+
+ // False match: first byte matches multiple times before the full slice
matches
+ // "ab" in "aabc": 'a' at index 0 (check: bytes[1]='a' != 'b' ✗), then
'a' at 1 (bytes[2]='b' == 'b' ✓) -> 1
+
ByteString1.fromString("aabc").indexOfSlice(ByteString1.fromString("ab"))
should ===(1)
}
"indexOfSlice (specialized)" in {
val slice0 = "xyz".getBytes(StandardCharsets.UTF_8)
@@ -1162,12 +1239,150 @@ class ByteStringSpec extends AnyWordSpec with Matchers
with Checkers {
val byteStringXxyz = ByteString1.fromString("xxyz")
byteStringXxyz.indexOfSlice(slice0) should ===(1)
+ byteStringXxyz.indexOfSlice(slice0, -1) should ===(1)
byteStringXxyz.indexOfSlice(slice0, 2) should ===(-1)
+ byteStringXxyz.indexOfSlice(Seq.empty) should ===(0)
+ byteStringXxyz.indexOfSlice(Seq.empty, -1) should ===(0)
+ byteStringXxyz.indexOfSlice(Seq.empty, 1) should ===(1)
+
+ // empty slice at from == length: should return length (consistent with
Scala standard library)
+ byteStringXxyz.indexOfSlice(Seq.empty, 4) should ===(4)
+ // empty slice at from > length: should return -1
+ byteStringXxyz.indexOfSlice(Seq.empty, 5) should ===(-1)
+
+ // Empty source
+ ByteString.empty.indexOfSlice(Array.empty[Byte]) should ===(0)
+ ByteString.empty.indexOfSlice(Array[Byte]('a')) should ===(-1)
+
+ // Slice equals entire source
+
ByteString1.fromString("abc").indexOfSlice("abc".getBytes(StandardCharsets.UTF_8))
should ===(0)
+
+ // Slice longer than source
+
ByteString1.fromString("ab").indexOfSlice("abc".getBytes(StandardCharsets.UTF_8))
should ===(-1)
+
+ // Cross-segment match in ByteStrings: "bc" spans segment boundary of
("ab" ++ "cd")
+ ByteStrings(ByteString1.fromString("ab"), ByteString1.fromString("cd"))
+ .indexOfSlice(Array[Byte]('b', 'c')) should ===(1)
+
+ // False match: first byte matches multiple times before the full slice
matches
+ ByteString1.fromString("aabc").indexOfSlice(Array[Byte]('a', 'b'))
should ===(1)
val byteStringWithOffset = ByteString1(
"abcdefghijklmnopqrstuvwxyz".getBytes(StandardCharsets.UTF_8), 2, 24)
byteStringWithOffset.indexOfSlice(slice0) should ===(21)
}
+ "lastIndexOfSlice" in {
+ val slice0 = ByteString1.fromString("xyz")
+ val slice1 = ByteString1.fromString("xyzabc")
+ val notSlice = ByteString1.fromString("12345")
+ val pByte = ByteString1.fromString("p")
+ val byteStringLong = ByteString1.fromString("abcdefghijklmnopqrstuvwxyz")
+ val byteStrings = ByteStrings(byteStringLong, byteStringLong)
+ byteStringLong.lastIndexOfSlice(slice0) should ===(23)
+ byteStringLong.lastIndexOfSlice(slice1) should ===(-1)
+ byteStringLong.lastIndexOfSlice(notSlice) should ===(-1)
+ byteStringLong.lastIndexOfSlice(pByte) should ===(15)
+
+ byteStrings.lastIndexOfSlice(slice0) should ===(49)
+ byteStrings.lastIndexOfSlice(slice1) should ===(23)
+ byteStrings.lastIndexOfSlice(notSlice) should ===(-1)
+ byteStrings.lastIndexOfSlice(pByte) should ===(41)
+ byteStrings.lastIndexOfSlice(pByte, 40) should ===(15)
+
+ val byteStringXxyz = ByteString1.fromString("xxyz")
+ byteStringXxyz.lastIndexOfSlice(slice0) should ===(1)
+ byteStringXxyz.lastIndexOfSlice(slice0, 10) should ===(1)
+ byteStringXxyz.lastIndexOfSlice(slice0, 0) should ===(-1)
+ byteStringXxyz.lastIndexOfSlice(slice0, 2) should ===(1)
+ byteStringXxyz.lastIndexOfSlice(Seq.empty) should ===(4)
+ byteStringXxyz.lastIndexOfSlice(Seq.empty, 2) should ===(2)
+
+ val xyzx = ByteString1.fromString("xyzx")
+ xyzx.lastIndexOfSlice(slice0) should ===(0)
+
+ // Empty source with empty slice -> 0; with non-empty slice -> -1
+ ByteString.empty.lastIndexOfSlice(ByteString.empty) should ===(0)
+ ByteString.empty.lastIndexOfSlice(ByteString1.fromString("a")) should
===(-1)
+
+ // Slice equals entire source -> 0
+
ByteString1.fromString("abc").lastIndexOfSlice(ByteString1.fromString("abc"))
should ===(0)
+
+ // Slice longer than source -> -1
+
ByteString1.fromString("ab").lastIndexOfSlice(ByteString1.fromString("abc"))
should ===(-1)
+
+ // end = -1 for non-empty slice -> -1
+
ByteString1.fromString("abc").lastIndexOfSlice(ByteString1.fromString("a"), -1)
should ===(-1)
+
+ // False-match retry: tail byte 'b' matches at index 2, but bytes[1]='b'
!= 'a'; retries, finds at index 1, bytes[0]='a' == 'a'
+
ByteString1.fromString("abb").lastIndexOfSlice(ByteString1.fromString("ab"))
should ===(0)
+
+ // Repeated pattern: "aa" in "aaaa" -> last occurrence starts at index 2
+
ByteString1.fromString("aaaa").lastIndexOfSlice(ByteString1.fromString("aa"))
should ===(2)
+
+ // Cross-segment match in ByteStrings: slice "bc" spans segment boundary
of ("ab" ++ "cd")
+ ByteStrings(ByteString1.fromString("ab"), ByteString1.fromString("cd"))
+ .lastIndexOfSlice(ByteString1.fromString("bc")) should ===(1)
+ }
+ "lastIndexOfSlice (specialized)" in {
+ val slice0 = "xyz".getBytes(StandardCharsets.UTF_8)
+ val slice1 = "xyzabc".getBytes(StandardCharsets.UTF_8)
+ val notSlice = "12345".getBytes(StandardCharsets.UTF_8)
+ val pByte = Array('p'.toByte)
+ val byteStringLong = ByteString1.fromString("abcdefghijklmnopqrstuvwxyz")
+ val byteStrings = ByteStrings(byteStringLong, byteStringLong)
+ byteStringLong.lastIndexOfSlice(slice0) should ===(23)
+ byteStringLong.lastIndexOfSlice(slice1) should ===(-1)
+ byteStringLong.lastIndexOfSlice(notSlice) should ===(-1)
+ byteStringLong.lastIndexOfSlice(pByte) should ===(15)
+
+ byteStrings.lastIndexOfSlice(slice0) should ===(49)
+ byteStrings.lastIndexOfSlice(slice1) should ===(23)
+ byteStrings.lastIndexOfSlice(notSlice) should ===(-1)
+ byteStrings.lastIndexOfSlice(pByte) should ===(41)
+ byteStrings.lastIndexOfSlice(pByte, 40) should ===(15)
+
+ val byteStringXxyz = ByteString1.fromString("xxyz")
+ byteStringXxyz.lastIndexOfSlice(slice0) should ===(1)
+ byteStringXxyz.lastIndexOfSlice(slice0, 10) should ===(1)
+ byteStringXxyz.lastIndexOfSlice(slice0, 0) should ===(-1)
+ byteStringXxyz.lastIndexOfSlice(slice0, 2) should ===(1)
+ byteStringXxyz.lastIndexOfSlice(Seq.empty) should ===(4)
+ byteStringXxyz.lastIndexOfSlice(Seq.empty, 2) should ===(2)
+
+ val xyzx = ByteString1.fromString("xyzx")
+ xyzx.lastIndexOfSlice(slice0) should ===(0)
+
+ val byteStringWithOffset = ByteString1(
+ "abcdefghijklmnopqrstuvwxyz".getBytes(StandardCharsets.UTF_8), 2, 24)
+ byteStringWithOffset.lastIndexOfSlice(slice0) should ===(21)
+
+ val concat0 = makeMultiByteStringsSample()
+ concat0.lastIndexOfSlice(Array(16.toByte, 0xFF.toByte)) should ===(17)
+ concat0.lastIndexOfSlice(Array(16.toByte, 0xFE.toByte)) should ===(-1)
+
+ // Empty source with empty slice -> 0; with non-empty slice -> -1
+ ByteString.empty.lastIndexOfSlice(Array.empty[Byte]) should ===(0)
+ ByteString.empty.lastIndexOfSlice(Array[Byte]('a')) should ===(-1)
+
+ // Slice equals entire source -> 0
+
ByteString1.fromString("abc").lastIndexOfSlice("abc".getBytes(StandardCharsets.UTF_8))
should ===(0)
+
+ // Slice longer than source -> -1
+
ByteString1.fromString("ab").lastIndexOfSlice("abc".getBytes(StandardCharsets.UTF_8))
should ===(-1)
+
+ // end = -1 for non-empty slice -> -1
+ ByteString1.fromString("abc").lastIndexOfSlice(Array[Byte]('a'), -1)
should ===(-1)
+
+ // False-match retry: tail byte 'b' matches at index 2, but bytes[1]='b'
!= 'a'; retries, finds at index 1
+ ByteString1.fromString("abb").lastIndexOfSlice(Array[Byte]('a', 'b'))
should ===(0)
+
+ // Repeated pattern: "aa" in "aaaa" -> last occurrence starts at index 2
+ ByteString1.fromString("aaaa").lastIndexOfSlice(Array[Byte]('a', 'a'))
should ===(2)
+
+ // Cross-segment match in ByteStrings: slice "bc" spans segment boundary
of ("ab" ++ "cd")
+ ByteStrings(ByteString1.fromString("ab"), ByteString1.fromString("cd"))
+ .lastIndexOfSlice(Array[Byte]('b', 'c')) should ===(1)
+ }
"startsWith (specialized)" in {
val slice0 = "abcdefghijk".getBytes(StandardCharsets.UTF_8)
val slice1 = "xyz".getBytes(StandardCharsets.UTF_8)
diff --git a/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
b/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
index 982227ee94..c36ac54b70 100644
--- a/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
+++ b/actor/src/main/scala/org/apache/pekko/util/ByteString.scala
@@ -1259,10 +1259,10 @@ sealed abstract class ByteString
/**
* Finds index of last occurrence of some byte in this ByteString before or
at some end index.
*
- * Similar to lastIndexOf, but it avoids boxing if the value is already a
byte.
+ * Similar to `lastIndexOf`, but it avoids boxing if the value is already a
byte.
*
* @param elem the element value to search for.
- * @param end the end index
+ * @param end the end index (inclusive)
* @return the index `<= end` of the last element of this ByteString that
is equal (as determined by `==`)
* to `elem`, or `-1`, if none exists.
* @since 2.0.0
@@ -1272,7 +1272,7 @@ sealed abstract class ByteString
/**
* Finds index of last occurrence of some byte in this ByteString.
*
- * Similar to lastIndexOf, but it avoids boxing if the value is already a
byte.
+ * Similar to `lastIndexOf`, but it avoids boxing if the value is already a
byte.
*
* @param elem the element value to search for.
* @return the index of the last element of this ByteString that is equal
(as determined by `==`)
@@ -1294,17 +1294,19 @@ sealed abstract class ByteString
}
true
}
- val headByte = slice.head.asInstanceOf[Byte]
- @tailrec def rec(from: Int): Int = {
- val startPos = indexOf(headByte, from, length - slice.length + 1)
- if (startPos == -1) -1
- else if (check(startPos)) startPos
- else rec(startPos + 1)
- }
val sliceLength = slice.length
- if (sliceLength == 0) 0
- else if (sliceLength == 1) indexOf(headByte, from)
- else rec(math.max(0, from))
+ if (sliceLength == 0) if (from > length) -1 else math.max(from, 0)
+ else {
+ val headByte = slice.head.asInstanceOf[Byte]
+ @tailrec def rec(from: Int): Int = {
+ val startPos = indexOf(headByte, from, length - slice.length + 1)
+ if (startPos == -1) -1
+ else if (check(startPos)) startPos
+ else rec(startPos + 1)
+ }
+ if (sliceLength == 1) indexOf(headByte, from)
+ else rec(math.max(0, from))
+ }
}
/**
@@ -1330,16 +1332,20 @@ sealed abstract class ByteString
}
true
}
- @tailrec def rec(from: Int): Int = {
- val startPos = indexOf(slice.head, from, length - slice.length + 1)
- if (startPos == -1) -1
- else if (check(startPos)) startPos
- else rec(startPos + 1)
- }
val sliceLength = slice.length
- if (sliceLength == 0) 0
- else if (sliceLength == 1) indexOf(slice.head, from)
- else rec(math.max(0, from))
+ if (sliceLength == 0) if (from > length) -1 else math.max(from, 0)
+ else if (sliceLength > length) -1
+ else {
+ val headByte = slice.head
+ @tailrec def rec(from: Int): Int = {
+ val startPos = indexOf(headByte, from, length - slice.length + 1)
+ if (startPos == -1) -1
+ else if (check(startPos)) startPos
+ else rec(startPos + 1)
+ }
+ if (sliceLength == 1) indexOf(headByte, from)
+ else rec(math.max(0, from))
+ }
}
/**
@@ -1353,6 +1359,103 @@ sealed abstract class ByteString
*/
def indexOfSlice(slice: Array[Byte]): Int = indexOfSlice(slice, 0)
+ override def lastIndexOfSlice[B >: Byte](slice: scala.collection.Seq[B],
end: Int): Int = {
+ val sliceLength = slice.length
+ if (sliceLength == 0) if (end < 0) -1 else math.min(end, length)
+ else if (sliceLength > length) -1
+ else {
+ val tailByte = slice(sliceLength - 1).asInstanceOf[Byte]
+ // Check all bytes of the slice except the last one (which was matched
by lastIndexOf)
+ def check(startPos: Int): Boolean = {
+ var i = startPos
+ var j = 0
+ while (j < sliceLength - 1) {
+ // let's trust the calling code has ensured that we have enough
bytes in this ByteString
+ if (apply(i) != slice(j)) return false
+ i += 1
+ j += 1
+ }
+ true
+ }
+ // Cap end to the max valid slice start position to avoid Int overflow
when end is very large
+ val effectiveEnd = math.min(end, length - sliceLength)
+ val maxEndPos = effectiveEnd + sliceLength - 1
+ @tailrec def rec(currEnd: Int): Int = {
+ val endPos = lastIndexOf(tailByte, currEnd)
+ if (endPos < sliceLength - 1) -1
+ else {
+ val startPos = endPos - sliceLength + 1
+ if (check(startPos)) startPos
+ else rec(endPos - 1)
+ }
+ }
+ if (sliceLength == 1) lastIndexOf(tailByte, effectiveEnd)
+ else rec(maxEndPos)
+ }
+ }
+
+ /**
+ * Finds index of last occurrence of some slice in this ByteString before or
at some end index.
+ *
+ * Uses `lastIndexOf` on the last byte of the slice to efficiently find
candidate positions,
+ * then verifies the full slice match.
+ *
+ * @param slice the slice to search for.
+ * @param end the end index — the largest index at which the slice may
start
+ * @return the largest index `<= end` of the first element of this
+ * ByteString that starts a slice equal (as determined by `==`)
+ * to `slice`, or `-1`, if none exists.
+ * @since 2.0.0
+ */
+ def lastIndexOfSlice(slice: Array[Byte], end: Int): Int = {
+ val sliceLength = slice.length
+ if (sliceLength == 0) if (end < 0) -1 else math.min(end, length)
+ else if (sliceLength > length) -1
+ else {
+ val tailByte = slice(sliceLength - 1)
+ // Check all bytes of the slice except the last one (which was matched
by lastIndexOf)
+ def check(startPos: Int): Boolean = {
+ var i = startPos
+ var j = 0
+ while (j < sliceLength - 1) {
+ // let's trust the calling code has ensured that we have enough
bytes in this ByteString
+ if (apply(i) != slice(j)) return false
+ i += 1
+ j += 1
+ }
+ true
+ }
+ // Cap end to the max valid slice start position to avoid Int overflow
when end is very large
+ val effectiveEnd = math.min(end, length - sliceLength)
+ val maxEndPos = effectiveEnd + sliceLength - 1
+ @tailrec def rec(currEnd: Int): Int = {
+ val endPos = lastIndexOf(tailByte, currEnd)
+ if (endPos < sliceLength - 1) -1
+ else {
+ val startPos = endPos - sliceLength + 1
+ if (check(startPos)) startPos
+ else rec(endPos - 1)
+ }
+ }
+ if (sliceLength == 1) lastIndexOf(tailByte, effectiveEnd)
+ else rec(maxEndPos)
+ }
+ }
+
+ /**
+ * Finds index of last occurrence of some slice in this ByteString.
+ *
+ * Uses `lastIndexOf` on the last byte of the slice to efficiently find
candidate positions,
+ * then verifies the full slice match.
+ *
+ * @param slice the slice to search for.
+ * @return the index of the last element of this
+ * ByteString that starts a slice equal (as determined by `==`)
+ * to `slice`, or `-1`, if none exists.
+ * @since 2.0.0
+ */
+ def lastIndexOfSlice(slice: Array[Byte]): Int = lastIndexOfSlice(slice,
length)
+
override def contains[B >: Byte](elem: B): Boolean = indexOf(elem, 0) != -1
/**
diff --git
a/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_lastIndexOfSlice_Benchmark.scala
b/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_lastIndexOfSlice_Benchmark.scala
new file mode 100644
index 0000000000..f3695ec6e6
--- /dev/null
+++
b/bench-jmh/src/main/scala/org/apache/pekko/util/ByteString_lastIndexOfSlice_Benchmark.scala
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * license agreements; and to You under the Apache License, version 2.0:
+ *
+ * https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * This file is part of the Apache Pekko project, which was derived from Akka.
+ */
+
+/*
+ * Copyright (C) 2014-2022 Lightbend Inc. <https://www.lightbend.com>
+ */
+
+package org.apache.pekko.util
+
+import java.nio.charset.StandardCharsets
+import java.util.concurrent.TimeUnit
+
+import org.openjdk.jmh.annotations._
+
+@State(Scope.Benchmark)
+@Measurement(timeUnit = TimeUnit.MILLISECONDS)
+class ByteString_lastIndexOfSlice_Benchmark {
+ val start = ByteString("abcdefg") ++ ByteString("hijklmno") ++
ByteString("pqrstuv")
+ val bss = start ++ start ++ start ++ start ++ start ++ ByteString("xyz")
+
+ val bs = bss.compact // compacted
+ val abc = "abc".getBytes(StandardCharsets.UTF_8)
+ val hv = "hijklmnopqrstuv".getBytes(StandardCharsets.UTF_8)
+
+ @Benchmark
+ def bss_lastIndexOfSlice: Int = bss.lastIndexOfSlice(abc)
+
+ @Benchmark
+ def bs_lastIndexOfSlice_abc: Int = bs.lastIndexOfSlice(abc)
+
+ @Benchmark
+ def bs_lastIndexOfSlice_hv: Int = bs.lastIndexOfSlice(hv)
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
