Mercurial > lbo > hg > leveldb-rs

changeset 117:6147b3a3eeea

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Decommision types that are generic over a comparator.
author Lewin Bormann <lbo@spheniscida.de>
date Sun, 25 Dec 2016 10:47:08 +0000
parents 02b8cf7b62e5
children c2539cd2d021
files src/block.rs src/lib.rs src/memtable.rs src/merging_iter.rs src/options.rs src/skipmap.rs src/table_builder.rs src/table_reader.rs src/test_util.rs src/types.rs src/write_batch.rs
diffstat 11 files changed, 210 insertions(+), 274 deletions(-) [+]
line wrap: on
line diff
--- a/src/block.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/block.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -3,8 +3,7 @@
 use std::rc::Rc;
 
 use options::Options;
-use types::LdbIterator;
-use types::Comparator;
+use types::{LdbIterator, cmp};
 
 use integer_encoding::FixedInt;
 use integer_encoding::VarInt;
@@ -27,19 +26,17 @@
 /// A RESTART is a fixed u32 pointing to the beginning of an ENTRY.
 ///
 /// N_RESTARTS contains the number of restarts.
-pub struct Block<C: Comparator> {
+pub struct Block {
     block: Rc<BlockContents>,
-    cmp: C,
 }
 
-impl<C: Comparator> Block<C> {
-    pub fn iter(&self) -> BlockIter<C> {
+impl Block {
+    pub fn iter(&self) -> BlockIter {
         let restarts = u32::decode_fixed(&self.block[self.block.len() - 4..]);
         let restart_offset = self.block.len() - 4 - 4 * restarts as usize;
 
         BlockIter {
             block: self.block.clone(),
-            cmp: self.cmp,
             offset: 0,
             restarts_off: restart_offset,
             current_entry_offset: 0,
@@ -54,20 +51,14 @@
         self.block.clone()
     }
 
-    pub fn new(contents: BlockContents, cmp: C) -> Block<C> {
+    pub fn new(contents: BlockContents) -> Block {
         assert!(contents.len() > 4);
-        Block {
-            block: Rc::new(contents),
-            cmp: cmp,
-        }
+        Block { block: Rc::new(contents) }
     }
 }
 
-
-#[derive(Debug)]
-pub struct BlockIter<C: Comparator> {
+pub struct BlockIter {
     block: Rc<BlockContents>,
-    cmp: C,
     // start of next entry
     offset: usize,
     // offset of restarts area
@@ -81,7 +72,7 @@
     val_offset: usize,
 }
 
-impl<C: Comparator> BlockIter<C> {
+impl BlockIter {
     fn number_restarts(&self) -> usize {
         u32::decode_fixed(&self.block[self.block.len() - 4..]) as usize
     }
@@ -92,7 +83,7 @@
     }
 }
 
-impl<C: Comparator> BlockIter<C> {
+impl BlockIter {
     // Returns SHARED, NON_SHARED and VALSIZE from the current position. Advances self.offset.
     fn parse_entry(&mut self) -> (usize, usize, usize) {
         let mut i = 0;
@@ -134,7 +125,7 @@
     }
 }
 
-impl<C: Comparator> Iterator for BlockIter<C> {
+impl Iterator for BlockIter {
     type Item = (Vec<u8>, Vec<u8>);
 
     fn next(&mut self) -> Option<Self::Item> {
@@ -158,7 +149,7 @@
     }
 }
 
-impl<C: Comparator> LdbIterator for BlockIter<C> {
+impl LdbIterator for BlockIter {
     fn reset(&mut self) {
         self.offset = 0;
         self.current_restart_ix = 0;
@@ -214,9 +205,9 @@
             // At a restart, the shared part is supposed to be 0.
             assert_eq!(shared, 0);
 
-            let cmp = self.cmp.cmp(to, &self.block[self.offset..self.offset + non_shared]);
+            let c = cmp(to, &self.block[self.offset..self.offset + non_shared]);
 
-            if cmp == Ordering::Less {
+            if c == Ordering::Less {
                 right = middle - 1;
             } else {
                 left = middle;
@@ -229,7 +220,7 @@
 
         // Linear search from here on
         while let Some((k, _)) = self.next() {
-            if self.cmp.cmp(k.as_slice(), to) >= Ordering::Equal {
+            if cmp(k.as_slice(), to) >= Ordering::Equal {
                 return;
             }
         }
@@ -248,9 +239,8 @@
     }
 }
 
-pub struct BlockBuilder<C: Comparator> {
+pub struct BlockBuilder {
     opt: Options,
-    cmp: C,
     buffer: Vec<u8>,
     restarts: Vec<u32>,
 
@@ -258,15 +248,14 @@
     counter: usize,
 }
 
-impl<C: Comparator> BlockBuilder<C> {
-    pub fn new(o: Options, cmp: C) -> BlockBuilder<C> {
+impl BlockBuilder {
+    pub fn new(o: Options) -> BlockBuilder {
         let mut restarts = vec![0];
         restarts.reserve(1023);
 
         BlockBuilder {
             buffer: Vec::with_capacity(o.block_size),
             opt: o,
-            cmp: cmp,
             restarts: restarts,
             last_key: Vec::new(),
             counter: 0,
@@ -294,8 +283,7 @@
 
     pub fn add(&mut self, key: &[u8], val: &[u8]) {
         assert!(self.counter <= self.opt.block_restart_interval);
-        assert!(self.buffer.is_empty() ||
-                self.cmp.cmp(self.last_key.as_slice(), key) == Ordering::Less);
+        assert!(self.buffer.is_empty() || cmp(self.last_key.as_slice(), key) == Ordering::Less);
 
         let mut shared = 0;
 
@@ -377,7 +365,7 @@
         let mut o = Options::default();
         o.block_restart_interval = 3;
 
-        let mut builder = BlockBuilder::new(o, StandardComparator);
+        let mut builder = BlockBuilder::new(o);
 
         for &(k, v) in get_data().iter() {
             builder.add(k, v);
@@ -393,13 +381,13 @@
     fn test_block_empty() {
         let mut o = Options::default();
         o.block_restart_interval = 16;
-        let builder = BlockBuilder::new(o, StandardComparator);
+        let builder = BlockBuilder::new(o);
 
         let blockc = builder.finish();
         assert_eq!(blockc.len(), 8);
         assert_eq!(blockc, vec![0, 0, 0, 0, 1, 0, 0, 0]);
 
-        let block = Block::new(blockc, StandardComparator);
+        let block = Block::new(blockc);
 
         for _ in block.iter() {
             panic!("expected 0 iterations");
@@ -409,14 +397,14 @@
     #[test]
     fn test_block_build_iterate() {
         let data = get_data();
-        let mut builder = BlockBuilder::new(Options::default(), StandardComparator);
+        let mut builder = BlockBuilder::new(Options::default());
 
         for &(k, v) in data.iter() {
             builder.add(k, v);
         }
 
         let block_contents = builder.finish();
-        let block = Block::new(block_contents, StandardComparator).iter();
+        let block = Block::new(block_contents).iter();
         let mut i = 0;
 
         assert!(!block.valid());
@@ -434,14 +422,14 @@
         let mut o = Options::default();
         o.block_restart_interval = 3;
         let data = get_data();
-        let mut builder = BlockBuilder::new(o, StandardComparator);
+        let mut builder = BlockBuilder::new(o);
 
         for &(k, v) in data.iter() {
             builder.add(k, v);
         }
 
         let block_contents = builder.finish();
-        let mut block = Block::new(block_contents, StandardComparator).iter();
+        let mut block = Block::new(block_contents).iter();
 
         assert!(!block.valid());
         assert_eq!(block.next(),
@@ -463,7 +451,7 @@
         o.block_restart_interval = 3;
 
         let data = get_data();
-        let mut builder = BlockBuilder::new(o, StandardComparator);
+        let mut builder = BlockBuilder::new(o);
 
         for &(k, v) in data.iter() {
             builder.add(k, v);
@@ -471,7 +459,7 @@
 
         let block_contents = builder.finish();
 
-        let mut block = Block::new(block_contents, StandardComparator).iter();
+        let mut block = Block::new(block_contents).iter();
 
         block.seek(&"prefix_key2".as_bytes());
         assert!(block.valid());
@@ -498,7 +486,7 @@
             o.block_restart_interval = block_restart_interval;
 
             let data = get_data();
-            let mut builder = BlockBuilder::new(o, StandardComparator);
+            let mut builder = BlockBuilder::new(o);
 
             for &(k, v) in data.iter() {
                 builder.add(k, v);
@@ -506,7 +494,7 @@
 
             let block_contents = builder.finish();
 
-            let mut block = Block::new(block_contents, StandardComparator).iter();
+            let mut block = Block::new(block_contents).iter();
 
             block.seek_to_last();
             assert!(block.valid());
--- a/src/lib.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/lib.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -27,7 +27,5 @@
 
 mod test_util;
 
-pub use types::Comparator;
-
 #[cfg(test)]
 mod tests {}
--- a/src/memtable.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/memtable.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -1,62 +1,17 @@
 use std::cmp::Ordering;
 
-use key_types::{LookupKey, UserKey, InternalKey, parse_memtable_key, build_memtable_key, parse_tag};
-use types::{Comparator, StandardComparator};
-use types::{ValueType, SequenceNumber, Status, LdbIterator};
+use key_types::{LookupKey, UserKey, InternalKey, parse_memtable_key, build_memtable_key};
+use types::{ValueType, SequenceNumber, Status, LdbIterator, cmp};
 use skipmap::{SkipMap, SkipMapIter};
 
-/// An internal comparator wrapping a user-supplied comparator. This comparator is used to compare
-/// memtable keys, which contain length prefixes and a sequence number.
-/// The ordering is determined by asking the wrapped comparator; ties are broken by *reverse*
-/// ordering the sequence numbers. (This means that when having an entry abx/4 and searching for
-/// abx/5, then abx/4 is counted as "greater-or-equal", making snapshot functionality work at all)
-#[derive(Clone, Copy)]
-struct MemtableKeyComparator<C: Comparator> {
-    internal: C,
+/// Provides Insert/Get/Iterate, based on the SkipMap implementation.
+pub struct MemTable {
+    map: SkipMap,
 }
 
-impl<C: Comparator> Comparator for MemtableKeyComparator<C> {
-    fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
-        let (akeylen, akeyoff, atag, _, _) = parse_memtable_key(a);
-        let (bkeylen, bkeyoff, btag, _, _) = parse_memtable_key(b);
-
-        let userkey_a = &a[akeyoff..akeyoff + akeylen];
-        let userkey_b = &b[bkeyoff..bkeyoff + bkeylen];
-
-        let userkey_order = self.internal.cmp(userkey_a, userkey_b);
-        println!("{:?}", userkey_order);
-
-        if userkey_order != Ordering::Equal {
-            userkey_order
-        } else {
-            // look at sequence number, in reverse order
-            let (_, aseq) = parse_tag(atag);
-            let (_, bseq) = parse_tag(btag);
-
-            // reverse!
-            bseq.cmp(&aseq)
-        }
-    }
-}
-
-/// Provides Insert/Get/Iterate, based on the SkipMap implementation.
-pub struct MemTable<C: Comparator> {
-    map: SkipMap<MemtableKeyComparator<C>>,
-    cmp: C,
-}
-
-impl MemTable<StandardComparator> {
-    pub fn new() -> MemTable<StandardComparator> {
-        MemTable::new_custom_cmp(StandardComparator {})
-    }
-}
-
-impl<C: Comparator> MemTable<C> {
-    pub fn new_custom_cmp(comparator: C) -> MemTable<C> {
-        MemTable {
-            map: SkipMap::new_with_cmp(MemtableKeyComparator { internal: comparator }),
-            cmp: comparator,
-        }
+impl MemTable {
+    pub fn new() -> MemTable {
+        MemTable { map: SkipMap::new() }
     }
     pub fn approx_mem_usage(&self) -> usize {
         self.map.approx_memory()
@@ -77,9 +32,8 @@
             let (fkeylen, fkeyoff, tag, vallen, valoff) = parse_memtable_key(foundkey);
 
             // Compare user key -- if equal, proceed
-            if self.cmp.cmp(&key.memtable_key()[lkeyoff..lkeyoff + lkeylen],
-                            &foundkey[fkeyoff..fkeyoff + fkeylen]) ==
-               Ordering::Equal {
+            if cmp(&key.memtable_key()[lkeyoff..lkeyoff + lkeylen],
+                   &foundkey[fkeyoff..fkeyoff + fkeylen]) == Ordering::Equal {
                 if tag & 0xff == ValueType::TypeValue as u64 {
                     return Result::Ok(foundkey[valoff..valoff + vallen].to_vec());
                 } else {
@@ -90,7 +44,7 @@
         Result::Err(Status::NotFound("not found".to_string()))
     }
 
-    pub fn iter<'a>(&'a self) -> MemtableIterator<'a, C> {
+    pub fn iter<'a>(&'a self) -> MemtableIterator<'a> {
         MemtableIterator {
             _tbl: self,
             skipmapiter: self.map.iter(),
@@ -98,12 +52,12 @@
     }
 }
 
-pub struct MemtableIterator<'a, C: 'a + Comparator> {
-    _tbl: &'a MemTable<C>,
-    skipmapiter: SkipMapIter<'a, MemtableKeyComparator<C>>,
+pub struct MemtableIterator<'a> {
+    _tbl: &'a MemTable,
+    skipmapiter: SkipMapIter<'a>,
 }
 
-impl<'a, C: 'a + Comparator> Iterator for MemtableIterator<'a, C> {
+impl<'a> Iterator for MemtableIterator<'a> {
     type Item = (InternalKey<'a>, &'a [u8]);
 
     fn next(&mut self) -> Option<Self::Item> {
@@ -124,7 +78,7 @@
     }
 }
 
-impl<'a, C: 'a + Comparator> LdbIterator for MemtableIterator<'a, C> {
+impl<'a> LdbIterator for MemtableIterator<'a> {
     fn reset(&mut self) {
         self.skipmapiter.reset();
     }
@@ -177,7 +131,7 @@
     use key_types::*;
     use types::*;
 
-    fn get_memtable() -> MemTable<StandardComparator> {
+    fn get_memtable() -> MemTable {
         let mut mt = MemTable::new();
         let entries = vec![(115, "abc", "122"),
                            (120, "abc", "123"),
--- a/src/merging_iter.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/merging_iter.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -1,5 +1,4 @@
-use types::LdbIterator;
-use types::Comparator;
+use types::{cmp, LdbIterator};
 
 use std::cmp::Ordering;
 
@@ -21,23 +20,20 @@
     Rvrs,
 }
 
-pub struct MergingIter<'a, 'b: 'a, C: Comparator> {
+pub struct MergingIter<'a, 'b: 'a> {
     iters: Vec<&'a mut LdbIterator<Item = (&'b [u8], &'b [u8])>>,
     current: Option<usize>,
-    cmp: C,
     direction: Direction,
 }
 
-impl<'a, 'b: 'a, C: 'b + Comparator> MergingIter<'a, 'b, C> {
+impl<'a, 'b: 'a> MergingIter<'a, 'b> {
     /// Construct a new merging iterator.
-    pub fn new(iters: Vec<&'a mut LdbIterator<Item = (&'b [u8], &'b [u8])>>,
-               c: C)
-               -> MergingIter<'a, 'b, C> {
+    pub fn new(iters: Vec<&'a mut LdbIterator<Item = (&'b [u8], &'b [u8])>>)
+               -> MergingIter<'a, 'b> {
         let mi = MergingIter {
             iters: iters,
             current: None,
             direction: Direction::Fwd,
-            cmp: c,
         };
         mi
     }
@@ -64,7 +60,7 @@
                             if i != current {
                                 self.iters[i].seek(key);
                                 if let Some((current_key, _)) = self.iters[i].current() {
-                                    if self.cmp.cmp(current_key, key) == Ordering::Equal {
+                                    if cmp(current_key, key) == Ordering::Equal {
                                         self.iters[i].next();
                                     }
                                 }
@@ -109,7 +105,7 @@
         for i in 1..self.iters.len() {
             if let Some(current) = self.iters[i].current() {
                 if let Some(smallest) = self.iters[next_ix].current() {
-                    if self.cmp.cmp(current.0, smallest.0) == ord {
+                    if cmp(current.0, smallest.0) == ord {
                         next_ix = i;
                     }
                 } else {
@@ -125,7 +121,7 @@
     }
 }
 
-impl<'a, 'b: 'a, C: 'b + Comparator> Iterator for MergingIter<'a, 'b, C> {
+impl<'a, 'b: 'a> Iterator for MergingIter<'a, 'b> {
     type Item = (&'b [u8], &'b [u8]);
 
     fn next(&mut self) -> Option<Self::Item> {
@@ -146,7 +142,7 @@
     }
 }
 
-impl<'a, 'b: 'a, C: 'b + Comparator> LdbIterator for MergingIter<'a, 'b, C> {
+impl<'a, 'b: 'a> LdbIterator for MergingIter<'a, 'b> {
     fn valid(&self) -> bool {
         return self.current.is_some() && self.iters.iter().any(|it| it.valid());
     }
@@ -189,7 +185,6 @@
     use super::*;
 
     use test_util::TestLdbIter;
-    use types::StandardComparator;
     use types::LdbIterator;
     use skipmap::tests;
 
@@ -199,7 +194,7 @@
         let mut iter = skm.iter();
         let mut iter2 = skm.iter();
 
-        let mut miter = MergingIter::new(vec![&mut iter], StandardComparator);
+        let mut miter = MergingIter::new(vec![&mut iter]);
 
         loop {
             if let Some((k, v)) = miter.next() {
@@ -221,7 +216,7 @@
         let mut iter = skm.iter();
         let mut iter2 = skm.iter();
 
-        let mut miter = MergingIter::new(vec![&mut iter, &mut iter2], StandardComparator);
+        let mut miter = MergingIter::new(vec![&mut iter, &mut iter2]);
 
         loop {
             if let Some((k, v)) = miter.next() {
@@ -243,7 +238,7 @@
         let mut iter = skm.iter();
         let mut iter2 = skm.iter();
 
-        let mut miter = MergingIter::new(vec![&mut iter, &mut iter2], StandardComparator);
+        let mut miter = MergingIter::new(vec![&mut iter, &mut iter2]);
 
         let first = miter.next();
         miter.next();
@@ -266,7 +261,7 @@
         let mut it2 = TestLdbIter::new(vec![(b("abb"), val), (b("abd"), val)]);
         let expected = vec![b("aba"), b("abb"), b("abc"), b("abd"), b("abe")];
 
-        let iter = MergingIter::new(vec![&mut it1, &mut it2], StandardComparator);
+        let iter = MergingIter::new(vec![&mut it1, &mut it2]);
 
         let mut i = 0;
         for (k, _) in iter {
@@ -283,7 +278,7 @@
         let mut it1 = TestLdbIter::new(vec![(b("aba"), val), (b("abc"), val), (b("abe"), val)]);
         let mut it2 = TestLdbIter::new(vec![(b("abb"), val), (b("abd"), val)]);
 
-        let mut iter = MergingIter::new(vec![&mut it1, &mut it2], StandardComparator);
+        let mut iter = MergingIter::new(vec![&mut it1, &mut it2]);
 
         assert!(!iter.valid());
         iter.next();
@@ -310,7 +305,7 @@
         let mut it1 = TestLdbIter::new(vec![(b("aba"), val), (b("abc"), val), (b("abe"), val)]);
         let mut it2 = TestLdbIter::new(vec![(b("abb"), val), (b("abd"), val)]);
 
-        let mut iter = MergingIter::new(vec![&mut it1, &mut it2], StandardComparator);
+        let mut iter = MergingIter::new(vec![&mut it1, &mut it2]);
 
         iter.next();
         iter.next();
--- a/src/options.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/options.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -26,7 +26,6 @@
     // pub logger: Logger,
     pub write_buffer_size: usize,
     pub max_open_files: usize,
-    // pub block_cache: Cache,
     pub block_size: usize,
     pub block_restart_interval: usize,
     pub compression_type: CompressionType,
--- a/src/skipmap.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/skipmap.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -1,11 +1,40 @@
-use types::{Comparator, StandardComparator, LdbIterator};
+use types::{cmp, LdbIterator};
 use rand::{Rng, SeedableRng, StdRng};
+use key_types::{parse_tag, parse_memtable_key};
+
 use std::cmp::Ordering;
 use std::mem::{replace, size_of};
 
 const MAX_HEIGHT: usize = 12;
 const BRANCHING_FACTOR: u32 = 4;
 
+/// An internal comparator wrapping a user-supplied comparator. This comparator is used to compare
+/// memtable keys, which contain length prefixes and a sequence number.
+/// The ordering is determined by asking the wrapped comparator; ties are broken by *reverse*
+/// ordering the sequence numbers. (This means that when having an entry abx/4 and searching for
+/// abx/5, then abx/4 is counted as "greater-or-equal", making snapshot functionality work at all)
+fn memtable_key_cmp(a: &[u8], b: &[u8]) -> Ordering {
+    let (akeylen, akeyoff, atag, _, _) = parse_memtable_key(a);
+    let (bkeylen, bkeyoff, btag, _, _) = parse_memtable_key(b);
+
+    let userkey_a = &a[akeyoff..akeyoff + akeylen];
+    let userkey_b = &b[bkeyoff..bkeyoff + bkeylen];
+
+    let userkey_order = cmp(userkey_a, userkey_b);
+    println!("{:?}", userkey_order);
+
+    if userkey_order != Ordering::Equal {
+        userkey_order
+    } else {
+        // look at sequence number, in reverse order
+        let (_, aseq) = parse_tag(atag);
+        let (_, bseq) = parse_tag(btag);
+
+        // reverse!
+        bseq.cmp(&aseq)
+    }
+}
+
 /// A node in a skipmap contains links to the next node and others that are further away (skips);
 /// `skips[0]` is the immediate element after, that is, the element contained in `next`.
 struct Node {
@@ -19,23 +48,23 @@
 /// `contains()`; in order to get full key and value for an entry, use a `SkipMapIter` instance,
 /// `seek()` to the key to look up (this is as fast as any lookup in a skip map), and then call
 /// `current()`.
-pub struct SkipMap<C: Comparator> {
+pub struct SkipMap {
     head: Box<Node>,
     rand: StdRng,
-    cmp: C,
     len: usize,
     // approximation of memory used.
     approx_mem: usize,
+    cmp: Box<Fn(&[u8], &[u8]) -> Ordering>,
 }
 
-impl SkipMap<StandardComparator> {
-    pub fn new() -> SkipMap<StandardComparator> {
-        SkipMap::new_with_cmp(StandardComparator {})
+impl SkipMap {
+    fn new_standard() -> SkipMap {
+        let mut skm = SkipMap::new();
+        skm.cmp = Box::new(cmp);
+        skm
     }
-}
 
-impl<C: Comparator> SkipMap<C> {
-    pub fn new_with_cmp(c: C) -> SkipMap<C> {
+    pub fn new() -> SkipMap {
         let mut s = Vec::new();
         s.resize(MAX_HEIGHT, None);
 
@@ -47,9 +76,9 @@
                 value: Vec::new(),
             }),
             rand: StdRng::from_seed(&[0xde, 0xad, 0xbe, 0xef]),
-            cmp: c,
             len: 0,
             approx_mem: size_of::<Self>() + MAX_HEIGHT * size_of::<Option<*mut Node>>(),
+            cmp: Box::new(memtable_key_cmp),
         }
     }
 
@@ -88,7 +117,7 @@
         loop {
             unsafe {
                 if let Some(next) = (*current).skips[level] {
-                    let ord = self.cmp.cmp((*next).key.as_slice(), key);
+                    let ord = (self.cmp)((*next).key.as_slice(), key);
 
                     match ord {
                         Ordering::Less => {
@@ -113,7 +142,7 @@
         unsafe {
             if current.is_null() {
                 return None;
-            } else if self.cmp.cmp(&(*current).key, key) == Ordering::Less {
+            } else if (self.cmp)(&(*current).key, key) == Ordering::Less {
                 return None;
             } else {
                 return Some(&(*current));
@@ -131,7 +160,7 @@
         loop {
             unsafe {
                 if let Some(next) = (*current).skips[level] {
-                    let ord = self.cmp.cmp((*next).key.as_slice(), key);
+                    let ord = (self.cmp)((*next).key.as_slice(), key);
 
                     match ord {
                         Ordering::Less => {
@@ -152,7 +181,7 @@
             if current.is_null() || (*current).key.is_empty() {
                 // If we're past the end for some reason or at the head
                 return None;
-            } else if self.cmp.cmp(&(*current).key, key) != Ordering::Less {
+            } else if (self.cmp)(&(*current).key, key) != Ordering::Less {
                 return None;
             } else {
                 return Some(&(*current));
@@ -178,7 +207,7 @@
             unsafe {
                 if let Some(next) = (*current).skips[level] {
                     // If the wanted position is after the current node
-                    let ord = self.cmp.cmp(&(*next).key, &key);
+                    let ord = (self.cmp)(&(*next).key, &key);
 
                     assert!(ord != Ordering::Equal, "No duplicates allowed");
 
@@ -232,7 +261,7 @@
         unsafe { replace(&mut (*current).next, Some(new)) };
     }
 
-    pub fn iter<'a>(&'a self) -> SkipMapIter<'a, C> {
+    pub fn iter<'a>(&'a self) -> SkipMapIter<'a> {
         SkipMapIter {
             map: self,
             current: self.head.as_ref() as *const Node,
@@ -259,12 +288,12 @@
     }
 }
 
-pub struct SkipMapIter<'a, C: Comparator + 'a> {
-    map: &'a SkipMap<C>,
+pub struct SkipMapIter<'a> {
+    map: &'a SkipMap,
     current: *const Node,
 }
 
-impl<'a, C: Comparator + 'a> Iterator for SkipMapIter<'a, C> {
+impl<'a> Iterator for SkipMapIter<'a> {
     type Item = (&'a [u8], &'a [u8]);
 
     fn next(&mut self) -> Option<Self::Item> {
@@ -278,7 +307,7 @@
     }
 }
 
-impl<'a, C: Comparator> LdbIterator for SkipMapIter<'a, C> {
+impl<'a> LdbIterator for SkipMapIter<'a> {
     fn reset(&mut self) {
         let new = self.map.iter();
         self.current = new.current;
@@ -321,8 +350,8 @@
     use super::*;
     use types::*;
 
-    pub fn make_skipmap() -> SkipMap<StandardComparator> {
-        let mut skm = SkipMap::new();
+    pub fn make_skipmap() -> SkipMap {
+        let mut skm = SkipMap::new_standard();
         let keys = vec!["aba", "abb", "abc", "abd", "abe", "abf", "abg", "abh", "abi", "abj",
                         "abk", "abl", "abm", "abn", "abo", "abp", "abq", "abr", "abs", "abt",
                         "abu", "abv", "abw", "abx", "aby", "abz"];
@@ -382,7 +411,7 @@
 
     #[test]
     fn test_iterator_0() {
-        let skm = SkipMap::new();
+        let skm = SkipMap::new_standard();
         let mut i = 0;
 
         for (_, _) in skm.iter() {
--- a/src/table_builder.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/table_builder.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -4,7 +4,7 @@
 use filter_block::FilterBlockBuilder;
 use key_types::InternalKey;
 use options::{CompressionType, Options};
-use types::Comparator;
+use types::cmp;
 
 use std::io::Write;
 use std::cmp::Ordering;
@@ -21,10 +21,7 @@
 pub const TABLE_BLOCK_COMPRESS_LEN: usize = 1;
 pub const TABLE_BLOCK_CKSUM_LEN: usize = 4;
 
-fn find_shortest_sep<'a, C: Comparator>(c: &C,
-                                        lo: InternalKey<'a>,
-                                        hi: InternalKey<'a>)
-                                        -> Vec<u8> {
+fn find_shortest_sep<'a>(lo: InternalKey<'a>, hi: InternalKey<'a>) -> Vec<u8> {
     let min;
 
     if lo.len() < hi.len() {
@@ -45,7 +42,7 @@
         if lo[diff_at] < 0xff && lo[diff_at] + 1 < hi[diff_at] {
             let mut result = Vec::from(&lo[0..diff_at + 1]);
             result[diff_at] += 1;
-            assert_eq!(c.cmp(&result, hi), Ordering::Less);
+            assert_eq!(cmp(&result, hi), Ordering::Less);
             return result;
         }
         return Vec::from(lo);
@@ -103,34 +100,29 @@
 /// the index block, padding to fill up to 40 B and at the end the 8B magic number
 /// 0xdb4775248b80fb57.
 
-pub struct TableBuilder<'a, C: Comparator, Dst: Write, FilterPol: FilterPolicy> {
+pub struct TableBuilder<'a, Dst: Write, FilterPol: FilterPolicy> {
     o: Options,
-    cmp: C,
     dst: Dst,
 
     offset: usize,
     num_entries: usize,
     prev_block_last_key: Vec<u8>,
 
-    data_block: Option<BlockBuilder<C>>,
-    index_block: Option<BlockBuilder<C>>,
+    data_block: Option<BlockBuilder>,
+    index_block: Option<BlockBuilder>,
     filter_block: Option<FilterBlockBuilder<'a, FilterPol>>,
 }
 
-impl<'a, C: Comparator, Dst: Write> TableBuilder<'a, C, Dst, NoFilterPolicy> {
-    pub fn new_no_filter(opt: Options,
-                         cmp: C,
-                         dst: Dst)
-                         -> TableBuilder<'a, C, Dst, NoFilterPolicy> {
+impl<'a, Dst: Write> TableBuilder<'a, Dst, NoFilterPolicy> {
+    pub fn new_no_filter(opt: Options, dst: Dst) -> TableBuilder<'a, Dst, NoFilterPolicy> {
         TableBuilder {
             o: opt,
-            cmp: cmp,
             dst: dst,
             offset: 0,
             prev_block_last_key: vec![],
             num_entries: 0,
-            data_block: Some(BlockBuilder::new(opt, cmp)),
-            index_block: Some(BlockBuilder::new(opt, cmp)),
+            data_block: Some(BlockBuilder::new(opt)),
+            index_block: Some(BlockBuilder::new(opt)),
             filter_block: None,
         }
     }
@@ -140,21 +132,16 @@
 /// calculating checksums and bloom filters.
 /// It's recommended that you use InternalFilterPolicy as FilterPol, as that policy extracts the
 /// underlying user keys from the InternalKeys used as keys in the table.
-impl<'a, C: Comparator, Dst: Write, FilterPol: FilterPolicy> TableBuilder<'a, C, Dst, FilterPol> {
-    pub fn new(opt: Options,
-               cmp: C,
-               dst: Dst,
-               fpol: FilterPol)
-               -> TableBuilder<'a, C, Dst, FilterPol> {
+impl<'a, Dst: Write, FilterPol: FilterPolicy> TableBuilder<'a, Dst, FilterPol> {
+    pub fn new(opt: Options, dst: Dst, fpol: FilterPol) -> TableBuilder<'a, Dst, FilterPol> {
         TableBuilder {
             o: opt,
-            cmp: cmp,
             dst: dst,
             offset: 0,
             prev_block_last_key: vec![],
             num_entries: 0,
-            data_block: Some(BlockBuilder::new(opt, cmp)),
-            index_block: Some(BlockBuilder::new(opt, cmp)),
+            data_block: Some(BlockBuilder::new(opt)),
+            index_block: Some(BlockBuilder::new(opt)),
             filter_block: Some(FilterBlockBuilder::new(fpol)),
         }
     }
@@ -165,8 +152,7 @@
 
     pub fn add(&mut self, key: InternalKey<'a>, val: &[u8]) {
         assert!(self.data_block.is_some());
-        assert!(self.num_entries == 0 ||
-                self.cmp.cmp(&self.prev_block_last_key, key) == Ordering::Less);
+        assert!(self.num_entries == 0 || cmp(&self.prev_block_last_key, key) == Ordering::Less);
 
         if self.data_block.as_ref().unwrap().size_estimate() > self.o.block_size {
             self.write_data_block(key);
@@ -189,7 +175,7 @@
         assert!(self.data_block.is_some());
 
         let block = self.data_block.take().unwrap();
-        let sep = find_shortest_sep(&self.cmp, block.last_key(), next_key);
+        let sep = find_shortest_sep(&block.last_key(), next_key);
         self.prev_block_last_key = Vec::from(block.last_key());
         let contents = block.finish();
 
@@ -198,7 +184,7 @@
         let enc_len = handle.encode_to(&mut handle_enc);
 
         self.index_block.as_mut().unwrap().add(&sep, &handle_enc[0..enc_len]);
-        self.data_block = Some(BlockBuilder::new(self.o, self.cmp));
+        self.data_block = Some(BlockBuilder::new(self.o));
 
         let ctype = self.o.compression_type;
 
@@ -243,7 +229,7 @@
         }
 
         // Create metaindex block
-        let mut meta_ix_block = BlockBuilder::new(self.o, self.cmp);
+        let mut meta_ix_block = BlockBuilder::new(self.o);
 
         if self.filter_block.is_some() {
             // if there's a filter block, write the filter block and add it to the metaindex block.
@@ -278,26 +264,23 @@
 #[cfg(test)]
 mod tests {
     use super::{find_shortest_sep, Footer, TableBuilder};
-    use types::StandardComparator;
     use blockhandle::BlockHandle;
     use filter::BloomPolicy;
     use options::Options;
 
     #[test]
     fn test_shortest_sep() {
-        assert_eq!(find_shortest_sep(&StandardComparator, "abcd".as_bytes(), "abcf".as_bytes()),
+        assert_eq!(find_shortest_sep("abcd".as_bytes(), "abcf".as_bytes()),
                    "abce".as_bytes());
-        assert_eq!(find_shortest_sep(&StandardComparator,
-                                     "abcdefghi".as_bytes(),
-                                     "abcffghi".as_bytes()),
+        assert_eq!(find_shortest_sep("abcdefghi".as_bytes(), "abcffghi".as_bytes()),
                    "abce".as_bytes());
-        assert_eq!(find_shortest_sep(&StandardComparator, "a".as_bytes(), "a".as_bytes()),
+        assert_eq!(find_shortest_sep("a".as_bytes(), "a".as_bytes()),
                    "a".as_bytes());
-        assert_eq!(find_shortest_sep(&StandardComparator, "a".as_bytes(), "b".as_bytes()),
+        assert_eq!(find_shortest_sep("a".as_bytes(), "b".as_bytes()),
                    "a".as_bytes());
-        assert_eq!(find_shortest_sep(&StandardComparator, "abc".as_bytes(), "zzz".as_bytes()),
+        assert_eq!(find_shortest_sep("abc".as_bytes(), "zzz".as_bytes()),
                    "b".as_bytes());
-        assert_eq!(find_shortest_sep(&StandardComparator, "".as_bytes(), "".as_bytes()),
+        assert_eq!(find_shortest_sep("".as_bytes(), "".as_bytes()),
                    "".as_bytes());
     }
 
@@ -320,7 +303,7 @@
         let mut d = Vec::with_capacity(512);
         let mut opt = Options::default();
         opt.block_restart_interval = 3;
-        let mut b = TableBuilder::new(opt, StandardComparator, &mut d, BloomPolicy::new(4));
+        let mut b = TableBuilder::new(opt, &mut d, BloomPolicy::new(4));
 
         let data = vec![("abc", "def"), ("abd", "dee"), ("bcd", "asa"), ("bsr", "a00")];
 
@@ -338,7 +321,7 @@
         let mut d = Vec::with_capacity(512);
         let mut opt = Options::default();
         opt.block_restart_interval = 3;
-        let mut b = TableBuilder::new(opt, StandardComparator, &mut d, BloomPolicy::new(4));
+        let mut b = TableBuilder::new(opt, &mut d, BloomPolicy::new(4));
 
         // Test two equal consecutive keys
         let data = vec![("abc", "def"), ("abc", "dee"), ("bcd", "asa"), ("bsr", "a00")];
--- a/src/table_reader.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/table_reader.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -4,7 +4,7 @@
 use filter_block::FilterBlockReader;
 use options::{self, CompressionType, Options};
 use table_builder::{self, Footer};
-use types::{Comparator, LdbIterator};
+use types::{cmp, LdbIterator};
 use key_types::InternalKey;
 
 use std::io::{self, Read, Seek, SeekFrom, Result};
@@ -33,10 +33,7 @@
 }
 
 /// Reads a block at location.
-fn read_block<R: Read + Seek, C: Comparator>(cmp: &C,
-                                             f: &mut R,
-                                             location: &BlockHandle)
-                                             -> Result<TableBlock<C>> {
+fn read_block<R: Read + Seek>(f: &mut R, location: &BlockHandle) -> Result<TableBlock> {
     // The block is denoted by offset and length in BlockHandle. A block in an encoded
     // table is followed by 1B compression type and 4B checksum.
     let buf = try!(read_bytes(f, location));
@@ -48,20 +45,20 @@
                                                   table_builder::TABLE_BLOCK_COMPRESS_LEN,
                                                   table_builder::TABLE_BLOCK_CKSUM_LEN)));
     Ok(TableBlock {
-        block: Block::new(buf, *cmp),
+        block: Block::new(buf),
         checksum: u32::decode_fixed(&cksum),
         compression: options::int_to_compressiontype(compress[0] as u32)
             .unwrap_or(CompressionType::CompressionNone),
     })
 }
 
-struct TableBlock<C: Comparator> {
-    block: Block<C>,
+struct TableBlock {
+    block: Block,
     checksum: u32,
     compression: CompressionType,
 }
 
-impl<C: Comparator> TableBlock<C> {
+impl TableBlock {
     /// Verify checksum of block
     fn verify(&self) -> bool {
         let mut digest = crc32::Digest::new(crc32::CASTAGNOLI);
@@ -72,24 +69,23 @@
     }
 }
 
-pub struct Table<R: Read + Seek, C: Comparator, FP: FilterPolicy> {
+pub struct Table<R: Read + Seek, FP: FilterPolicy> {
     file: R,
     file_size: usize,
 
     opt: Options,
-    cmp: C,
 
     footer: Footer,
-    indexblock: Block<C>,
+    indexblock: Block,
     filters: Option<FilterBlockReader<FP>>,
 }
 
-impl<R: Read + Seek, C: Comparator, FP: FilterPolicy> Table<R, C, FP> {
-    pub fn new(mut file: R, size: usize, cmp: C, fp: FP, opt: Options) -> Result<Table<R, C, FP>> {
+impl<R: Read + Seek, FP: FilterPolicy> Table<R, FP> {
+    pub fn new(mut file: R, size: usize, fp: FP, opt: Options) -> Result<Table<R, FP>> {
         let footer = try!(read_footer(&mut file, size));
 
-        let indexblock = try!(read_block(&cmp, &mut file, &footer.index));
-        let metaindexblock = try!(read_block(&cmp, &mut file, &footer.meta_index));
+        let indexblock = try!(read_block(&mut file, &footer.index));
+        let metaindexblock = try!(read_block(&mut file, &footer.meta_index));
 
         if !indexblock.verify() || !metaindexblock.verify() {
             return Err(io::Error::new(io::ErrorKind::InvalidData,
@@ -118,7 +114,6 @@
         Ok(Table {
             file: file,
             file_size: size,
-            cmp: cmp,
             opt: opt,
             footer: footer,
             filters: filter_block_reader,
@@ -126,8 +121,8 @@
         })
     }
 
-    fn read_block(&mut self, location: &BlockHandle) -> Result<TableBlock<C>> {
-        let b = try!(read_block(&self.cmp, &mut self.file, location));
+    fn read_block(&mut self, location: &BlockHandle) -> Result<TableBlock> {
+        let b = try!(read_block(&mut self.file, location));
 
         if !b.verify() {
             Err(io::Error::new(io::ErrorKind::InvalidData, "Data block failed verification"))
@@ -151,7 +146,7 @@
     }
 
     // Iterators read from the file; thus only one iterator can be borrowed (mutably) per scope
-    fn iter<'a>(&'a mut self) -> TableIterator<'a, R, C, FP> {
+    fn iter<'a>(&'a mut self) -> TableIterator<'a, R, FP> {
         let iter = TableIterator {
             current_block: self.indexblock.iter(), // just for filling in here
             current_block_off: 0,
@@ -162,32 +157,57 @@
         iter
     }
 
-    /// Retrieve value from table
-    pub fn get<'a>(&mut self, k: InternalKey<'a>) -> Option<Vec<u8>> {
+    /// Retrieve value from table. This function uses the attached filters, so is better suited if
+    /// you frequently look for non-existing values (as it will detect the non-existence of an
+    /// entry in a block without having to load the block).
+    pub fn get<'a>(&mut self, to: InternalKey<'a>) -> Option<Vec<u8>> {
         let mut iter = self.iter();
 
-        iter.seek(k);
+        iter.seek(to);
 
-        if let Some((fkey, fval)) = iter.current() {
-            if fkey == k { Some(fval) } else { None }
+        if let Some((k, v)) = iter.current() {
+            if k == to { Some(v) } else { None }
         } else {
             None
         }
+
+        // Future impl:
+        //
+        // let mut index_block = self.indexblock.iter();
+        //
+        // index_block.seek(to);
+        //
+        // if let Some((past_block, handle)) = index_block.current() {
+        // if cmp(to, &past_block) == Ordering::Less {
+        // ok, found right block: continue
+        // if let Ok(()) = self.load_block(&handle) {
+        // self.current_block.seek(to);
+        // } else {
+        // return None;
+        // }*/
+        // return None;
+        // } else {
+        // return None;
+        // }
+        // } else {
+        // return None;
+        // }
+        //
     }
 }
 
 /// This iterator is a "TwoLevelIterator"; it uses an index block in order to get an offset hint
 /// into the data blocks.
-pub struct TableIterator<'a, R: 'a + Read + Seek, C: 'a + Comparator, FP: 'a + FilterPolicy> {
-    table: &'a mut Table<R, C, FP>,
-    current_block: BlockIter<C>,
+pub struct TableIterator<'a, R: 'a + Read + Seek, FP: 'a + FilterPolicy> {
+    table: &'a mut Table<R, FP>,
+    current_block: BlockIter,
     current_block_off: usize,
-    index_block: BlockIter<C>,
+    index_block: BlockIter,
 
     init: bool,
 }
 
-impl<'a, C: Comparator, R: Read + Seek, FP: FilterPolicy> TableIterator<'a, R, C, FP> {
+impl<'a, R: Read + Seek, FP: FilterPolicy> TableIterator<'a, R, FP> {
     // Skips to the entry referenced by the next entry in the index block.
     // This is called once a block has run out of entries.
     fn skip_to_next_entry(&mut self) -> Result<bool> {
@@ -210,7 +230,7 @@
     }
 }
 
-impl<'a, C: Comparator, R: Read + Seek, FP: FilterPolicy> Iterator for TableIterator<'a, R, C, FP> {
+impl<'a, R: Read + Seek, FP: FilterPolicy> Iterator for TableIterator<'a, R, FP> {
     type Item = (Vec<u8>, Vec<u8>);
 
     fn next(&mut self) -> Option<Self::Item> {
@@ -233,10 +253,7 @@
     }
 }
 
-impl<'a, C: Comparator, R: Read + Seek, FP: FilterPolicy> LdbIterator for TableIterator<'a,
-                                                                                        R,
-                                                                                        C,
-                                                                                        FP> {
+impl<'a, R: Read + Seek, FP: FilterPolicy> LdbIterator for TableIterator<'a, R, FP> {
     // A call to valid() after seeking is necessary to ensure that the seek worked (e.g., no error
     // while reading from disk)
     fn seek(&mut self, to: &[u8]) {
@@ -245,27 +262,23 @@
 
         self.index_block.seek(to);
 
-        if let Some((k, _)) = self.index_block.current() {
-            if self.table.cmp.cmp(to, &k) <= Ordering::Equal {
-                // ok, found right block: continue below
+        if let Some((past_block, handle)) = self.index_block.current() {
+            if cmp(to, &past_block) == Ordering::Less {
+                // ok, found right block: continue
+                if let Ok(()) = self.load_block(&handle) {
+                    self.current_block.seek(to);
+                    self.init = true;
+                } else {
+                    self.reset();
+                    return;
+                }
             } else {
                 self.reset();
+                return;
             }
         } else {
             panic!("Unexpected None from current() (bug)");
         }
-
-        // Read block and seek to entry in that block
-        if let Some((k, handle)) = self.index_block.current() {
-            assert!(self.table.cmp.cmp(to, &k) <= Ordering::Equal);
-
-            if let Ok(()) = self.load_block(&handle) {
-                self.current_block.seek(to);
-                self.init = true;
-            } else {
-                self.reset();
-            }
-        }
     }
 
     fn prev(&mut self) -> Option<Self::Item> {
@@ -313,7 +326,7 @@
     use filter::BloomPolicy;
     use options::Options;
     use table_builder::TableBuilder;
-    use types::{StandardComparator, LdbIterator};
+    use types::LdbIterator;
 
     use std::io::Cursor;
 
@@ -337,7 +350,7 @@
         opt.block_size = 32;
 
         {
-            let mut b = TableBuilder::new(opt, StandardComparator, &mut d, BloomPolicy::new(4));
+            let mut b = TableBuilder::new(opt, &mut d, BloomPolicy::new(4));
             let data = build_data();
 
             for &(k, v) in data.iter() {
@@ -362,7 +375,6 @@
 
         let mut table = Table::new(Cursor::new(&src as &[u8]),
                                    size,
-                                   StandardComparator,
                                    BloomPolicy::new(4),
                                    Options::default())
             .unwrap();
@@ -397,7 +409,6 @@
 
         let mut table = Table::new(Cursor::new(&src as &[u8]),
                                    size,
-                                   StandardComparator,
                                    BloomPolicy::new(4),
                                    Options::default())
             .unwrap();
@@ -416,11 +427,9 @@
     #[test]
     fn test_table_iterator_filter() {
         let (src, size) = build_table();
-        let data = build_data();
 
         let mut table = Table::new(Cursor::new(&src as &[u8]),
                                    size,
-                                   StandardComparator,
                                    BloomPolicy::new(4),
                                    Options::default())
             .unwrap();
@@ -444,7 +453,6 @@
 
         let mut table = Table::new(Cursor::new(&src as &[u8]),
                                    size,
-                                   StandardComparator,
                                    BloomPolicy::new(4),
                                    Options::default())
             .unwrap();
@@ -478,7 +486,6 @@
 
         let mut table = Table::new(Cursor::new(&src as &[u8]),
                                    size,
-                                   StandardComparator,
                                    BloomPolicy::new(4),
                                    Options::default())
             .unwrap();
@@ -514,7 +521,6 @@
 
         let mut table = Table::new(Cursor::new(&src as &[u8]),
                                    size,
-                                   StandardComparator,
                                    BloomPolicy::new(4),
                                    Options::default())
             .unwrap();
@@ -536,7 +542,6 @@
 
         let mut table = Table::new(Cursor::new(&src as &[u8]),
                                    size,
-                                   StandardComparator,
                                    BloomPolicy::new(4),
                                    Options::default())
             .unwrap();
--- a/src/test_util.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/test_util.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -1,7 +1,4 @@
-use types::LdbIterator;
-use types::Comparator;
-use types::StandardComparator;
-
+use types::{cmp, LdbIterator};
 use std::cmp::Ordering;
 
 pub struct TestLdbIter<'a> {
@@ -53,8 +50,7 @@
     }
     fn seek(&mut self, k: &[u8]) {
         self.ix = 0;
-        while self.ix < self.v.len() &&
-              StandardComparator.cmp(self.v[self.ix].0, k) == Ordering::Less {
+        while self.ix < self.v.len() && cmp(self.v[self.ix].0, k) == Ordering::Less {
             self.ix += 1;
         }
     }
--- a/src/types.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/types.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -21,19 +21,8 @@
     IOError(String),
 }
 
-/// Trait used to influence how SkipMap determines the order of elements. Use StandardComparator
-/// for the normal implementation using numerical comparison.
-pub trait Comparator: Copy {
-    fn cmp(&self, &[u8], &[u8]) -> Ordering;
-}
-
-#[derive(Clone, Copy, Default)]
-pub struct StandardComparator;
-
-impl Comparator for StandardComparator {
-    fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
-        a.cmp(b)
-    }
+pub fn cmp(a: &[u8], b: &[u8]) -> Ordering {
+    a.cmp(b)
 }
 
 pub struct Range<'a> {
--- a/src/write_batch.rs	Sun Dec 25 09:13:43 2016 +0000
+++ b/src/write_batch.rs	Sun Dec 25 10:47:08 2016 +0000
@@ -1,5 +1,5 @@
 use memtable::MemTable;
-use types::{Comparator, SequenceNumber, ValueType};
+use types::{SequenceNumber, ValueType};
 use integer_encoding::{VarInt, VarIntWriter, FixedInt};
 
 use std::io::Write;
@@ -82,7 +82,7 @@
         }
     }
 
-    pub fn insert_into_memtable<C: Comparator>(&self, seq: SequenceNumber, mt: &mut MemTable<C>) {
+    pub fn insert_into_memtable(&self, seq: SequenceNumber, mt: &mut MemTable) {
         let mut sequence_num = seq;
 
         for (k, v) in self.iter() {