iridium-db 0.4.0

A high-performance vector-graph hybrid storage and indexing engine
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

use std::collections::HashMap;

use crate::features::storage::sstable::Entry;

#[derive(Debug)]
pub enum MergeError {
    EmptyInput,
}

pub type Result<T> = std::result::Result<T, MergeError>;

/// Merge runs newest-first, returning only the latest entry per key.
pub fn merge_latest_by_key(runs_newest_first: &[Vec<Entry>]) -> Result<Vec<Entry>> {
    if runs_newest_first.is_empty() {
        return Err(MergeError::EmptyInput);
    }

    let mut seen: HashMap<u64, Entry> = HashMap::new();
    for run in runs_newest_first {
        for entry in run {
            seen.entry(entry.key).or_insert_with(|| entry.clone());
        }
    }

    let mut merged: Vec<Entry> = seen.into_values().collect();
    merged.sort_by(|a, b| (a.key, a.version).cmp(&(b.key, b.version)));
    Ok(merged)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::features::storage::sstable::EntryKind;

    #[test]
    fn merge_prefers_newest_run() {
        let older = vec![
            Entry {
                key: 1,
                version: 1,
                kind: EntryKind::EdgeDelta,
                value: b"old-1".to_vec(),
            },
            Entry {
                key: 2,
                version: 1,
                kind: EntryKind::EdgeDelta,
                value: b"old-2".to_vec(),
            },
        ];
        let newer = vec![
            Entry {
                key: 2,
                version: 2,
                kind: EntryKind::FullNode,
                value: b"new-2".to_vec(),
            },
            Entry {
                key: 3,
                version: 1,
                kind: EntryKind::VectorDelta,
                value: b"new-3".to_vec(),
            },
        ];

        let merged = merge_latest_by_key(&[newer.clone(), older]).unwrap();
        assert_eq!(merged.len(), 3);
        assert!(merged.iter().any(|e| e.key == 1 && e.value == b"old-1"));
        assert!(merged.iter().any(|e| e.key == 2 && e.value == b"new-2"));
        assert!(merged.iter().any(|e| e.key == 3 && e.value == b"new-3"));
    }
}