linux-imx
Public
Source
committed 5968a70d7af3
3
*4
4
* This program is free software; you can redistribute it and/or5
5
* modify it under the terms of the GNU General Public License6
6
* as published by the Free Software Foundation; either version7
7
* 2 of the License, or (at your option) any later version.8
8
*9
9
* Authors: Thomas Graf <tgraf@suug.ch>10
10
* Pablo Neira Ayuso <pablo@netfilter.org>11
11
*12
12
* ==========================================================================13
-
*13
+
*/14
+
15
+
/**16
+
* DOC: ts_intro14
17
* INTRODUCTION15
18
*16
19
* The textsearch infrastructure provides text searching facilities for17
20
* both linear and non-linear data. Individual search algorithms are18
21
* implemented in modules and chosen by the user.19
22
*20
23
* ARCHITECTURE21
24
*22
-
* User25
+
* .. code-block:: none26
+
*27
+
* User23
28
* +----------------+24
29
* | finish()|<--------------(6)-----------------+25
30
* |get_next_block()|<--------------(5)---------------+ |26
31
* | | Algorithm | |27
32
* | | +------------------------------+28
33
* | | | init() find() destroy() |29
34
* | | +------------------------------+30
35
* | | Core API ^ ^ ^31
36
* | | +---------------+ (2) (4) (8)32
37
* | (1)|----->| prepare() |---+ | |33
38
* | (3)|----->| find()/next() |-----------+ |34
39
* | (7)|----->| destroy() |----------------------+35
40
* +----------------+ +---------------+36
-
* 37
-
* (1) User configures a search by calling _prepare() specifying the38
-
* search parameters such as the pattern and algorithm name.41
+
*42
+
* (1) User configures a search by calling textsearch_prepare() specifying43
+
* the search parameters such as the pattern and algorithm name.39
44
* (2) Core requests the algorithm to allocate and initialize a search40
45
* configuration according to the specified parameters.41
-
* (3) User starts the search(es) by calling _find() or _next() to42
-
* fetch subsequent occurrences. A state variable is provided43
-
* to the algorithm to store persistent variables.46
+
* (3) User starts the search(es) by calling textsearch_find() or47
+
* textsearch_next() to fetch subsequent occurrences. A state variable48
+
* is provided to the algorithm to store persistent variables.44
49
* (4) Core eventually resets the search offset and forwards the find()45
50
* request to the algorithm.46
51
* (5) Algorithm calls get_next_block() provided by the user continuously47
52
* to fetch the data to be searched in block by block.48
53
* (6) Algorithm invokes finish() after the last call to get_next_block49
54
* to clean up any leftovers from get_next_block. (Optional)50
-
* (7) User destroys the configuration by calling _destroy().55
+
* (7) User destroys the configuration by calling textsearch_destroy().51
56
* (8) Core notifies the algorithm to destroy algorithm specific52
57
* allocations. (Optional)53
58
*54
59
* USAGE55
60
*56
61
* Before a search can be performed, a configuration must be created57
62
* by calling textsearch_prepare() specifying the searching algorithm,58
63
* the pattern to look for and flags. As a flag, you can set TS_IGNORECASE59
64
* to perform case insensitive matching. But it might slow down60
65
* performance of algorithm, so you should use it at own your risk.61
66
* The returned configuration may then be used for an arbitrary62
67
* amount of times and even in parallel as long as a separate struct63
68
* ts_state variable is provided to every instance.64
69
*65
-
* The actual search is performed by either calling textsearch_find_-66
-
* continuous() for linear data or by providing an own get_next_block()67
-
* implementation and calling textsearch_find(). Both functions return70
+
* The actual search is performed by either calling71
+
* textsearch_find_continuous() for linear data or by providing72
+
* an own get_next_block() implementation and73
+
* calling textsearch_find(). Both functions return68
74
* the position of the first occurrence of the pattern or UINT_MAX if69
75
* no match was found. Subsequent occurrences can be found by calling70
76
* textsearch_next() regardless of the linearity of the data.71
77
*72
78
* Once you're done using a configuration it must be given back via73
79
* textsearch_destroy.74
80
*75
-
* EXAMPLE81
+
* EXAMPLE::76
82
*77
83
* int pos;78
84
* struct ts_config *conf;79
85
* struct ts_state state;80
86
* const char *pattern = "chicken";81
87
* const char *example = "We dance the funky chicken";82
88
*83
89
* conf = textsearch_prepare("kmp", pattern, strlen(pattern),84
90
* GFP_KERNEL, TS_AUTOLOAD);85
91
* if (IS_ERR(conf)) {86
92
* err = PTR_ERR(conf);87
93
* goto errout;88
94
* }89
95
*90
-
* pos = textsearch_find_continuous(conf, &state, example, strlen(example));96
+
* pos = textsearch_find_continuous(conf, \&state, example, strlen(example));91
97
* if (pos != UINT_MAX)92
-
* panic("Oh my god, dancing chickens at %d\n", pos);98
+
* panic("Oh my god, dancing chickens at \%d\n", pos);93
99
*94
100
* textsearch_destroy(conf);95
-
* ==========================================================================96
101
*/102
+
/* ========================================================================== */97
103
98
104
#include <linux/module.h>99
105
#include <linux/types.h>100
106
#include <linux/string.h>101
107
#include <linux/init.h>102
108
#include <linux/rculist.h>103
109
#include <linux/rcupdate.h>104
110
#include <linux/err.h>105
111
#include <linux/textsearch.h>106
112
#include <linux/slab.h>218
224
* @conf: search configuration219
225
* @state: search state220
226
* @data: data to search in221
227
* @len: length of data222
228
*223
229
* A simplified version of textsearch_find() for continuous/linear data.224
230
* Call textsearch_next() to retrieve subsequent matches.225
231
*226
232
* Returns the position of first occurrence of the pattern or227
233
* %UINT_MAX if no occurrence was found.228
-
*/ 234
+
*/229
235
unsigned int textsearch_find_continuous(struct ts_config *conf,230
236
struct ts_state *state,231
237
const void *data, unsigned int len)232
238
{233
239
struct ts_linear_state *st = (struct ts_linear_state *) state->cb;234
240
235
241
conf->get_next_block = get_linear_data;236
242
st->data = data;237
243
st->len = len;238
244