Lines Matching refs:needle
7 the empty needle, the standard library reports matches only at valid UTF-8
51 # Example: repeating a search for the same needle
54 measurable in some workloads. In cases where the same needle is used to search
103 needle: Vec<u8>
105 proptests::matches_naive(false, &haystack, &needle, $fwd)
118 needle: Vec<u8>
120 proptests::matches_naive(true, &haystack, &needle, $rev)
169 /// with respect to both the needle and the haystack. That is, this runs
170 /// in `O(needle.len() + haystack.len())` time.
192 needle: &'n N,
194 FindIter::new(haystack, Finder::new(needle))
203 /// with respect to both the needle and the haystack. That is, this runs
204 /// in `O(needle.len() + haystack.len())` time.
226 needle: &'n N,
228 FindRevIter::new(haystack, FinderRev::new(needle))
231 /// Returns the index of the first occurrence of the given needle.
233 /// Note that if you're are searching for the same needle in many different
240 /// with respect to both the needle and the haystack. That is, this runs
241 /// in `O(needle.len() + haystack.len())` time.
259 pub fn find(haystack: &[u8], needle: &[u8]) -> Option<usize> {
261 rabinkarp::find(haystack, needle)
263 Finder::new(needle).find(haystack)
267 /// Returns the index of the last occurrence of the given needle.
269 /// Note that if you're are searching for the same needle in many different
276 /// with respect to both the needle and the haystack. That is, this runs
277 /// in `O(needle.len() + haystack.len())` time.
296 pub fn rfind(haystack: &[u8], needle: &[u8]) -> Option<usize> {
298 rabinkarp::rfind(haystack, needle)
300 FinderRev::new(needle).rfind(haystack)
309 /// needle.
329 /// borrows the finder and needle.
332 /// this copies the needle.
362 self.pos = pos + core::cmp::max(1, self.finder.needle().len());
374 /// needle.
379 /// When searching with an empty needle, this gets set to `None` after
395 /// borrows the finder and needle.
398 /// this copies the needle.
435 /// A single substring searcher fixed to a particular needle.
440 /// concern when it's necessary to re-use the same needle to search multiple
447 /// the lifetime of its needle.
454 /// Create a new finder for the given needle.
456 pub fn new<B: ?Sized + AsRef<[u8]>>(needle: &'n B) -> Finder<'n> {
457 FinderBuilder::new().build_forward(needle)
460 /// Returns the index of the first occurrence of this needle in the given
466 /// with respect to both the needle and the haystack. That is, this runs
467 /// in `O(needle.len() + haystack.len())` time.
493 /// with respect to both the needle and the haystack. That is, this runs
494 /// in `O(needle.len() + haystack.len())` time.
523 /// borrows the needle.
526 /// this copies the needle.
542 /// needle itself. Namely, a finder's needle can be either borrowed or
543 /// owned, so the lifetime of the needle returned must necessarily be the
550 /// Returns the needle that this finder searches for.
552 /// Note that the lifetime of the needle returned is tied to the lifetime
554 /// finder's needle can be either borrowed or owned, so the lifetime of the
555 /// needle returned must necessarily be the shorter of the two.
557 pub fn needle(&self) -> &[u8] {
558 self.searcher.needle()
562 /// A single substring reverse searcher fixed to a particular needle.
567 /// concern when it's necessary to re-use the same needle to search multiple
574 /// the lifetime of its needle.
581 /// Create a new reverse finder for the given needle.
583 pub fn new<B: ?Sized + AsRef<[u8]>>(needle: &'n B) -> FinderRev<'n> {
584 FinderBuilder::new().build_reverse(needle)
587 /// Returns the index of the last occurrence of this needle in the given
596 /// with respect to both the needle and the haystack. That is, this runs
597 /// in `O(needle.len() + haystack.len())` time.
624 /// with respect to both the needle and the haystack. That is, this runs
625 /// in `O(needle.len() + haystack.len())` time.
654 /// borrows the needle.
657 /// this copies the needle.
673 /// needle itself. Namely, a finder's needle can be either borrowed or
674 /// owned, so the lifetime of the needle returned must necessarily be the
681 /// Returns the needle that this finder searches for.
683 /// Note that the lifetime of the needle returned is tied to the lifetime
685 /// finder's needle can be either borrowed or owned, so the lifetime of the
686 /// needle returned must necessarily be the shorter of the two.
688 pub fn needle(&self) -> &[u8] {
689 self.searcher.needle()
709 /// Build a forward finder using the given needle from the current
713 needle: &'n B,
715 Finder { searcher: Searcher::new(self.config, needle.as_ref()) }
718 /// Build a reverse finder using the given needle from the current
722 needle: &'n B,
724 FinderRev { searcher: SearcherRev::new(needle.as_ref()) }
740 /// variety of parameters (CPU support, target, needle size, haystack size and
745 /// The actual needle we're searching for.
749 needle: CowBytes<'n>,
750 /// A collection of facts computed on the needle that are useful for more
762 /// A collection of facts computed about a search needle.
768 /// The offsets of "rare" bytes detected in the needle.
772 /// one or two bytes. If we pick bytes from the needle that occur
779 /// A Rabin-Karp hash of the needle.
801 /// A special case for empty needles. An empty needle always matches, even
804 /// This is used whenever the needle is a single byte. In this case, we
808 /// linear time guarantee. In general, it's used when the needle is bigger
820 fn new(config: SearcherConfig, needle: &'n [u8]) -> Searcher<'n> {
823 let ninfo = NeedleInfo::new(needle);
828 needle,
830 Searcher { needle: CowBytes::new(needle), ninfo, prefn, kind }
832 if needle.len() == 0 {
835 if needle.len() == 1 {
836 return mk(OneByte(needle[0]));
840 if let Some(fwd) = x86::avx::Forward::new(&ninfo, needle) {
842 } else if let Some(fwd) = x86::sse::Forward::new(&ninfo, needle) {
848 if let Some(fwd) = wasm::Forward::new(&ninfo, needle) {
853 mk(TwoWay(twoway::Forward::new(needle)))
873 fn needle(&self) -> &[u8] {
874 self.needle.as_slice()
894 needle: CowBytes::new(self.needle()),
919 needle: self.needle.into_owned(),
937 let needle = self.needle();
938 if haystack.len() < needle.len() {
947 if rabinkarp::is_fast(haystack, needle) {
948 rabinkarp::find_with(&self.ninfo.nhash, haystack, needle)
950 self.find_tw(tw, state, haystack, needle)
958 rabinkarp::find_with(&self.ninfo.nhash, haystack, needle)
960 gs.find(haystack, needle)
972 rabinkarp::find_with(&self.ninfo.nhash, haystack, needle)
974 gs.find(haystack, needle)
980 /// Calls Two-Way on the given haystack/needle.
995 needle: &[u8],
1005 return tw.find(Some(&mut pre), haystack, needle);
1008 tw.find(None, haystack, needle)
1013 pub(crate) fn new(needle: &[u8]) -> NeedleInfo {
1015 rarebytes: RareNeedleBytes::forward(needle),
1016 nhash: NeedleHash::forward(needle),
1030 /// The actual needle we're searching for.
1031 needle: CowBytes<'n>,
1032 /// A Rabin-Karp hash of the needle.
1040 /// A special case for empty needles. An empty needle always matches, even
1043 /// This is used whenever the needle is a single byte. In this case, we
1047 /// linear time guarantee. In general, it's used when the needle is bigger
1053 fn new(needle: &'n [u8]) -> SearcherRev<'n> {
1056 let kind = if needle.len() == 0 {
1058 } else if needle.len() == 1 {
1059 OneByte(needle[0])
1061 TwoWay(twoway::Reverse::new(needle))
1064 needle: CowBytes::new(needle),
1065 nhash: NeedleHash::reverse(needle),
1070 fn needle(&self) -> &[u8] {
1071 self.needle.as_slice()
1083 needle: CowBytes::new(self.needle()),
1099 needle: self.needle.into_owned(),
1112 let needle = self.needle();
1113 if haystack.len() < needle.len() {
1122 if rabinkarp::is_fast(haystack, needle) {
1123 rabinkarp::rfind_with(&self.nhash, haystack, needle)
1125 tw.rfind(haystack, needle)
1189 needle: &[u8],
1193 naive_rfind(haystack, needle) == search(haystack, needle)
1195 naive_find(haystack, needle) == search(haystack, needle)
1199 /// Naively search forwards for the given needle in the given haystack.
1200 fn naive_find(haystack: &[u8], needle: &[u8]) -> Option<usize> {
1201 if needle.is_empty() {
1203 } else if haystack.len() < needle.len() {
1206 for i in 0..(haystack.len() - needle.len() + 1) {
1207 if needle == &haystack[i..i + needle.len()] {
1214 /// Naively search in reverse for the given needle in the given haystack.
1215 fn naive_rfind(haystack: &[u8], needle: &[u8]) -> Option<usize> {
1216 if needle.is_empty() {
1218 } else if haystack.len() < needle.len() {
1221 for i in (0..(haystack.len() - needle.len() + 1)).rev() {
1222 if needle == &haystack[i..i + needle.len()] {
1237 /// Each test is a (needle, haystack, expected_fwd, expected_rev) tuple.
1283 /// accepts a haystack and a needle and returns the starting position
1284 /// of the first occurrence of needle in the haystack, or `None` if one
1289 for &(needle, haystack, expected_fwd, _) in SEARCH_TESTS {
1290 let (n, h) = (needle.as_bytes(), haystack.as_bytes());
1294 "needle: {:?}, haystack: {:?}, expected: {:?}",
1303 /// accepts a haystack and a needle and returns the starting position of
1304 /// the last occurrence of needle in the haystack, or `None` if one doesn't
1309 for &(needle, haystack, _, expected_rev) in SEARCH_TESTS {
1310 let (n, h) = (needle.as_bytes(), haystack.as_bytes());
1314 "needle: {:?}, haystack: {:?}, expected: {:?}",