lolistealer/src/search.rs

//! Searcher in slice

use memchr::{
    memchr_iter,
    memrchr_iter,
};

#[inline]
#[cfg(feature="mem_find")] 
pub fn find(haystack: &[u8], needle: &[u8]) -> Option<usize>
{
    if needle.len() < 1 {
	return None;
    }
    for sz in memchr_iter(needle[0], haystack) {
	if &haystack[sz..std::cmp::min(sz+needle.len(), haystack.len())] == needle {
	    return Some(sz);
	}
    }

    None
}

#[inline]
#[cfg(feature="mem_find")] 
pub fn find_back(haystack: &[u8], needle: &[u8]) -> Option<usize>
{
    if needle.len() < 1 {
	return None;
    }
    for sz in memrchr_iter(needle[0], haystack) {
	if &haystack[sz..std::cmp::min(sz+needle.len(), haystack.len())] == needle {
	    return Some(sz+needle.len());
	}
    }

    None
}

#[inline(always)]
#[cfg(not(feature="mem_find"))]
pub fn find(haystack: &[u8], needle: &[u8]) -> Option<usize>
{
    wfind(haystack, needle)
}


#[inline(always)]
#[cfg(not(feature="mem_find"))]
pub fn find_back(haystack: &[u8], needle: &[u8]) -> Option<usize>
{
    wfind_back(haystack, needle)
}

#[inline]
fn wfind(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    haystack.windows(needle.len()).position(|window| window == needle)
}

#[inline]
fn wfind_back(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    haystack.windows(needle.len()).rev().position(|window| window == needle).and_then(|v| Some(haystack.len() - v))
}

#[cfg(test)]
mod tests
{
    use super::*;
    const HAYSTACK: &str = r#"awn r9anw09e8tja\ł]erj\æ][jw3-9r8ja9w8jera9je\đ →je\¶}j g\}iejđ \→æje\¶iaj-wie ¶3-928H09Q82H39 -Ł ¶j@\}]ẻ¶\ }æ]ĸ«ø𳶲38r 9W³¶\ ³¶}→ E→ ÞÆØ→ŁẺLOLE!!!¶ØĸÆŁŁ¶ĸØÞ@ĸ³øþĸ}@→Ħ³¶Ø@ŁŁĸ}→²ĦE}Ħ¶ 30r EJ}AJ"#;
    const NEEDLE: &str = "LOLE!!!";
    #[test]
    fn mfind()
    {
	let haystack = HAYSTACK.as_bytes();
	let needle= NEEDLE.as_bytes();

	assert_eq!(wfind(haystack, needle), find(haystack, needle));
    }
    
    #[test]
    fn mfind_back()
    {
	let haystack = HAYSTACK.as_bytes();
	let needle= NEEDLE.as_bytes();

	assert_eq!(wfind_back(haystack, needle), find_back(haystack, needle));
    }

    #[cfg(nightly)]
    mod benchmarks {
	use super::{
	    NEEDLE, HAYSTACK,
	};
	use test::{
	    Bencher, black_box,
	};
	#[bench]
	fn mfind(b: &mut Bencher)
	{
	    
	    let haystack = HAYSTACK.as_bytes();
	    let needle= NEEDLE.as_bytes();

	    b.iter(|| {
		black_box(super::find(haystack,needle));
	    });
	}
	#[bench]
	fn mfind_back(b: &mut Bencher)
	{
	    
	    let haystack = HAYSTACK.as_bytes();
	    let needle= NEEDLE.as_bytes();

	    b.iter(|| {
		black_box(super::find_back(haystack,needle));
	    });
	}
	
	#[bench]
	fn wfind(b: &mut Bencher)
	{
	    
	    let haystack = HAYSTACK.as_bytes();
	    let needle= NEEDLE.as_bytes();

	    b.iter(|| {
		black_box(super::wfind(haystack,needle));
	    });
	}
	#[bench]
	fn wfind_back(b: &mut Bencher)
	{
	    
	    let haystack = HAYSTACK.as_bytes();
	    let needle= NEEDLE.as_bytes();

	    b.iter(|| {
		black_box(super::wfind_back(haystack,needle));
	    });
	}
    }
}