--- a/src/block.rs	Sun Jun 12 17:10:19 2016 +0200
+++ b/src/block.rs	Sun Jun 12 18:55:42 2016 +0200
@@ -67,6 +67,7 @@
             offset: 0,
             key: Vec::new(),
             val_offset: 0,
+            current_entry_offset: 0,
         }
     }
 }
@@ -74,7 +75,11 @@
 
 pub struct BlockIter<'a, C: 'a + Comparator> {
     block: &'a Block<C>,
+    // start of next entry
     offset: usize,
+    // start of current entry
+    current_entry_offset: usize,
+    // tracks the last restart we encountered
     current_restart_ix: usize,
 
     // We assemble the key from two parts usually, so we keep the current full key here.
@@ -119,9 +124,9 @@
     type Item = (Vec<u8>, &'a [u8]);
 
     fn next(&mut self) -> Option<Self::Item> {
-        let current_offset = self.offset;
+        self.current_entry_offset = self.offset;
 
-        if current_offset >= self.block.restarts_off {
+        if self.current_entry_offset >= self.block.restarts_off {
             return None;
         }
         let (shared, non_shared, valsize) = self.parse_entry();
@@ -132,7 +137,8 @@
 
         let num_restarts = self.block.number_restarts();
         while self.current_restart_ix + 1 < num_restarts &&
-              self.block.get_restart_point(self.current_restart_ix + 1) < current_offset {
+              self.block.get_restart_point(self.current_restart_ix + 1) <
+              self.current_entry_offset {
             self.current_restart_ix += 1;
         }
         Some((self.key.clone(), &self.block.data[self.val_offset..self.val_offset + valsize]))
@@ -140,6 +146,36 @@
 }
 
 impl<'a, C: 'a + Comparator> LdbIterator<'a> for BlockIter<'a, C> {
+    fn prev(&mut self) -> Option<Self::Item> {
+        // as in the original implementation -- seek to last restart point, then look for key
+        let current_offset = self.current_entry_offset;
+
+        // At the beginning, can't go further back
+        if current_offset == 0 {
+            self.reset();
+            return None;
+        }
+
+        while self.block.get_restart_point(self.current_restart_ix) >= current_offset {
+            self.current_restart_ix -= 1;
+        }
+
+        self.offset = self.block.get_restart_point(self.current_restart_ix);
+        assert!(self.offset < current_offset);
+
+        let mut result;
+
+        loop {
+            result = self.next();
+            println!("next! {:?}", (self.current_entry_offset, self.offset));
+
+            if self.offset >= current_offset {
+                break;
+            }
+        }
+        result
+
+    }
     fn seek(&mut self, to: &[u8]) {
         self.reset();
 
@@ -321,7 +357,6 @@
         }
 
         let block_contents = builder.finish();
-
         let block = Block::new(block_contents);
         let block_iter = block.iter();
         let mut i = 0;
@@ -334,6 +369,35 @@
     }
 
     #[test]
+    fn test_iterate_reverse() {
+        let mut o = Options::default();
+        o.block_restart_interval = 3;
+        let data = get_data();
+        let mut builder = BlockBuilder::new(o);
+
+        for &(k, v) in data.iter() {
+            builder.add(k, v);
+        }
+
+        let block_contents = builder.finish();
+        let block = Block::new(block_contents);
+        let mut block_iter = block.iter();
+
+        assert!(!block_iter.valid());
+        assert_eq!(block_iter.next(),
+                   Some(("key1".as_bytes().to_vec(), "value1".as_bytes())));
+        assert!(block_iter.valid());
+        block_iter.next();
+        assert!(block_iter.valid());
+        block_iter.prev();
+        assert!(block_iter.valid());
+        assert_eq!(block_iter.current(),
+                   ("key1".as_bytes().to_vec(), "value1".as_bytes()));
+        block_iter.prev();
+        assert!(!block_iter.valid());
+    }
+
+    #[test]
     fn test_seek() {
         let mut o = Options::default();
         o.block_restart_interval = 3;

--- a/src/memtable.rs	Sun Jun 12 17:10:19 2016 +0200
+++ b/src/memtable.rs	Sun Jun 12 18:55:42 2016 +0200
@@ -202,6 +202,23 @@
 }
 
 impl<'a, C: 'a + Comparator> LdbIterator<'a> for MemtableIterator<'a, C> {
+    fn prev(&mut self) -> Option<Self::Item> {
+        loop {
+            if let Some((foundkey, _)) = self.skipmapiter.prev() {
+                let (keylen, keyoff, tag, vallen, valoff) =
+                    MemTable::<C>::parse_memtable_key(foundkey);
+
+                if tag & 0xff == ValueType::TypeValue as u64 {
+                    return Some((&foundkey[keyoff..keyoff + keylen],
+                                 &foundkey[valoff..valoff + vallen]));
+                } else {
+                    continue;
+                }
+            } else {
+                return None;
+            }
+        }
+    }
     fn valid(&self) -> bool {
         self.skipmapiter.valid()
     }
@@ -296,6 +313,27 @@
     }
 
     #[test]
+    fn test_memtable_iterator_reverse() {
+        let mt = get_memtable();
+        let mut iter = mt.iter();
+
+        iter.next();
+        assert!(iter.valid());
+        assert_eq!(iter.current().0, vec![97, 98, 99].as_slice());
+
+        iter.next();
+        assert!(iter.valid());
+        assert_eq!(iter.current().0, vec![97, 98, 100].as_slice());
+
+        iter.prev();
+        assert!(iter.valid());
+        assert_eq!(iter.current().0, vec![97, 98, 99].as_slice());
+
+        iter.prev();
+        assert!(!iter.valid());
+    }
+
+    #[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, keyoff, tag, vallen, valoff) =

--- a/src/skipmap.rs	Sun Jun 12 17:10:19 2016 +0200
+++ b/src/skipmap.rs	Sun Jun 12 18:55:42 2016 +0200
@@ -112,6 +112,38 @@
         return unsafe { &(*current) };
     }
 
+    /// Finds the node immediately before the node with key
+    fn get_next_smaller<'a>(&'a self, key: &[u8]) -> &'a Node {
+        // Start at the highest skip link of the head node, and work down from there
+        let mut current: *const Node = unsafe { transmute_copy(&self.head.as_ref()) };
+        let mut level = self.head.skips.len() - 1;
+
+        loop {
+            unsafe {
+                if let Some(next) = (*current).skips[level] {
+                    let ord = C::cmp((*next).key.as_slice(), key);
+
+                    match ord {
+                        Ordering::Less => {
+                            current = next;
+                            continue;
+                        }
+                        _ => {
+                            if level == 0 {
+                                return &(*current);
+                            }
+                        }
+                    }
+                }
+            }
+            if level == 0 {
+                break;
+            }
+            level -= 1;
+        }
+        return unsafe { &(*current) };
+    }
+
     pub fn insert(&mut self, key: Vec<u8>, val: Vec<u8>) {
         assert!(!key.is_empty());
 
@@ -242,6 +274,17 @@
         assert!(self.valid());
         unsafe { (&(*self.current).key, &(*self.current).value) }
     }
+    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 !prev.key.is_empty() {
+            Some(unsafe { (&(*self.current).key, &(*self.current).value) })
+        } else {
+            None
+        }
+    }
 }
 
 #[cfg(test)]
@@ -290,7 +333,7 @@
     }
 
     #[test]
-    fn test_seek() {
+    fn test_find() {
         let skm = make_skipmap();
         assert_eq!(skm.get_greater_or_equal(&"abf".as_bytes().to_vec()).key,
                    "abf".as_bytes().to_vec());
@@ -298,6 +341,14 @@
                    "abz".as_bytes().to_vec());
         assert_eq!(skm.get_greater_or_equal(&"aaa".as_bytes().to_vec()).key,
                    "aba".as_bytes().to_vec());
+        assert_eq!(skm.get_greater_or_equal(&"ab".as_bytes()).key.as_slice(),
+                   "aba".as_bytes());
+        assert_eq!(skm.get_greater_or_equal(&"abc".as_bytes()).key.as_slice(),
+                   "abc".as_bytes());
+        assert_eq!(skm.get_next_smaller(&"abd".as_bytes()).key.as_slice(),
+                   "abc".as_bytes());
+        assert_eq!(skm.get_next_smaller(&"ab{".as_bytes()).key.as_slice(),
+                   "abz".as_bytes());
     }
 
     #[test]
@@ -347,6 +398,19 @@
             }
         }
         assert_eq!(iter.next(), None);
+    }
 
+    #[test]
+    fn test_iterator_prev() {
+        let skm = make_skipmap();
+        let mut iter = skm.iter();
+
+        iter.next();
+        assert!(iter.valid());
+        iter.prev();
+        assert!(!iter.valid());
+        iter.seek(&"abc".as_bytes());
+        iter.prev();
+        assert_eq!(iter.current(), ("abb".as_bytes(), "def".as_bytes()));
     }
 }

--- a/src/types.rs	Sun Jun 12 17:10:19 2016 +0200
+++ b/src/types.rs	Sun Jun 12 18:55:42 2016 +0200
@@ -77,6 +77,7 @@
     fn seek(&mut self, key: &[u8]);
     fn valid(&self) -> bool;
     fn current(&'a self) -> Self::Item;
+    fn prev(&mut self) -> Option<Self::Item>;
 }
 
 /// Supplied to DB read operations.