hamt

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
• type HamtShard
  • func NewHamtFromDag(dserv dag.DAGService, nd node.Node) (*HamtShard, error)
  • func NewHamtShard(dserv dag.DAGService, size int) (*HamtShard, error)
  • func (ds *HamtShard) EnumLinks(ctx context.Context) ([]*node.Link, error)
  • func (ds *HamtShard) Find(ctx context.Context, name string) (node.Node, error)
  • func (ds *HamtShard) ForEachLink(ctx context.Context, f func(*node.Link) error) error
  • func (ds *HamtShard) Label() string
  • func (ds *HamtShard) Node() (node.Node, error)
  • func (ds *HamtShard) Remove(ctx context.Context, name string) error
  • func (ds *HamtShard) Set(ctx context.Context, name string, nd node.Node) error

Constants

const (
	HashMurmur3 uint64 = 0x22
)

Types

type HamtShard

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

func NewHamtFromDag

func NewHamtFromDag(dserv dag.DAGService, nd node.Node) (*HamtShard, error)

func NewHamtShard

func NewHamtShard(dserv dag.DAGService, size int) (*HamtShard, error)

func (*HamtShard) EnumLinks

func (ds *HamtShard) EnumLinks(ctx context.Context) ([]*node.Link, error)

func (*HamtShard) Find

func (ds *HamtShard) Find(ctx context.Context, name string) (node.Node, error)

func (*HamtShard) ForEachLink

func (ds *HamtShard) ForEachLink(ctx context.Context, f func(*node.Link) error) error

func (*HamtShard) Label

func (ds *HamtShard) Label() string

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

func (*HamtShard) Node

func (ds *HamtShard) Node() (node.Node, error)

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

func (*HamtShard) Remove

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

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

func (*HamtShard) Set

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

Set sets 'name' = nd in the HAMT