Last active
December 7, 2016 22:00
-
-
Save gmbeard/5944b82c1bd644958873b3211066709f to your computer and use it in GitHub Desktop.
Non-allocating search for a word in a stream by rotate-and-read
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::io::Read; | |
fn fill(buf: &mut [u8]) { | |
for (i, n) in buf.iter_mut().enumerate() { | |
*n = i as u8; | |
} | |
} | |
fn rotate<T: Copy + Default>(buf: &mut [T], at: usize) -> usize { | |
let num = buf.len() - at; | |
let ptr = buf[at..].as_ptr(); // as *const T; | |
unsafe { | |
std::ptr::copy(ptr, buf[0..].as_mut_ptr(), num); | |
} | |
// for n in at..buf.len() { | |
// let tmp = std::mem::replace(&mut buf[n], T::default()); | |
// std::mem::replace(&mut buf[n-at], tmp); | |
// } | |
num | |
} | |
fn position<T: PartialEq>(buf: &[T], comp: &[T]) -> Option<usize> { | |
let mut matches = 0; | |
let result = buf.iter().position(|v| { | |
if *v == comp[matches] { | |
matches += 1; | |
} | |
else { | |
matches = 0; | |
} | |
if matches == comp.len() { | |
true | |
} | |
else { | |
false | |
} | |
}); | |
match result { | |
Some(n) => Some(n + 1 - matches), | |
_ => None | |
} | |
} | |
fn find_in_stream<T: Read>(mut buf: Vec<u8>, mut stream: T, phrase: &[u8]) | |
-> Option<usize> { | |
let mut consumed = 0; | |
let mut read_from = 0; | |
let mut pos = None; | |
loop { | |
match stream.read(&mut buf[read_from..]) { | |
Ok(0) | Err(_) => break, | |
Ok(_) => {} | |
} | |
if let Some(n) = position(&buf, phrase) { | |
pos = Some(n + consumed); | |
break; | |
} | |
read_from = buf.len() / 2; | |
consumed += rotate(&mut buf, read_from); | |
} | |
pos | |
} | |
fn main() { | |
println!("Hello, world!"); | |
} | |
#[cfg(test)] | |
mod tests { | |
extern crate std; | |
use std::vec::Vec; | |
use std::io::Cursor; | |
use super::{fill, rotate, find_in_stream}; | |
const PHRASE: &'static [u8] | |
= b"The quick brown fox jumps over the lazy dog"; | |
#[test] | |
fn should_rotate() { | |
let mut buf: Vec<u8> = Vec::with_capacity(10); | |
buf.resize(10, 0x00); | |
fill(&mut buf); | |
let i = rotate(&mut buf, 8); | |
assert_eq!(&buf[..i], &[8, 9]); | |
} | |
#[test] | |
fn should_find_word_at_correct_position() { | |
const BUFFER_SIZE: usize = 16; | |
let mut buf = Vec::<u8>::with_capacity(BUFFER_SIZE); | |
buf.resize(BUFFER_SIZE, 0x00); | |
let reader = Cursor::new(PHRASE); | |
assert_eq!(Some(20), find_in_stream(buf, reader, b"jumps")); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment