use bbtree::unsync::BBTreeMap;
use crate::types::MemEntry;
pub trait MemTable: Send + Sync {
fn insert(&mut self, key: Vec<u8>, entry: MemEntry);
fn get(&self, key: &[u8]) -> Option<MemEntry>;
fn range(&self, start: &[u8], end: &[u8]) -> Vec<(Vec<u8>, MemEntry)>;
fn prefix(&self, prefix: &[u8]) -> Vec<(Vec<u8>, MemEntry)>;
fn iter(&self) -> Vec<(Vec<u8>, MemEntry)>;
fn len(&self) -> usize;
fn clear(&mut self);
fn is_empty(&self) -> bool {
self.len() == 0
}
}
pub struct BTreeMemTable {
inner: std::collections::BTreeMap<Vec<u8>, MemEntry>,
}
impl BTreeMemTable {
pub fn new() -> Self {
BTreeMemTable {
inner: std::collections::BTreeMap::new(),
}
}
}
impl Default for BTreeMemTable {
fn default() -> Self {
Self::new()
}
}
impl MemTable for BTreeMemTable {
fn insert(&mut self, key: Vec<u8>, entry: MemEntry) {
self.inner.insert(key, entry);
}
fn get(&self, key: &[u8]) -> Option<MemEntry> {
self.inner.get(key).cloned()
}
fn range(&self, start: &[u8], end: &[u8]) -> Vec<(Vec<u8>, MemEntry)> {
use std::ops::Bound;
self.inner
.range((
Bound::Included(start.to_vec()),
Bound::Excluded(end.to_vec()),
))
.map(|(k, v)| (k.clone(), v.clone()))
.collect()
}
fn prefix(&self, prefix: &[u8]) -> Vec<(Vec<u8>, MemEntry)> {
self.inner
.range(prefix.to_vec()..)
.take_while(|(k, _)| k.starts_with(prefix))
.map(|(k, v)| (k.clone(), v.clone()))
.collect()
}
fn iter(&self) -> Vec<(Vec<u8>, MemEntry)> {
self.inner.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
}
fn len(&self) -> usize {
self.inner.len()
}
fn clear(&mut self) {
self.inner.clear();
}
}
pub struct BBTreeMemTable {
inner: BBTreeMap<Vec<u8>, MemEntry>,
}
impl BBTreeMemTable {
pub fn new() -> Self {
BBTreeMemTable {
inner: BBTreeMap::new(),
}
}
}
impl Default for BBTreeMemTable {
fn default() -> Self {
Self::new()
}
}
impl MemTable for BBTreeMemTable {
fn insert(&mut self, key: Vec<u8>, entry: MemEntry) {
self.inner.insert(key, entry);
}
fn get(&self, key: &[u8]) -> Option<MemEntry> {
self.inner.get(key).cloned()
}
fn range(&self, start: &[u8], end: &[u8]) -> Vec<(Vec<u8>, MemEntry)> {
use std::ops::Bound;
self.inner
.range((
Bound::Included(start.to_vec()),
Bound::Excluded(end.to_vec()),
))
.map(|(k, v)| (k.clone(), v.clone()))
.collect()
}
fn prefix(&self, prefix: &[u8]) -> Vec<(Vec<u8>, MemEntry)> {
self.inner
.range(prefix.to_vec()..)
.take_while(|(k, _)| k.starts_with(prefix))
.map(|(k, v)| (k.clone(), v.clone()))
.collect()
}
fn iter(&self) -> Vec<(Vec<u8>, MemEntry)> {
self.inner.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
}
fn len(&self) -> usize {
self.inner.len()
}
fn clear(&mut self) {
self.inner.clear();
}
}
pub struct BBTreeConcurrentMemTable {
inner: bbtree::BBTreeMap<Vec<u8>, MemEntry>,
count: usize,
}
impl BBTreeConcurrentMemTable {
pub fn new() -> Self {
BBTreeConcurrentMemTable {
inner: bbtree::BBTreeMap::new(),
count: 0,
}
}
}
impl Default for BBTreeConcurrentMemTable {
fn default() -> Self {
Self::new()
}
}
impl MemTable for BBTreeConcurrentMemTable {
fn insert(&mut self, key: Vec<u8>, entry: MemEntry) {
match self.inner.insert(key, entry) {
Ok(None) => self.count += 1,
Ok(Some(_)) => {}
Err(_) => panic!("BBTreeConcurrentMemTable: allocation failed"),
}
}
fn get(&self, key: &[u8]) -> Option<MemEntry> {
self.inner.get_cloned(key)
}
fn range(&self, start: &[u8], end: &[u8]) -> Vec<(Vec<u8>, MemEntry)> {
use std::ops::Bound;
let mut results = Vec::new();
self.inner.scan::<[u8], ()>(
(Bound::Included(start), Bound::Excluded(end)),
|k, v| {
results.push((k.clone(), v.clone()));
std::ops::ControlFlow::Continue(())
},
);
results
}
fn prefix(&self, prefix: &[u8]) -> Vec<(Vec<u8>, MemEntry)> {
use std::ops::Bound;
let mut results = Vec::new();
self.inner.scan::<[u8], ()>(
(Bound::Included(prefix), Bound::Unbounded),
|k, v| {
if !k.starts_with(prefix) {
return std::ops::ControlFlow::Break(());
}
results.push((k.clone(), v.clone()));
std::ops::ControlFlow::Continue(())
},
);
results
}
fn iter(&self) -> Vec<(Vec<u8>, MemEntry)> {
use std::ops::Bound;
let mut results = Vec::new();
self.inner.scan::<[u8], ()>(
(Bound::Unbounded, Bound::Unbounded),
|k, v| {
results.push((k.clone(), v.clone()));
std::ops::ControlFlow::Continue(())
},
);
results
}
fn len(&self) -> usize {
self.count
}
fn clear(&mut self) {
self.inner = bbtree::BBTreeMap::new();
self.count = 0;
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::types::{encode_key, Operation};
fn make_entry(lsn: u64, value: &[u8]) -> MemEntry {
MemEntry {
key: vec![],
value: Some(value.to_vec()),
op: Operation::Put,
lsn,
timestamp: 0,
ttl: 0,
}
}
fn assert_object_safe(_: Box<dyn MemTable>) {}
#[test]
fn test_object_safe() {
let m: Box<dyn MemTable> = Box::new(BTreeMemTable::new());
assert_object_safe(m);
}
#[test]
fn test_insert_and_get() {
let mut m = BTreeMemTable::new();
let key = encode_key(b"ns", b"k1");
let entry = make_entry(1, b"val1");
m.insert(key.clone(), entry);
assert!(m.get(&key).is_some());
assert_eq!(m.get(&key).unwrap().value, Some(b"val1".to_vec()));
}
#[test]
fn test_overwrite_lsn() {
let mut m = BTreeMemTable::new();
let key = encode_key(b"ns", b"k1");
m.insert(key.clone(), make_entry(1, b"v1"));
m.insert(key.clone(), make_entry(2, b"v2"));
let entry = m.get(&key).unwrap();
assert_eq!(entry.lsn, 2);
assert_eq!(entry.value, Some(b"v2".to_vec()));
}
#[test]
fn test_len() {
let mut m = BTreeMemTable::new();
for i in 0..10u8 {
m.insert(encode_key(b"ns", &[i]), make_entry(i as u64, &[i]));
}
assert_eq!(m.len(), 10);
}
#[test]
fn test_namespace_isolation() {
let mut m = BTreeMemTable::new();
m.insert(encode_key(b"ns_a", b"key1"), make_entry(1, b"va1"));
m.insert(encode_key(b"ns_a", b"key2"), make_entry(2, b"va2"));
m.insert(encode_key(b"ns_b", b"key1"), make_entry(3, b"vb1"));
let ns_a_prefix = encode_key(b"ns_a", b"");
let ns_a_results = m.prefix(&ns_a_prefix);
assert_eq!(ns_a_results.len(), 2);
for (_, entry) in &ns_a_results {
assert!(
entry.value != Some(b"vb1".to_vec()),
"ns_b key leaked into ns_a prefix scan"
);
}
let ns_b_prefix = encode_key(b"ns_b", b"");
let ns_b_results = m.prefix(&ns_b_prefix);
assert_eq!(ns_b_results.len(), 1);
}
#[test]
fn test_range_isolation() {
let mut m = BTreeMemTable::new();
m.insert(encode_key(b"a", b"k1"), make_entry(1, b"va1"));
m.insert(encode_key(b"a", b"k2"), make_entry(2, b"va2"));
m.insert(encode_key(b"b", b"k1"), make_entry(3, b"vb1"));
let start = encode_key(b"a", b"");
let end = encode_key(b"b", b"");
let results = m.range(&start, &end);
for (_, entry) in &results {
assert!(
entry.value != Some(b"vb1".to_vec()),
"ns_b key appeared in ns_a range"
);
}
}
}