• Thomas Graf's avatar
    [LIB]: Naive finite state machine based textsearch · 6408f79c
    Thomas Graf authored
    A finite state machine consists of n states (struct ts_fsm_token)
    representing the pattern as a finite automation. The data is read
    sequentially on a octet basis. Every state token specifies the number
    of recurrences and the type of value accepted which can be either a
    specific character or ctype based set of characters. The available
    type of recurrences include 1, (0|1), [0 n], and [1 n].
    
    The algorithm differs between strict/non-strict mode specyfing
    whether the pattern has to start at the first octect. Strict mode
    is enabled by default and can be disabled by inserting
    TS_FSM_HEAD_IGNORE as the first token in the chain.
    
    The runtime performance of the algorithm should be around O(n),
    however while in strict mode the average runtime can be better.
    Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    6408f79c
ts_fsm.c 10.5 KB