Lines Matching +full:quality +full:- +full:of +full:- +full:service

1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * lib/ts_bm.c Boyer-Moore text search implementation
9 * Implements Boyer-Moore string matching algorithm:
12 * Communications of the Association for Computing Machinery,
13 * 20(10), 1977, pp. 762-772.
16 * [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004
17 * http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
19 * Note: Since Boyer-Moore (BM) performs searches for matchings from right
24 * Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose
30 * Quality of Service (QoS) policies, and you don't mind about possible
64 u8 t = *(text-i); in matchpat()
69 if (t != *(pattern-i)) in matchpat()
79 unsigned int i, text_len, consumed = state->offset; in bm_find()
82 const u8 icase = conf->flags & TS_IGNORECASE; in bm_find()
85 int shift = bm->patlen - 1; in bm_find()
87 text_len = conf->get_next_block(consumed, &text, conf, state); in bm_find()
96 i = matchpat(&bm->pattern[bm->patlen-1], bm->patlen, in bm_find()
98 if (i == bm->patlen) { in bm_find()
101 return consumed + (shift-(bm->patlen-1)); in bm_find()
104 bs = bm->bad_shift[text[shift-i]]; in bm_find()
107 shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]); in bm_find()
117 int x = i+g-1, y = j+g-1, ret = 0; in subpattern()
119 while(pattern[x--] == pattern[y--]) { in subpattern()
124 if (--g == 0) { in subpattern()
125 ret = pattern[i-1] != pattern[j-1]; in subpattern()
138 bm->bad_shift[i] = bm->patlen; in compute_prefix_tbl()
139 for (i = 0; i < bm->patlen - 1; i++) { in compute_prefix_tbl()
140 bm->bad_shift[bm->pattern[i]] = bm->patlen - 1 - i; in compute_prefix_tbl()
142 bm->bad_shift[tolower(bm->pattern[i])] in compute_prefix_tbl()
143 = bm->patlen - 1 - i; in compute_prefix_tbl()
147 * of a subpattern */ in compute_prefix_tbl()
148 bm->good_shift[0] = 1; in compute_prefix_tbl()
149 for (i = 1; i < bm->patlen; i++) in compute_prefix_tbl()
150 bm->good_shift[i] = bm->patlen; in compute_prefix_tbl()
151 for (i = bm->patlen-1, g = 1; i > 0; g++, i--) { in compute_prefix_tbl()
152 for (j = i-1; j >= 1-g ; j--) in compute_prefix_tbl()
153 if (subpattern(bm->pattern, i, j, g)) { in compute_prefix_tbl()
154 bm->good_shift[g] = bm->patlen-j-g; in compute_prefix_tbl()
173 conf->flags = flags; in bm_init()
175 bm->patlen = len; in bm_init()
176 bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len; in bm_init()
179 bm->pattern[i] = toupper(((u8 *)pattern)[i]); in bm_init()
181 memcpy(bm->pattern, pattern, len); in bm_init()
190 return bm->pattern; in bm_get_pattern()
196 return bm->patlen; in bm_get_pattern_len()
219 MODULE_DESCRIPTION("Boyer-Moore text search implementation");