From 16649f5db93dc4e745ab8bb35a90f20acaecfabe Mon Sep 17 00:00:00 2001 From: Chris Mikkelson Date: Sun, 7 Apr 2024 11:56:05 -0500 Subject: [PATCH 1/1] Initial commit --- .gitignore | 1 + Cargo.lock | 65 +++++++++++++++ Cargo.toml | 9 ++ src/bin/mtbl_dump.rs | 3 + src/bin/mtbl_info.rs | 3 + src/bin/mtbl_merge.rs | 3 + src/bin/mtbl_verify.rs | 3 + src/entry.rs | 89 ++++++++++++++++++++ src/iter.rs | 182 +++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 5 ++ tests/entry.rs | 9 ++ 11 files changed, 372 insertions(+) create mode 100644 .gitignore create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 src/bin/mtbl_dump.rs create mode 100644 src/bin/mtbl_info.rs create mode 100644 src/bin/mtbl_merge.rs create mode 100644 src/bin/mtbl_verify.rs create mode 100644 src/entry.rs create mode 100644 src/iter.rs create mode 100644 src/lib.rs create mode 100644 tests/entry.rs diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/target diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..457e834 --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,65 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "lender" +version = "0.2.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "39b1f7f753a5da003547d93e9e8f6542e81db06adad15dda47a9cd12559ab2e0" +dependencies = [ + "lender-derive", +] + +[[package]] +name = "lender-derive" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "556faf0c9adb22669a5f9f6b4ed804c8048d205dcd00fadd463affbb02931d26" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "mtbl" +version = "0.1.0" +dependencies = [ + "lender", +] + +[[package]] +name = "proc-macro2" +version = "1.0.79" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e835ff2298f5721608eb1a980ecaee1aef2c132bf95ecc026a11b7bf3c01c02e" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "quote" +version = "1.0.35" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "291ec9ab5efd934aaf503a6466c5d5251535d108ee747472c3977cc5acc868ef" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "syn" +version = "2.0.57" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "11a6ae1e52eb25aab8f3fb9fca13be982a373b8f1157ca14b897a825ba4a2d35" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "unicode-ident" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..66ae1c3 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "mtbl" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +lender = "0.2.9" diff --git a/src/bin/mtbl_dump.rs b/src/bin/mtbl_dump.rs new file mode 100644 index 0000000..e7a11a9 --- /dev/null +++ b/src/bin/mtbl_dump.rs @@ -0,0 +1,3 @@ +fn main() { + println!("Hello, world!"); +} diff --git a/src/bin/mtbl_info.rs b/src/bin/mtbl_info.rs new file mode 100644 index 0000000..e7a11a9 --- /dev/null +++ b/src/bin/mtbl_info.rs @@ -0,0 +1,3 @@ +fn main() { + println!("Hello, world!"); +} diff --git a/src/bin/mtbl_merge.rs b/src/bin/mtbl_merge.rs new file mode 100644 index 0000000..e7a11a9 --- /dev/null +++ b/src/bin/mtbl_merge.rs @@ -0,0 +1,3 @@ +fn main() { + println!("Hello, world!"); +} diff --git a/src/bin/mtbl_verify.rs b/src/bin/mtbl_verify.rs new file mode 100644 index 0000000..e7a11a9 --- /dev/null +++ b/src/bin/mtbl_verify.rs @@ -0,0 +1,3 @@ +fn main() { + println!("Hello, world!"); +} diff --git a/src/entry.rs b/src/entry.rs new file mode 100644 index 0000000..23088fa --- /dev/null +++ b/src/entry.rs @@ -0,0 +1,89 @@ +use std::cmp::Ordering; +pub use std::rc::Rc; + +#[derive(Debug, Clone)] +pub struct Entry { + pub key: Rc>, + pub value: Rc>, +} + +impl Entry { + pub fn new() -> Entry { + Entry { + key: Rc::new(Vec::new()), + value: Rc::new(Vec::new()), + } + } + pub fn from_key_value, V: AsRef<[u8]>>(k: K, v: V) -> Entry { + let mut key = Vec::::with_capacity(k.as_ref().len()); + let mut value = Vec::::with_capacity(v.as_ref().len()); + + key.extend_from_slice(k.as_ref()); + value.extend_from_slice(v.as_ref()); + + Entry { + key: Rc::new(key), + value: Rc::new(value), + } + } + + pub fn unpack(&self) -> (&[u8], &[u8]) { + (self.key.as_slice(), self.value.as_slice()) + } +} + +// Entries are ordered and compared by key only +impl PartialOrd for Entry { + fn partial_cmp(&self, other: &Self) -> Option { + self.key.partial_cmp(&other.key) + } +} + +impl PartialEq for Entry { + fn eq(&self, other: &Self) -> bool { + self.key == other.key + } +} + +#[cfg(test)] +mod test { + + use crate::*; + + struct TestIter(Entry); + + impl TestIter { + fn new() -> TestIter { + TestIter(Entry::new()) + } + } + + impl Iterator for TestIter { + type Item = Entry; + + fn next(&mut self) -> Option { + println!("key strong_count = {}", Rc::strong_count(&self.0.key)); + Rc::make_mut(&mut self.0.key).push(0); + Some(self.0.clone()) + } + } + + #[test] + fn test_iter() { + for e in TestIter::new() { + if e.key.len() > 3 { + break; + } + } + } + + #[test] + fn test_iter_filter() { + for e in TestIter::new().filter(|x: &Entry| x.key.len() % 2 == 0) { + println!("{:?}", e); + if e.key.len() > 6 { + break; + } + } + } +} diff --git a/src/iter.rs b/src/iter.rs new file mode 100644 index 0000000..5c4ab88 --- /dev/null +++ b/src/iter.rs @@ -0,0 +1,182 @@ +use crate::entry::Entry; +use std::cell::RefCell; +use std::iter::Iterator; +use std::rc::Rc; + +pub trait Iter: Iterator + Sized { + fn seek>(&mut self, key: T); + + fn wrap_iter) -> O, O: Iterator>(self, f: F) -> impl Iter + { + let it = IterBox::new(self); + WrapIter { + inner: it.clone(), + outer: f(it), + } + } + + // provided methods + fn filter_seek(&mut self, filter: F) -> impl Iter + where + F: FnMut(&Entry, &mut Vec) -> FilterSeekResult, + { + FilterSeek { + inner: self, + filter_func: filter, + seek_key: Vec::new(), + } + } +} + +// WrapIter + +pub struct IterBox(Rc>); + +impl Clone for IterBox { + fn clone(&self) -> Self { + IterBox(self.0.clone()) + } +} + +impl IterBox { + fn new(i: I) -> IterBox { + IterBox(Rc::new(RefCell::new(i))) + } +} + +impl Iterator for IterBox { + type Item = Entry; + + fn next(&mut self) -> Option { + self.0.borrow_mut().next() + } +} + +impl Iter for IterBox { + fn seek>(&mut self, key: T) { + self.0.borrow_mut().seek(key); + } +} + +struct WrapIter> { + inner: IterBox, + outer: O, +} + +impl> Iterator for WrapIter { + type Item = Entry; + + fn next(&mut self) -> Option { + self.outer.next() + } +} + +impl> Iter for WrapIter { + fn seek>(&mut self, key: T) { + self.inner.seek(key) + } +} + +// FilterSeek + +pub enum FilterSeekResult { + Keep, + Skip, + Seek, +} +pub use FilterSeekResult::*; + +struct FilterSeek<'i, I: Iterator, F: FnMut(&Entry, &mut Vec) -> FilterSeekResult> +{ + inner: &'i mut I, + filter_func: F, + seek_key: Vec, +} + +impl<'i, I, F> Iterator for FilterSeek<'i, I, F> +where + F: FnMut(&Entry, &mut Vec) -> FilterSeekResult, + I: Iter, +{ + type Item = Entry; + + fn next(&mut self) -> Option { + self.seek_key.clear(); + while let Some(e) = self.inner.next() { + match (self.filter_func)(&e, &mut self.seek_key) { + Skip => continue, + Keep => return Some(e), + Seek => self.inner.seek(self.seek_key.as_slice()), + } + } + None + } +} + +impl<'i, I, F> Iter for FilterSeek<'i, I, F> +where + F: FnMut(&Entry, &mut Vec) -> FilterSeekResult, + I: Iter, +{ + fn seek>(&mut self, key: T) { + self.inner.seek(key.as_ref()); + } +} + +#[cfg(test)] +mod test { + use super::*; + + struct TestIter(u8); + + impl Iterator for TestIter { + type Item = Entry; + + fn next(&mut self) -> Option { + match self.0 { + 255 => None, + _ => { + let res = Entry::from_key_value(vec![self.0], vec![self.0]); + self.0 = self.0 + 1; + Some(res) + } + } + } + } + + impl Iter for TestIter { + fn seek>(&mut self, kr: T) { + self.0 = kr.as_ref()[0]; + } + } + + #[test] + fn test_iter_filter() { + let mut ti = TestIter(0); + let v: Vec = ti + .filter_seek(|e, k| { + let b = e.key[0]; + if b % 2 > 0 { + if b < 60 { + k.push((b + 1) * 4); + return FilterSeekResult::Seek; + } + return FilterSeekResult::Skip; + } + FilterSeekResult::Keep + }) + .filter(|e| e.key[0] % 5 == 0) + .collect(); + println!("length = {}", v.len()); + assert!(v.into_iter().all(|e| e.key[0] % 2 == 0)); + } + + #[test] + fn test_iter_wrap() { + let ti = TestIter(0); + let mut mi = ti.wrap_iter(|i| i.filter(|e| e.key[0] % 2 == 0)); + mi.seek(&[100]); + let v: Vec = mi.collect(); + println!("{:?}", v); + } +} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..34db328 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,5 @@ +pub mod entry; +pub mod iter; + +pub use entry::*; +pub use iter::*; diff --git a/tests/entry.rs b/tests/entry.rs new file mode 100644 index 0000000..343cb68 --- /dev/null +++ b/tests/entry.rs @@ -0,0 +1,9 @@ +use mtbl; + +#[test] +fn from_key_value() { + let e = mtbl::Entry::from_key_value(vec![0u8, 1, 2, 3], vec![4u8, 5, 6, 7]); + println!("{:?}", e); + let (k, v) = e.unpack(); + println!("{:?}", (k, v)); +} -- 2.50.1