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
• func Logtwo(v int) (int, error)
• type Shard
  • func NewHamtFromDag(dserv ipld.DAGService, nd ipld.Node) (*Shard, error)
  • func NewShard(dserv ipld.DAGService, size int) (*Shard, error)
  • func NewShardValue(dserv ipld.DAGService, size int, key string, value *ipld.Link) (*Shard, error)
  • func (ds *Shard) CidBuilder() cid.Builder
  • func (ds *Shard) EnumLinks(ctx context.Context) ([]*ipld.Link, error)
  • func (ds *Shard) EnumLinksAsync(ctx context.Context) <-chan format.LinkResult
  • func (ds *Shard) Find(ctx context.Context, name string) (*ipld.Link, error)
  • func (ds *Shard) ForEachLink(ctx context.Context, f func(*ipld.Link) error) error
  • func (ds *Shard) Link() (*ipld.Link, error)
  • func (ds *Shard) Node() (ipld.Node, error)
  • func (ds *Shard) Remove(ctx context.Context, name string) error
  • func (ds *Shard) Set(ctx context.Context, name string, nd ipld.Node) error
  • func (ds *Shard) SetCidBuilder(builder cid.Builder)
  • func (ds *Shard) SetLink(ctx context.Context, name string, lnk *ipld.Link) error
  • func (ds *Shard) Swap(ctx context.Context, name string, node ipld.Node) (*ipld.Link, error)
  • func (ds *Shard) Take(ctx context.Context, name string) (*ipld.Link, error)

Constants

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

Functions

func Logtwo

func Logtwo(v int) (int, error)

Types

type Shard

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

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

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

func NewShardValue

func NewShardValue(dserv ipld.DAGService, size int, key string, value *ipld.Link) (*Shard, error)

NewShardValue creates a new, empty HAMT shard with the given key, value and size.

func (*Shard) CidBuilder

func (ds *Shard) CidBuilder() cid.Builder

CidBuilder gets the CID Builder, may be nil if unset

func (*Shard) EnumLinks

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

EnumLinks collects all links in the Shard.

func (*Shard) EnumLinksAsync

func (ds *Shard) EnumLinksAsync(ctx context.Context) <-chan format.LinkResult

EnumLinksAsync returns a channel which will receive Links in the directory as they are enumerated, where order is not guaranteed

func (*Shard) Find

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

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

func (*Shard) ForEachLink

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

ForEachLink walks the Shard and calls the given function.

func (*Shard) Link

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

Link returns a merklelink to this shard node

func (*Shard) Node

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

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

func (*Shard) Remove

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

Remove deletes the named entry if it exists. Otherwise, it returns os.ErrNotExist.

func (*Shard) Set

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

Set sets 'name' = nd in the HAMT

func (*Shard) SetCidBuilder

func (ds *Shard) SetCidBuilder(builder cid.Builder)

SetCidBuilder sets the CID Builder

func (*Shard) SetLink

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

Set sets 'name' = nd in the HAMT, using directly the information in the given link. This avoids writing the given node, then reading it to making a link out of it.

func (*Shard) Swap

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

Swap sets a link pointing to the passed node as the value under the name key in this Shard or its children. It also returns the previous link under that name key (if any).

func (*Shard) Take

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

Take is similar to the public Remove but also returns the old removed link (if it exists).