From 55787709c8208b78b9db258e2e8b05d4c4d2ffd6 Mon Sep 17 00:00:00 2001 From: Chris Mikkelson Date: Fri, 19 Jul 2024 12:10:19 -0500 Subject: [PATCH] WIP commit: attempt to make Source object safe Use associated iterator types instead of `impl Iter`. Move get, get_prefix, get_range to separate "Ranges" trait, with a generic default implementation based on iter() enabled by "DefaultRanges" trait. WIP due to one pesky lifetime issue. --- src/merger.rs | 29 ++++++++++++------- src/source.rs | 78 ++++++++++++++++++++++++++++++++++++--------------- 2 files changed, 75 insertions(+), 32 deletions(-) diff --git a/src/merger.rs b/src/merger.rs index a7d671e..78e0362 100644 --- a/src/merger.rs +++ b/src/merger.rs @@ -1,4 +1,4 @@ -use crate::{Entry, Iter, Source}; +use crate::{source::Ranges, Entry, Iter, Source}; use std::cmp::Ordering; use std::collections::BinaryHeap; @@ -42,7 +42,7 @@ impl Ord for MergeEntry { } } -struct MergeIter { +pub struct MergeIter { heap: BinaryHeap>, finished: Vec, last_key: Vec, @@ -145,19 +145,26 @@ impl Iter for MergeIter { } impl Source for Merger { - fn iter(&self) -> impl Iter { + type It = MergeIter; + fn iter(&self) -> Self::It { MergeIter::from(self.sources.iter().map(|s| s.iter())) } +} + +impl Ranges for Merger { + type Get = MergeIter<::Get>; + type Prefix = MergeIter<::Prefix>; + type Range = MergeIter<::Range>; - fn get(&self, key: &[u8]) -> impl Iter { + fn get(&self, key: &[u8]) -> Self::Get { MergeIter::from(self.sources.iter().map(|s| s.get(key))) } - fn get_prefix(&self, prefix: &[u8]) -> impl Iter { + fn get_prefix(&self, prefix: &[u8]) -> Self::Prefix { MergeIter::from(self.sources.iter().map(|s| s.get_prefix(prefix))) } - fn get_range(&self, start: &[u8], end: &[u8]) -> impl Iter { + fn get_range(&self, start: &[u8], end: &[u8]) -> Self::Range { MergeIter::from(self.sources.iter().map(|s| s.get_range(start, end))) } } @@ -167,15 +174,17 @@ mod test { use super::Merger; use crate::source::test::TestSource; use crate::{Entry, Source}; + use std::marker::PhantomData; fn tnum(m: u8) -> Vec { Vec::from_iter((1u8..255).into_iter().filter(|i| i % m == 0)) } - fn test_source(m: u8) -> TestSource { - TestSource(Vec::from_iter( - tnum(m).into_iter().map(|n| Entry::new(vec![n], vec![0])), - )) + fn test_source<'a>(m: u8) -> TestSource<'a> { + TestSource( + Vec::from_iter(tnum(m).into_iter().map(|n| Entry::new(vec![n], vec![0]))), + PhantomData, + ) } #[test] diff --git a/src/source.rs b/src/source.rs index 0bb74a6..1f7ce31 100644 --- a/src/source.rs +++ b/src/source.rs @@ -5,25 +5,43 @@ pub trait Iter: Iterator { fn seek(&mut self, key: &[u8]); } -impl<'a> Iter for Box { +impl Iter for Box { fn seek(&mut self, key: &[u8]) { self.as_mut().seek(key); } } pub trait Source { - fn iter(&self) -> impl Iter; + type It: Iter; + fn iter(&self) -> ::It; +} +pub trait DefaultRanges {} +pub trait Ranges { + type Get: Iter; + type Prefix: Iter; + type Range: Iter; + + fn get(&self, key: &[u8]) -> Self::Get; + fn get_prefix(&self, prefix: &[u8]) -> Self::Prefix; + fn get_range(&self, start: &[u8], end: &[u8]) -> Self::Range; +} - fn get(&self, key: &[u8]) -> impl Iter { +impl Ranges for S { + type Get = RangeIter<::It>; + type Prefix = PrefixIter<::It>; + type Range = RangeIter<::It>; + + fn get(&self, key: &[u8]) -> Self::Get { let mut res = RangeIter { iter: self.iter(), + start: Vec::from(key), end: Vec::from(key), }; res.seek(key); res } - fn get_prefix(&self, prefix: &[u8]) -> impl Iter { + fn get_prefix(&self, prefix: &[u8]) -> Self::Prefix { let mut res = PrefixIter { iter: self.iter(), prefix: Vec::from(prefix), @@ -32,9 +50,10 @@ pub trait Source { res } - fn get_range(&self, start: &[u8], end: &[u8]) -> impl Iter { + fn get_range(&self, start: &[u8], end: &[u8]) -> Self::Range { let mut res = RangeIter { iter: self.iter(), + start: Vec::from(start), end: Vec::from(end), }; res.seek(start); @@ -42,7 +61,7 @@ pub trait Source { } } -struct PrefixIter { +pub struct PrefixIter { iter: I, prefix: Vec, } @@ -65,8 +84,9 @@ impl Iter for PrefixIter { } } -struct RangeIter { +pub struct RangeIter { iter: I, + start: Vec, end: Vec, } @@ -84,18 +104,26 @@ impl Iterator for RangeIter { impl Iter for RangeIter { fn seek(&mut self, key: &[u8]) { - self.iter.seek(key); + if key <= self.start.as_slice() { + self.iter.seek(self.start.as_slice()); + } else if key > self.end.as_slice() { + self.iter.seek(self.end.as_slice()); + self.iter.next(); + } else { + self.iter.seek(key); + } } } #[cfg(test)] pub mod test { - use super::{Entry, Iter, Source}; + use super::{DefaultRanges, Entry, Iter, Ranges, Source}; + use std::marker::PhantomData; - pub struct TestSource(pub Vec); + pub struct TestSource<'a>(pub Vec, pub PhantomData<&'a u8>); struct TestIter<'a> { - source: &'a TestSource, + source: &'a TestSource<'a>, off: usize, } @@ -122,23 +150,29 @@ pub mod test { } } - impl Source for TestSource { - fn iter(&self) -> impl Iter { + impl<'a> Source for TestSource<'a> { + type It = TestIter<'a>; + + fn iter(&self) -> TestIter<'a> { TestIter { source: self, off: 0, } } } - - fn test_source() -> TestSource { - TestSource(vec![ - Entry::new(vec![0, 0, 0, 0], vec![0]), - Entry::new(vec![0, 0, 0, 1], vec![1]), - Entry::new(vec![0, 0, 1, 0], vec![2]), - Entry::new(vec![0, 1, 0, 0], vec![3]), - Entry::new(vec![1, 0, 0, 0], vec![4]), - ]) + impl<'a> DefaultRanges for TestSource<'a> {} + + fn test_source<'a>() -> TestSource<'a> { + TestSource( + vec![ + Entry::new(vec![0, 0, 0, 0], vec![0]), + Entry::new(vec![0, 0, 0, 1], vec![1]), + Entry::new(vec![0, 0, 1, 0], vec![2]), + Entry::new(vec![0, 1, 0, 0], vec![3]), + Entry::new(vec![1, 0, 0, 0], vec![4]), + ], + PhantomData, + ) } #[test] -- 2.50.1