1 /*
2 * Copyright 2020 The Netty Project
3 *
4 * The Netty Project licenses this file to you under the Apache License, version 2.0 (the
5 * "License"); you may not use this file except in compliance with the License. You may obtain a
6 * copy of the License at:
7 *
8 * https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software distributed under the License
11 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12 * or implied. See the License for the specific language governing permissions and limitations under
13 * the License.
14 */
15 package io.netty.buffer.search;
16
17 import io.netty.util.internal.PlatformDependent;
18
19 /**
20 * Implements
21 * <a href="https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm">Knuth-Morris-Pratt</a>
22 * string search algorithm.
23 * Use static {@link AbstractSearchProcessorFactory#newKmpSearchProcessorFactory}
24 * to create an instance of this factory.
25 * Use {@link KmpSearchProcessorFactory#newSearchProcessor} to get an instance of {@link io.netty.util.ByteProcessor}
26 * implementation for performing the actual search.
27 * @see AbstractSearchProcessorFactory
28 */
29 public class KmpSearchProcessorFactory extends AbstractSearchProcessorFactory {
30
31 private final int[] jumpTable;
32 private final byte[] needle;
33
34 public static class Processor implements SearchProcessor {
35
36 private final byte[] needle;
37 private final int[] jumpTable;
38 private long currentPosition;
39
40 Processor(byte[] needle, int[] jumpTable) {
41 this.needle = needle;
42 this.jumpTable = jumpTable;
43 }
44
45 @Override
46 public boolean process(byte value) {
47 while (currentPosition > 0 && PlatformDependent.getByte(needle, currentPosition) != value) {
48 currentPosition = PlatformDependent.getInt(jumpTable, currentPosition);
49 }
50 if (PlatformDependent.getByte(needle, currentPosition) == value) {
51 currentPosition++;
52 }
53 if (currentPosition == needle.length) {
54 currentPosition = PlatformDependent.getInt(jumpTable, currentPosition);
55 return false;
56 }
57
58 return true;
59 }
60
61 @Override
62 public void reset() {
63 currentPosition = 0;
64 }
65 }
66
67 KmpSearchProcessorFactory(byte[] needle) {
68 this.needle = needle.clone();
69 this.jumpTable = new int[needle.length + 1];
70
71 int j = 0;
72 for (int i = 1; i < needle.length; i++) {
73 while (j > 0 && needle[j] != needle[i]) {
74 j = jumpTable[j];
75 }
76 if (needle[j] == needle[i]) {
77 j++;
78 }
79 jumpTable[i + 1] = j;
80 }
81 }
82
83 /**
84 * Returns a new {@link Processor}.
85 */
86 @Override
87 public Processor newSearchProcessor() {
88 return new Processor(needle, jumpTable);
89 }
90
91 }