diff options
Diffstat (limited to 'src/router.rs')
| -rw-r--r-- | src/router.rs | 162 |
1 files changed, 162 insertions, 0 deletions
diff --git a/src/router.rs b/src/router.rs new file mode 100644 index 0000000..18ed429 --- /dev/null +++ b/src/router.rs @@ -0,0 +1,162 @@ +use std::collections::VecDeque; + +#[derive(Clone, Copy)] +enum TablePointer<R> where R: Clone + Copy { + Link(usize), + Route(R), + RouteWithLink(usize, R), + NotFound, +} + +pub struct NoMatchingRoute; + +pub type RouteMatch<'a, R> = Result<(R, &'a str), NoMatchingRoute>; + +#[derive(Clone)] +pub struct RoutingTable<R> where R: Copy { + tables: Vec<[TablePointer<R>; 128]>, +} + +impl<R> RoutingTable<R> where R: Copy { + pub fn new() -> RoutingTable<R> { + let zero_table = [TablePointer::NotFound; 128]; + RoutingTable { + tables: vec![zero_table], + } + } + + pub fn insert(&mut self, path: &str, route: R) { + assert!(!path.is_empty()); + let mut index: usize = 0; + let p: Vec<usize> = path.as_bytes().iter().map(|i| usize::from(*i)).collect(); + let mut path_queue = VecDeque::from(p); + + while path_queue.len() > 1 { + let ch = path_queue.pop_front().unwrap() as usize % 128; + match self.tables[index][ch] { + TablePointer::NotFound => { + self.tables.push([TablePointer::NotFound; 128]); + let i_other_table = self.tables.len() - 1; + self.tables[index][ch] = TablePointer::Link(i_other_table); + path_queue.push_front(ch); + } + TablePointer::Link(i_other_table) => { + index = i_other_table as usize; + } + TablePointer::RouteWithLink(i_other_table, _) => { + index = i_other_table as usize; + path_queue.push_front(ch); + } + TablePointer::Route(route) => { + self.tables.push([TablePointer::NotFound; 128]); + let i_other_table = self.tables.len() - 1; + self.tables[index][ch] = TablePointer::RouteWithLink(i_other_table, route); + path_queue.push_front(ch); + } + } + } + // last character element in path + let ch = path_queue.pop_front().unwrap() % 128; + match self.tables[index][ch] { + TablePointer::NotFound => { + // slot is empty, just place the Route + self.tables[index][ch] = TablePointer::Route(route) + } + TablePointer::Link(i) => { + // slot is filled with link to longer path. Replace by RouteWithLink + self.tables[index][ch] = TablePointer::RouteWithLink(i, route); + } + _ => { + panic!("Not expected here, maybe duplicate") + } + } + } + + pub fn match_path<'a>(&self, path: &'a str) -> RouteMatch<'a, R> { + let mut table: &[TablePointer<R>; 128] = &self.tables[0]; + let path_bytes = path.as_bytes(); + let path_max_i = path_bytes.len() - 1; + + let mut i = 0; + while i <= path_max_i { + let ch = path_bytes[i] as usize % 128; + match table[ch] { + TablePointer::NotFound => { + return Err(NoMatchingRoute); + } + TablePointer::Link(i_other_table) => { + table = &self.tables[i_other_table]; + i += 1; + } + TablePointer::RouteWithLink(i_other_table, route) => { + if i == path_max_i { + return Ok((route, Default::default())); + } else { + table = &self.tables[i_other_table]; + } + } + TablePointer::Route(route) => { + return Ok((route, path.get(i + 1..=path_max_i).unwrap())); + } + } + } + Err(NoMatchingRoute) + } +} + +#[cfg(test)] +mod test1 { + use super::*; + use test::Bencher; + + #[derive(Clone, Copy)] + enum Route { + Login, + Logout, + Info, + Check + } + + #[bench] + fn bench_1(b: &mut Bencher) { + let mut r = RoutingTable::new(); + r.insert("/login", Route::Login); + r.insert("/info", Route::Info); + r.insert("/logout", Route::Logout); + r.insert("/logout2", Route::Info); + r.insert("/check", Route::Check); + + match r.tables[0][47] { + TablePointer::Link(n) => assert!(n == 1), + _ => panic!("Wrong"), + } + + b.iter(|| { + match r.match_path("/login") { + RouteMatch::Match(Route::Login, rest) => assert_eq!(rest, ""), + _ => panic!("Wrong") + } + match r.match_path("/logout") { + RouteMatch::Match(Route::Logout, rest) => assert_eq!(rest, ""), + _ => panic!("Wrong") + } + match r.match_path("/info") { + RouteMatch::Match(Route::Info, rest) => assert_eq!(rest, ""), + _ => panic!("Wrong") + } + match r.match_path("/logout2") { + RouteMatch::Match(Route::Info, rest) => assert_eq!(rest, ""), + _ => panic!("Wrong") + } + match r.match_path("/asdasdasd") { + RouteMatch::None => (), + _ => panic!("Wrong") + } + + match r.match_path("/login/foo/bar") { + RouteMatch::Match(Route::Login, rest) => assert_eq!(rest, "/foo/bar"), + _ => panic!("Wrong") + } + }) + } +}
\ No newline at end of file |