Lines Matching +full:- +full:j
1 /* SPDX-License-Identifier: BSD-3-Clause */
3 * Copyright (c) 1994-2009 Red Hat, Inc.
33 /* Byte-wise substring search, using the Two-Way algorithm.
42 AVAILABLE(h, h_l, j, n_l) A macro that returns nonzero if there are
44 H[J]. H is 'unsigned char *', H_L, J,
46 lvalue. For NUL-terminated searches,
51 For case-insensitivity, you may optionally define:
67 /* We use the Two-Way string matching algorithm, which guarantees
70 Boyer-Moore algorithm to achieve improved (potentially sub-linear)
73 See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
74 and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
77 /* Point at which computing a bad-byte shift table is likely to be
82 hand, on non-POSIX systems with CHAR_BIT larger than eight, the
110 non-empty NEEDLE have a local period of at least 1 and no greater
128 size_t j; /* Index into NEEDLE for current candidate suffix. */ in critical_factorization() local
134 0 <= j < NEEDLE_LEN - 1 in critical_factorization()
135 -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed) in critical_factorization()
138 p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j] in critical_factorization()
144 j = 0; in critical_factorization()
146 while (j + k < needle_len) in critical_factorization()
148 a = CANON_ELEMENT (needle[j + k]); in critical_factorization()
153 j += k; in critical_factorization()
155 p = j - max_suffix; in critical_factorization()
164 j += p; in critical_factorization()
171 max_suffix = j++; in critical_factorization()
179 j = 0; in critical_factorization()
181 while (j + k < needle_len) in critical_factorization()
183 a = CANON_ELEMENT (needle[j + k]); in critical_factorization()
188 j += k; in critical_factorization()
190 p = j - max_suffix_rev; in critical_factorization()
199 j += p; in critical_factorization()
206 max_suffix_rev = j++; in critical_factorization()
219 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
226 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
228 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
234 size_t j; /* Index into current window of HAYSTACK. */ in two_way_short_needle() local
240 periodic (with a period as large as NEEDLE_LEN - suffix). */ in two_way_short_needle()
251 j = 0; in two_way_short_needle()
252 while (AVAILABLE (haystack, haystack_len, j, needle_len)) in two_way_short_needle()
257 == CANON_ELEMENT (haystack[i + j]))) in two_way_short_needle()
262 i = suffix - 1; in two_way_short_needle()
264 == CANON_ELEMENT (haystack[i + j]))) in two_way_short_needle()
265 --i; in two_way_short_needle()
267 return (RETURN_TYPE) (haystack + j); in two_way_short_needle()
270 j += period; in two_way_short_needle()
271 memory = needle_len - period; in two_way_short_needle()
275 j += i - suffix + 1; in two_way_short_needle()
284 period = MAX (suffix, needle_len - suffix) + 1; in two_way_short_needle()
285 j = 0; in two_way_short_needle()
286 while (AVAILABLE (haystack, haystack_len, j, needle_len)) in two_way_short_needle()
291 == CANON_ELEMENT (haystack[i + j]))) in two_way_short_needle()
296 i = suffix - 1; in two_way_short_needle()
298 == CANON_ELEMENT (haystack[i + j]))) in two_way_short_needle()
299 --i; in two_way_short_needle()
301 return (RETURN_TYPE) (haystack + j); in two_way_short_needle()
302 j += period; in two_way_short_needle()
305 j += i - suffix + 1; in two_way_short_needle()
311 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
318 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
321 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
328 size_t j; /* Index into current window of HAYSTACK. */ in two_way_long_needle() local
335 periodic (with a period as large as NEEDLE_LEN - suffix). */ in two_way_long_needle()
341 shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */ in two_way_long_needle()
345 shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1; in two_way_long_needle()
356 j = 0; in two_way_long_needle()
357 while (AVAILABLE (haystack, haystack_len, j, needle_len)) in two_way_long_needle()
361 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])]; in two_way_long_needle()
369 shift = needle_len - period; in two_way_long_needle()
372 j += shift; in two_way_long_needle()
378 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i]) in two_way_long_needle()
379 == CANON_ELEMENT (haystack[i + j]))) in two_way_long_needle()
381 if (needle_len - 1 <= i) in two_way_long_needle()
384 i = suffix - 1; in two_way_long_needle()
386 == CANON_ELEMENT (haystack[i + j]))) in two_way_long_needle()
387 --i; in two_way_long_needle()
389 return (RETURN_TYPE) (haystack + j); in two_way_long_needle()
392 j += period; in two_way_long_needle()
393 memory = needle_len - period; in two_way_long_needle()
397 j += i - suffix + 1; in two_way_long_needle()
407 period = MAX (suffix, needle_len - suffix) + 1; in two_way_long_needle()
408 j = 0; in two_way_long_needle()
409 while (AVAILABLE (haystack, haystack_len, j, needle_len)) in two_way_long_needle()
413 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])]; in two_way_long_needle()
416 j += shift; in two_way_long_needle()
422 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i]) in two_way_long_needle()
423 == CANON_ELEMENT (haystack[i + j]))) in two_way_long_needle()
425 if (needle_len - 1 <= i) in two_way_long_needle()
428 i = suffix - 1; in two_way_long_needle()
430 == CANON_ELEMENT (haystack[i + j]))) in two_way_long_needle()
431 --i; in two_way_long_needle()
433 return (RETURN_TYPE) (haystack + j); in two_way_long_needle()
434 j += period; in two_way_long_needle()
437 j += i - suffix + 1; in two_way_long_needle()