Mercurial > lbo > hg > leveldb-rs
changeset 25:0fa95071021c
Convert all Iterator/LdbIterator types to use slices
efficiency yay!
| author | Lewin Bormann <lbo@spheniscida.de> |
|---|---|
| date | Sun, 12 Jun 2016 11:02:33 +0200 |
| parents | cc51ccd8970c |
| children | d54a08be9b8a |
| files | src/memtable.rs src/skipmap.rs src/types.rs |
| diffstat | 3 files changed, 60 insertions(+), 50 deletions(-) [+] |
line wrap: on
line diff
--- a/src/memtable.rs Sun Jun 12 11:01:45 2016 +0200 +++ b/src/memtable.rs Sun Jun 12 11:02:33 2016 +0200 @@ -118,13 +118,13 @@ buf } - /// Parses a memtable key and returns (keylen, key, tag, vallen, val). - /// If the key only contains (keylen, key, tag), the vallen and val return values will be + /// Parses a memtable key and returns (keylen, key offset, tag, vallen, val offset). + /// If the key only contains (keylen, key, tag), the vallen and val offset return values will be /// meaningless. - fn parse_memtable_key(mkey: &Vec<u8>) -> (usize, Vec<u8>, u64, usize, Vec<u8>) { + fn parse_memtable_key(mkey: &[u8]) -> (usize, usize, u64, usize, usize) { let (keylen, mut i): (usize, usize) = VarInt::decode_var(&mkey); - let key = mkey[i..i + keylen].to_vec(); + let keyoff = i; i += keylen; if mkey.len() > i { @@ -132,13 +132,14 @@ i += 8; let (vallen, j): (usize, usize) = VarInt::decode_var(&mkey[i..]); + + let valoff = i + j; + i += j; - let val = mkey[i..].to_vec(); - - return (keylen, key, tag, vallen, val); + return (keylen, keyoff, tag, vallen, valoff); } else { - return (keylen, key, 0, 0, Vec::new()); + return (keylen, keyoff, 0, 0, 0); } } @@ -149,12 +150,13 @@ if iter.valid() { let foundkey = iter.current().0; - let (lkeylen, lkey, _, _, _) = Self::parse_memtable_key(key.memtable_key()); - let (fkeylen, fkey, tag, vallen, val) = Self::parse_memtable_key(foundkey); + let (lkeylen, lkeyoff, _, _, _) = Self::parse_memtable_key(key.memtable_key()); + let (fkeylen, fkeyoff, tag, vallen, valoff) = Self::parse_memtable_key(foundkey); - if C::cmp(&lkey, &fkey) == Ordering::Equal { + if C::cmp(&key.memtable_key()[lkeyoff..lkeyoff + lkeylen], + &foundkey[fkeyoff..fkeyoff + fkeylen]) == Ordering::Equal { if tag & 0xff == ValueType::TypeValue as u64 { - return Result::Ok(val); + return Result::Ok(foundkey[valoff..valoff + vallen].to_vec()); } else { return Result::Err(Status::NotFound(String::new())); } @@ -177,15 +179,17 @@ } impl<'a, C: 'a + Comparator> Iterator for MemtableIterator<'a, C> { - type Item = (Vec<u8>, Vec<u8>); + type Item = (&'a [u8], &'a [u8]); fn next(&mut self) -> Option<Self::Item> { loop { if let Some((foundkey, _)) = self.skipmapiter.next() { - let (_, key, tag, _, val) = MemTable::<C>::parse_memtable_key(foundkey); + let (keylen, keyoff, tag, vallen, valoff) = + MemTable::<C>::parse_memtable_key(foundkey); if tag & 0xff == ValueType::TypeValue as u64 { - return Some((key, val)); + return Some((&foundkey[keyoff..keyoff + keylen], + &foundkey[valoff..valoff + vallen])); } else { continue; } @@ -200,14 +204,14 @@ fn valid(&self) -> bool { self.skipmapiter.valid() } - fn current(&self) -> Self::Item { + fn current(&'a self) -> Self::Item { assert!(self.valid()); - let (foundkey, _) = self.skipmapiter.current(); - let (_, key, tag, _, val) = MemTable::<C>::parse_memtable_key(foundkey); + let (foundkey, _): (&'a [u8], &'a [u8]) = self.skipmapiter.current(); + let (keylen, keyoff, tag, vallen, valoff) = MemTable::<C>::parse_memtable_key(foundkey); if tag & 0xff == ValueType::TypeValue as u64 { - return (key, val); + return (&foundkey[keyoff..keyoff + keylen], &foundkey[valoff..valoff + vallen]); } else { panic!("should not happen"); } @@ -249,7 +253,7 @@ &"123".as_bytes().to_vec()); assert_eq!(mt.map.iter().next().unwrap().0, - &vec![3, 97, 98, 99, 1, 123, 0, 0, 0, 0, 0, 0, 3, 49, 50, 51]); + vec![3, 97, 98, 99, 1, 123, 0, 0, 0, 0, 0, 0, 3, 49, 50, 51].as_slice()); } #[test] @@ -269,6 +273,7 @@ } if let Result::Ok(v) = mt.get(&LookupKey::new(&"abc".as_bytes().to_vec(), 124)) { + println!("{:?}", v); panic!("found"); } } @@ -282,23 +287,23 @@ iter.next(); assert!(iter.valid()); - assert_eq!(iter.current().0, vec![97, 98, 99]); - assert_eq!(iter.current().1, vec![49, 50, 51]); + assert_eq!(iter.current().0, vec![97, 98, 99].as_slice()); + assert_eq!(iter.current().1, vec![49, 50, 51].as_slice()); iter.seek(&"abf".as_bytes().to_vec()); - assert_eq!(iter.current().0, vec![97, 98, 102]); - assert_eq!(iter.current().1, vec![49, 50, 54]); + assert_eq!(iter.current().0, vec![97, 98, 102].as_slice()); + assert_eq!(iter.current().1, vec![49, 50, 54].as_slice()); } #[test] fn test_parse_memtable_key() { let key = vec![3, 1, 2, 3, 1, 123, 0, 0, 0, 0, 0, 0, 3, 4, 5, 6]; - let (keylen, key, tag, vallen, val) = + let (keylen, keyoff, tag, vallen, valoff) = MemTable::<StandardComparator>::parse_memtable_key(&key); assert_eq!(keylen, 3); - assert_eq!(key, vec![1, 2, 3]); + assert_eq!(&key[keyoff..keyoff + keylen], vec![1, 2, 3].as_slice()); assert_eq!(tag, 123 << 8 | 1); assert_eq!(vallen, 3); - assert_eq!(val, vec![4, 5, 6]); + assert_eq!(&key[valoff..valoff + vallen], vec![4, 5, 6].as_slice()); } }
--- a/src/skipmap.rs Sun Jun 12 11:01:45 2016 +0200 +++ b/src/skipmap.rs Sun Jun 12 11:02:33 2016 +0200 @@ -11,13 +11,13 @@ /// Trait used to influence how SkipMap determines the order of elements. Use StandardComparator /// for the normal implementation using numerical comparison. pub trait Comparator { - fn cmp(&Vec<u8>, &Vec<u8>) -> Ordering; + fn cmp(&[u8], &[u8]) -> Ordering; } pub struct StandardComparator; impl Comparator for StandardComparator { - fn cmp(a: &Vec<u8>, b: &Vec<u8>) -> Ordering { + fn cmp(a: &[u8], b: &[u8]) -> Ordering { a.cmp(b) } } @@ -230,6 +230,20 @@ current: *const Node, } +impl<'a, C: Comparator + 'a> Iterator for SkipMapIter<'a, C> { + type Item = (&'a [u8], &'a [u8]); + + fn next(&mut self) -> Option<Self::Item> { + // we first go to the next element, then return that -- in order to skip the head node + unsafe { + (*self.current).next.as_ref().map(|next| { + self.current = transmute_copy(&next.as_ref()); + ((*self.current).key.as_slice(), (*self.current).value.as_slice()) + }) + } + } +} + impl<'a, C: Comparator> LdbIterator<'a> for SkipMapIter<'a, C> { fn seek(&mut self, key: &Vec<u8>) { let node = self.map.get_greater_or_equal(key); @@ -238,26 +252,12 @@ fn valid(&self) -> bool { unsafe { !(*self.current).key.is_empty() } } - fn current(&'a self) -> (&'a Vec<u8>, &'a Vec<u8>) { + fn current(&'a self) -> Self::Item { assert!(self.valid()); unsafe { (&(*self.current).key, &(*self.current).value) } } } -impl<'a, C: Comparator + 'a> Iterator for SkipMapIter<'a, C> { - type Item = (&'a Vec<u8>, &'a Vec<u8>); - - fn next(&mut self) -> Option<Self::Item> { - // we first go to the next element, then return that -- in order to skip the head node - unsafe { - (*self.current).next.as_ref().map(|next| { - self.current = transmute_copy(&next.as_ref()); - (&(*self.current).key, &(*self.current).value) - }) - } - } -} - #[cfg(test)] mod tests { use super::*; @@ -345,12 +345,10 @@ iter.next(); assert!(iter.valid()); iter.seek(&"abz".as_bytes().to_vec()); - assert_eq!(iter.current(), - (&"abz".as_bytes().to_vec(), &"def".as_bytes().to_vec())); + assert_eq!(iter.current(), ("abz".as_bytes(), "def".as_bytes())); // go back to beginning iter.seek(&"aba".as_bytes().to_vec()); - assert_eq!(iter.current(), - (&"aba".as_bytes().to_vec(), &"def".as_bytes().to_vec())); + assert_eq!(iter.current(), ("aba".as_bytes(), "def".as_bytes())); iter.seek(&"".as_bytes().to_vec()); assert!(iter.valid());
--- a/src/types.rs Sun Jun 12 11:01:45 2016 +0200 +++ b/src/types.rs Sun Jun 12 11:02:33 2016 +0200 @@ -22,6 +22,10 @@ /// An extension of the standard `Iterator` trait that supports some methods necessary for LevelDB. /// This works because the iterators used are stateful and keep the last returned element. pub trait LdbIterator<'a>: Iterator { + // We're emulating LevelDB's Slice type here using actual slices with the lifetime of the + // iterator. The lifetime of the iterator is usually the one of the backing storage (Block, + // MemTable, SkipMap...) + //type Item = (&'a [u8], &'a [u8]); fn seek(&mut self, key: &Vec<u8>); fn valid(&self) -> bool; fn current(&'a self) -> Self::Item; @@ -56,7 +60,11 @@ impl SnapshotList { pub fn new() -> SnapshotList { - SnapshotList { map: HashMap::new(), newest: 0, oldest: 0 } + SnapshotList { + map: HashMap::new(), + newest: 0, + oldest: 0, + } } pub fn new_snapshot(&mut self, seq: SequenceNumber) -> Snapshot { @@ -91,7 +99,6 @@ pub fn empty(&self) -> bool { self.oldest == 0 } - } #[cfg(test)]