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
73
74

//! # Writer for CRC trees

use std::{
    collections::BTreeMap,
    io::{self, Write},
    ops::Range,
};

use crate::crc::CRC;

/// Write a CRC tree to file
///
/// This function recursively subdivides the given `range` to implement a depth first tree-order traversal
///
/// For every leaf it calls [`Iterator::next`] and writes out the CRC key, left and right subindices
/// and then the payload using `write_value`.
fn write_crc_tree_recursive<V, W: Write, I: Iterator<Item = (CRC, V)>>(
    writer: &mut W,
    iterator: &mut I,
    range: Range<u32>,
    write_value: fn(&mut W, V) -> io::Result<()>,
) -> io::Result<()> {
    let len = range.end - range.start;
    match len {
        0 => { /* Ignore */ }
        _ => {
            let mid = range.start + len / 2;

            let left_range = range.start..mid;
            let left_len = left_range.end - left_range.start;
            let left_ptr = if left_len == 0 {
                u32::MAX
            } else {
                left_range.start + left_len / 2
            };

            let right_range = (mid + 1)..range.end;
            let right_len = right_range.end - right_range.start;
            let right_ptr = if right_len == 0 {
                u32::MAX
            } else {
                right_range.start + right_len / 2
            };

            write_crc_tree_recursive(writer, iterator, left_range, write_value)?;

            let (crc, data) = iterator.next().unwrap();
            writer.write_all(&crc.to_raw().to_le_bytes())?;
            writer.write_all(&left_ptr.to_le_bytes())?;
            writer.write_all(&right_ptr.to_le_bytes())?;
            write_value(writer, data)?;

            write_crc_tree_recursive(writer, iterator, right_range, write_value)?;
        }
    }

    Ok(())
}

/// Write a CRC tree to a writer
pub fn write_crc_tree<V, W: Write>(
    writer: &mut W,
    tree: &BTreeMap<CRC, V>,
    write_value: fn(&mut W, &V) -> io::Result<()>,
) -> io::Result<()> {
    let len = tree.len() as u32;
    writer.write_all(&len.to_le_bytes())?;
    write_crc_tree_recursive(
        writer,
        &mut tree.iter().map(|(a, b)| (*a, b)),
        0..len,
        write_value,
    )
}