Mercurial > lbo > hg > leveldb-rs

changeset 74:f05cafb37230

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LdbIterator interface and adapt implementors
author Lewin Bormann <lbo@spheniscida.de>
date Sun, 17 Jul 2016 16:36:56 +0200
parents 416a07a89e9d
children 94ea2222178f
files src/block.rs src/memtable.rs src/skipmap.rs src/types.rs
diffstat 4 files changed, 72 insertions(+), 42 deletions(-) [+]
line wrap: on
line diff
--- a/src/block.rs	Fri Jul 15 20:21:26 2016 +0200
+++ b/src/block.rs	Sun Jul 17 16:36:56 2016 +0200
@@ -137,7 +137,7 @@
     }
 }
 
-impl<'a, C: 'a + Comparator> LdbIterator<'a> for BlockIter<'a, C> {
+impl<'a, C: 'a + Comparator> LdbIterator for BlockIter<'a, C> {
     fn reset(&mut self) {
         self.offset = 0;
         self.current_restart_ix = 0;
@@ -215,9 +215,12 @@
         !self.key.is_empty() && self.val_offset > 0 && self.val_offset < self.block.restarts_off
     }
 
-    fn current(&self) -> Self::Item {
-        assert!(self.valid());
-        (self.key.clone(), &self.block.data[self.val_offset..self.offset])
+    fn current(&self) -> Option<Self::Item> {
+        if self.valid() {
+            Some((self.key.clone(), &self.block.data[self.val_offset..self.offset]))
+        } else {
+            None
+        }
     }
 }
 
@@ -426,7 +429,7 @@
         block_iter.prev();
         assert!(block_iter.valid());
         assert_eq!(block_iter.current(),
-                   ("key1".as_bytes().to_vec(), "value1".as_bytes()));
+                   Some(("key1".as_bytes().to_vec(), "value1".as_bytes())));
         block_iter.prev();
         assert!(!block_iter.valid());
     }
@@ -451,11 +454,11 @@
         iter.seek(&"prefix_key2".as_bytes());
         assert!(iter.valid());
         assert_eq!(iter.current(),
-                   ("prefix_key2".as_bytes().to_vec(), "value".as_bytes()));
+                   Some(("prefix_key2".as_bytes().to_vec(), "value".as_bytes())));
 
         iter.seek(&"key1".as_bytes());
         assert!(iter.valid());
         assert_eq!(iter.current(),
-                   ("key1".as_bytes().to_vec(), "value1".as_bytes()));
+                   Some(("key1".as_bytes().to_vec(), "value1".as_bytes())));
     }
 }
--- a/src/memtable.rs	Fri Jul 15 20:21:26 2016 +0200
+++ b/src/memtable.rs	Sun Jul 17 16:36:56 2016 +0200
@@ -144,8 +144,8 @@
         let mut iter = self.map.iter();
         iter.seek(key.memtable_key());
 
-        if iter.valid() {
-            let foundkey = iter.current().0;
+        if let Some(e) = iter.current() {
+            let foundkey = e.0;
             let (lkeylen, lkeyoff, _, _, _) = Self::parse_memtable_key(key.memtable_key());
             let (fkeylen, fkeyoff, tag, vallen, valoff) = Self::parse_memtable_key(foundkey);
 
@@ -196,7 +196,7 @@
     }
 }
 
-impl<'a, C: 'a + Comparator> LdbIterator<'a> for MemtableIterator<'a, C> {
+impl<'a, C: 'a + Comparator> LdbIterator for MemtableIterator<'a, C> {
     fn reset(&mut self) {
         self.skipmapiter.reset();
     }
@@ -220,14 +220,20 @@
     fn valid(&self) -> bool {
         self.skipmapiter.valid()
     }
-    fn current(&'a self) -> Self::Item {
-        assert!(self.valid());
+    fn current(&self) -> Option<Self::Item> {
+        if !self.valid() {
+            return None;
+        }
 
-        let (foundkey, _): (&'a [u8], &'a [u8]) = self.skipmapiter.current();
-        let (keylen, keyoff, tag, vallen, valoff) = MemTable::<C>::parse_memtable_key(foundkey);
+        if let Some((foundkey, _)) = self.skipmapiter.current() {
+            let (keylen, keyoff, tag, vallen, valoff) = MemTable::<C>::parse_memtable_key(foundkey);
 
-        if tag & 0xff == ValueType::TypeValue as u64 {
-            return (&foundkey[keyoff..keyoff + keylen], &foundkey[valoff..valoff + vallen]);
+            if tag & 0xff == ValueType::TypeValue as u64 {
+                return Some((&foundkey[keyoff..keyoff + keylen],
+                             &foundkey[valoff..valoff + vallen]));
+            } else {
+                panic!("should not happen");
+            }
         } else {
             panic!("should not happen");
         }
@@ -324,12 +330,12 @@
 
         iter.next();
         assert!(iter.valid());
-        assert_eq!(iter.current().0, vec![97, 98, 99].as_slice());
-        assert_eq!(iter.current().1, vec![49, 50, 51].as_slice());
+        assert_eq!(iter.current().unwrap().0, vec![97, 98, 99].as_slice());
+        assert_eq!(iter.current().unwrap().1, vec![49, 50, 51].as_slice());
 
         iter.seek("abf".as_bytes());
-        assert_eq!(iter.current().0, vec![97, 98, 102].as_slice());
-        assert_eq!(iter.current().1, vec![49, 50, 54].as_slice());
+        assert_eq!(iter.current().unwrap().0, vec![97, 98, 102].as_slice());
+        assert_eq!(iter.current().unwrap().1, vec![49, 50, 54].as_slice());
     }
 
     #[test]
@@ -339,15 +345,15 @@
 
         iter.next();
         assert!(iter.valid());
-        assert_eq!(iter.current().0, vec![97, 98, 99].as_slice());
+        assert_eq!(iter.current().unwrap().0, vec![97, 98, 99].as_slice());
 
         iter.next();
         assert!(iter.valid());
-        assert_eq!(iter.current().0, vec![97, 98, 100].as_slice());
+        assert_eq!(iter.current().unwrap().0, vec![97, 98, 100].as_slice());
 
         iter.prev();
         assert!(iter.valid());
-        assert_eq!(iter.current().0, vec![97, 98, 99].as_slice());
+        assert_eq!(iter.current().unwrap().0, vec![97, 98, 99].as_slice());
 
         iter.prev();
         assert!(!iter.valid());
--- a/src/skipmap.rs	Fri Jul 15 20:21:26 2016 +0200
+++ b/src/skipmap.rs	Sun Jul 17 16:36:56 2016 +0200
@@ -260,7 +260,7 @@
     }
 }
 
-impl<'a, C: Comparator> LdbIterator<'a> for SkipMapIter<'a, C> {
+impl<'a, C: Comparator> LdbIterator for SkipMapIter<'a, C> {
     fn reset(&mut self) {
         let new = self.map.iter();
         self.current = new.current;
@@ -272,17 +272,24 @@
     fn valid(&self) -> bool {
         unsafe { !(*self.current).key.is_empty() }
     }
-    fn current(&'a self) -> Self::Item {
-        assert!(self.valid());
-        unsafe { (&(*self.current).key, &(*self.current).value) }
+    fn current(&self) -> Option<Self::Item> {
+        if self.valid() {
+            Some(unsafe { (&(*self.current).key, &(*self.current).value) })
+        } else {
+            None
+        }
     }
     fn prev(&mut self) -> Option<Self::Item> {
         // Going after the original implementation here; we just seek to the node before current().
-        let prev = self.map.get_next_smaller(self.current().0);
-        self.current = unsafe { transmute_copy(&prev) };
+        if let Some(current) = self.current() {
+            let prev = self.map.get_next_smaller(current.0);
+            self.current = unsafe { transmute_copy(&prev) };
 
-        if !prev.key.is_empty() {
-            Some(unsafe { (&(*self.current).key, &(*self.current).value) })
+            if !prev.key.is_empty() {
+                Some(unsafe { (&(*self.current).key, &(*self.current).value) })
+            } else {
+                None
+            }
         } else {
             None
         }
@@ -290,11 +297,11 @@
 }
 
 #[cfg(test)]
-mod tests {
+pub mod tests {
     use super::*;
     use types::*;
 
-    fn make_skipmap() -> SkipMap<StandardComparator> {
+    pub fn make_skipmap() -> SkipMap<StandardComparator> {
         let mut skm = SkipMap::new();
         let keys = vec!["aba", "abb", "abc", "abd", "abe", "abf", "abg", "abh", "abi", "abj",
                         "abk", "abl", "abm", "abn", "abo", "abp", "abq", "abr", "abs", "abt",
@@ -397,10 +404,12 @@
         iter.next();
         assert!(iter.valid());
         iter.seek(&"abz".as_bytes().to_vec());
-        assert_eq!(iter.current(), ("abz".as_bytes(), "def".as_bytes()));
+        assert_eq!(iter.current().unwrap(),
+                   ("abz".as_bytes(), "def".as_bytes()));
         // go back to beginning
         iter.seek(&"aba".as_bytes().to_vec());
-        assert_eq!(iter.current(), ("aba".as_bytes(), "def".as_bytes()));
+        assert_eq!(iter.current().unwrap(),
+                   ("aba".as_bytes(), "def".as_bytes()));
 
         iter.seek(&"".as_bytes().to_vec());
         assert!(iter.valid());
@@ -426,6 +435,7 @@
         assert!(!iter.valid());
         iter.seek(&"abc".as_bytes());
         iter.prev();
-        assert_eq!(iter.current(), ("abb".as_bytes(), "def".as_bytes()));
+        assert_eq!(iter.current().unwrap(),
+                   ("abb".as_bytes(), "def".as_bytes()));
     }
 }
--- a/src/types.rs	Fri Jul 15 20:21:26 2016 +0200
+++ b/src/types.rs	Sun Jul 17 16:36:56 2016 +0200
@@ -1,4 +1,5 @@
 use std::cmp::Ordering;
+use std::default::Default;
 
 pub enum ValueType {
     TypeDeletion = 0,
@@ -20,11 +21,11 @@
 
 /// Trait used to influence how SkipMap determines the order of elements. Use StandardComparator
 /// for the normal implementation using numerical comparison.
-pub trait Comparator: Copy {
+pub trait Comparator: Copy + Default {
     fn cmp(&[u8], &[u8]) -> Ordering;
 }
 
-#[derive(Clone, Copy)]
+#[derive(Clone, Copy, Default)]
 pub struct StandardComparator;
 
 impl Comparator for StandardComparator {
@@ -42,7 +43,7 @@
 /// This works because the iterators used are stateful and keep the last returned element.
 ///
 /// Note: Implementing types are expected to hold `!valid()` before the first call to `next()`.
-pub trait LdbIterator<'a>: Iterator {
+pub trait LdbIterator: 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...)
@@ -50,12 +51,22 @@
 
     /// Seek the iterator to `key` or the next bigger key.
     fn seek(&mut self, key: &[u8]);
-    /// Resets the iterator to be `!valid()` again
+    /// Resets the iterator to be `!valid()` again (before first element)
     fn reset(&mut self);
     /// Returns true if `current()` would return a valid item.
     fn valid(&self) -> bool;
-    /// Return the current item. Panics if `!valid()`.
-    fn current(&'a self) -> Self::Item;
+    /// Return the current item.
+    fn current(&self) -> Option<Self::Item>;
     /// Go to the previous item.
     fn prev(&mut self) -> Option<Self::Item>;
+
+    /// You should override this with a more efficient solution.
+    fn seek_to_last(&mut self) {
+        while let Some(_) = self.next() {
+        }
+    }
+    fn seek_to_first(&mut self) {
+        self.reset();
+        self.next();
+    }
 }