blart 0.5.0

An implementation of an adaptive radix tree packaged as a BTreeMap replacement
Documentation 
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

use std::{
    collections::BTreeMap, error::Error, ffi::CString, fs::OpenOptions, io::Read, path::PathBuf,
};

use argh::FromArgs;
use blart::TreeMap;

/// Count words in file
#[derive(FromArgs)]
struct CountWords {
    /// which map implementation to use for counting
    #[argh(positional, short = 'j')]
    map_impl: String,

    /// input to read keys from an external file
    #[argh(positional)]
    input_file: PathBuf,
}

fn main() -> Result<(), Box<dyn Error>> {
    let args: CountWords = argh::from_env();

    let mut input_file = OpenOptions::new()
        .read(true)
        .open(args.input_file)
        .expect("unable to open text file");

    let metadata = input_file
        .metadata()
        .expect("file metadata should be available");
    let file_len = metadata.len() as usize;
    let mut contents = Vec::with_capacity(file_len);

    let bytes_read = input_file
        .read_to_end(&mut contents)
        .expect("should be able to read entire file");

    assert_eq!(
        bytes_read, file_len,
        "should have read entire file into memory"
    );

    let stats = match args.map_impl.as_str() {
        "std" => count_words_std(&contents),
        "blart" => count_words_blart(&contents),
        other => panic!("unknown map impl '{other}'"),
    };

    println!("STATS: {stats:?}");

    Ok(())
}

#[derive(Debug)]
#[expect(dead_code)] // this struct is used for its debug repr
struct WordStats {
    num_unique: u64,
    first_word: CString,
    first_word_count: u64,
    last_word: CString,
    last_word_count: u64,
}

fn count_words_blart(contents: &[u8]) -> WordStats {
    let mut map = TreeMap::<CString, u64>::new();

    for word in contents.split_inclusive(|b| *b == SPLIT_BYTE) {
        let word = CString::new(word).unwrap();

        map.entry(word)
            .and_modify(|count| {
                *count += 1;
            })
            .or_insert(1);
    }

    let (first_word, first_word_count) = map
        .first_key_value()
        .expect("there should be at least 1 word in the map");

    let (last_word, last_word_count) = map
        .last_key_value()
        .expect("there should be at least 1 word in the map");

    WordStats {
        num_unique: map.len() as u64,
        last_word: last_word.clone(),
        last_word_count: *last_word_count,
        first_word: first_word.clone(),
        first_word_count: *first_word_count,
    }
}

const SPLIT_BYTE: u8 = b' ';

fn count_words_std(contents: &[u8]) -> WordStats {
    let mut map = BTreeMap::<CString, u64>::new();

    for word in contents.split_inclusive(|b| *b == SPLIT_BYTE) {
        let word = CString::new(word).unwrap();

        map.entry(word)
            .and_modify(|count| {
                *count += 1;
            })
            .or_insert(1);
    }

    let (first_word, first_word_count) = map
        .first_key_value()
        .expect("there should be at least 1 word in the map");

    let (last_word, last_word_count) = map
        .last_key_value()
        .expect("there should be at least 1 word in the map");

    WordStats {
        num_unique: map.len() as u64,
        last_word: last_word.clone(),
        last_word_count: *last_word_count,
        first_word: first_word.clone(),
        first_word_count: *first_word_count,
    }
}