Crate wnfs_hamt

source ·
Expand description

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§

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§

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.