Lines Matching refs:needle
80 pub(crate) fn new(needle: &[u8]) -> Forward { in new()
81 if needle.is_empty() { in new()
85 let byteset = ApproximateByteSet::new(needle); in new()
86 let min_suffix = Suffix::forward(needle, SuffixKind::Minimal); in new()
87 let max_suffix = Suffix::forward(needle, SuffixKind::Maximal); in new()
94 let shift = Shift::forward(needle, period_lower_bound, critical_pos); in new()
111 needle: &[u8], in find()
113 debug_assert!(!needle.is_empty(), "needle should not be empty"); in find()
114 debug_assert!(needle.len() <= haystack.len(), "haystack too short"); in find()
118 self.find_small_imp(pre, haystack, needle, period) in find()
121 self.find_large_imp(pre, haystack, needle, shift) in find()
134 needle: &[u8], in find_general()
136 if needle.is_empty() { in find_general()
138 } else if haystack.len() < needle.len() { in find_general()
141 self.find(pre, haystack, needle) in find_general()
156 needle: &[u8], in find_small_imp()
159 let last_byte = needle.len() - 1; in find_small_imp()
162 while pos + needle.len() <= haystack.len() { in find_small_imp()
166 pos += pre.call(&haystack[pos..], needle)?; in find_small_imp()
169 if pos + needle.len() > haystack.len() { in find_small_imp()
175 pos += needle.len(); in find_small_imp()
179 while i < needle.len() && needle[i] == haystack[pos + i] { in find_small_imp()
182 if i < needle.len() { in find_small_imp()
187 while j > shift && needle[j] == haystack[pos + j] { in find_small_imp()
190 if j <= shift && needle[shift] == haystack[pos + shift] { in find_small_imp()
194 shift = needle.len() - period; in find_small_imp()
205 needle: &[u8], in find_large_imp()
208 let last_byte = needle.len() - 1; in find_large_imp()
210 'outer: while pos + needle.len() <= haystack.len() { in find_large_imp()
213 pos += pre.call(&haystack[pos..], needle)?; in find_large_imp()
214 if pos + needle.len() > haystack.len() { in find_large_imp()
221 pos += needle.len(); in find_large_imp()
225 while i < needle.len() && needle[i] == haystack[pos + i] { in find_large_imp()
228 if i < needle.len() { in find_large_imp()
232 if needle[j] != haystack[pos + j] { in find_large_imp()
247 pub(crate) fn new(needle: &[u8]) -> Reverse { in new()
248 if needle.is_empty() { in new()
252 let byteset = ApproximateByteSet::new(needle); in new()
253 let min_suffix = Suffix::reverse(needle, SuffixKind::Minimal); in new()
254 let max_suffix = Suffix::reverse(needle, SuffixKind::Maximal); in new()
262 let shift = Shift::reverse(needle, period_lower_bound, critical_pos); in new()
278 needle: &[u8], in rfind()
280 debug_assert!(!needle.is_empty(), "needle should not be empty"); in rfind()
281 debug_assert!(needle.len() <= haystack.len(), "haystack too short"); in rfind()
288 self.rfind_small_imp(haystack, needle, period) in rfind()
291 self.rfind_large_imp(haystack, needle, shift) in rfind()
300 fn rfind_general(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> { in rfind_general()
301 if needle.is_empty() { in rfind_general()
303 } else if haystack.len() < needle.len() { in rfind_general()
306 self.rfind(haystack, needle) in rfind_general()
314 needle: &[u8], in rfind_small_imp()
317 let nlen = needle.len(); in rfind_small_imp()
327 while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] { in rfind_small_imp()
330 if i > 0 || needle[0] != haystack[pos - nlen] { in rfind_small_imp()
335 while j < shift && needle[j] == haystack[pos - nlen + j] { in rfind_small_imp()
352 needle: &[u8], in rfind_large_imp()
355 let nlen = needle.len(); in rfind_large_imp()
363 while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] { in rfind_large_imp()
366 if i > 0 || needle[0] != haystack[pos - nlen] { in rfind_large_imp()
370 while j < nlen && needle[j] == haystack[pos - nlen + j] { in rfind_large_imp()
437 needle: &[u8], in forward()
441 let large = cmp::max(critical_pos, needle.len() - critical_pos); in forward()
442 if critical_pos * 2 >= needle.len() { in forward()
446 let (u, v) = needle.split_at(critical_pos); in forward()
460 needle: &[u8], in reverse()
464 let large = cmp::max(critical_pos, needle.len() - critical_pos); in reverse()
465 if (needle.len() - critical_pos) * 2 >= needle.len() { in reverse()
469 let (v, u) = needle.split_at(critical_pos); in reverse()
496 fn forward(needle: &[u8], kind: SuffixKind) -> Suffix { in forward()
497 debug_assert!(!needle.is_empty()); in forward()
519 while candidate_start + offset < needle.len() { in forward()
520 let current = needle[suffix.pos + offset]; in forward()
521 let candidate = needle[candidate_start + offset]; in forward()
546 fn reverse(needle: &[u8], kind: SuffixKind) -> Suffix { in reverse()
547 debug_assert!(!needle.is_empty()); in reverse()
550 let mut suffix = Suffix { pos: needle.len(), period: 1 }; in reverse()
551 if needle.len() == 1 { in reverse()
554 let mut candidate_start = needle.len() - 1; in reverse()
558 let current = needle[suffix.pos - offset - 1]; in reverse()
559 let candidate = needle[candidate_start - offset - 1]; in reverse()
652 fn new(needle: &[u8]) -> ApproximateByteSet { in new()
654 for &b in needle { in new()
680 fn get_suffix_forward(needle: &[u8], kind: SuffixKind) -> (&[u8], usize) { in get_suffix_forward()
681 let s = Suffix::forward(needle, kind); in get_suffix_forward()
682 (&needle[s.pos..], s.period) in get_suffix_forward()
686 fn get_suffix_reverse(needle: &[u8], kind: SuffixKind) -> (&[u8], usize) { in get_suffix_reverse()
687 let s = Suffix::reverse(needle, kind); in get_suffix_reverse()
688 (&needle[..s.pos], s.period) in get_suffix_reverse()
697 fn naive_maximal_suffix_forward(needle: &[u8]) -> &[u8] { in naive_maximal_suffix_forward()
698 let mut sufs = suffixes(needle); in naive_maximal_suffix_forward()
705 fn naive_maximal_suffix_reverse(needle: &[u8]) -> Vec<u8> { in naive_maximal_suffix_reverse()
706 let mut reversed = needle.to_vec(); in naive_maximal_suffix_reverse()
853 needle: &[u8], in twoway_find()
855 Forward::new(needle).find_general(None, haystack, needle) in twoway_find()
860 needle: &[u8], in twoway_rfind()
862 Reverse::new(needle).rfind_general(haystack, needle) in twoway_rfind()
875 let needle = "abab"; in regression_rev_small_period() localVariable
876 assert_eq!(Some(0), rfind(haystack.as_bytes(), needle.as_bytes())); in regression_rev_small_period()