hamt

Documentation

Overview

Package hamt implements a hash array mapped trie.

http://lampwww.epfl.ch/papers/idealhashtrees.pdf

It is persistent in the functional sense.

Because Go doesn't have unions, and interfaces are twice as big as pointers, we use separate bitmaps and arrays (slices) for values and pointers. This has the side benefit of allowing both a value and a pointer in a node. e.g. in the case of a collision, only one value must be pushed down to a new child node instead of both the new and the old.

Unlike a conventional hash map, it just stores items. This works well when items already contain the key, or for a set. To make a map, the item type should be a struct with the key and value.

It has two modes, mutable and immutable. This allows "batching" updates to share path copying.

• Mutable returns an updateable copy.
• Freeze returns an immutable copy.

Put and Delete can only be used when mutable. When mutable it is NOT thread safe, it should be thread contained.

If items are large, the element (E) type should probably be a pointer. However, to maintain immutability, items should not be modified via pointer. The code is not written to use *E because that's not what you want for e.g. string or int

Index

• Constants
• type Chain
  • func ReadChain[K comparable, E Item[K]](st *stor.Stor, off uint64, rdfn func(st *stor.Stor, r *stor.Reader) E) Chain[K, E]
  • func (c *Chain[K, E]) Cksum() uint32
  • func (c *Chain[K, E]) WriteChain(store *stor.Stor) (uint64, Chain[K, E])
• type Hamt
  • func (ht Hamt[K, E]) All() iter.Seq[E]
  • func (ht Hamt[K, E]) Cksum() uint32
  • func (ht Hamt[K, E]) Delete(key K) bool
  • func (ht Hamt[K, E]) Freeze() Hamt[K, E]
  • func (ht Hamt[K, E]) Get(key K) (E, bool)
  • func (ht Hamt[K, E]) IsNil() bool
  • func (ht Hamt[K, E]) MustGet(key K) E
  • func (ht Hamt[K, E]) Mutable() Hamt[K, E]
  • func (ht Hamt[K, E]) Put(item E)
  • func (ht Hamt[K, E]) SameAs(ht2 Hamt[K, E]) bool
  • func (ht Hamt[K, E]) Write(st *stor.Stor, prevOff uint64, lastMod int) uint64
• type Item

Constants

const All = math.MinInt

Types

type Chain

type Chain[K comparable, E Item[K]] struct {
	Hamt[K, E]
	// offs are the offsets in the database file
	// of the item chunks in the current chain, oldest first.
	// These are used for "merging" chunks to manage chain size.
	Offs []uint64
	// ages are the oldest/min ages in the chunks.
	// They are parallel to offs (same len).
	Ages []int
	// clock counts persists.
	// lastMod is set to the current clock to mark an item as modified.
	Clock int
}

func ReadChain

func ReadChain[K comparable, E Item[K]](st *stor.Stor, off uint64,
	rdfn func(st *stor.Stor, r *stor.Reader) E) Chain[K, E]

func (*Chain[K, E]) Cksum

func (c *Chain[K, E]) Cksum() uint32

func (*Chain[K, E]) WriteChain

func (c *Chain[K, E]) WriteChain(store *stor.Stor) (uint64, Chain[K, E])

WriteChain writes a new chunk of items containing at least the newly modified items plus the contents of zero or more older chunks. It returns a new ItemChain. It does not modify the original. Conceptually we merge chunks, but actually we write a new chunk containing old and new items and unlink/abandon the old chunk(s).

type Hamt

type Hamt[K comparable, E Item[K]] struct {
	// contains filtered or unexported fields
}

func (Hamt[K, E]) All

func (ht Hamt[K, E]) All() iter.Seq[E]

func (Hamt[K, E]) Cksum

func (ht Hamt[K, E]) Cksum() uint32

Cksum on Hamt is for the logical state, whereas Cksum on Chain is physical.

func (Hamt[K, E]) Delete

func (ht Hamt[K, E]) Delete(key K) bool

Delete removes an item. It returns whether the item was found.

func (Hamt[K, E]) Freeze

func (ht Hamt[K, E]) Freeze() Hamt[K, E]

func (Hamt[K, E]) Get

func (ht Hamt[K, E]) Get(key K) (E, bool)

func (Hamt[K, E]) IsNil

func (ht Hamt[K, E]) IsNil() bool

func (Hamt[K, E]) MustGet

func (ht Hamt[K, E]) MustGet(key K) E

func (Hamt[K, E]) Mutable

func (ht Hamt[K, E]) Mutable() Hamt[K, E]

func (Hamt[K, E]) Put

func (ht Hamt[K, E]) Put(item E)

func (Hamt[K, E]) SameAs

func (ht Hamt[K, E]) SameAs(ht2 Hamt[K, E]) bool

func (Hamt[K, E]) Write

func (ht Hamt[K, E]) Write(st *stor.Stor, prevOff uint64, lastMod int) uint64

type Item

type Item[K comparable] interface {
	Key() K
	Hash(K) uint64
	Cksum() uint32
	StorSize() int
	IsTomb() bool
	LastMod() int
	SetLastMod(mod int)
	Write(w *stor.Writer)
}