Skip to content

Commit eca2120

Browse files
swankjesseswankjesse
authored
Re-implement Buffer.rangeEquals on Buffer.indexOf (#1628)
The old rangeEquals function was embarassingly inefficient, using a full scan of the segments linked-list for each element. That optimization is already done in indexOf(), which has almost all of what we need for rangeEquals(). This adds an offset and count slice to the input ByteString in indexOf(), and then leverages that to simplify rangeEquals(). Co-authored-by: Jesse Wilson <jwilson@squareup.com>
1 parent b4b5fd2 commit eca2120

8 files changed

Lines changed: 87 additions & 59 deletions

File tree

‎okio/src/commonMain/kotlin/okio/internal/Buffer.kt‎

Lines changed: 23 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1285,12 +1285,15 @@ internal inline fun Buffer.commonIndexOf(b: Byte, fromIndex: Long, toIndex: Long
12851285
}
12861286
}
12871287

1288-
internal inline fun Buffer.commonIndexOf(
1288+
internal fun Buffer.commonIndexOf(
12891289
bytes: ByteString,
12901290
fromIndex: Long,
12911291
toIndex: Long = Long.MAX_VALUE,
1292+
bytesOffset: Int = 0,
1293+
byteCount: Int = bytes.size,
12921294
): Long {
1293-
require(bytes.size > 0) { "bytes is empty" }
1295+
checkOffsetAndCount(bytes.size.toLong(), bytesOffset.toLong(), byteCount.toLong())
1296+
require(byteCount > 0) { "byteCount == 0" }
12941297
require(fromIndex >= 0) { "fromIndex < 0: $fromIndex" }
12951298
require(fromIndex <= toIndex) { "fromIndex > toIndex: $fromIndex > $toIndex" }
12961299

@@ -1306,15 +1309,17 @@ internal inline fun Buffer.commonIndexOf(
13061309
// Scan through the segments, searching for the lead byte. Each time that is found, delegate
13071310
// to rangeEquals() to check for a complete match.
13081311
val targetByteArray = bytes.internalArray()
1309-
val b0 = targetByteArray[0]
1310-
val bytesSize = bytes.size
1311-
val resultLimit = minOf(toIndex, size - bytesSize + 1L)
1312+
val b0 = targetByteArray[bytesOffset]
1313+
val resultLimit = minOf(toIndex, size - byteCount + 1L)
13121314
while (offset < resultLimit) {
13131315
// Scan through the current segment.
13141316
val data = s.data
13151317
val segmentLimit = minOf(s.limit, s.pos + resultLimit - offset).toInt()
13161318
for (pos in (s.pos + fromIndex - offset).toInt() until segmentLimit) {
1317-
if (data[pos] == b0 && rangeEquals(s, pos + 1, targetByteArray, 1, bytesSize)) {
1319+
if (
1320+
data[pos] == b0 &&
1321+
rangeEquals(s, pos + 1, targetByteArray, bytesOffset + 1, byteCount)
1322+
) {
13181323
return pos - s.pos + offset
13191324
}
13201325
}
@@ -1393,20 +1398,18 @@ internal inline fun Buffer.commonRangeEquals(
13931398
bytesOffset: Int,
13941399
byteCount: Int,
13951400
): Boolean {
1396-
if (offset < 0L ||
1397-
bytesOffset < 0 ||
1398-
byteCount < 0 ||
1399-
size - offset < byteCount ||
1400-
bytes.size - bytesOffset < byteCount
1401-
) {
1402-
return false
1403-
}
1404-
for (i in 0 until byteCount) {
1405-
if (this[offset + i] != bytes[bytesOffset + i]) {
1406-
return false
1407-
}
1408-
}
1409-
return true
1401+
if (byteCount < 0) return false
1402+
if (offset < 0 || offset + byteCount > size) return false
1403+
if (bytesOffset < 0 || bytesOffset + byteCount > bytes.size) return false
1404+
if (byteCount == 0) return true
1405+
1406+
return commonIndexOf(
1407+
bytes = bytes,
1408+
bytesOffset = bytesOffset,
1409+
byteCount = byteCount,
1410+
fromIndex = offset,
1411+
toIndex = offset + 1,
1412+
) != -1L
14101413
}
14111414

14121415
internal inline fun Buffer.commonEquals(other: Any?): Boolean {

‎okio/src/commonMain/kotlin/okio/internal/RealBufferedSource.kt‎

Lines changed: 47 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -333,23 +333,42 @@ internal inline fun RealBufferedSource.commonIndexOf(b: Byte, fromIndex: Long, t
333333
return -1L
334334
}
335335

336-
internal inline fun RealBufferedSource.commonIndexOf(
336+
internal fun RealBufferedSource.commonIndexOf(
337337
bytes: ByteString,
338+
bytesOffset: Int = 0,
339+
byteCount: Int = bytes.size,
338340
fromIndex: Long,
339341
toIndex: Long = Long.MAX_VALUE,
340342
): Long {
343+
checkOffsetAndCount(bytes.size.toLong(), bytesOffset.toLong(), byteCount.toLong())
344+
341345
var fromIndex = fromIndex
342346
check(!closed) { "closed" }
343347

344348
while (true) {
345-
val result = buffer.indexOf(bytes, fromIndex, toIndex)
349+
val result = buffer.commonIndexOf(
350+
bytes = bytes,
351+
bytesOffset = bytesOffset,
352+
byteCount = byteCount,
353+
fromIndex = fromIndex,
354+
toIndex = toIndex,
355+
)
346356
if (result != -1L) return result
347357

348358
val lastBufferSize = buffer.size
349-
val nextFromIndex = lastBufferSize - bytes.size + 1
359+
val nextFromIndex = lastBufferSize - byteCount + 1
350360
if (nextFromIndex >= toIndex) return -1L
351-
352-
if (!matchPossibleByExpandingBuffer(buffer, bytes, fromIndex, toIndex)) return -1L
361+
if (
362+
!buffer.isMatchPossibleByExpandingBuffer(
363+
bytes = bytes,
364+
bytesOffset = bytesOffset,
365+
byteCount = byteCount,
366+
fromIndex = fromIndex,
367+
toIndex = toIndex,
368+
)
369+
) {
370+
return -1L
371+
}
353372
if (source.read(buffer, Segment.SIZE.toLong()) == -1L) return -1L
354373

355374
// Keep searching, picking up from where we left off.
@@ -372,20 +391,21 @@ internal inline fun RealBufferedSource.commonIndexOf(
372391
* if the next loaded byte is 'o' then the result will be 1. But if the source's loaded content is
373392
* 'look', we know the result is -1 without loading more data.
374393
*/
375-
private fun matchPossibleByExpandingBuffer(
376-
buffer: Buffer,
394+
private fun Buffer.isMatchPossibleByExpandingBuffer(
377395
bytes: ByteString,
396+
bytesOffset: Int,
397+
byteCount: Int,
378398
fromIndex: Long,
379399
toIndex: Long,
380400
): Boolean {
381401
// Load new data if the match could come entirely in that new data.
382-
if (buffer.size < toIndex) return true
402+
if (size < toIndex) return true
383403

384404
// Load new data if a prefix of 'bytes' matches a suffix of 'buffer'.
385-
val begin = maxOf(1, buffer.size - toIndex + 1).toInt()
386-
val limit = minOf(bytes.size, buffer.size - fromIndex + 1).toInt()
405+
val begin = maxOf(1, size - toIndex + 1).toInt()
406+
val limit = minOf(byteCount, size - fromIndex + 1).toInt()
387407
for (i in limit - 1 downTo begin) {
388-
if (buffer.rangeEquals(buffer.size - i, bytes, 0, i)) {
408+
if (rangeEquals(size - i, bytes, bytesOffset, i)) {
389409
return true
390410
}
391411
}
@@ -394,7 +414,10 @@ private fun matchPossibleByExpandingBuffer(
394414
return false
395415
}
396416

397-
internal inline fun RealBufferedSource.commonIndexOfElement(targetBytes: ByteString, fromIndex: Long): Long {
417+
internal inline fun RealBufferedSource.commonIndexOfElement(
418+
targetBytes: ByteString,
419+
fromIndex: Long,
420+
): Long {
398421
var fromIndex = fromIndex
399422
check(!closed) { "closed" }
400423

@@ -418,19 +441,18 @@ internal inline fun RealBufferedSource.commonRangeEquals(
418441
): Boolean {
419442
check(!closed) { "closed" }
420443

421-
if (offset < 0L ||
422-
bytesOffset < 0 ||
423-
byteCount < 0 ||
424-
bytes.size - bytesOffset < byteCount
425-
) {
426-
return false
427-
}
428-
for (i in 0 until byteCount) {
429-
val bufferOffset = offset + i
430-
if (!request(bufferOffset + 1)) return false
431-
if (buffer[bufferOffset] != bytes[bytesOffset + i]) return false
432-
}
433-
return true
444+
if (byteCount < 0) return false
445+
if (offset < 0) return false
446+
if (bytesOffset < 0 || bytesOffset + byteCount > bytes.size) return false
447+
if (byteCount == 0) return true
448+
449+
return commonIndexOf(
450+
bytes = bytes,
451+
bytesOffset = bytesOffset,
452+
byteCount = byteCount,
453+
fromIndex = offset,
454+
toIndex = offset + 1,
455+
) != -1L
434456
}
435457

436458
internal inline fun RealBufferedSource.commonPeek(): BufferedSource {

‎okio/src/commonTest/kotlin/okio/CommonBufferedSourceTest.kt‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -716,7 +716,7 @@ class CommonBufferedSourceTest(
716716
var e = assertFailsWith<IllegalArgumentException> {
717717
source.indexOf(ByteString.of())
718718
}
719-
assertEquals("bytes is empty", e.message)
719+
assertEquals("byteCount == 0", e.message)
720720

721721
e = assertFailsWith<IllegalArgumentException> {
722722
source.indexOf("hi".encodeUtf8(), -1)

‎okio/src/jvmMain/kotlin/okio/Buffer.kt‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -477,17 +477,18 @@ actual class Buffer : BufferedSource, BufferedSink, Cloneable, ByteChannel {
477477
actual override fun indexOf(b: Byte, fromIndex: Long) = indexOf(b, fromIndex, Long.MAX_VALUE)
478478

479479
actual override fun indexOf(b: Byte, fromIndex: Long, toIndex: Long): Long =
480-
commonIndexOf(b, fromIndex, toIndex)
480+
commonIndexOf(b, fromIndex = fromIndex, toIndex = toIndex)
481481

482482
@Throws(IOException::class)
483483
actual override fun indexOf(bytes: ByteString): Long = indexOf(bytes, 0)
484484

485485
@Throws(IOException::class)
486-
actual override fun indexOf(bytes: ByteString, fromIndex: Long): Long = commonIndexOf(bytes, fromIndex)
486+
actual override fun indexOf(bytes: ByteString, fromIndex: Long): Long =
487+
indexOf(bytes, fromIndex, Long.MAX_VALUE)
487488

488489
@Throws(IOException::class)
489490
actual override fun indexOf(bytes: ByteString, fromIndex: Long, toIndex: Long): Long =
490-
commonIndexOf(bytes, fromIndex, toIndex)
491+
commonIndexOf(bytes, fromIndex = fromIndex, toIndex = toIndex)
491492

492493
actual override fun indexOfElement(targetBytes: ByteString) = indexOfElement(targetBytes, 0L)
493494

‎okio/src/jvmMain/kotlin/okio/RealBufferedSource.kt‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -122,13 +122,13 @@ internal actual class RealBufferedSource actual constructor(
122122
actual override fun indexOf(b: Byte, fromIndex: Long): Long =
123123
indexOf(b, fromIndex, Long.MAX_VALUE)
124124
actual override fun indexOf(b: Byte, fromIndex: Long, toIndex: Long): Long =
125-
commonIndexOf(b, fromIndex, toIndex)
125+
commonIndexOf(b, fromIndex = fromIndex, toIndex = toIndex)
126126

127127
actual override fun indexOf(bytes: ByteString): Long = indexOf(bytes, 0L)
128128
actual override fun indexOf(bytes: ByteString, fromIndex: Long): Long =
129-
commonIndexOf(bytes, fromIndex)
129+
indexOf(bytes, fromIndex, Long.MAX_VALUE)
130130
actual override fun indexOf(bytes: ByteString, fromIndex: Long, toIndex: Long): Long =
131-
commonIndexOf(bytes, fromIndex, toIndex)
131+
commonIndexOf(bytes, fromIndex = fromIndex, toIndex = toIndex)
132132
actual override fun indexOfElement(targetBytes: ByteString): Long =
133133
indexOfElement(targetBytes, 0L)
134134
actual override fun indexOfElement(targetBytes: ByteString, fromIndex: Long): Long =

‎okio/src/jvmTest/kotlin/okio/BufferedSourceTest.kt‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -803,7 +803,7 @@ class BufferedSourceTest(
803803
source.indexOf(ByteString.of())
804804
fail()
805805
} catch (e: IllegalArgumentException) {
806-
assertEquals("bytes is empty", e.message)
806+
assertEquals("byteCount == 0", e.message)
807807
}
808808
try {
809809
source.indexOf("hi".encodeUtf8(), -1)

‎okio/src/nonJvmMain/kotlin/okio/Buffer.kt‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -216,14 +216,15 @@ actual class Buffer : BufferedSource, BufferedSink {
216216
actual override fun indexOf(b: Byte, fromIndex: Long): Long = indexOf(b, fromIndex, Long.MAX_VALUE)
217217

218218
actual override fun indexOf(b: Byte, fromIndex: Long, toIndex: Long): Long =
219-
commonIndexOf(b, fromIndex, toIndex)
219+
commonIndexOf(b, fromIndex = fromIndex, toIndex = toIndex)
220220

221221
actual override fun indexOf(bytes: ByteString): Long = indexOf(bytes, 0)
222222

223-
actual override fun indexOf(bytes: ByteString, fromIndex: Long): Long = commonIndexOf(bytes, fromIndex)
223+
actual override fun indexOf(bytes: ByteString, fromIndex: Long): Long =
224+
indexOf(bytes, fromIndex, Long.MAX_VALUE)
224225

225226
actual override fun indexOf(bytes: ByteString, fromIndex: Long, toIndex: Long): Long =
226-
commonIndexOf(bytes, fromIndex, toIndex)
227+
commonIndexOf(bytes, fromIndex = fromIndex, toIndex = toIndex)
227228

228229
actual override fun indexOfElement(targetBytes: ByteString): Long = indexOfElement(targetBytes, 0L)
229230

‎okio/src/nonJvmMain/kotlin/okio/RealBufferedSource.kt‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -90,12 +90,13 @@ internal actual class RealBufferedSource actual constructor(
9090
actual override fun indexOf(b: Byte, fromIndex: Long): Long =
9191
indexOf(b, fromIndex, Long.MAX_VALUE)
9292
actual override fun indexOf(b: Byte, fromIndex: Long, toIndex: Long): Long =
93-
commonIndexOf(b, fromIndex, toIndex)
93+
commonIndexOf(b, fromIndex = fromIndex, toIndex = toIndex)
9494

9595
actual override fun indexOf(bytes: ByteString): Long = indexOf(bytes, 0L)
96-
actual override fun indexOf(bytes: ByteString, fromIndex: Long): Long = commonIndexOf(bytes, fromIndex)
96+
actual override fun indexOf(bytes: ByteString, fromIndex: Long): Long =
97+
indexOf(bytes, fromIndex, Long.MAX_VALUE)
9798
actual override fun indexOf(bytes: ByteString, fromIndex: Long, toIndex: Long): Long =
98-
commonIndexOf(bytes, fromIndex, toIndex)
99+
commonIndexOf(bytes, fromIndex = fromIndex, toIndex = toIndex)
99100
actual override fun indexOfElement(targetBytes: ByteString): Long =
100101
indexOfElement(targetBytes, 0L)
101102
actual override fun indexOfElement(targetBytes: ByteString, fromIndex: Long): Long =

0 commit comments

Comments
 (0)