declanvk/blart

# BLART [][crates-url] [][docs-url] BLART 是一个自适应基数树的实现，用作映射和集合数据结构的底层支持。自适应基数树在键分解为字节字符串时提供了出色的空间效率和性能。 ## 示例 以下是使用 `TreeMap` 类型的示例（ blatantly stolen from [the standard library][stdlib-example-1]）： ``` use blart::TreeMap; // type inference lets us omit an explicit type signature (which // would be `TreeMap<&str, &str>` in this example). let mut movie_reviews: TreeMap<_, _> = TreeMap::new(); // review some movies. let _ = movie_reviews.try_insert("Office Space", "Deals with real issues in the workplace.").unwrap(); let _ = movie_reviews.try_insert("Pulp Fiction", "Masterpiece.").unwrap(); let _ = movie_reviews.try_insert("The Godfather", "Very enjoyable.").unwrap(); let _ = movie_reviews.try_insert("The Blues Brothers", "Eye lyked it a lot.").unwrap(); // check for a specific one. if !movie_reviews.contains_key("Les Misérables") { println!("We've got {} reviews, but Les Misérables ain't one.", movie_reviews.len()); } // oops, this review has a lot of spelling mistakes, let's delete it. movie_reviews.remove("The Blues Brothers"); // look up the values associated with some keys. let to_find = ["Up!", "Office Space"]; for movie in &to_find { match movie_reviews.get(movie) { Some(review) => println!("{movie}: {review}"), None => println!("{movie} is unreviewed.") } } // Look up the value for a key (will panic if the key is not found). println!("Movie review: {}", movie_reviews["Office Space"]); // iterate over everything. for (movie, review) in &movie_reviews { println!("{movie}: \"{review}\""); } ``` ## 文档 - [主分支 `main` 的文档][declanvk-blart-docs] ## 测试 ### Miri 目前我们使用一些特定的 crate（`sptr` 以及未来会回到 `core::ptr::*`）来确保与 [Strict Provenance][sp-issue] 兼容。以下的 `MIRIFLAGS` 配置应该能启用检查以确保兼容性。 ``` MIRIFLAGS="-Zmiri-strict-provenance -Zmiri-symbolic-alignment-check" cargo +nightly miri test ``` 我认为这很有用，因为我们正在对标记指针实现进行一些指针操作，修改指针内容以存储数据位。 ## 模糊测试 要运行模糊测试，请使用以下命令： ``` cargo +nightly fuzz run -j 8 -s address tree_map_api -- -max_len=32768 -max_total_time=3600 && cargo +nightly fuzz cmin tree_map_api ``` 这将运行总计 3600 秒（1 小时）的模糊测试，使用 8 个任务（我开发机器核心数的一半），并使用地址 sanitizer。`cmin` 命令用于在生成新条目后压缩语料库。 ### 覆盖率 要从模糊测试语料库生成覆盖率数据： ``` cargo +nightly fuzz coverage tree_map_api ``` 要生成 HTML 格式的行级覆盖率报告： ``` TARGET_TRIPLE="$(rustc --print host-tuple)" "$(rustc --print sysroot)/lib/rustlib/${TARGET_TRIPLE}/bin/llvm-cov" show \ --show-instantiations --show-line-counts-or-regions --Xdemangler=rustfilt --format=html \ --ignore-filename-regex='\.cargo/registry' --ignore-filename-regex='rustlib/src/rust/' \ --instr-profile=fuzz/coverage/tree_map_api/coverage.profdata \ "target/${TARGET_TRIPLE}/coverage/${TARGET_TRIPLE}/release/tree_map_api" > cov.html ``` 在浏览器中打开 `cov.html`。要查看按文件划分的覆盖率摘要： ``` TARGET_TRIPLE="$(rustc --print host-tuple)" "$(rustc --print sysroot)/lib/rustlib/${TARGET_TRIPLE}/bin/llvm-cov" report \ --Xdemangler=rustfilt --show-branch-summary=false --show-functions --use-color \ --ignore-filename-regex='\.cargo/registry' --ignore-filename-regex='rustlib/src/rust/' \ --instr-profile=fuzz/coverage/tree_map_api/coverage.profdata \ "target/${TARGET_TRIPLE}/coverage/${TARGET_TRIPLE}/release/tree_map_api" \ "src/" | less --chop-long-lines --RAW-CONTROL-CHARS ``` ## 基准测试 要运行基准测试，请安装 [`cargo-criterion`][cargo-criterion]，然后运行： ``` cargo +nightly criterion --history-id "$(git rev-parse --short HEAD)-0" ``` 或 ``` cargo bench --bench ``` 如果遇到“Permission denied”错误，请更新 perf_event_paranoid： ``` sudo sh -c 'echo 1 >/proc/sys/kernel/perf_event_paranoid' ``` 更多详细信息请查看以下 [链接][superuser-run-perf]。 ## 性能分析 我使用一个相对真实的基准测试：计算文本文件中的单词数。要开始，请下载一个文本文件，例如： ``` curl -o profiling-data/Ulysses.txt https://www.gutenberg.org/cache/epub/4300/pg4300.txt ``` 然后使用 `profiling` 配置文件构建单词计数示例： ``` RUSTFLAGS="-C force-frame-pointers=yes" cargo build --profile profiling --examples ``` 接着在下载的数据上运行单词计数工作负载并进行性能分析： ``` samply record ./target/profiling/examples/count_words blart profiling-data/book-chapters-combined.txt ``` ## 变异测试 - https://github.com/sourcefrog/cargo-mutants - https://mutants.rs/ 要获取初始的失败变异体列表，请运行： ``` cargo mutants ``` 要在现有的 `mutants.out` 目录上迭代，更新代码并添加更多测试后运行： ``` cargo mutants --iterate ``` 如果你想对特定文件运行变异测试，请使用： ``` cargo mutants -f example.rs ``` 如果你安装了 `cargo-nextest`，可以在 CLI 调用中添加 `--test-tool=nextest`。 要获取当前的变异体列表： ``` cargo mutants --iterate --list | sort ``` `sorted` 命令有助于将文件分组。 ## 许可证 根据以下之一授权： - Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) 或 http://www.apache.org/licenses/LICENSE-2.0) - MIT 许可证 ([LICENSE-MIT](LICENSE-MIT) 或 http://opensource.org/licenses/MIT) 由你自行选择。 ## 贡献 除非你明确声明否则，你对工作有意提交的贡献，在 Apache-2.0 许可证定义下，应被双重授权，不附加任何额外条款或条件。

标签：Crates.io, Miri, Rust, Rust crate, 内存高效, 删除, 可视化界面, 字节字符串, 开源库, 插入, 搜索, 搜索引擎爬虫, 数据库引擎, 数据结构, 文档生成, 映射, 查找, 树, 测试, 生成式AI, 系统编程, 索引, 网络流量审计, 自适应基数树, 迭代器, 通知系统, 键值存储, 集合