Crate wnfs_hamt

This Rust crate provides an implementation of a Hash Array Mapped Trie (HAMT) based on IPLD.

HAMT is a data structure that hashes keys and uses increments of the hash at each level to determine placement of the entry or child node in the tree structure.

The number of bits used for index calculation at each level is determined by the bitWidth. Each node can hold up to 2^bitWidth elements, which are stored in an array. Entries are stored in key-sorted order in buckets. If a bucket already contains the maximum number of elements, a new child node is created and entries are inserted into the new node.

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.

The implementation is based on fvm_ipld_hamt with some modifications for async blockstore access and immutability-by-default.

Modules

constants

serializable

Structs

Hamt

Hash Array Mapped Trie (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie.

HashNibbles

HashNibbles is a wrapper around a byte slice that provides a cursor for traversing the nibbles.

HashPrefix

This represents the location of a intermediate or leaf node in the HAMT.

HashPrefixIterator

An iterator over the nibbles of a HashPrefix.

KeyValueChange

Represents a change to some key-value pair of a HAMT node.

Node

Represents a node in the HAMT tree structure.

Pair

A key-value pair type.

Enums

ChangeType

This type represents the different kinds of changes to a node.

Constants

MAX_HASH_NIBBLE_LENGTH

The number of nibbles in a HashOutput.

Traits

Hasher

A common trait for the ability to generate a hash of some data.

Functions

diff

Compare two nodes and get the key-value changes made to the main node.

diff_helper

merge

Merges a node with another with the help of a resolver function.

Type Aliases

BitMaskType

The bitmask used by the HAMT which 16-bit, [u8; 2] type.