hamt

package
v0.4.16-rc3 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 9, 2018 License: MIT Imports: 12 Imported by: 0

Documentation

Overview

Package hamt implements a Hash Array Mapped Trie over ipfs merkledag nodes. It is implemented mostly as described in the wikipedia article on HAMTs, however the table size is variable (usually 256 in our usages) as opposed to 32 as suggested in the article. The hash function used is currently Murmur3, but this value is configurable (the datastructure reports which hash function its using).

The one algorithmic change we implement that is not mentioned in the wikipedia article is the collapsing of empty shards. Given the following tree: ( '[' = shards, '{' = values ) [ 'A' ] -> [ 'B' ] -> { "ABC" }

|       L-> { "ABD" }
L-> { "ASDF" }

If we simply removed "ABC", we would end up with a tree where shard 'B' only has a single child. This causes two issues, the first, is that now we have an extra lookup required to get to "ABD". The second issue is that now we have a tree that contains only "ABD", but is not the same tree that we would get by simply inserting "ABD" into a new tree. To address this, we always check for empty shard nodes upon deletion and prune them to maintain a consistent tree, independent of insertion order.

Index

Constants

View Source
const (
	// HashMurmur3 is the multiformats identifier for Murmur3
	HashMurmur3 uint64 = 0x22
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Shard added in v0.4.14

type Shard struct {
	// contains filtered or unexported fields
}

A Shard represents the HAMT. It should be initialized with NewShard().

func NewHamtFromDag

func NewHamtFromDag(dserv ipld.DAGService, nd ipld.Node) (*Shard, error)

NewHamtFromDag creates new a HAMT shard from the given DAG.

func NewShard added in v0.4.14

func NewShard(dserv ipld.DAGService, size int) (*Shard, error)

NewShard creates a new, empty HAMT shard with the given size.

func (ds *Shard) EnumLinks(ctx context.Context) ([]*ipld.Link, error)

EnumLinks collects all links in the Shard.

func (*Shard) Find added in v0.4.14

func (ds *Shard) Find(ctx context.Context, name string) (*ipld.Link, error)

Find searches for a child node by 'name' within this hamt

func (ds *Shard) ForEachLink(ctx context.Context, f func(*ipld.Link) error) error

ForEachLink walks the Shard and calls the given function.

func (*Shard) Label added in v0.4.14

func (ds *Shard) Label() string

Label for Shards is the empty string, this is used to differentiate them from value entries

func (ds *Shard) Link() (*ipld.Link, error)

Link returns a merklelink to this shard node

func (*Shard) Node added in v0.4.14

func (ds *Shard) Node() (ipld.Node, error)

Node serializes the HAMT structure into a merkledag node with unixfs formatting

func (*Shard) Prefix added in v0.4.14

func (ds *Shard) Prefix() *cid.Prefix

Prefix gets the CID Prefix, may be nil if unset

func (*Shard) Remove added in v0.4.14

func (ds *Shard) Remove(ctx context.Context, name string) error

Remove deletes the named entry if it exists, this operation is idempotent.

func (*Shard) Set added in v0.4.14

func (ds *Shard) Set(ctx context.Context, name string, nd ipld.Node) error

Set sets 'name' = nd in the HAMT

func (*Shard) SetPrefix added in v0.4.14

func (ds *Shard) SetPrefix(prefix *cid.Prefix)

SetPrefix sets the CID Prefix

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL