use key_types::{self, LookupKey};
use types;
use std::cmp::Ordering;
use std::rc::Rc;
type WrappedCmp = Rc<Box<Cmp>>;
pub trait Cmp {
fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering;
fn find_shortest_sep(&self, from: &[u8], to: &[u8]) -> Vec<u8>;
fn find_short_succ(&self, key: &[u8]) -> Vec<u8>;
fn id(&self) -> &'static str;
}
#[derive(Clone)]
pub struct DefaultCmp;
impl Cmp for DefaultCmp {
fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
a.cmp(b)
}
fn id(&self) -> &'static str {
"leveldb.BytewiseComparator"
}
fn find_shortest_sep(&self, a: &[u8], b: &[u8]) -> Vec<u8> {
if a == b {
return a.to_vec();
}
let min = if a.len() < b.len() { a.len() } else { b.len() };
let mut diff_at = 0;
while diff_at < min && a[diff_at] == b[diff_at] {
diff_at += 1;
}
while diff_at < min {
let diff = a[diff_at];
if diff < 0xff && diff + 1 < b[diff_at] {
let mut sep = Vec::from(&a[0..diff_at + 1]);
sep[diff_at] += 1;
assert!(self.cmp(&sep, b) == Ordering::Less);
return sep;
}
diff_at += 1;
}
let mut sep = Vec::with_capacity(a.len() + 1);
sep.extend_from_slice(a);
let mut i = a.len() - 1;
while i > 0 && sep[i] == 0xff {
i -= 1;
}
if sep[i] < 0xff {
sep[i] += 1;
if self.cmp(&sep, b) == Ordering::Less {
return sep;
} else {
sep[i] -= 1;
}
}
sep.extend_from_slice(&[0]);
return sep;
}
fn find_short_succ(&self, a: &[u8]) -> Vec<u8> {
let mut result = a.to_vec();
for i in 0..a.len() {
if a[i] != 0xff {
result[i] += 1;
result.resize(i + 1, 0);
return result;
}
}
result.push(255);
return result;
}
}
#[derive(Clone)]
pub struct InternalKeyCmp(pub Rc<Box<Cmp>>);
impl Cmp for InternalKeyCmp {
fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
key_types::cmp_internal_key(self.0.as_ref().as_ref(), a, b)
}
fn id(&self) -> &'static str {
self.0.id()
}
fn find_shortest_sep(&self, a: &[u8], b: &[u8]) -> Vec<u8> {
if a == b {
return a.to_vec();
}
let (_, seqa, keya) = key_types::parse_internal_key(a);
let (_, _, keyb) = key_types::parse_internal_key(b);
let sep: Vec<u8> = self.0.find_shortest_sep(keya, keyb);
if sep.len() < keya.len() && self.0.cmp(keya, &sep) == Ordering::Less {
return LookupKey::new(&sep, types::MAX_SEQUENCE_NUMBER)
.internal_key()
.to_vec();
}
return LookupKey::new(&sep, seqa).internal_key().to_vec();
}
fn find_short_succ(&self, a: &[u8]) -> Vec<u8> {
let (_, seq, key) = key_types::parse_internal_key(a);
let succ: Vec<u8> = self.0.find_short_succ(key);
return LookupKey::new(&succ, seq).internal_key().to_vec();
}
}
impl InternalKeyCmp {
pub fn cmp_inner(&self, a: &[u8], b: &[u8]) -> Ordering {
self.0.cmp(a, b)
}
}
#[derive(Clone)]
pub struct MemtableKeyCmp(pub Rc<Box<Cmp>>);
impl Cmp for MemtableKeyCmp {
fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
key_types::cmp_memtable_key(self.0.as_ref().as_ref(), a, b)
}
fn id(&self) -> &'static str {
self.0.id()
}
fn find_shortest_sep(&self, _: &[u8], _: &[u8]) -> Vec<u8> {
panic!("find* functions are invalid on MemtableKeyCmp");
}
fn find_short_succ(&self, _: &[u8]) -> Vec<u8> {
panic!("find* functions are invalid on MemtableKeyCmp");
}
}
#[cfg(test)]
mod tests {
use super::*;
use key_types::LookupKey;
use types;
#[test]
fn test_cmp_defaultcmp_shortest_sep() {
assert_eq!(
DefaultCmp.find_shortest_sep("abcd".as_bytes(), "abcf".as_bytes()),
"abce".as_bytes()
);
assert_eq!(
DefaultCmp.find_shortest_sep("abc".as_bytes(), "acd".as_bytes()),
"abd".as_bytes()
);
assert_eq!(
DefaultCmp.find_shortest_sep("abcdefghi".as_bytes(), "abcffghi".as_bytes()),
"abce".as_bytes()
);
assert_eq!(
DefaultCmp.find_shortest_sep("a".as_bytes(), "a".as_bytes()),
"a".as_bytes()
);
assert_eq!(
DefaultCmp.find_shortest_sep("a".as_bytes(), "b".as_bytes()),
"a\0".as_bytes()
);
assert_eq!(
DefaultCmp.find_shortest_sep("abc".as_bytes(), "zzz".as_bytes()),
"b".as_bytes()
);
assert_eq!(
DefaultCmp.find_shortest_sep("yyy".as_bytes(), "z".as_bytes()),
"yyz".as_bytes()
);
assert_eq!(
DefaultCmp.find_shortest_sep("".as_bytes(), "".as_bytes()),
"".as_bytes()
);
}
#[test]
fn test_cmp_defaultcmp_short_succ() {
assert_eq!(
DefaultCmp.find_short_succ("abcd".as_bytes()),
"b".as_bytes()
);
assert_eq!(
DefaultCmp.find_short_succ("zzzz".as_bytes()),
"{".as_bytes()
);
assert_eq!(DefaultCmp.find_short_succ(&[]), &[0xff]);
assert_eq!(
DefaultCmp.find_short_succ(&[0xff, 0xff, 0xff]),
&[0xff, 0xff, 0xff, 0xff]
);
}
#[test]
fn test_cmp_internalkeycmp_shortest_sep() {
let cmp = InternalKeyCmp(Rc::new(Box::new(DefaultCmp)));
assert_eq!(
cmp.find_shortest_sep(
LookupKey::new("abcd".as_bytes(), 1).internal_key(),
LookupKey::new("abcf".as_bytes(), 2).internal_key()
),
LookupKey::new("abce".as_bytes(), 1).internal_key()
);
assert_eq!(
cmp.find_shortest_sep(
LookupKey::new("abcd".as_bytes(), 1).internal_key(),
LookupKey::new("abce".as_bytes(), 2).internal_key()
),
LookupKey::new("abcd\0".as_bytes(), 1).internal_key()
);
assert_eq!(
cmp.find_shortest_sep(
LookupKey::new("abc".as_bytes(), 1).internal_key(),
LookupKey::new("zzz".as_bytes(), 2).internal_key()
),
LookupKey::new("b".as_bytes(), types::MAX_SEQUENCE_NUMBER).internal_key()
);
assert_eq!(
cmp.find_shortest_sep(
LookupKey::new("abc".as_bytes(), 1).internal_key(),
LookupKey::new("acd".as_bytes(), 2).internal_key()
),
LookupKey::new("abd".as_bytes(), 1).internal_key()
);
assert_eq!(
cmp.find_shortest_sep(
LookupKey::new("abc".as_bytes(), 1).internal_key(),
LookupKey::new("abe".as_bytes(), 2).internal_key()
),
LookupKey::new("abd".as_bytes(), 1).internal_key()
);
assert_eq!(
cmp.find_shortest_sep(
LookupKey::new("".as_bytes(), 1).internal_key(),
LookupKey::new("".as_bytes(), 2).internal_key()
),
LookupKey::new("".as_bytes(), 1).internal_key()
);
assert_eq!(
cmp.find_shortest_sep(
LookupKey::new("abc".as_bytes(), 2).internal_key(),
LookupKey::new("abc".as_bytes(), 2).internal_key()
),
LookupKey::new("abc".as_bytes(), 2).internal_key()
);
}
#[test]
fn test_cmp_internalkeycmp() {
let cmp = InternalKeyCmp(Rc::new(Box::new(DefaultCmp)));
let a = LookupKey::new("abc".as_bytes(), 2).internal_key().to_vec();
let b = LookupKey::new("abc".as_bytes(), 1).internal_key().to_vec();
let c = LookupKey::new("abd".as_bytes(), 3).internal_key().to_vec();
let d = "xyy".as_bytes();
let e = "xyz".as_bytes();
assert_eq!(Ordering::Less, cmp.cmp(&a, &b));
assert_eq!(Ordering::Equal, cmp.cmp(&a, &a));
assert_eq!(Ordering::Greater, cmp.cmp(&b, &a));
assert_eq!(Ordering::Less, cmp.cmp(&a, &c));
assert_eq!(Ordering::Less, cmp.cmp_inner(d, e));
assert_eq!(Ordering::Greater, cmp.cmp_inner(e, d));
}
#[test]
#[should_panic]
fn test_cmp_memtablekeycmp_panics() {
let cmp = MemtableKeyCmp(Rc::new(Box::new(DefaultCmp)));
cmp.cmp(&[1, 2, 3], &[4, 5, 6]);
}
}