use super::{
Index, IndexApply, IndexKeeper, IndexModify, KeyChanges, Leaf, Node, NodeRef, Nodes, Value, ValueChange, ValueMode,
};
use crate::{
error::{IndexChangeError, PERes, PIRes},
id::RecRef,
index::config::IndexTypeInternal,
};
use rand::random;
use std::{collections::HashMap, ops::Bound, rc::Rc};
impl<V> std::fmt::Display for Value<V>
where
V: std::fmt::Display,
{
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
Value::Cluster(x) => {
write!(f, "{} values: [", x.len())?;
for v in x {
write!(f, " {}, ", v)?;
}
write!(f, "]")?;
}
Value::Single(v) => {
write!(f, "value: {}", v)?;
}
}
Ok(())
}
}
fn print_nodes<K: IndexTypeInternal, V: IndexTypeInternal>(
tree: &mut dyn IndexKeeper<K, V>,
node: &Nodes<K>,
depth: usize,
) -> PERes<()> {
let padding = String::from_utf8(vec![b' '; depth]).unwrap();
for i in 0..node.len() {
if i == 0 {
println!("{} __ ", padding);
} else {
println!("{} {} ", padding, node.keys[i - 1]);
}
print_node(tree, &node.pointers[i], depth + 1)?;
}
Ok(())
}
fn print_leaf<K: IndexTypeInternal, V: IndexTypeInternal>(
_tree: &mut dyn IndexKeeper<K, V>,
leaf: &Leaf<K, V>,
depth: usize,
) -> PERes<()> {
let padding = String::from_utf8(vec![b' '; depth]).unwrap();
println!("{} ", padding);
for i in 0..leaf.len() {
println!("{} {} {} ", padding, leaf.entries[i].key, leaf.entries[i].value);
}
println!("{} ", padding);
Ok(())
}
fn print_node<K: IndexTypeInternal, V: IndexTypeInternal>(
tree: &mut dyn IndexKeeper<K, V>,
node: &NodeRef,
depth: usize,
) -> PERes<()> {
match tree.load(node)? {
Node::Node(n) => {
print_nodes(tree, &n, depth)?;
}
Node::Leaf(l) => {
print_leaf(tree, &l, depth)?;
}
}
Ok(())
}
fn print_tree<K: IndexTypeInternal, V: IndexTypeInternal>(tree: &mut dyn IndexKeeper<K, V>) -> PERes<()> {
let root = tree.get_root()?;
if let Some(r) = root {
print_node(tree, &r, 0)?;
} else {
println!(" Empty Root");
}
Ok(())
}
fn random_pointer() -> NodeRef {
RecRef::new(random::<u64>(), random::<u32>())
}
struct MockIndexKeeper<K: Clone + Ord, V: Clone> {
store: HashMap<NodeRef, Node<K, V>>,
root: Option<NodeRef>,
v: ValueMode,
name: String,
}
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(),
}
}
fn new_mode(v: ValueMode) -> MockIndexKeeper<K, V> {
MockIndexKeeper {
store: HashMap::new(),
root: None,
v,
name: "test_index".to_string(),
}
}
}
impl<K: Clone + Ord, V: Clone> IndexKeeper<K, V> for MockIndexKeeper<K, V> {
fn load_with(&self, node: &NodeRef, _reuse: Option<Nodes<K>>) -> PERes<Node<K, V>> {
self.load(node)
}
fn load(&self, node: &NodeRef) -> PERes<Node<K, V>> {
Ok(self.store.get(&node).unwrap().clone())
}
fn get_root(&self) -> PERes<Option<NodeRef>> {
Ok(self.root.clone())
}
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 load_modify(&self, node: &NodeRef) -> PIRes<Option<(Rc<Node<K, V>>, u16)>> {
Ok(Some((Rc::new(self.store.get(&node).unwrap().clone()), 0)))
}
fn lock(&mut self, _node: &NodeRef, _version: u16) -> PIRes<bool> {
Ok(true)
}
fn unlock(&mut self, _node: &NodeRef) -> PIRes<bool> {
Ok(true)
}
fn unlock_config(&mut self) -> PIRes<bool> {
Ok(true)
}
fn lock_config(&mut self) -> PIRes<bool> {
Ok(true)
}
fn owned(&mut self, _node_ref: &NodeRef, mut node: Rc<Node<K, V>>) -> Node<K, V> {
Rc::make_mut(&mut node);
Rc::try_unwrap(node).ok().unwrap()
}
fn insert(&mut self, node: Node<K, V>) -> PIRes<NodeRef> {
let node_ref = random_pointer();
self.store.insert(node_ref.clone(), node.clone());
Ok(node_ref)
}
fn update(&mut self, node_ref: &NodeRef, node: Node<K, V>, _version: u16) -> PIRes<()> {
self.store.insert(node_ref.clone(), node);
Ok(())
}
fn get_root_refresh(&mut self) -> PIRes<Option<NodeRef>> {
Ok(self.root.clone())
}
fn set_root(&mut self, root: Option<NodeRef>) -> PIRes<()> {
Ok(self.root = root)
}
fn delete(&mut self, node: &NodeRef, _version: u16) -> PIRes<()> {
self.store.remove(&node);
Ok(())
}
fn bottom_limit(&self) -> usize {
10
}
fn top_limit(&self) -> usize {
30
}
}
#[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();
print_tree(&mut keeper).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();
print_tree(&mut keeper).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();
print_tree(&mut keeper).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();
print_tree(&mut keeper).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();
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();
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));
}
}