1
use super::{
2
    Index, IndexApply, IndexKeeper, IndexModify, IndexType, KeyChanges, Leaf, Node, NodeRef, Nodes, PRes, Value,
3
    ValueChange, ValueMode,
4
};
5
use crate::{error::PersyError, id::RecRef};
6
use rand::random;
7
use std::{collections::HashMap, ops::Bound, rc::Rc};
8

9
impl<V> std::fmt::Display for Value<V>
10
where
11
    V: std::fmt::Display,
12
{
13 1
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
14 1
        match self {
15 1
            Value::CLUSTER(x) => {
16 0
                write!(f, "{} values: [", x.len())?;
17 0
                for v in x {
18 0
                    write!(f, " {}, ", v)?;
19
                }
20 0
                write!(f, "]")?;
21
            }
22 1
            Value::SINGLE(v) => {
23 1
                write!(f, "value: {}", v)?;
24
            }
25
        }
26 1
        Ok(())
27 1
    }
28
}
29

30 1
fn print_nodes<K: IndexType, V: IndexType>(
31
    tree: &mut dyn IndexKeeper<K, V>,
32
    node: &Nodes<K>,
33
    depth: usize,
34
) -> PRes<()> {
35 1
    let padding = String::from_utf8(vec![b' '; depth]).unwrap();
36 1
    for i in 0..node.len() {
37 1
        if i == 0 {
38 1
            println!("{} __ ", padding);
39
        } else {
40 1
            println!("{} {}  ", padding, node.keys[i - 1]);
41
        }
42 1
        print_node(tree, &node.pointers[i], depth + 1)?;
43
    }
44 1
    Ok(())
45 1
}
46

47 1
fn print_leaf<K: IndexType, V: IndexType>(
48
    _tree: &mut dyn IndexKeeper<K, V>,
49
    leaf: &Leaf<K, V>,
50
    depth: usize,
51
) -> PRes<()> {
52 1
    let padding = String::from_utf8(vec![b' '; depth]).unwrap();
53 1
    println!("{} ", padding);
54 1
    for i in 0..leaf.len() {
55 1
        println!("{} {} {} ", padding, leaf.entries[i].key, leaf.entries[i].value);
56
    }
57 1
    println!("{} ", padding);
58 1
    Ok(())
59 1
}
60

61 1
fn print_node<K: IndexType, V: IndexType>(tree: &mut dyn IndexKeeper<K, V>, node: &NodeRef, depth: usize) -> PRes<()> {
62 1
    match tree.load(node)? {
63 1
        Node::NODE(n) => {
64 1
            print_nodes(tree, &n, depth)?;
65 1
        }
66 1
        Node::LEAF(l) => {
67 1
            print_leaf(tree, &l, depth)?;
68 1
        }
69 0
    }
70 1
    Ok(())
71 1
}
72

73 1
fn print_tree<K: IndexType, V: IndexType>(tree: &mut dyn IndexKeeper<K, V>) -> PRes<()> {
74 1
    let root = tree.get_root()?;
75 1
    if let Some(r) = root {
76 1
        print_node(tree, &r, 0)?;
77
    } else {
78 1
        println!(" Empty Root");
79
    }
80

81 1
    Ok(())
82 1
}
83 1
fn random_pointer() -> NodeRef {
84 1
    RecRef::new(random::<u64>(), random::<u32>())
85 1
}
86

87
struct MockIndexKeeper<K: Clone + Ord, V: Clone> {
88
    store: HashMap<NodeRef, Node<K, V>>,
89
    root: Option<NodeRef>,
90
    v: ValueMode,
91
    name: String,
92
}
93

94
impl<K: Clone + Ord, V: Clone> MockIndexKeeper<K, V> {
95 1
    fn new() -> MockIndexKeeper<K, V> {
96 1
        MockIndexKeeper {
97 1
            store: HashMap::new(),
98 1
            root: None,
99 1
            v: ValueMode::REPLACE,
100 1
            name: "test_index".to_string(),
101 0
        }
102 1
    }
103

104 1
    fn new_mode(v: ValueMode) -> MockIndexKeeper<K, V> {
105 1
        MockIndexKeeper {
106 1
            store: HashMap::new(),
107 1
            root: None,
108
            v,
109 1
            name: "test_index".to_string(),
110 0
        }
111 1
    }
112
}
113

114
impl<K: Clone + Ord, V: Clone> IndexKeeper<K, V> for MockIndexKeeper<K, V> {
115 1
    fn load(&self, node: &NodeRef) -> PRes<Node<K, V>> {
116 1
        Ok(self.store.get(&node).unwrap().clone())
117 1
    }
118 1
    fn get_root(&self) -> PRes<Option<NodeRef>> {
119 1
        Ok(self.root.clone())
120 1
    }
121

122 1
    fn value_mode(&self) -> ValueMode {
123 1
        self.v.clone()
124 1
    }
125

126 1
    fn index_name(&self) -> &String {
127 1
        &self.name
128 1
    }
129
}
130

131
impl<K: Clone + Ord, V: Clone> IndexModify<K, V> for MockIndexKeeper<K, V> {
132 1
    fn load_modify(&self, node: &NodeRef) -> PRes<Option<(Rc<Node<K, V>>, u16)>> {
133 1
        Ok(Some((Rc::new(self.store.get(&node).unwrap().clone()), 0)))
134 1
    }
135

136 1
    fn lock(&mut self, _node: &NodeRef, _version: u16) -> PRes<bool> {
137 1
        Ok(true)
138 1
    }
139

140 0
    fn unlock(&mut self, _node: &NodeRef) -> PRes<bool> {
141 0
        Ok(true)
142 0
    }
143
    fn unlock_config(&mut self) -> PRes<bool> {
144
        Ok(true)
145
    }
146

147 1
    fn lock_config(&mut self) -> PRes<bool> {
148 1
        Ok(true)
149 1
    }
150

151 1
    fn owned(&mut self, _node_ref: &NodeRef, mut node: Rc<Node<K, V>>) -> Node<K, V> {
152 1
        Rc::make_mut(&mut node);
153 1
        Rc::try_unwrap(node).ok().unwrap()
154 1
    }
155 1
    fn insert(&mut self, node: Node<K, V>) -> PRes<NodeRef> {
156 1
        let node_ref = random_pointer();
157 1
        self.store.insert(node_ref.clone(), node.clone());
158 1
        Ok(node_ref)
159 1
    }
160

161 1
    fn update(&mut self, node_ref: &NodeRef, node: Node<K, V>, _version: u16) -> PRes<()> {
162 1
        self.store.insert(node_ref.clone(), node);
163 1
        Ok(())
164 1
    }
165

166 1
    fn get_root_refresh(&mut self) -> PRes<Option<NodeRef>> {
167 1
        Ok(self.root.clone())
168 1
    }
169

170 1
    fn set_root(&mut self, root: Option<NodeRef>) -> PRes<()> {
171 1
        Ok(self.root = root)
172 1
    }
173

174 1
    fn delete(&mut self, node: &NodeRef, _version: u16) -> PRes<()> {
175 1
        self.store.remove(&node);
176 1
        Ok(())
177 1
    }
178 1
    fn bottom_limit(&self) -> usize {
179
        10
180 1
    }
181 1
    fn top_limit(&self) -> usize {
182
        30
183 1
    }
184
}
185

186
#[test]
187 1
fn test_single_add() {
188 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
189 1
    let mut changes = Vec::new();
190 1
    changes.push(KeyChanges::single_add(1, 1));
191 1
    changes.push(KeyChanges::single_add(2, 2));
192 1
    changes.push(KeyChanges::single_add(3, 4));
193 1
    keeper.apply(&changes).unwrap();
194 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(2))));
195 1
}
196

197
#[test]
198 1
fn test_many_add() {
199 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
200 1
    let mut changes = Vec::new();
201 1
    for i in 0..200 {
202 1
        changes.push(KeyChanges::single_add(i, i));
203
    }
204 1
    keeper.apply(&changes).unwrap();
205 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(2))));
206 1
    assert_eq!(keeper.get(&100).ok(), Some(Some(Value::SINGLE(100))));
207 1
    assert_eq!(keeper.get(&201).ok(), Some(None));
208 1
}
209

210
#[test]
211 1
fn test_many_add_multiple_times() {
212 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
213 1
    let mut changes = Vec::new();
214 1
    for n in 0..8 {
215 1
        for i in 0..20 {
216 1
            changes.push(KeyChanges::single_add(i, i));
217
        }
218 1
        keeper.apply(&changes).unwrap();
219 1
        assert_eq!(keeper.get(&(n + 2)).ok(), Some(Some(Value::SINGLE(n + 2))));
220
    }
221 1
}
222

223
#[test]
224 1
fn test_single_add_remove() {
225 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
226 1
    let mut changes = Vec::new();
227 1
    changes.push(KeyChanges::single_add(1, 1));
228 1
    changes.push(KeyChanges::single_add(2, 2));
229 1
    changes.push(KeyChanges::single_add(3, 4));
230 1
    keeper.apply(&changes).unwrap();
231 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(2))));
232

233 1
    let mut changes = Vec::new();
234 1
    changes.push(KeyChanges::single_delete(1, Some(1)));
235 1
    changes.push(KeyChanges::single_delete(2, Some(2)));
236 1
    changes.push(KeyChanges::single_delete(3, Some(4)));
237 1
    keeper.apply(&changes).unwrap();
238 1
    assert_eq!(keeper.get(&2).ok(), Some(None));
239 1
}
240

241
#[test]
242 1
fn test_aggregate_add_remove() {
243 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
244 1
    let mut changes = Vec::new();
245 1
    changes.push(KeyChanges::new(
246
        2,
247 1
        vec![ValueChange::ADD(1), ValueChange::REMOVE(Some(1)), ValueChange::ADD(2)],
248
    ));
249 1
    keeper.apply(&changes).unwrap();
250 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(2))));
251

252 1
    let mut changes = Vec::new();
253 1
    changes.push(KeyChanges::new(
254
        2,
255 1
        vec![
256 1
            ValueChange::REMOVE(Some(2)),
257 1
            ValueChange::ADD(1),
258 1
            ValueChange::REMOVE(Some(1)),
259
        ],
260
    ));
261 1
    keeper.apply(&changes).unwrap();
262 1
    assert_eq!(keeper.get(&2).ok(), Some(None));
263 1
}
264

265
#[test]
266 1
fn test_group_replace_remove() {
267 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
268 1
    let mut changes = Vec::new();
269 1
    changes.push(KeyChanges::new(2, vec![ValueChange::ADD(1), ValueChange::ADD(2)]));
270 1
    keeper.apply(&changes).unwrap();
271 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(2))));
272

273 1
    let mut changes = Vec::new();
274 1
    changes.push(KeyChanges::new(2, vec![ValueChange::REMOVE(Some(2))]));
275 1
    keeper.apply(&changes).unwrap();
276 1
    assert_eq!(keeper.get(&2).ok(), Some(None));
277 1
}
278

279
#[test]
280 1
fn test_group_values_remove() {
281 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::CLUSTER);
282 1
    let mut changes = Vec::new();
283 1
    changes.push(KeyChanges::new(
284
        2,
285 1
        vec![ValueChange::ADD(1), ValueChange::ADD(2), ValueChange::ADD(3)],
286
    ));
287 1
    keeper.apply(&changes).unwrap();
288 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::CLUSTER(vec![1, 2, 3]))));
289

290 1
    let mut changes = Vec::new();
291 1
    changes.push(KeyChanges::new(
292
        2,
293 1
        vec![ValueChange::REMOVE(Some(1)), ValueChange::REMOVE(Some(2))],
294
    ));
295 1
    keeper.apply(&changes).unwrap();
296 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(3))));
297 1
}
298

299
#[test]
300 1
fn test_group_values_remove_no_order() {
301 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::CLUSTER);
302 1
    let mut changes = Vec::new();
303 1
    changes.push(KeyChanges::new(
304
        2,
305 1
        vec![ValueChange::ADD(3), ValueChange::ADD(1), ValueChange::ADD(2)],
306
    ));
307 1
    keeper.apply(&changes).unwrap();
308 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::CLUSTER(vec![3, 1, 2]))));
309

310 1
    let mut changes = Vec::new();
311 1
    changes.push(KeyChanges::new(
312
        2,
313 1
        vec![ValueChange::REMOVE(Some(1)), ValueChange::REMOVE(Some(2))],
314
    ));
315 1
    keeper.apply(&changes).unwrap();
316 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(3))));
317 1
}
318

319
#[test]
320 1
fn test_add_same_value_twice() {
321 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::CLUSTER);
322 1
    let mut changes = Vec::new();
323 1
    changes.push(KeyChanges::new(
324
        2,
325 1
        vec![ValueChange::ADD(1), ValueChange::ADD(2), ValueChange::ADD(1)],
326
    ));
327

328 1
    changes.push(KeyChanges::new(1, vec![ValueChange::ADD(1), ValueChange::ADD(1)]));
329 1
    keeper.apply(&changes).unwrap();
330 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::CLUSTER(vec![1, 2]))));
331 1
    assert_eq!(keeper.get(&1).ok(), Some(Some(Value::SINGLE(1))));
332 1
}
333

334
#[test]
335 1
fn test_add_to_esclusive() {
336 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::EXCLUSIVE);
337 1
    let mut changes = Vec::new();
338 1
    changes.push(KeyChanges::new(2, vec![ValueChange::ADD(1)]));
339 1
    keeper.apply(&changes).unwrap();
340 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(1))));
341 1
    let mut changes = Vec::new();
342 1
    changes.push(KeyChanges::new(2, vec![ValueChange::ADD(1)]));
343

344 1
    keeper.apply(&changes).unwrap();
345 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(1))));
346 1
    let mut changes = Vec::new();
347 1
    changes.push(KeyChanges::new(2, vec![ValueChange::ADD(2)]));
348 1
    assert!(match keeper.apply(&changes) {
349 1
        Err(PersyError::IndexDuplicateKey(ref idxname, ref keyname)) if (idxname == "test_index" && keyname == "2") => {
350 1
            true
351
        }
352 0
        _ => false,
353
    });
354 1
}
355

356
#[test]
357 1
fn test_group_key_remove() {
358 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new_mode(ValueMode::CLUSTER);
359 1
    let mut changes = Vec::new();
360 1
    changes.push(KeyChanges::new(2, vec![ValueChange::ADD(1), ValueChange::ADD(2)]));
361 1
    keeper.apply(&changes).unwrap();
362 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::CLUSTER(vec![1, 2]))));
363

364 1
    let mut changes = Vec::new();
365 1
    changes.push(KeyChanges::new(2, vec![ValueChange::REMOVE(None)]));
366 1
    keeper.apply(&changes).unwrap();
367 1
    assert_eq!(keeper.get(&2).ok(), Some(None));
368 1
}
369

370
#[test]
371 1
fn test_many_add_remove() {
372 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
373 1
    let mut changes = Vec::new();
374 1
    for i in 0..200 {
375 1
        changes.push(KeyChanges::single_add(i, i));
376
    }
377 1
    changes.sort_by_key(|k| k.k);
378 1
    keeper.apply(&changes).unwrap();
379 1
    print_tree(&mut keeper).unwrap();
380 1
    assert_eq!(keeper.get(&2).ok(), Some(Some(Value::SINGLE(2))));
381 1
    assert_eq!(keeper.get(&100).ok(), Some(Some(Value::SINGLE(100))));
382 1
    assert_eq!(keeper.get(&201).ok(), Some(None));
383 1
    let mut changes = Vec::new();
384 1
    for i in 0..200 {
385 1
        changes.push(KeyChanges::single_delete(i, Some(i)));
386
    }
387 1
    changes.sort_by_key(|k| k.k);
388 1
    keeper.apply(&changes).unwrap();
389 1
    print_tree(&mut keeper).unwrap();
390 1
    assert_eq!(keeper.get_root().ok(), Some(None));
391 1
    assert_eq!(keeper.get(&2).ok(), Some(None));
392 1
    assert_eq!(keeper.get(&100).ok(), Some(None));
393 1
}
394

395
#[test]
396 1
fn test_many_add_remove_multiple_times() {
397 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
398 1
    let mut changes = Vec::new();
399 1
    let mut rchanges = Vec::new();
400 1
    for n in 0..8 {
401 1
        for i in 0..20 {
402 1
            changes.push(KeyChanges::single_add(i, i));
403 1
            rchanges.push(KeyChanges::single_delete(i, Some(i)));
404
        }
405 1
        changes.sort_by_key(|k| k.k);
406 1
        keeper.apply(&changes).unwrap();
407 1
        assert_eq!(keeper.get(&(n + 2)).ok(), Some(Some(Value::SINGLE(n + 2))));
408 1
        rchanges.sort_by_key(|k| k.k);
409 1
        keeper.apply(&rchanges).unwrap();
410 1
        assert_eq!(keeper.get(&(n + 2)).ok(), Some(None));
411
    }
412 1
}
413

414
#[test]
415 1
fn test_iter_from() {
416 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
417 1
    let mut changes = Vec::new();
418 1
    for i in 0..50 {
419 1
        changes.push(KeyChanges::single_add(i, i));
420
    }
421 1
    keeper.apply(&changes).unwrap();
422 1
    print_tree(&mut keeper).unwrap();
423 1
    let mut iter = keeper.iter_from(Bound::Included(&5)).unwrap();
424 1
    let next = iter.iter.next();
425

426 1
    assert_eq!(5, next.unwrap().key);
427 1
    let next = iter.iter.next();
428 1
    assert_eq!(6, next.unwrap().key);
429 1
    let mut last_val = None;
430 1
    for v in iter.iter {
431 1
        last_val = Some(v);
432 1
    }
433 1
    let mut next_page = keeper
434 1
        .iter_from(Bound::Excluded(&last_val.clone().unwrap().key))
435 1
        .unwrap();
436 1
    let next = next_page.iter.next();
437 1
    assert_eq!(last_val.unwrap().key + 1, next.unwrap().key);
438 1
}
439

440
#[test]
441 1
fn test_iter() {
442 1
    let mut keeper = MockIndexKeeper::<u8, u8>::new();
443 1
    let mut changes = Vec::new();
444 1
    for i in 0..50 {
445 1
        changes.push(KeyChanges::single_add(i, i));
446
    }
447 1
    keeper.apply(&changes).unwrap();
448 1
    print_tree(&mut keeper).unwrap();
449 1
    let mut iter = keeper.iter_from(Bound::Unbounded).unwrap();
450 1
    let next = iter.iter.next();
451

452 1
    assert_eq!(0, next.unwrap().key);
453 1
    let mut last_val = None;
454 1
    for v in iter.iter {
455 1
        last_val = Some(v);
456 1
    }
457 1
    let mut next_page = keeper
458 1
        .iter_from(Bound::Excluded(&last_val.clone().unwrap().key))
459 1
        .unwrap();
460 1
    let next = next_page.iter.next();
461 1
    assert_eq!(last_val.unwrap().key + 1, next.unwrap().key);
462 1
    let mut last_val = None;
463 1
    for v in next_page.iter {
464 1
        last_val = Some(v);
465 1
    }
466 1
    assert_eq!(last_val.unwrap().key, 49);
467 1
    let mut next_page = keeper.iter_from(Bound::Excluded(&49)).unwrap();
468 1
    assert!(next_page.iter.next().is_none());
469 1
}
470

471
#[test]
472 1
fn test_a_lot_add_remove_multiple_times() {
473 1
    let mut keeper = MockIndexKeeper::<u32, u32>::new();
474 1
    let mut changes = Vec::new();
475 1
    let mut remove = Vec::new();
476 1
    for n in 1..30 {
477 1
        for i in 1..200 {
478 1
            changes.push(KeyChanges::single_add(i * n, i * n));
479 1
            if i % 2 == 0 {
480 1
                remove.push(KeyChanges::single_delete(i * n, Some(i * n)));
481
            }
482
        }
483 1
        changes.sort_by_key(|k| k.k);
484 1
        keeper.apply(&changes).unwrap();
485 1
        assert_eq!(keeper.get(&(2 * n)).ok(), Some(Some(Value::SINGLE(2 * n))));
486 1
        assert_eq!(keeper.get(&(100 * n)).ok(), Some(Some(Value::SINGLE(100 * n))));
487 1
        assert_eq!(keeper.get(&20001).ok(), Some(None));
488 1
        remove.sort_by_key(|k| k.k);
489 1
        keeper.apply(&remove).unwrap();
490 1
        assert_eq!(keeper.get(&(2 * n)).ok(), Some(None));
491 1
        assert_eq!(keeper.get(&(100 * n)).ok(), Some(None));
492
    }
493 1
}
494

495
#[test]
496 1
fn test_big_tree() {
497 1
    let mut keeper = MockIndexKeeper::<u32, u32>::new();
498 1
    for n in 1..20 {
499 1
        let mut changes = Vec::new();
500 1
        let mut remove = Vec::new();
501 1
        for i in 1..301 {
502 1
            changes.push(KeyChanges::single_add(i * n, i * n));
503 1
            if i % 2 == 0 {
504 1
                remove.push(KeyChanges::single_delete(i * n, Some(i * n)));
505
            }
506
        }
507 1
        keeper.apply(&changes).unwrap();
508 1
        assert_eq!(keeper.get(&(2 * n)).ok(), Some(Some(Value::SINGLE(2 * n))));
509 1
        assert_eq!(keeper.get(&(100 * n)).ok(), Some(Some(Value::SINGLE(100 * n))));
510 1
        assert_eq!(keeper.get(&20001).ok(), Some(None));
511

512 1
        keeper.apply(&remove).unwrap();
513 1
        assert_eq!(keeper.get(&(2 * n)).ok(), Some(None));
514 1
        assert_eq!(keeper.get(&(100 * n)).ok(), Some(None));
515 1
    }
516 1
}

Read our documentation on viewing source code .

Loading