use super::{
super::super::ValueMode, BottomDepth, Index, IndexApply, IndexKeeper, IndexLimits, IndexModify, KeyChanges,
LockGroup, Node, Path, PosRef, TreeNode, TreeNodeRef, Value, key_changes::ValueChange,
};
use crate::{
error::{IndexChangeError, PERes, PIRes},
id::RecRef,
};
use rand::random;
use std::{collections::HashMap, collections::hash_map::Entry, ops::Bound};
fn random_pointer() -> TreeNodeRef {
RecRef::new(random::<u64>(), random::<u32>())
}
struct LockData {
version: u16,
counter: u32,
}
struct MockIndexKeeper<K: Clone + Ord, V: Clone> {
store: HashMap<TreeNodeRef, TreeNode<K, V>>,
root: Option<TreeNodeRef>,
v: ValueMode,
name: String,
locked: HashMap<TreeNodeRef, LockData>,
deleted: HashMap<TreeNodeRef, ()>,
limits: IndexLimits,
}
impl<K: Clone + Ord, V: Clone> MockIndexKeeper<K, V> {
fn new() -> MockIndexKeeper<K, V> {
MockIndexKeeper {
store: HashMap::new(),
root: None,
v: ValueMode::Replace,
name: "test_index".to_string(),
locked: HashMap::new(),
deleted: HashMap::new(),
limits: IndexLimits::new(10, 30),
}
}
fn new_mode(v: ValueMode) -> MockIndexKeeper<K, V> {
MockIndexKeeper {
store: HashMap::new(),
root: None,
v,
name: "test_index".to_string(),
locked: HashMap::new(),
deleted: HashMap::new(),
limits: IndexLimits::new(10, 30),
}
}
}
impl<K: Clone + Ord, V: Clone> IndexKeeper<K, V> for MockIndexKeeper<K, V> {
fn load_with(&self, node: &TreeNodeRef, _reuse: Option<Node<K>>) -> PERes<TreeNode<K, V>> {
self.load(node)
}
fn failable_load(&self, node: &TreeNodeRef) -> PERes<Option<TreeNode<K, V>>> {
Ok(self.store.get(node).cloned())
}
fn get_root(&self) -> PERes<Option<TreeNodeRef>> {
Ok(self.root)
}
fn value_mode(&self) -> ValueMode {
self.v.clone()
}
fn index_name(&self) -> &String {
&self.name
}
}
impl<K: Clone + Ord, V: Clone> IndexModify<K, V> for MockIndexKeeper<K, V> {
fn lock(&mut self, node: &TreeNodeRef, version: u16) -> PIRes<bool> {
if let Some(lock_data) = self.locked.get_mut(node) {
assert!(version == lock_data.version);
lock_data.counter += 1;
Ok(true)
} else {
self.locked.insert(*node, LockData { version, counter: 1 });
Ok(true)
}
}
fn unlock(&mut self, node: &TreeNodeRef) -> bool {
if let Entry::Occupied(mut x) = self.locked.entry(*node) {
x.get_mut().counter -= 1;
if x.get().counter == 0 {
x.remove();
true
} else {
false
}
} else {
false
}
}
fn lock_config(&mut self) -> PIRes<bool> {
Ok(true)
}
fn insert(&mut self, node: TreeNode<K, V>) -> PIRes<TreeNodeRef> {
let node_ref = random_pointer();
self.store.insert(node_ref, node);
self.locked.insert(node_ref, LockData { version: 0, counter: 1 });
Ok(node_ref)
}
fn load_from_node<R, C>(&self, node_ref: &TreeNodeRef, loader: C) -> PIRes<Option<R>>
where
C: FnOnce(&TreeNode<K, V>, u16) -> R,
{
assert!(self.locked.contains_key(node_ref));
let ret = if let Some(stored) = self.store.get(node_ref) {
assert!(!self.deleted.contains_key(node_ref));
let ret = loader(stored, 0);
Some(ret)
} else {
None
};
Ok(ret)
}
fn update_with<R, C>(&mut self, node_ref: &TreeNodeRef, updater: C) -> PIRes<R>
where
C: FnOnce(&mut TreeNode<K, V>) -> (bool, R),
{
assert!(self.locked.contains_key(node_ref));
assert!(!self.deleted.contains_key(node_ref));
let ret = if let Some(mut stored) = self.store.remove(node_ref) {
let (_changed, ret) = updater(&mut stored);
self.store.insert(*node_ref, stored);
ret
} else {
panic!("updating missing record")
};
Ok(ret)
}
fn get_root_refresh(&mut self) -> PIRes<Option<TreeNodeRef>> {
Ok(self.root)
}
fn set_root(&mut self, root: Option<TreeNodeRef>) -> PIRes<()> {
self.root = root;
Ok(())
}
fn delete(&mut self, node: &TreeNodeRef, _version: u16) -> PIRes<()> {
assert!(self.locked.contains_key(node));
self.deleted.insert(*node, ());
self.store.remove(node);
Ok(())
}
fn delete_to_own(&mut self, node: &TreeNodeRef) -> PIRes<TreeNode<K, V>> {
assert!(self.locked.contains_key(node));
self.deleted.insert(*node, ());
let node_data = if let Some(rec) = self.store.remove(node) {
Some(rec)
} else {
panic!("record should be locked so should exists");
};
Ok(node_data.unwrap())
}
fn limits(&self) -> &IndexLimits {
&self.limits
}
fn is_locked(&mut self, node: &TreeNodeRef) -> bool {
self.locked.contains_key(node)
}
}
#[test]
fn test_single_add() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
changes.push(KeyChanges::single_add(1, 1));
changes.push(KeyChanges::single_add(2, 2));
changes.push(KeyChanges::single_add(3, 4));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(2))));
}
#[test]
fn test_many_add() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
for i in 0..200 {
changes.push(KeyChanges::single_add(i, i));
}
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(2))));
assert_eq!(keeper.get(&100).ok(), Some(Some(Value::Single(100))));
assert_eq!(keeper.get(&201).ok(), Some(None));
}
#[test]
fn test_many_add_multiple_times() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
for n in 0..8 {
for i in 0..20 {
changes.push(KeyChanges::single_add(i, i));
}
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&(n + 2)).ok(), Some(Some(Value::Single(n + 2))));
}
}
#[test]
fn test_single_add_remove() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
changes.push(KeyChanges::single_add(1, 1));
changes.push(KeyChanges::single_add(2, 2));
changes.push(KeyChanges::single_add(3, 4));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(2))));
let mut changes = Vec::new();
changes.push(KeyChanges::single_delete(1, Some(1)));
changes.push(KeyChanges::single_delete(2, Some(2)));
changes.push(KeyChanges::single_delete(3, Some(4)));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(None));
}
#[test]
fn test_aggregate_add_remove() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
changes.push(KeyChanges::new(
2,
vec![ValueChange::Add(1), ValueChange::Remove(Some(1)), ValueChange::Add(2)],
));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(2))));
let mut changes = Vec::new();
changes.push(KeyChanges::new(
2,
vec![
ValueChange::Remove(Some(2)),
ValueChange::Add(1),
ValueChange::Remove(Some(1)),
],
));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(None));
}
#[test]
fn test_group_replace_remove() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
changes.push(KeyChanges::new(2, vec![ValueChange::Add(1), ValueChange::Add(2)]));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(2))));
let mut changes = Vec::new();
changes.push(KeyChanges::new(2, vec![ValueChange::Remove(Some(2))]));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(None));
}
#[test]
fn test_group_values_remove() {
let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::Cluster);
let mut changes = Vec::new();
changes.push(KeyChanges::new(
2,
vec![ValueChange::Add(1), ValueChange::Add(2), ValueChange::Add(3)],
));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Cluster(vec![1, 2, 3]))));
let mut changes = Vec::new();
changes.push(KeyChanges::new(
2,
vec![ValueChange::Remove(Some(1)), ValueChange::Remove(Some(2))],
));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(3))));
}
#[test]
fn test_group_values_remove_no_order() {
let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::Cluster);
let mut changes = Vec::new();
changes.push(KeyChanges::new(
2,
vec![ValueChange::Add(3), ValueChange::Add(1), ValueChange::Add(2)],
));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Cluster(vec![1, 2, 3]))));
let mut changes = Vec::new();
changes.push(KeyChanges::new(
2,
vec![ValueChange::Remove(Some(1)), ValueChange::Remove(Some(2))],
));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(3))));
}
#[test]
fn test_add_same_value_twice() {
let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::Cluster);
let mut changes = Vec::new();
changes.push(KeyChanges::new(
2,
vec![ValueChange::Add(1), ValueChange::Add(2), ValueChange::Add(1)],
));
changes.push(KeyChanges::new(1, vec![ValueChange::Add(1), ValueChange::Add(1)]));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Cluster(vec![1, 2]))));
assert_eq!(keeper.get(&1).ok(), Some(Some(Value::Single(1))));
}
#[test]
fn test_add_to_exclusive() {
let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::Exclusive);
let mut changes = Vec::new();
changes.push(KeyChanges::new(2, vec![ValueChange::Add(1)]));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(1))));
let mut changes = Vec::new();
changes.push(KeyChanges::new(2, vec![ValueChange::Add(1)]));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(1))));
let mut changes = Vec::new();
changes.push(KeyChanges::new(2, vec![ValueChange::Add(2)]));
assert!(match keeper.apply(&changes) {
Err(IndexChangeError::IndexDuplicateKey(ref idxname, ref keyname))
if (idxname == "test_index" && keyname == "2") =>
{
true
}
_ => false,
});
}
#[test]
fn test_group_key_remove() {
let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::Cluster);
let mut changes = Vec::new();
changes.push(KeyChanges::new(2, vec![ValueChange::Add(1), ValueChange::Add(2)]));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Cluster(vec![1, 2]))));
let mut changes = Vec::new();
changes.push(KeyChanges::new(2, vec![ValueChange::Remove(None)]));
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(None));
}
#[test]
fn test_many_add_remove() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
for i in 0..200 {
changes.push(KeyChanges::single_add(i, i));
}
changes.sort_by_key(|k| k.k);
keeper.apply(&changes).unwrap();
#[cfg(feature = "experimental_inspect")]
crate::inspect::inspect_tree(&mut keeper, &mut crate::inspect::PrintTreeInspector::new()).unwrap();
assert_eq!(keeper.get(&2).ok(), Some(Some(Value::Single(2))));
assert_eq!(keeper.get(&100).ok(), Some(Some(Value::Single(100))));
assert_eq!(keeper.get(&201).ok(), Some(None));
let mut changes = Vec::new();
for i in 0..200 {
changes.push(KeyChanges::single_delete(i, Some(i)));
}
changes.sort_by_key(|k| k.k);
keeper.apply(&changes).unwrap();
#[cfg(feature = "experimental_inspect")]
crate::inspect::inspect_tree(&mut keeper, &mut crate::inspect::PrintTreeInspector::new()).unwrap();
assert_eq!(keeper.get_root().ok(), Some(None));
assert_eq!(keeper.get(&2).ok(), Some(None));
assert_eq!(keeper.get(&100).ok(), Some(None));
}
#[test]
fn test_many_add_remove_multiple_times() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
let mut rchanges = Vec::new();
for n in 0..8 {
for i in 0..20 {
changes.push(KeyChanges::single_add(i, i));
rchanges.push(KeyChanges::single_delete(i, Some(i)));
}
changes.sort_by_key(|k| k.k);
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&(n + 2)).ok(), Some(Some(Value::Single(n + 2))));
rchanges.sort_by_key(|k| k.k);
keeper.apply(&rchanges).unwrap();
assert_eq!(keeper.get(&(n + 2)).ok(), Some(None));
}
}
#[test]
fn test_iter_from() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
for i in 0..50 {
changes.push(KeyChanges::single_add(i, i));
}
keeper.apply(&changes).unwrap();
#[cfg(feature = "experimental_inspect")]
crate::inspect::inspect_tree(&mut keeper, &mut crate::inspect::PrintTreeInspector::new()).unwrap();
let mut iter = keeper.iter_from(Bound::Included(&5)).unwrap();
let next = iter.iter.next();
assert_eq!(5, next.unwrap().key);
let next = iter.iter.next();
assert_eq!(6, next.unwrap().key);
let mut last_val = None;
for v in iter.iter {
last_val = Some(v);
}
let mut next_page = keeper
.iter_from(Bound::Excluded(&last_val.clone().unwrap().key))
.unwrap();
let next = next_page.iter.next();
assert_eq!(last_val.unwrap().key + 1, next.unwrap().key);
}
#[test]
fn test_iter() {
let mut keeper = MockIndexKeeper::<u8, u8>::new();
let mut changes = Vec::new();
for i in 0..50 {
changes.push(KeyChanges::single_add(i, i));
}
keeper.apply(&changes).unwrap();
#[cfg(feature = "experimental_inspect")]
crate::inspect::inspect_tree(&mut keeper, &mut crate::inspect::PrintTreeInspector::new()).unwrap();
let mut iter = keeper.iter_from(Bound::Unbounded).unwrap();
let next = iter.iter.next();
assert_eq!(0, next.unwrap().key);
let mut last_val = None;
for v in iter.iter {
last_val = Some(v);
}
let mut next_page = keeper
.iter_from(Bound::Excluded(&last_val.clone().unwrap().key))
.unwrap();
let next = next_page.iter.next();
assert_eq!(last_val.unwrap().key + 1, next.unwrap().key);
let mut last_val = None;
for v in next_page.iter {
last_val = Some(v);
}
assert_eq!(last_val.unwrap().key, 49);
let mut next_page = keeper.iter_from(Bound::Excluded(&49)).unwrap();
assert!(next_page.iter.next().is_none());
}
#[test]
fn test_a_lot_add_remove_multiple_times() {
let mut keeper = MockIndexKeeper::<u32, u32>::new();
let mut changes = Vec::new();
let mut remove = Vec::new();
for n in 1..30 {
for i in 1..200 {
changes.push(KeyChanges::single_add(i * n, i * n));
if i % 2 == 0 {
remove.push(KeyChanges::single_delete(i * n, Some(i * n)));
}
}
changes.sort_by_key(|k| k.k);
keeper.apply(&changes).unwrap();
#[cfg(feature = "experimental_inspect")]
crate::inspect::inspect_tree(&mut keeper, &mut crate::inspect::PrintTreeInspector::new()).unwrap();
assert_eq!(keeper.get(&(2 * n)).ok(), Some(Some(Value::Single(2 * n))));
assert_eq!(keeper.get(&(100 * n)).ok(), Some(Some(Value::Single(100 * n))));
assert_eq!(keeper.get(&20001).ok(), Some(None));
remove.sort_by_key(|k| k.k);
keeper.apply(&remove).unwrap();
#[cfg(feature = "experimental_inspect")]
crate::inspect::inspect_tree(&mut keeper, &mut crate::inspect::PrintTreeInspector::new()).unwrap();
assert_eq!(keeper.get(&(2 * n)).ok(), Some(None));
assert_eq!(keeper.get(&(100 * n)).ok(), Some(None));
}
}
#[test]
fn test_big_tree() {
let mut keeper = MockIndexKeeper::<u32, u32>::new();
for n in 1..20 {
let mut changes = Vec::new();
let mut remove = Vec::new();
for i in 1..301 {
changes.push(KeyChanges::single_add(i * n, i * n));
if i % 2 == 0 {
remove.push(KeyChanges::single_delete(i * n, Some(i * n)));
}
}
keeper.apply(&changes).unwrap();
assert_eq!(keeper.get(&(2 * n)).ok(), Some(Some(Value::Single(2 * n))));
assert_eq!(keeper.get(&(100 * n)).ok(), Some(Some(Value::Single(100 * n))));
assert_eq!(keeper.get(&20001).ok(), Some(None));
keeper.apply(&remove).unwrap();
assert_eq!(keeper.get(&(2 * n)).ok(), Some(None));
assert_eq!(keeper.get(&(100 * n)).ok(), Some(None));
}
}
#[test]
fn test_lock_group_parent_lock() {
let id = PosRef::new(&10u8, 1, RecRef::new(10, 20));
let mut group = LockGroup::<u8>::new(BottomDepth(0));
let mut path = Path::new(1u8);
path.push(id.clone(), 10, 40);
path.push(PosRef::new(&10u8, 10, RecRef::new(10, 21)), 10, 40);
group.add(path, 10, &None);
let mut path = Path::new(11u8);
path.push(id.clone(), 10, 40);
path.push(PosRef::new(&20u8, 11, RecRef::new(10, 23)), 10, 40);
group.add(path, 30, &None);
let mut path = Path::new(30u8);
path.push(id, 10, 40);
path.push(PosRef::new(&30u8, 12, RecRef::new(10, 22)), 10, 40);
group.add(path, 50, &None);
let res = group.parent_group(&IndexLimits::new(20, 40));
assert_eq!(res.len(), 1);
assert_eq!(res[0].add_count(), 2);
assert_eq!(res[0].remove_count(), 1);
}
#[test]
fn test_lock_group_last_change_different_parent() {
let id = RecRef::new(10, 20);
let mut group = LockGroup::<u8>::new(BottomDepth(0));
let mut path = Path::new(10u8);
path.push(PosRef::new(&1u8, 1, id), 10, 40);
path.push(PosRef::new(&10u8, 10, RecRef::new(10, 21)), 10, 40);
group.add(path, 30, &None);
let mut path = Path::new(20u8);
path.push(PosRef::new(&1u8, 1, id), 10, 40);
path.push(PosRef::new(&20u8, 11, RecRef::new(10, 23)), 10, 40);
group.add(path, 30, &None);
let mut path = Path::new(30u8);
path.push(PosRef::new(&1u8, 2, RecRef::new(10, 30)), 10, 40);
path.push(PosRef::new(&30u8, 12, RecRef::new(10, 22)), 10, 40);
group.add(path, 50, &None);
let res = group.parent_group(&IndexLimits::new(20, 40));
assert_eq!(res.len(), 2);
assert_eq!(res[1].add_count(), 2);
}