AhoCorasicSearchProcessorFactory.java — netty Source File

Source Code

/*
 * Copyright 2020 The Netty Project
 *
 * The Netty Project licenses this file to you under the Apache License, version 2.0 (the
 * "License"); you may not use this file except in compliance with the License. You may obtain a
 * copy of the License at:
 *
 * https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */
package io.netty.buffer.search;

import io.netty.util.internal.PlatformDependent;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

/**
 * Implements <a href="https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm">Aho–Corasick</a>
 * string search algorithm.
 * Use static {@link AbstractMultiSearchProcessorFactory#newAhoCorasicSearchProcessorFactory}
 * to create an instance of this factory.
 * Use {@link AhoCorasicSearchProcessorFactory#newSearchProcessor} to get an instance of
 * {@link io.netty.util.ByteProcessor} implementation for performing the actual search.
 * @see AbstractMultiSearchProcessorFactory
 */
public class AhoCorasicSearchProcessorFactory extends AbstractMultiSearchProcessorFactory {

    private final int[] jumpTable;
    private final int[] matchForNeedleId;

    static final int BITS_PER_SYMBOL = 8;
    static final int ALPHABET_SIZE = 1 << BITS_PER_SYMBOL;

    private static class Context {
        int[] jumpTable;
        int[] matchForNeedleId;
    }

    public static class Processor implements MultiSearchProcessor {

        private final int[] jumpTable;
        private final int[] matchForNeedleId;
        private long currentPosition;

        Processor(int[] jumpTable, int[] matchForNeedleId) {
            this.jumpTable = jumpTable;
            this.matchForNeedleId = matchForNeedleId;
        }

        @Override
        public boolean process(byte value) {
            currentPosition = PlatformDependent.getInt(jumpTable, currentPosition | (value & 0xffL));
            if (currentPosition < 0) {
// ... (132 more lines)