wnfs_hamt/
lib.rs

1//! This Rust crate provides an implementation of a [Hash Array Mapped Trie (HAMT)](https://en.wikipedia.org/wiki/Hash_array_mapped_trie) based on IPLD.
2//!
3//! HAMT is a data structure that hashes keys and uses increments of the hash at each level to
4//! determine placement of the entry or child node in the tree structure.
5//!
6//! The number of bits used for index calculation at each level is determined by the bitWidth.
7//! Each node can hold up to 2^bitWidth elements, which are stored in an array. Entries are stored in key-sorted order in buckets.
8//! If a bucket already contains the maximum number of elements, a new child node is created and entries are inserted into the new node.
9//!
10//! The data elements array is only allocated to store actual entries, and a map bitfield is used to determine if an index exists in the data array.
11//!
12//! The implementation is based on [fvm_ipld_hamt](https://github.com/filecoin-project/ref-fvm/tree/master/ipld/hamt) with some modifications for async blockstore access and immutability-by-default.
13
14pub mod constants;
15mod diff;
16mod error;
17mod hamt;
18mod hash;
19mod merge;
20mod node;
21mod pointer;
22pub mod serializable;
23
24pub(crate) use constants::*;
25pub use diff::*;
26pub use hamt::*;
27pub use hash::*;
28pub use merge::*;
29pub use node::*;
30pub use pointer::*;
31
32#[cfg(any(test, feature = "test_utils"))]
33pub mod strategies;