KmpSearchProcessorFactory Class — netty Architecture

Source Code

buffer/src/main/java/io/netty/buffer/search/KmpSearchProcessorFactory.java lines 29–91

public class KmpSearchProcessorFactory extends AbstractSearchProcessorFactory {

    private final int[] jumpTable;
    private final byte[] needle;

    public static class Processor implements SearchProcessor {

        private final byte[] needle;
        private final int[] jumpTable;
        private long currentPosition;

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

        @Override
        public boolean process(byte value) {
            while (currentPosition > 0 && PlatformDependent.getByte(needle, currentPosition) != value) {
                currentPosition = PlatformDependent.getInt(jumpTable, currentPosition);
            }
            if (PlatformDependent.getByte(needle, currentPosition) == value) {
                currentPosition++;
            }
            if (currentPosition == needle.length) {
                currentPosition = PlatformDependent.getInt(jumpTable, currentPosition);
                return false;
            }

            return true;
        }

        @Override
        public void reset() {
            currentPosition = 0;
        }
    }

    KmpSearchProcessorFactory(byte[] needle) {
        this.needle = needle.clone();
        this.jumpTable = new int[needle.length + 1];

        int j = 0;
        for (int i = 1; i < needle.length; i++) {
            while (j > 0 && needle[j] != needle[i]) {
                j = jumpTable[j];
            }
            if (needle[j] == needle[i]) {
                j++;
            }
            jumpTable[i + 1] = j;
        }
    }

    /**
     * Returns a new {@link Processor}.
     */
    @Override
    public Processor newSearchProcessor() {
        return new Processor(needle, jumpTable);
    }

}