查看本类的 API文档回源码主页即时通讯网 - 即时通讯开发者社区!
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  }